结合快速鲁棒性特征改进ORB的特征点匹配算法

摘要：针对定向二进制简单描述符（ORB）算法不具备尺度不变性的问题，提出一种结合快速鲁棒性特征（SURF）算法和ORB的改进算法。首先，利用Hessian矩阵检测特征点的方法，使得提取出的特征点具有尺度不变性；然后，用orb生成特征描述子；接着采用K近邻算法进行粗匹配；最后，通过比率测试、对称测试、最小平方中值（LMedS）定理全文中，“最小中值定理”是否应该为“最小平方中值定理”或“最小中值平方定理”更为规范些？请明确。回复：“最小中值定理”统一改为“最小平方中值定理”，英文翻译不用动进行提纯。尺度变化时，该算法比ORB的匹配精度提高了74.3个百分点，比SURF的匹配精度提高了4.8个百分点；旋转变化时，该算法比ORB的匹配精度提高了6.6另外，根据表2的数据，此处是6.6吧？请明确。个百分点；匹配时间高于SURF低于ORB。实验结果表明，改进算法不仅保持了ORB的旋转不变性，而且具备了尺度不变性，在不失速度的前提下，匹配精度得到较大提高。

关键词：

特征点匹配；尺度不变性；旋转不变性；比率测试；对称测试；最小平方中值定理

中图分类号： TP391.9 文献标志码：A

0引言

图像特征点匹配是计算机视觉的关键技术之一，广泛应用于三维重建、图像拼接、目标识别等领域[1-4]。Lowe[5]于2004年正式提出了尺度不变特征变换（Scale Invariant Feature Transform， SIFT）算法，其独特性好，信息量丰富；但该算法的计算量大、匹配速度较慢。此后，Bay等[6]于2006年提出了快速鲁棒性特征（Speeded Up Robust Feature， SURF）算法，不仅简化了SIFT算法，而且在重复性、独特性和鲁棒性三个方面均超过或接近SIFT算法，计算速度也显著提高。随着计算机视觉技术的发展对特征点匹配精度和速度的要求越来越高，Roblee等[7]在2011年的 计算机视觉国际会议（Internation Conference on Computer Vision， ICCV）提出了定向二进制简单描述符（Oriented fast and Rotated Brief，ORB）算法，其计算速度比SURF快一个数量级，比SIFT快两个数量级，匹配性能也不逊于SURF和SIFT。

ORB是一种局部不变特征描述子，对图像的平移、旋转具有不变性；但却并不具备尺度不变性[8-9]。文献[10]利用ORB进行匹配时，采用改进的随机采样一致性（RANdom Sample Consensus， RANSAC）进行提纯，使得匹配精度得到了提高；文献[11]同样在运用ORB匹配时，结合随机采样一致性方法，剔除错误匹配，并利用最小二乘估计变换参数，对图像进行矫正；文献[12]结合SIFT的算法思想对ORB进行改进，实现了尺度不变性。以上研究解决了一些问题，但是在使用RANSAC算法中，判定内外点距离阈值、随机抽样本集的次数和一致性集合的大小这3个参数需要根据不同的图像设置不同的值，频繁地设置参数，极大地影响了计算效率；并且文献[12]结合SIFT的算法思想会降低计算速度，匹配精度也不高。针对上述情况，结合SURF检测子和ORB描述子，并利用比率测试和对称测试进行筛选，最后运用最小平方中值（Least Median Squares， LMedS）定理再次提纯，从而克服了ORB不具有尺度不变性和RANSAC设置的参数较多的缺陷，并且匹配精度得到进一步提高。

1ORB算法原理

1.1特征点提取

ORB算法采用加速分割测试特征（Features from Accelerated Segment Test， FAST）算子来提取特征点，FAST角点检测定义为：若某像素点具有与其邻域内一定数量的像素点不同的特征时，该像素点被检测为角点，例如在灰度图像，某像素点周围有足够多像素点的灰度值均高于或低于该点的灰度值[13-14]。选取像素点H，并设该点的像素值为HP，考虑该像素点周围的16个像素点，若在以H点为圆心，16个像素点组成的圆上有N（一般取9或者12）个连续的像素点，它们的像素点比HP+T （T为选取的阈值）大，或者比HP-T小，那么该像素点就是角点。FAST角点检测速度快，但却不具备旋转尺度不变性和旋转不变性。

