结合尺度不变特征的ORB算法改进

卢健;何耀祯;陈旭;刘通

【摘 要】针对ORB(ORiented Brief,方向描述符)算法不具备尺度不变性,且匹配点对错误较多等缺点,结合SURF(Speed-up Robust Features,加速稳健特征)与ORB提出一种新的算法.通过计算积分图像,使用盒子滤波器近似高斯滤波,构建尺度空间,通过Hessian矩阵检测出具备尺度不变的特征点;用ORB对特征点进行描述,采用Hamming距离完成粗匹配;使用改进的RANSAC (RANdom SAmple Consensus,随机抽样一致)减少其迭代次数,同时,去除错误的匹配点对.实验结果表明,在尺度变化时,改进算法的平均准确度为86.3％,约为ORB的3.1倍;综合对比时,改进算法的平均精度可达85.1％,是ORB的2.4倍,平均耗时高于ORB,但远低于SIFT,在不失精度的前提下有效地保证了鲁棒性和实时性. 【期刊名称】《测控技术》 【年(卷),期】2019(038)003 【总页数】6页(P97-101,107)

【关键词】ORB;尺度空间;Hessian矩阵;Hamming距离;改进RANSAC 【作 者】卢健;何耀祯;陈旭;刘通

【作者单位】西安工程大学电子信息学院,陕西西安710048;西安工程大学电子信息学院,陕西西安710048;西安工程大学电子信息学院,陕西西安710048;西安工程大学电子信息学院,陕西西安710048 【正文语种】中 文

【中图分类】TP391

图像特征点匹配是计算机视觉中重要而基础的内容[1]，它被广泛地运用于模式识别、目标跟踪、图像拼接等领域[2]。在过去的十几年里，很多经典算法被提出。David G.Lowe提出的SIFT(Scale-Invariant Features Transform,尺度不变特征变换)算法提取的特征点稳定，描述子信息量丰富，但是计算量大，匹配时间较慢[3]。2006年Bay等提出SURF[4](Speeded-Up Robust Features，快速鲁棒特征)算法，它较SIFT算法做了很大的改进，即通过计算积分图像，以及使用盒子滤波器近似高斯滤波器等方式进行加速运算，据统计SURF算法在速度上比SIFT快一个数量级，并且对于尺度变化、旋转变化、光照变化具备较强的鲁棒性[4]。2011年，Rublee等人在ICCV上提出ORB[5](Oriented Brief)算法，该算法的运行速度极快，据统计，该算法计算速度比SIFT快两个数量级，比SURF快一个数量级[6]，就速度而言，它是目前匹配算法中最快的。ORB是一种局部不变特征描述子，在图像发生旋转时，也能保持很好的鲁棒性，但是它因为没有在尺度空间检测特征点以致其不具备尺度不变性，所以在图像尺度变化时匹配准确度会下降[7]，此时匹配精度远低于SIFT、SURF算法。文献[8]通过SIFT检测具备尺度不变的特征点，然后使用ORB进行描述和匹配，解决了尺度不变的问题，但实时性不高。文献[9]通过结合SURF算法，解决尺度不变的问题，且相对使用SIFT提取特征点速度有了提升，但是存在错误点对匹配的问题。文献[10]将ORB算法运用在图像拼接上，实现快速拼接。可见若能够保持算法运行速度的同时提高尺度变化时的精确度，则ORB会有更多的用途。

针对ORB算法不具备尺度不变性、错误匹配点对较多等问题，本文提出一种改进算法，通过在尺度空间提取特征点，使其对尺度变换有了较强鲁棒性的同时使用改进的随机抽样一致对匹配点对提纯，做到在不失精度的情况下实时匹配。

1 ORB算法 1.1 特征点检测

ORB算法采用以速度快著称的加速分割测试特征(Features From Accelerated Segment Test,FAST)来提取特征点。检测原理是，以特征点为圆心做半径为3个像素的圆，圆周经过的16个像素点中，若有连续N个像素的灰度值大于Hc+T或小于Hc-T，则认为该像素为特征点,其中Hc为中心像素的灰度值，T为设定的灰度检测阈值[7,10]。在取得特征点后，计算Harris响应，并根据响应强度进行排序。 (1)

1.2 特征点方向

采用灰度质心的方式，计算特征点的方向。以特征点为中心，取邻域U，计算质心位置。以该特征点为原点建立坐标系，连接质心，构造向量，将该向量的方向作为特征点的方向[8]。

