一种基于非线性尺度空间的ORB特征匹配算法研究

郭芮 许钢 李若楠 赵春叶 江娟娟

摘 要：ORB（Oriented FAST and rotated BRIEF）特征描述算法具有旋转不变性、匹配速度快的特点，但没有解决尺度不变性、误匹配率高的问题。针对此缺陷，提出一种改进的ORB特征点匹配算法，完成特征点的检测、匹配以及剔除误匹配。改进算法首先借鉴了A-KAZE基于非线性扩散滤波构建尺度空间的方法;其次利用ORB特征检测子在所构建的非线性尺度空间进行特征点的检测;再次对采集到的特征点生成特征描述子;最后在使用Hamming距离匹配的基础上再对其结果采用PROSAC算法剔除噪声点。实验结果表明，改进后的算法相较于原ORB算法，有效地解决了ORB算法不具备尺度不变性的问题，且匹配精度大幅提高，适用于尺度变化较大且实时性高的环境，具有较好的工程意义。

关键词：改进ORB算法;A-KAZE;非线性扩散滤波;尺度不变性;特征点匹配

中图分类号：TP181

文献标识码： A

近年来，科学技术迅猛发展，值此方兴未艾之际，计算机视觉技术应运而生，正不断渗透到人们的日常生活中，其中比较重要的内容就是图像中特征点匹配算法的研究，它广泛应用于多个领域中[1-3]，例如移动机器人导航、图像拼接、三维重建以及医学图像分析等计算机视觉领域的基础研究。目前最为广泛的特征点匹配算法有SIFT[4]、SURF[5]、ORB[6]等。

LAWE[4]等人于1999年提出了尺度不变的特征变换SIFT（Scale￣invariant Feature Transform）算法，该算法基于特定兴趣点而与图像大小和旋转无关，对于图像旋转、尺度缩放具有较好的稳定性，同时对亮度、视角等条件的微小变化鲁棒性强，但该算法的局部特征点检测和描述子特征是建立在高维的基础上，这使得整个过程计算量庞大、消耗时间多，难以满足实时性的要求。为了克服上述不足，2006年BAY[5]等人基于SIFT的基础上提出一种加速鲁棒性特征SURF（Speeded Up Robust Feature）算法，由于SURF算法最大的特点在于采用了哈尔特征以及积分图像的概念，这使得典型的SURF算子比SIFT算子快大概3倍左右，大大加快了程序执行效率。机器视觉技术的发展使得人们更加关注特征匹配算法在执行效率方面的性能，有大量学者研究表明，ORB算法的运行速度比上述两种算法快至少一个数量级。该算法于2011年由RUBLEE[6]等人在ICCV上提出，它在特征点质量和性能间取得了较好的折中。从实时性角度评测，它是目前运行速度较快的算法。ORB是一种局部不变特征检测子，即图像发生旋转变换时仍可以保持很好的鲁棒性，但对于图像尺度变化较大的图像，传统ORB算法的匹配效果却不理想[7]，由于该算法尺度空间的构建环节不够成熟，当图像尺度发生突变时，图像特征匹配的精度会受影响。文献[8-10]分别通过结合SIFT和SURF检测算子使得改进后的ORB算法拥有尺度不变特性，但实时性和匹配精度难以兼得，可见对ORB的研究仍具有非常大的意义。

本论文提出一种基于非线性尺度空间的ORB特征匹配改进算法，该算法借鉴A-KAZE[11]（Accelerated-KAZE）算法思想对ORB进行改进，通过构建非线性尺度空间提取显著特征点，使其对尺度变换的图像具备较强的表现。与此同时，使用PROSAC[12]（渐进一致性采样）对匹配点对提纯，进而提高ORB算法的匹配质量，从而达到不失精度的条件下满足实时匹配的目的。

1 传统的ORB算法

ORB算法具有局部不变性，该算法采用以速度著称的加速分割测试特征FAST[6]（Feature From Accelerated Segment Test）检测特征点，利用旋转二进制鲁棒基元独立特征BRIEF[6]（Binary robust independent elementary feature）算法生成描述符，再以Hamming距离为相似性度量准则比较描述符完成粗匹配。其主要步骤如下：

（1）關键点提取：采用o-FAST算法进行关键点提取，加入Rosin灰度质心法（Intensity Centroid）为其提供方向特性，使得后面的特征描述符具有方向信息;

（2）建立特征描述符：ORB算子采用具备旋转角度的改进BRIEF算法，即rBRIEF算法。其主要思想是依据像素点灰度值的大小，利用随机选点机制在某个特征点的周边选取一定数量的像素点对测试集，生成二进制串描述符;（3）特征点粗匹配：以Hamming距离作为相似性度量准则对描述子进行比较，若满足一定的条件则认为该特征点匹配对是正确的。该方法原理简单易于操作。