FAST角点主方向运用亮度中心算法，以特征点为中心；同时作为坐标原点，在其邻域U内计算质心位置，然后以特征点为起点，质心为终点构造向量，此向量的方向即为特征点的方向，计算过程如下所示。

区域U的矩定义为式（1）：

Mp，q=∑（x，y）∈UxpyqI（x，y）（1）

其中I（x，y）为点（x，y）处的灰度值，灰度矩设为C=（Cx，Cy）。其中：Cx=M1，0/M0，0，Cy=M0，1/M0，0，那么，FAST角点主方向为：

θ=arctan（M0，1/M1，0）（2）

1.2ORB特征描述子

ORB采用二进制的鲁棒性独立基本特征（Binary Robust Independent Elementary Feature， BRIEF）生成特征描述子[15]，BRIEF用二进制的方式描述图像区域，大幅度减少像素间的对比量。定义S×S大小的图像邻域P的测试准则τ为：

τ（p；x，y）=1，p（x）

0，p（x）≥p（y）（3）

其中P（x）是图像邻域P在x后面的上标T是否表示转置？那么，此处的x是否是矢量、向量或矩阵？请明确。另外，后面的x，哪个是矢量、向量或矩阵？也请一一指出。=（u，v）T处的灰度值

原内容为：“P（x）是图像邻域P在x=（u，v）T 处的灰度值”。现改为：“P（x）是图像邻域P在像素点x=（u，v） 处的灰度值，同理可知P（y）为图像邻域P在像素点y处的灰度值”

P（x）是图像邻域P在像素点x=（u，v） 处的灰度值，同理可知P（y）为图像邻域P在像素点y处的灰度值

。选择n个（x，y）测试点对时，通过二进制测试准则生成n维二进制比特串的描述子，如式（4）所示：

fn（p）=∑1≤i≤n2i-1τ（p；xi，yi）（4）

其中n的选值需综合比较计算速度、识别率和存储效率，一般选择64，128，256等。

由于BRIEF邻域准则测试时仅通过单一像素进行计算，容易受噪声影响。为了解决噪声影响问题，ORB的测试点均采用31×31像素邻域内的5×5子窗口，通过高斯分布选择子窗口，再对图像进行积分以加速计算。

上述生成的特征描述子是没有方向的，因此使用1.1节求得的特征点质心方向作为BRIEF的主方向，使得描述子具备旋转不变性。对于（xi，yi）处任意n个二进制准则集，定义一个2×n的矩阵：

M=x1x2…xny1y2…yn（5）

使用特征点质心方向θ对应的旋转矩阵Rθ，构建M的一个有向形式Mθ=RθM，此时旋转不变的BRIEF如式（6）所示：

gn（p，θ）=fn（p）|（xi，yi）∈Mθ（6）

通过贪心法则进行搜索，从计算得到的全部像素块中选择n个相关性最低的作为rBRIEF此处的“rBRIEF”，是否应该为“BRIEF”？请明确。旋转不变的二进制鲁棒性独立基本特征（Rotation invariance Binary Robust Independent Elementary Feature， RBRIEF）。

1.3特征点匹配

ORB生成的特征描述子为二进制码串形式，使用 Hamming 距离实现对特征点的匹配比较合适。

2结合SURF改进ORB的算法

由以上ORB算法原理可以看出，ORB虽然具有旋转不变性，但却并不具备尺度不变性，其根本原因在于FAST检测出的特征点不含尺度不变信息，从而使得描述子不具备尺度不变性，因此，解决的办法是使检测出的特征点具备尺度不变信息。

2.1Hessian矩阵检测特征点

设图像I中某点P=（x，y），则尺度为σ的Hessian矩阵定义为：