其中，邻域U计算质心的公式为 (2) 质心为 (3)

计算特征点的方向： (4)

1.3 特征点描述子

ORB算法采用二进制的BRIEF生成描述子。BRIEF通过从图像中特征点邻域中随机抽取像素点的灰度值比较进行描述。定义在S×S邻域P内的τ测试[9]： (5)

式中，p(x)为在邻域P内点x(u,v)处的像素灰度值；p(y)为点y(w,e)处的灰度值。测试时在特征点邻域中随机选取N对点对，进行τ测试，生成n维的二进制编码作为当前特征点的描述子，一般n设定为、128或256，如式(6)所示： (6)

由于采用BRIEF生成描述子时，在邻域中选取的点是单一像素的灰度值，容易受噪声影响，所以ORB中采取在特征点邻域31×31区域内的5×5子窗口进行τ测试，这样极大地提高了鲁棒性[8]。

设生成特征点描述符的n个测试点对为(xi,yi)，定义一个2×n的矩阵： (7)

利用前面灰度质心算得角度θ生成旋转矩阵Rθ，旋转后的坐标为 Sθ=RθS (8)

这样就可以得到具备旋转不变的描述子： gn(p,θ)=fn(p)|(xi,yi)∈Sθ (9)

1.4 特征点匹配

使用Hamming匹配，对经过上述过程的特征点二进制编码描述子进行相似性度量，当相似性大于设定阈值，则认为该点对为匹配点对[10]。

例如：A、B为两个二进制描述符 A：1011010100 B：1010010101

对等长的描述符按位比较其相同位数，计算占长度的百分比，则为相似程度。A、B相似程度为80%。在实际中，设定阈值，当相似程度大于阈值时，则认为该点对为匹配点对。 2 改进算法

结合SURF算法，先通过计算积分图像，提取具备尺度不变的特征点，然后通过ORB对特征点进行描述，生成二进制描述符，然后通过Hamming距离进行匹配，最后采用改进的RANSAC进行提纯。 总体思路流程如图1所示。 图1 算法流程图 2.1 多尺度特征点检测 2.1.1 积分图像

将彩色图像转换为灰度图像G，其积分图像可以由式(10)得到[11]： (10)

2.1.2 极值点检测

设图像I中一点P(x,y)，则尺度为σ的Hessian矩阵定义为 (11)

式中，Lxx,Lxy,Lyy为高斯滤波后图像在点P处各个方向的二阶导数。

由于求Hessian时先进行高斯平滑，然后求二阶导数。SURF算法中，采用盒子滤波器近似高斯滤波器[12]。两种滤波器模板如图2所示。图2(a)分别表示

Lxx,Lxy,Lyy，图2(b)使用盒子滤波器对图2(a)近似，用Dxx,Dyy,Dxy表示。其中，各部分权值较为简单。Dxx和Dyy中白色部分为1，黑色部分为-2；Dxy中白色部分为1，黑色部分为-1，其余部分权值均为0[13-14]。 图2 两种滤波器模板

计算Hessian矩阵行列式更为精确的近似公式为 det(H)=DxxDyy-(0.9Dxy)2 (12)

式中，0.9为实验所测得的经验值[4]。

SURF算法中，通过改变模板的大小，获得不同的尺度。通过使用积分图像，使得盒状滤波器的运算与它的大小无关，这也是SURF能够快速运算的一个重要原因[14]。将经过Hessian矩阵处理的每个像素与其三维邻域的26个点进行比较，若为最大值或最小值，则保留[15]。

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

2.1.3 特征点方向

以特征点为中心，以6s(s为特征点所在的尺度)为半径的圆形区域，统计所有像素点的Haar小波响应。采用一个张角为60°的扇形滑动窗口，计算其区域内的Haar小波水平与垂直方向的响应之和，并赋予高斯权重系数，使靠近中心的贡献更大，滑动扇形窗口，得到最大的响应区域对应的方向即为此特征点的主方向[16]。 方向分配如图3所示。 图3 方向分配示意图 2.1.4 描述

使用ORB描述子对得到具备尺度不变和旋转不变的特征点进行描述，得到二进制描述符。

2.2 粗匹配与提纯 2.2.1 粗匹配

得到二进制描述符后，进行Hamming距离匹配，取相似度最高的点对，作为匹配点对。 2.2.2 提纯

