目录

1. 简介

2. 特征提取：Fast特征

怎样提取特征？

怎样保证尺度不变性？

怎样保证旋转不变性？

解释1

= 解释2

3 特征描述：BRIEF算法描述

解释1

解释2

解释3 BRIEF 算法

参考：

---

1. 简介

ORB（Oriented FAST and Rotated BRIEF）是一种快速特征点提取和描述的算法。这个算法是由Ethan Rublee, Vincent Rabaud, Kurt Konolige以及Gary R.Bradski在2011年一篇名为“ORB：An Efficient Alternative to SIFTor SURF”的文章中提出。ORB算法分为两部分，分别是特征点提取和特征点描述。

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

据说，ORB算法的速度是sift的100倍，是surf的10倍。

2. 特征提取：Fast特征

ORB算法的特征提取是由FAST算法改进的，这里成为oFAST（FASTKeypoint Orientation）。也就是说，在使用FAST提取出特征点之后，给其定义一个特征点方向，以此来实现特征点的旋转不变形。FAST算法是公认的最快的特征点提取方法。FAST算法提取的特征点非常接近角点类型。oFAST算法如下：

 

图1  FAST特征点判断示意图

怎样提取特征？

步骤一：粗提取。该步能够提取大量的特征点，但是有很大一部分的特征点的质量不高。下面介绍提取方法。从图像中选取一点P，如上图1。我们判断该点是不是特征点的方法是，以P为圆心画一个半径为3pixel的圆。圆周上如果有连续n个像素点的灰度值比P点的灰度值大或者小，则认为P为特征点。一般n设置为12。为了加快特征点的提取，快速排出非特征点，首先检测1、9、5、13位置上的灰度值，如果P是特征点，那么这四个位置上有3个或3个以上的的像素值都大于或者小于P点的灰度值。如果不满足，则直接排出此点。

步骤二：机器学习的方法筛选最优特征点。简单来说就是使用ID3算法训练一个决策树，将特征点圆周上的16个像素输入决策树中，以此来筛选出最优的FAST特征点。

步骤三：非极大值抑制去除局部较密集特征点。使用非极大值抑制算法去除临近位置多个特征点的问题。为每一个特征点计算出其响应大小。计算方式是特征点P和其周围16个特征点偏差的绝对值和。在比较临近的特征点中，保留响应值较大的特征点，删除其余的特征点。

怎样保证尺度不变性？

步骤四：特征点的尺度不变形。建立金字塔，来实现特征点的多尺度不变性。设置一个比例因子scaleFactor（opencv默认为1.2）和金字塔的层数nlevels（pencv默认为8）。将原图像按比例因子缩小成nlevels幅图像。缩放后的图像为：I’= I/scaleFactork(k=1,2,…, nlevels)。nlevels幅不同比例的图像提取特征点总和作为这幅图像的oFAST特征点。

怎样保证旋转不变性？

解释1

步骤五：特征点的旋转不变性。ORB算法提出使用矩（moment）法来确定FAST特征点的方向。也就是说通过矩来计算特征点以r为半径范围内的质心，特征点坐标到质心形成一个向量作为该特征点的方向。矩定义如下：

其中，I(x,y)为图像灰度表达式。该矩的质心为：

 

假设角点坐标为O，则向量的角度即为该特征点的方向。计算公式如下：

= 解释2

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

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

3 特征描述：BRIEF算法描述

解释1

BRIEF算法计算出来的是一个二进制串的特征描述符。它是在一个特征点的邻域内，选择n对像素点pi、qi（i=1,2,…,n）。然后比较每个点对的灰度值的大小。如果I(pi)> I(qi)，则生成二进制串中的1，否则为0。所有的点对都进行比较，则生成长度为n的二进制串。一般n取128、256或512，opencv默认为256。另外，值得注意的是为了增加特征描述符的抗噪性，算法首先需要对图像进行高斯平滑处理。在ORB算法中，在这个地方进行了改进，在使用高斯函数进行平滑后，又用了其他操作，使其更加的具有抗噪性。具体方法下面将会描述。

关于在特征点SxS的区域内选取点对的方法，BRIEF论文(附件2)中测试了5种方法：

1）在图像块内平均采样；

2）p和q都符合(0,S2/25)的高斯分布；

3）p符合(0,S2/25)的高斯分布，而q符合(0,S2/100)的高斯分布；