H（P，σ）=Lxx（P，σ）Lxy（P，σ）Lxy（P，σ）Lyy（P，σ）（7）

其中Lxx（P，σ）是高斯滤波后的图像点P在x方向的二阶导数；同理，可求得Lxy（P，σ）、Lyy（P，σ）。

由于求Hessian时要先高斯滤波，然后求二阶导数，在离散的像素点中，可以用一个模板代替，如图1所示。此模板可以极大程度地提高计算速度，图1顶行分别为Lxx、Lyy和Lxy；底行中用模板近似为Dxx、Dyy和Dxy表示。

图1中白色部分的权值设为-1，黑色部分设为1，其他区域不设置权值，则计算Hessian矩阵行列式的比较精确的近似公式为：

det（H）=DxxDxx-（0.9Dxy）2（8）

其中0.9为实验测得的比较准确的参数，进而得到每个像素点的Hessian矩阵行列式的近似值。

改变模板的大小，重复上述步骤，可以得到不同尺度下的像素点的Hessian矩阵行列式的近似值。将经过Hessian矩阵处理过的每个像素点与其三维领邻域此处是否应该为“邻域”？请明确。的26个点进行大小比较，如果它是这26个点中的最大值或者最小值，则保留下来，当作初步的特征点。

接着采用三维线性插值法得到亚像素级的特征点，此时的特征点即具备尺度不变性。

2.2生成特征点描述子

首先采用求FAST角点主方向的方法，计算出通过Hessian矩阵行列式求得的特征点的主方向，接着使用1.2节中求ORB特征描述子的方法，计算出特征描述子，由于2.1节求得的特征点具备了尺度不变性，并且特征描述子是在特征点的基础上生成的，因此此时的特征描述子不仅具有旋转不变性，而且具有尺度不变性。

2.3特征点匹配

简单地说，K近邻算法采用测量不同特征值之间的距离方法进行分类。令K=2，即对于每个特征点，在另一幅图像中找到两个候选的匹配点，其中一个是最优匹配点，另一个为次优匹配点。

2.4剔除错误匹配点

首先采用比率测试，其原理为：如果最优匹配点的测量距离非常小，而次优匹配点的测量距离相对较大，那么最优匹配点无疑是安全可靠的；如果两个候选匹配点的测量距离相近，那么如果选择其中之一作为匹配点很可能出错，是不可靠的。比率测试正是检查这两个距离的比值，以除去不安全的匹配，因此对当前的匹配进行筛选，去除最有匹配和次优匹配强度响应强度大于设定阈值的匹配以及孤立的匹配。

接着采用对称测试，令左匹配为待匹配的两张图从左图到右图的匹配，右匹配为待匹配的两张图从右图到左图的匹配，对称测试即为对左匹配和右匹配进行检查，输出对称的匹配。

最后采用最小平方中值定理提纯，文献[10]中提出使用RANSAC算法进行提纯，RANSAC是一种随机参数估计算法，性能良好，经常被采用，但其内部的3个参数需要人为设置，因此本文采用最小平方中值（Least Median Square， LMedS）算法。LMedS随机抽选样本中的一个子集，首先通过最小方差计算子集参数，然后计算全部样本与该子集模型的偏差。区别于RANSAC，LMedS记录偏差值大小居中的那个样本的偏差，以及本次计算得到的模型参数，因此LMedS无需设定阈值来区分内点和外点。重复N次上述过程，选择N个偏差中值最小的一个，该偏差对应的模型参数作为最终的模型参数估计值。样本子集中样本的个数、期望的模型误差决定了迭代次数N的大小。最小平方中值定理克服了RANSAC的缺点，但其也存在缺点，当外点的个数占总样本数目的比例超过50%时，就无法得到正确的模型参数，而比率测试和对称测试经过筛选后，这个缺点也就克服了。

3实验结果与分析

为验证算法性能，所用电脑的处理器为Intel Core i54200，64位操作系统，内存为4.00GB，并使用Visual Studio 2013进行仿真实验。