粗匹配完成后存在许多的错误点对，在特征点匹配中常用RANSAC[17]对错误点对进行剔除，以得到较好的匹配效果[18]。 RANSAC的基本步骤

① 随机从数据集中抽取4个样本数据，将计算出的变换矩阵H，记为模型M； ② 计算数据集中所有数据与模型M的距离误差，若误差小于阈值，则记为inliers； ③ 若支持该模型的inliers数比前一次的支持模型数大，则更新M；否则，返回①； ④ 当迭代一定次数或者inliers数占数据集的比例大于阈值时，则认为找到正确模型，停止迭代，当前模型作为最优解返回。

RANSAC在计算正确模型时往往需要迭代多次，尤其是在数据集较大的情况下，因为它随机抽取样本，一方面可能抽取质量不高的样本，另一方面，数据集较大需要更多的测试，以计算正确的模型[17]。

为减少迭代次数，缩小计算代价，在计算过程中，对RANSAC进行以下改进。 对数据集的样本按下式进行排序： P(n)=pHarris+pmatch (13)

式中，pHarris为点对对应角点的响应强度；pmatch为对应点对的匹配相似度。将计算得到的前30%个样本作为前5次随机抽取的数据集。 改进RANSAC流程图如图4所示。 图4 改进RANSAC流程图

3 实验结果及分析

针对本文所提出的算法，设计了尺度不变性和综合不变性两个实验。编程仿真环境为Visual Studio 2012，计算系统为Win7，处理器为Intel® CoreTM i5-3230 2.6 GHz，内存4 GB。 3.1 尺度不变性实验

验证尺度不变性实验，首先在测试图片Beaver上进行初次验证，算法比较结果如图5所示。随后在10组测试图片上进行二次验证。

据图5(a)显示，ORB算法所取得的特征点数量不多，匹配成功的点对主要集中在尾部和腹部，存在分布不均匀的现象，并且有明显的错误匹配点对。图5(d)改进算法相对于图5(b) SIFT算法与图5(c) SURF算法而言，特征点提取数量足够多，且分布均匀。尺度变化测试结果如表1所示。由表1可知，本文改进算法的匹配正确率明显优于ORB算法，特征点提取数量与SIFT与SURF算法相当。匹配精度大约是ORB的2倍，但耗时有所增加。 图5 算法比较结果表1 尺度变化测试结果 Beaver匹配点对数正确率/%耗时

/msORB2347.862SIFT5082.08863SURF5379.21978改进算法3792.6297 然后，记录8组尺度变化的图片对SIFT、SURF、ORB与改进算法在尺度变化时的鲁棒性进行测试。鲁棒性测试结果如表2所示。

表2 鲁棒性测试结果组别匹配精度/%ORBSIFTSURF改进算法

126.393.4.687.8232.184.594.582.1321.993.091.5.2431.094.686.888.4530.692.291.392.6617.288.3.288.3723.994.291.081.0840.293.887.585.9923.787.285.784.31032.1.588.282.9平均精度27.991.1.986.3

从表2可以看出，ORB算法的准确度最低，在尺度变化时，匹配精度只有27.9%；其中SIFT表现最优，匹配精度达到91.1%，SIFT和SURF匹配精度相差1.2%；

改进算法的匹配精度为86.3%，可达到SIFT算法的94.3%，达到SURF算法的94.7%。

3.2 综合对比性实验

先选取一组存在尺度变化、旋转变化的测试图片Boat，测试结果如图6所示。 从图6(a)可以看出，ORB算法提取的特征点较少，并且分布不均匀，容易出现个别区域匹配点对过于密集的现象，并且存在明显的错误匹配。图6(b)为改进算法实验结果，可以看出，改进算法提取特征点数量足够多，并且在图像纹理变化剧烈的部分分布均匀，匹配精度是ORB的2倍。 图6 算法比较

对比实验结果数据如表3所示。

表3 对比测试结果数据Boat匹配点对数正确率/%耗时/msORB43.0256改进算法10792.3953

然后，随机选取10组存在尺度、旋转变化的测试图片，与ORB、SIFT、SURF算法进行对比，综合性耗时对比如图7所示。 图7 综合性耗时对比

从图7可以看出，ORB算法和改进算法运算速度较快，时间折线在图7中十分接近，SURF算法运行速度其次，SIFT算法运行速度最慢。 综合性精度对比数据如表4所示。