4）在空间量化极坐标下的离散位置随机采样；

5）把p固定为(0,0)，q在周围平均采样。

五种采样方法的示意图如下：

论文指出，第二种方法可以取得较好的匹配结果。在旋转不是非常厉害的图像里，用BRIEF生成的描述子的匹配质量非常高，作者测试的大多数情况中都超越了SURF。但在旋转大于30°后，BRIEF的匹配率快速降到0左右。BRIEF的耗时非常短，在相同情形下计算512个特征点的描述子时，SURF耗时335ms,BRIEF仅8.18ms；匹配SURF描述子需28.3ms，BRIEF仅需2.19ms。在要求不太高的情形下，BRIEF描述子更容易做到实时。

解释2

计算特征描述子

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

 

步骤：
1.以关键点P为圆心，以d为半径做圆O。
2.在圆O内某一模式选取N个点对。这里为方便说明，N=4，实际应用中N可以取512.
假设当前选取的4个点对如上图所示分别标记为：

3.定义操作T

 

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

则最终的描述子为：1011

解释3 BRIEF 算法

我们已经知道 ORB 如何使用 FAST 确定图像中的关键点，下面我们将了解 ORB 如何使用 BRIEF 算法，并将这些关键点转换为特征向量。

ORB 算法的第二步是将第一个算法发现的关键点变成特征向量，这些特征向量可以共同表示一个对象。

要创建特征向量，ORB 会用到 BRIEF 算法。BRIEF 是 Binary Robust Independent Elementary Features 的简称，它的作用是根据一组关键点创建二元特征向量。正如在简介视频中看到的，二元特征向量又称为二元描述符，是仅包含 1 和 0 的特征向量。在 BRIEF 中 每个关键点由一个二元特征向量描述，该向量一般为 128-512 位的字符串，其中仅包含 1 和 0。

注意，这里的“位”是二进制位的简称，1 位只能存储一个二进制值，要么 1 要么是 0。位字符串是一组位，这些是位字符串示例。

第一个是 1 位字符串 因此只存储 1 位。第二个是 2 位字符串，因此可以存储 2 个二进制位。在此示例中它存储的是 0 和 1。同样，第三个是 3 位字符串，因此可以存储 3 个位，以此类推。计算机运行的是二进制或机器代码，因此使用二元特征向量的一大优势是可以非常高效地存储在内存中，并且可以快速计算。速度对实时应用来说极为关键，这些特性不仅使 BRIEF 速度非常快，而且使 BRIEF 能够在计算资源非常有限的设备（例如智能手机）上运行。

BRIEF 如何为每个点创建这些二元描述符？BRIEF 算法首先利用高斯核对给定图像进行平滑处理，以防描述符对高频噪点过于敏感。然后，对于给定关键点，例如猫爪上的这个点。

BRIEF 从该关键点周围界定好的邻域内随机选择一对像素，关键点周围的邻域称为 Patch，它是一个具有特定像素宽度和高度的正方形。
这里显示的随机对中的第一个像素，是一个蓝色正方形，它是从以关键点为中心的高斯分布中抽取的一个像素，标准偏差或分散趋势为 σ。

这里显示为黄色正方形的像素，是随机对中的第二个像素。它是从以该第一个像素为中心的高斯分布中抽取的像素，标准偏差为 σ/2，经验表明这种高斯选择提高了特征匹配率。

BRIEF 然后开始为关键点构建二元描述符，方法是如下所示地比较这两个像素的亮度。如果第一个像素比第二个亮，则为描述符中的相应位分配值 1，否则分配值 0。

在这个示例中第二个像素比第一个亮，因此我们为特征向量的第一个位分配值 0。特征向量的第一个位对应的是这个关键点的第一个随机点对，然后 BRIEF 会针对同一关键点选择新的随机像素对比较它们的亮度并为特征向量中的下个位分配 1 或 0。

在上面新选取的随机像素中，我们看到现在第一个像素比第二个亮，因此为特征向量中的第二个位分配值 1。

对于 256 位向量，BRIEF 会针对同一关键点重复这一流程 256 次，然后转到下个关键点。接着将 256 个像素亮度比较结果放入该关键点的二元特征向量中。BRIEF 像这样为图像中的每个关键点创建一个向量。

参考：

• ORB特征提取详解
• ORB特征提取与匹配

• ORB 特征提取算法（理论篇）