3.1尺度不变性实验

为了验证本文提出的算法的尺度不变性，以尺度变化的图像作对比测试。其中：用ORB测试的结果如图2所示，可以明显看出，在尺度发生变化的时候，ORB的匹配效果并不是很好，匹配点过于集中某一部分，并且在尾巴和头部等地方存在一些明显的错误匹配；而使用本文算法测试的结果如图3所示，得到了较为理想的实验效果。对比图2和图3可以发现，本文算法克服了ORB不具备尺度不变性的缺陷，在图像发生较大尺度变化时，仍能取得较好的匹配效果。

为了验证本文算法在尺度变化时具有较高的匹配成功率，即匹配精度，用ORB、SURF以及本文算法分别随机统计实验中的5组匹配数据，如表1所示。

从表1可以看出，在尺度变化时，本文算法的匹配精度远高于ORB的匹配精度，本文算法的平均匹配精度约为97.2%，比ORB的平均匹配精度提高了74.3个百分点，说明了该算法在尺度不变性方面的优势。同时，本文算法比SURF的平均匹配精度提高了4.8个百分点，这要得益于提出的提纯算法的优越性能。

3.2旋转不变性实验

本文提出的算法和ORB算法都具备旋转不变性，为了验证本文算法的旋转不变性以及提出的比率测试、对称测试和最小平方中值定理在匹配提纯方面的优越性能，以旋转图像作为测试图像进行比较。其中图4是使用ORB的匹配效果，可以看出，ORB虽然具有旋转不变性，但是由于其只是简单地使用Hamming 距离实现特征点的匹配，因此存在错误匹配，例如在左下角出现了错误匹配。而使用本文算法进行匹配时，不仅具有旋转不变性，而且经过有效的提纯后，匹配精度得到了提高，其匹配效果如图5所示。

为了验证本文算法在旋转变化时仍然具有较高的匹配精度，随机统计实验中的5组匹配数据，如表2所示。

从表2可以看出，图像旋转时，本文算法的平均匹配精度约为98.1%，比ORB的平均匹配精度提高了约6.9%6.6个百分点此处改为“提高了6.6个百分点”，通过98.1-91.5得来，或改为“提高了7.2%，通过（98.1-91.5）/91.5得来”，是否符合表达？请明确。也包括前面的中文摘要中的描述。，说明了本文算法在旋转不变性方面同样具有良好性能。

3.3匹配时间对比实验

为了验证本文算法的实时性，随机统计实验中的5组匹配时间数据，如表3所示。

从表3可以看出，本文算法的平均匹配时间约为180.3ms，比ORB的平均匹配时间慢了约154.8ms；但却比SURF快了约100.6ms，说明了本文算法在实时性方面同样具有良好性能，但是提纯算法会耗费一点时间，使得匹配速度比ORB略慢。从以上实验可以看出，本文算法具备了尺度不变性和旋转不变性，匹配精度得到进一步提高，满足实时性需求，有一定的实用性。

4结语

本文提出了一种结合SURF和ORB的算法，该算法克服了ORB不具备尺度不变性的缺陷，并采用比率测试、对称测试、最小平方中值定理进一步提纯，通过实验验证了算法的通用性以及在匹配精度方面的优越性能。由于ORB计算速度本身就很快，同时SURF提取特征点也比较快，使得匹配点经过提纯后，计算速度也基本能满足实时性的需求，但其速度不如ORB，这也是接下来要进一步研究的地方。

参考文献：

[1]

朱琳，王莹，刘淑云，等.基于改进快速鲁棒特征的图像快速拼接算法[J].计算机应用，2014，34（10）：2944-2947.（ZHU L， WANG Y， LIU S Y， et al. Fast image mosaic algorithm based on improved fast robust feature [J]. Journal of Computer Applications， 2014， 34（10）： 2944-2947.）

[2]