2 改进的ORB特征匹配算法

本文提出的一种基于非线性尺度空间的改进ORB算子，其主要流程如1所示。

首先借鉴A-KAZE[8]算法原理利用FED数值分析框架来求解可变传导扩散方程，进而完成非线性尺度空间的构建;其次采用FAST-9算法在非线性尺度空间的每一层进行特征点的检测并计算特征点的质心方向;再次结合之前获取的具有方向特性的特征点，采用rBRIEF算法生成具有二进制字符串特点的特征描述子;最后使用FLANN方法计算汉明距离进行特征点的粗匹配，再对其匹配结果采用PROSAC算法（改进的RANSAC算法）剔除噪声点，实现更加精准的匹配。

2.1 尺度空间的构建

由于传统的ORB算法没有很好的解决尺度不变性，所以在进行角点检测之前要对其构建尺度空间。传统的基于Gaussian尺度空间的构建存在最大的缺陷就是高斯滤波无法保留边缘、边界、细节信息，它会把所有尺度的细节和噪声平滑到相同的水平，这导致其位置精度和独特性大打折扣。而基于A-KAZE算法的非线性尺度分解有望解决上述不足。

2.1.1 非线性扩散

鉴于传统的正向欧拉法在求解非线性方程数值时，迭代收敛步长非常短、消耗时间资源很大导致计算复杂度高。针对上述不足，本文在构建一个类似金字塔型的非线性尺度空间来求解非線性滤波扩散方程时，采用快速显示扩散FED[13]（Fast explicit diffusion）算法。可以通过非线性偏微分方程来描述传导方程：

2.2 特征点检测

ORB算法采用改进的FAST算法（oFAST）进行角点检测，早期的Harris和SIFT特征点提取算法都是基于自相关矩阵响应值的算法，一般会涉及到卷积运算，导致运算量庞大，FAST算法刚好克服了这方面的缺陷。ROSTEN等人于文献[15]给出FAST的定义：在某个候选像素点的圆形范围内，通过比较该点与邻域点的灰度差值来判别该点是否为特征点。具体的特征提取过程如下：

（1）确定检测范围：如图2所示，以像素点P为圆心，以3个像素单位为半径画圆，选取圆上16个像素点为待检测的点。

（2）设定合适阈值：将上述（1）中待检测的16个像素点的灰度值与P点灰度值逐一比较，两点灰度值之差的绝对值大于某一阈值εd，则认为这两点是不同的点。特征点的响应函数如下：

2.3 特征点描述

ORB算法采用改进的BRIEF算法（rBRIEF）建立描述符，其核心思想是采用随机选点机制在图像中选取像素点，通过比较它们的灰度值从而得到描述符。其具体过程如下：

（1）为消除原BRIEF描述符以像素为测试点所带来的噪声影响，改进算法在特征描述过程中，是以特征点为中心设定邻域为31×31像素的图像块，以此作为测试点集的候选区域。每次测试都是在一个5×5的子窗口内随机选取一个点对（x，y），使用如下准则进行二进制赋值：

通过greedy贪婪算法搜索出具有较高方差和较低相关性的n个（文献[6]中n=256）点对作为最终的描述符，大的方差和不相关性有利于描述符保持较大区分性和描述能力的特性，为后续的特征匹配打好基础。

2.4 特征点匹配

上节求得的特征描述符是一个二进制码串，这里先对其采用Hamming距离快速近似最近邻（FLANN）方法进行粗匹配。由于外界噪声因素的影响，粗匹配后的结果仍存在很多伪匹配对，影响匹配效果。故采用PROSAC算法剔除外点，从而提高匹配质量。

其中粗匹配中采用原理简单、操作方便的FLANN算法，该算法在OpenCV库中现已集成。由于RANSAC算法在剔除外点的过程中没有考虑特征点间的差异性，其随机抽样模式会带来迭代次数不稳定、浪费大量计算资源等弊端。本文采用PROSAC算法对特征点粗匹配对进行优化，该方法对包含较多离群点的数据仍然适用。其核心思想是依据一定准则将样本点进行降序排列，在较高匹配率的粗匹配子集中计算模型，从而减少迭代次数，最优估计解也会尽早出现。算法流程如下：

3 实验设置、结果及分析

实验一：针对本文所提出的改进算法，设计了两类实验：（1）尺度不变性对比实验;（2）综合不变性对比实验，即尺度和旋转角度同时改变的情况下进行的实验。使用上述两类实验，分别对两组图像进行测试，其中输入的原始图像格式为.png，像素大小：750×750，两张图像分别取自室内和室外环境。

3.1 尺度不变性测试结果分析