从表4中可看出，SIFT算法在特征点匹配中，精确度最高，达到90.8%；ORB算法精确度最低，为36.4%；改进算法精确度比SIFT算法差5.7%，比SURF算法差3.3%。

表4 综合性精度对比数据组别匹配精度/%ORBSIFTSURF改进算法

123.9.790.1.2229.692.594.585.7346.193.492.886.4433.388.782.981..290.288.5.60.287.493.691.2745.3.978.271.5829.291.790.6.22.5

92.687.184.51034.691.884.879.9平均精度34.0.888.485.1 4 结束语

本文针对ORB的缺点进行改进，通过结合快速鲁棒特征解决了算法不具备尺度不变的缺点，同时使用改进的RANSAC方法，在保证实时性的前提下，改善了匹配精度不高的问题。实验结果表明，算法的准确性明显提升，同时保证了实时性。 在接下来的工作中，可以通过以下措施对该算法做进一步优化： ① 对提取特征点的阈值进行自适应化，以减少人为操作。

② 在构造尺度金字塔时，对连续层间的图像信息进行度量，并进行主动调节，以保证图像尺度参数的合理性。

【相关文献】

[1] 许佳佳，张叶，张赫.基于改进Harris-SIFT算子的快速图像配准算法[J].电子测量与仪器学报,2015,29(1):48-45.

[2] Sinha S N,Frahm J M,Pollefeys M,et a1.Feature traking and matching in video using programmable graphics hardware[J].Machine Vision and Application,2011,22(1):207-217. [3] 周定富，何明一，杨青.一种基于特征点的稳健无缝图像拼接算法[J].测控技术,2009,28(6):32-36.

[4] Bay H,Ess A,Tuytelaar T,et al.Speeded-up robust feature(SURF)[J].Computer Vision and Image Understanding,2008,110(3):346-359.

[5] Rublee E,Rabaud V,Konolige K,et al.ORB:an efficient alternative to SIFT or SURF[C]//Proceedings of the IEEE International Conference on Computer Vision.2011:20-2571.

[6] 林汀,娄小平,刘锋，等.序列图像特征提取与匹配算法的改进[J].计算机工程与应用,2017,53(9):141-145.

[7] 戴雪梅,郎朗,陈孟元.基于改进ORB的图像特征点匹配研究[J].电子测量与仪器学报,2016,30(2):233-240.

[8] 许宏科,秦严严,陈会茹.基于改进ORB的图像特征点匹配[J].科学技术与工程,2014,14(18):105-109.

[9] 邢凯盛,凌有铸,陈孟元.ORB特征匹配的误匹配点剔除算法研究[J].电子测量与仪器学

报,2016,30(8):1255-1261.

[10] 佘建国,徐仁桐,陈宁.基于 ORB和改进RANSAC算法的图像拼接技术[J].江苏科技大学学报(自然科学版),2015,29(2):1-169.

[11] 周军太,龙永红.一种改进 SURF算法的图像配准[J].湖南工业大学学报,2011，25(2):95-99. [12] 谷宗运,谭红春,殷云霞，等.基于SURF和改进的RANSAC算法的医学图像配准[J].中国医学影像学杂志,2014,22(6):470-475.

[13] 刘奇，何明一.基于SURF特征匹配的图像拼接算法[J].测控技术,2010,29(10):27-31.

[14] Sattler T,Leibe B,Kobbelt L.SCRAMSAC:Improving RANSAC’s efficiency with a spatial consistency filter[C]//2009 IEEE 12th International Conference on Computer Vision.2009:2090-2097.

[15] 丁旭,何建忠.一种由DCT和SURF改进的图像感知哈希算法[J].小型微型计算机系统,2014,35(11):2553-2557.

[16] 朱奇光,王佳,张朋珍，等.基于高斯矩改进SURF算法的移动机器人定位研究[J].仪器仪表学报,2015,36(11):2451-2457.

[17] 曾朝阳,程相正,陈杭，等.基于改进SURF算子的高低分辨率图像配准方法[J].激光与红外,2014，44(2):207-212.

[18] Fishchler M A,Bolles R C.Random sample consensus:a paradigm for model fitting with application to image analysis and automated cartography[J].Communications of the ACM,1981,24(6):381-395.

[19] 罗文超,刘国栋,杨海燕.SIFT和改进的RANSAC算法在图像配准中的应用[J].计算机工程与应用,2013,49(15):147-149.