刘海燕，杨昌玉，刘春玲，等.基于梯度特征和颜色特征的运动目标跟踪算法[J].计算机应用，2012，32（5）：1265-1268.（LIU H Y， YANG C Y， LIU C L， et al. Moving target tracking algorithm based on gradient feature and color feature [J]. Journal of Computer Applications， 2012， 32（5）： 1265-1268.）

[3]

侯毅，周石琳，雷琳，等.基于ORB的快速完全仿射不变图像匹配[J]. 计算机工程与科学，2014，36（2）：303-310.（HOU Y， ZHOU S L， LEI L， et al. Fast fully affine invariant image matching based on ORB [J]. Computer Engineering & Science， 2014， 36（2）： 303-310.）

[4]

童宇，蔡自兴.基于特征匹配的全景图的生成[J].华中科技大学学报（自然科学版），2004，32（S1）：77-79.（TONG Y， CAI Z X. Generation of panoramic image based on feature matching [J]. Journal of Huazhong University of Science and Technology （Nature Science Edition）， 2004， 32（S1）： 77-79.）

[5]

LOWE D G. Object recognition from local scaleinvariant features [C]// Proceedings of the 1999 IEEE International Conference on Computer Vision. Piscataway， NJ： IEEE， 1999： 1150-1157.

[6]

BAY H， ESS A， TUYTELAARS T， et al. SURF： speeded up robust feature [J]. Computer Vision and Image Understanding， 2008， 110（3）： 346-359.

[7]

RUBLEE E， RABAUD V， KONOLIGE K， et al. ORB： an efficient alternative to SIFT or SURF [C]// Proceedings of the 2011 IEEE International Conference on Computer Vision. Piscataway， NJ： IEEE， 2011： 2564-2571.

[8]

刘铭.基于ORB算法的双目视觉测量与跟踪研究[D]. 哈尔滨：哈尔滨工业大学，2014：25.（LIU M. Binocular computer vision measurement and tracking research based on the ORB algorithm [D]. Harbin： Harbin Institute of Technology， 2014： 25.）

[9]

孟凡清.基于背景差分法与ORB算法的运动目标检测与跟踪算法研究[D].北京：北京印刷学院，2014：30-33.（MENG F Q. Study on the moving object detection and tracking based on background subtraction and ORB algorithm [D]. Beijing： Beijing Printing Institute， 2014： 30-33.）

[10]

佘建国，徐仁桐，陈宁.基于ORB和改进RANSAC算法的图像拼接技术[J].江苏科技大学学报（自然科学版），2015，29（2）：164-169.（YU J G， XU R T， CHEN N. Image stitching technology based on ORB and improved RANSAC algorithm [J]. Journal of Jiangsu University of Science and Technology （Nature Science Edition）， 2015， 29（2）： 164-169.）

[11]

张云生，邹峥嵘.基于改进ORB算法的遥感图像自动配准方法[J].国土资源遥感，2013，25（3）：20-24.（ZHANG Y S， ZOU Z R. Automatic registration method for remote sensing images based on improved ORB algorithm [J]. Remote Sensing for Land and Resources， 2013， 25（3）： 20-24.）

[12]

许宏科，秦严严，陈会茹.基于改进ORB的图像特征点匹配[J].科学技术与工程，2014，14（18）：105-109.（XU H K， QIN Y Y， CHEN H R. Feature points matching in images based on improved ORB [J]. Science Technology and Engineering， 2014， 14（18）： 105-109.）

[13]

ROSTEN E， DRUMMOND T. Fusing points and lines for high performance tracking [C]// Proceedings of the 2005 IEEE International Conference on Computer Vision. Piscataway， NJ： IEEE， 2005： 1508-1515.

[14]

ROSTEN E， DRUMMOND T. Machine learning for high speed corner detection [C]// ECCV’06： Proceedings of the 9th European Conference on Computer Vision. Berlin： Springer， 2006： 430-443.

[15]

CALONDER M， LEPETIT V， STRECHA C， et al. BRIEF： binary robust independent elementary features [C]// ECCV’10： Proceedings of the 11th European Conference on Computer vision. Berlin： Springer， 2010： 778-792.