通过图3、图4中的（a）、（b）对比实验以及表1不难发现，采用ORB算法的测试效果图中，未提纯前成功匹配的特征点对数目偏少，分别为361、329，提纯后正确匹配的点对数量分别为288、257，其正确匹配率分别为80%和78%。而采用改进算法的测试效果图中，未提纯前成功匹配的特征点对数目较多，分别为428、413，提纯后正确匹配的点对数量分别为398、376，其正确匹配率分别为93%和91%。相较于原算法，改进算法采用快速的FED算子来提高尺度空间的构建速度，并且沿用了ORB特征检测算法。在有效特征点数目增多的情况下，平均匹配精度提升了13%。但由于添加了PROSAC算法二次剔除误匹配点，相较于原ORB算法，运行时间平均增加了21.2 ms。

3.2 综合不变性测试结果分析

图5、图6是针对图像旋转、多尺度的综合测试效果图。表2是针对匹配精度和算法执行时间方面进行的定量分析。结合表2和两组（a）、（b）对比图可以看出，采用原算法的测试效果图中，未提纯前成功匹配的特征点对数量分别为341、314，提纯后正确匹配的点对数目分别为276、236，其准确率分别为81%和75%。而采用改进算法的测试效果图中，未提纯前成功匹配的特征点对数量分别为423、408，提纯后正确匹配的点对数目分别为389、359，其准确率分别为92%和88%。由此可得，改进算法提取到的特征点更加丰富，且增加了二次提纯特征点匹配对的环节，因此在匹配精度上平均提升了12%，在运行时间上平均增加了23.47 ms，但不影响实际应用中算法的实时性。

由图7不难发现，改进算法相较于原ORB算法，在尺度不变性方面鲁棒性更强，且角点检测更加稳定。

4 结语

本文针对ORB算法没有解决尺度不变性、误匹配率高等问题，提出优化算法。首先通过借鉴A-KAZE算法原理构建非线性尺度空间，其次沿用ORB算子在每层尺度空间的图像上进行特征提取并计算描述子，再次使用FLANN算子和PROSAC算法双重筛选原则剔除误匹配，最终得到匹配质量较高的结果。实验结果表明，改进算法有效地解决了尺度不变性的问题，提取到的特征点在细节和边缘方面处理得更好，并且匹配精确度和算法效率得到了一定改善，适用于匹配精度高、尺度变化较大的应用场景。

参考文献：

[1]SINHA S N， FRAHM J M， POLLEFEYS M， et al. Feature tracking and matching in video using programmable graphics hardware[J]. Machine Vision and Application， 2011， 22（1）： 207-217.

[2]丁文東，徐德，刘希龙，等. 移动机器人视觉里程计综述[J]. 自动化学报，2018，44（03） ： 385-400.

[3]NASROLLAHI K， MOESLUND T B. Super￣resolution： a comprehensive survey [J]. Machine Vision and Applications， 2014， 25（6）： 1423-1468.

[4]LOWE D G. Distinctive image features from scale￣invariant keypoints [J].International Journal of Computer Vision，2004，60（2） ： 91-110.

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

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

[7]ZHAO H Y， ZHAO H C， LV J F， et al. Multimodal image matching based on Multimodality Robust Line Segment Descriptor [J]. Neurocomputing， 2016， 177： 290-303.

[8]王健，于鸣，任洪娥. 一种用于图像拼接的改进ORB算法[J]. 液晶与显示，2018，33（06） ：520-527.

[9]邓仕雄，王晓红，刘继庚，等. 基于SURF算法和极线约束的无人机影像匹配研究[J]. 贵州大学学报（自然科学版），2018，35（01）： 35-39.

[10]张明浩，杨耀权，靳渤文. 基于图像增强技术的SURF特征匹配算法研究[J]. 自动化与仪表，2019，34（09）： 98-102.

[11]ALCANTARILLA P F， JESU N， BARTOLI A. Fast explicit diffusion for accelerated features in nonlinear scale spaces[C]. Electronic Proceedings of British Machine Vision Conference. Bristol： BMVC， 2013： 1-11.

[12]CHUM O， MATAS J. Matching with PROSAC￣progressive sample consensus[C]//2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR， 2005， 1： 220-226.

[13]WEICKERT J， GREWENIG S， SCHROERS C， et al. Cyclic schemes for PDE-based image analysis [J]. International Journal of Computer Vision， 2016， 118（3）： 275-299.

[14]GREWENIG S， WEICKERT J， BRUHN A. From box filtering to fast explicit diffusion [J]. Lecture Notes in Computer Science， 2010， 6376： 533-542.

[15]ROSTEN E，PORTER R，DRUMMOND T.Faster and Better： a machine learning approach to corner detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（1） ： 105-119.

[16]张岩，李建增，李德良，等. 快速稳健的自适应非线性尺度特征检测子[J]. 系统工程与电子技术，2016，38（11）： 2678-2684.

（责任编辑：于慧梅）