ORB-快速特征点提取和描述的算法

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倍。 ### ORB—快速特征点提取和描述的算法 #### 算法介绍 ORB（Oriented FAST and Rotated BRIEF）算法是由Ethan Rublee、Vincent Rabaud、Kurt Konolige以及Gary R.Bradski在2011年的文章《ORB：An Efficient Alternative to SIFT or SURF》中提出的。该算法旨在提供一种既高效又能保持较高准确性的特征点提取和描述方案。ORB结合了FAST特征点检测方法与BRIEF特征描述子的优点，并在它们的基础上进行了改进与优化。 #### 1.1 OFAST特征提取 ##### OFAST简介 ORB算法中的特征提取部分被称为OFAST（Oriented FAST），它基于FAST（Features from Accelerated Segment Test）算法，并增加了特征点方向的定义，以实现特征点的旋转不变性。 ##### 快速特征点提取步骤 **步骤一：粗提取** 1. **特征点初步判断**：选择图像中的任意一点P，以P为中心画一个半径为3pixel的圆。如果在圆周上存在连续n个像素点的灰度值比P点的灰度值大或小，则认为P可能是一个特征点。通常情况下，n被设置为12。 2. **快速排除**：首先检查圆周上的1、9、5、13四个位置上的像素值，如果P是特征点，则这四个位置中有至少三个像素值与P点的灰度值相比较为一致。如果不符合条件，则可快速排除该点。 **步骤二：筛选最优特征点** 1. **决策树筛选**：利用ID3算法训练决策树，输入特征点周围的16个像素值，以此筛选出最优质的特征点。 **步骤三：去除局部密集特征点** 1. **非极大值抑制**：为每个特征点计算其响应大小，即特征点与其周围16个像素点之间的偏差绝对值之和。在相邻的特征点中，保留响应值较大的点，删除其余特征点，以避免局部密集问题。 **步骤四：特征点的尺度不变性** 1. **金字塔构建**：通过设置比例因子（默认为1.2）和金字塔层级（默认为8），构建多尺度金字塔。对于每层金字塔，按比例因子缩小原始图像，提取特征点。最终，所有层的特征点组合构成该图像的OFAST特征点集合。 **步骤五：特征点的旋转不变性** 1. **矩（moment）法**：使用矩法确定特征点的方向。计算特征点坐标到质心的向量作为该特征点的方向。矩的计算公式如下： \[ m_{pq} = \sum_x \sum_y x^p y^q I(x,y) \] 其中\(I(x,y)\)为图像灰度表达式。质心的坐标计算公式为： \[ (c_x, c_y) = \left(\frac{m_{10}}{m_{00}}, \frac{m_{01}}{m_{00}}\right) \] 假设角点坐标为O，那么向量\(\vec{OC}\)的角度即为该特征点的方向，计算公式如下： \[ \theta = atan2(c_y - O_y, c_x - O_x) \] #### 1.2 rBRIEF特征描述 ##### rBRIEF特征描述简介 rBRIEF是在BRIEF特征描述的基础上加入了旋转因子进行改进的。 ##### BRIEF算法描述 BRIEF算法生成的是一个二进制串的特征描述符。在特征点邻域内选择n对像素点\(p_i\)、\(q_i\)（\(i=1,2,\ldots,n\)）。比较每对点的灰度值大小，如果\(I(p_i) > I(q_i)\)，则生成二进制串中的1；反之为0。所有点对比较的结果组成长度为n的二进制串，n一般取128、256或512，OpenCV默认为256。为了增强抗噪性，图像首先需要经过高斯平滑处理。 **像素对选取方法**： - 平均采样于图像块内； - \(p\)和\(q\)都符合\((0,S^2/25)\)的高斯分布； - \(p\)符合\((0,S^2/25)\)的高斯分布，而\(q\)符合\((0,S^2/100)\)的高斯分布； - 在空间量化极坐标下的离散位置随机采样； - 把\(p\)固定为\((0,0)\)，\(q\)在周围平均采样。 研究发现，第二种方法能获得较好的匹配结果。 #### 总结 ORB算法通过结合OFAST和rBRIEF两个主要组成部分，实现了特征点的快速提取与描述，同时保持了一定的旋转和尺度不变性。相比于传统的SIFT和SURF算法，ORB算法具有更高的效率，据称其速度是SIFT的100倍，是SURF的10倍，因此在实际应用中有着广泛的应用前景。