ORB（Oriented FAST and Rotated BRIEF）

Magicmanoooo 3月 09, 2019

简介

假如有两张人物图片，要确认这两张图片中的人物是否是同一个人。如果由人来判断，则很简单。但是，让计算机来完成这个功能就困难重重。一种可行的方法是：

分别找出两张图片中的特征点
描述这些特征点的属性
比较这两张图片的特征点的属性。如果有足够多的特征点具有相同的属性，那么就可以认为两张图片中的人物就是同一个人

ORB（Oriented FAST and Rotated BRIEF）就是一种特征提取并描述的方法。ORB分两部分，即特征点提取和特征点描述。

特征提取是由FAST（Features from Accelerated Segment Test）算法发展来的，特征点描述是根据BRIEF（Binary Robust Independent Elementary Features）特征描述算法改进的。ORB特征是将FAST特征点的检测方法与BRIEF特征描述子结合起来，并在它们原来的基础上做了改进与优化。

特征点的检测

图像的特征点可以简单的理解为图像中比较显著显著的点，如轮廓点，较暗区域中的亮点，较亮区域中的暗点等。

ORB采用FAST（features from accelerated segment test）算法来检测特征点。这个定义基于特征点周围的图像灰度值，检测候选特征点周围一圈的像素值。如果候选点周围领域内有足够多的像素点与该候选点的灰度值差别够大，则认为该候选点为一个特征点。

1. 粗提取（FAST具体计算过程）

从图片中选取一个像素点P，接着判断它是否是一个特征点。首先，把它的密度（即灰度值）设为Ip。
预先设定一个合适的阙值t ：当两个点的灰度值之差的绝对值大于t时，便认为这两个点不相同。
考虑该像素点周围的16个像素（以P为圆心，画一个半径为3 pixel的圆）。
如果这16个点中有连续的n个点都和点P不同，则点P就是一个特征点（这里n设定为12）。

为了加快特征点的提取，快速排除非特征点，首先检测1、9、5、13位置上的灰度值。如果P是特征点，那么这四个位置上将会有3个或3个以上的的像素值都大于或者小于P点的灰度值。如果不满足，则直接排除此点。

2. 使用`ID3`决策树，将特征点圆周上的16个像素输入决策树中，以此来筛选出最优的FAST特征点。

3. 使用非极大值抑制算法去除临近位置的多个特征点

具体做法：为每一个特征点计算出其响应大小（即，特征点P和其周围16个特征点偏差的绝对值和）。在比较临近的特征点中，保留响应值较大的特征点，删除其余的特征点。

4. 特征点的尺度不变性

需要构造尺度金字塔：设置一个比例因子factor（opencv默认为1.2）和金字塔的层数octaves（opencv默认为8，与SIFT不同，每层仅有一副图像）。将原图像按比例因子缩小成octaves幅图像。第s层的尺度为，原图在第0层；第s层图像大小为：

Rotated BRIEF（rBRIEF）特征点的描述

得到特征点后，需要以某种方式F来描述这些特征点的属性。这些属性的输出，称为该特征点的描述子（Feature Descritor）。ORB采用BRIEF算法来计算一个特征点的描述子。BRIEF算法的核心思想是：在关键点P的周围，以一定模式选取N个点对，把这N个点对的比较结果组合起来作为描述子。

算法的具体步骤为：

以关键点P为圆心，以d为半径做圆O。
在圆O内选取N个点对（此处为了方便说明，N=4，实际应用中N可以取512）。假设当前选取的4个点分别标记为：

定义操作T：

分别对已选取的点对进行T操作，将得到的结果进行组合：

所以，最终的描述子为：1011。

理想的特征点描述子应该具备的属性

在现实生活中，从不同的距离，不同的方向、角度，不同的光照条件下观察一个物体时，物体的大小，形状，明暗都会有所不同。但人类的大脑依然可以判断它是同一件物体。理想的特征描述子应该具备这些性质。即，在大小、方向、明暗不同的图像中，同一特征点应具有足够相似的描述子，称之为描述子的可复现性。

当以某种理想的方式分别计算下图中红色点的描述子时，应该得出同样的结果。即描述子应该对光照（亮度）不敏感，具备尺度一致性（大小），旋转一致性（角度）等。

上面用BRIEF算法得到的描述子并不具备以上这些性质。因此，需要改进算法。ORB并没有解决尺度一致性问题，在OpenCV的ORB实现中，采用了图像金字塔来改善这方面的性能。ORB主要解决BRIEF描述子不具备旋转不变性的问题。

根据BRIEF描述子的计算过程：在当前关键点P周围，以一定模式选取N个点对，组合这N个点对的T操作的结果，就为最终的描述子。当选取点对的时候，是以当前关键点为原点，以水平方向为X轴，以垂直方向为Y轴建立坐标系。当图片发生旋转时，坐标系不变，同样的取点模式取出来的点却不一样，计算得到的描述子也不一样，这是不符合要求的。因此，需要重新建立坐标系，使新的坐标系可以跟随图片的旋转而旋转。这样，以相同的取点模式取出来的点才具有一致性。

ORB在计算BRIEF描述子时，建立的坐标系是以关键点为圆心，以关键点和取点区域的形心的连线为X轴建立二维坐标系。

在上图中，P为关键点。圆内为取点区域，每个小格子代表一个像素。现在，把这块圆心区域看做一块木板，木板上每个点的质量等于其对应的像素值。根据积分学的知识，可以求出这个密度不均匀木板的质心Q。计算公式如下（其中，R为圆的半径）：

圆心是固定的，而且随着物体的旋转而旋转。当以PQ作为坐标轴时，在不同的旋转角度下，以同一取点模式取出来的点是一致的，这就解决了旋转一致性的问题。

特征点的匹配

ORB算法最大的特点就是计算速度快。这首先得益于使用FAST检测特征点。其次是使用BRIEF算法计算描述子，该描述子特有的二进制串的表现形式，不仅节约了存储空间，而且大大缩短了匹配的时间。

例如，特征点A、B的描述子如下：

现设定一个阈值，比如80%。在上述例子中，A，B只有最后一位不同，相似度为87.5%，大于80%，则A和B是匹配的。

将A和B进行异或操作，就可以轻松计算出A和B的相似度。而异或操作可以借组硬件完成，具有很高的效率，加快了匹配的速度。

简介