图像特征点匹配算法的研究

林　汀

（北京信息科技大学光电测试技术北京市重点实验室，北京100192）



图像特征点匹配算法的研究

林汀

（北京信息科技大学光电测试技术北京市重点实验室，北京100192）

摘要：特征点匹配是计算机视觉领域的一个重要课题，针对ORB算法在特征点匹配基本上没有尺度不变性，与SURF理论算法相结合，提出基于算法组合的改进算法SUORB。首先生成多尺度空间，并在多尺度空间里检测稳定的极值点，以便提取出的特征点具有尺度不变信息;然后使用ORB描述符来描述特征点，生成旋转不变性的二进制描述符;最后实现特征点匹配。实验结果表明，SUORB有效地解决ORB的缺陷，在图像尺度变化时，SUORB匹配算法比ORB匹配算法的准确度明显提高;同时SUORB和ORB两种算法的匹配速度很接近。

关键词：特征点；匹配；尺度空间；组合算法

0　引言

图像特征点匹配在目标跟踪、图像拼接、模式识别等领域有着广泛的应用[1-2]。David G．Lowe 2004年提出的SIFT（Scale-Invariant Feature Transform，尺度不变特征变换）特征点匹配算法具备尺度和旋转不变性特性，匹配准确性较高[3]，但是计算量较大，运算时间较长。针对这一不足之处，SURF（Speeded-Up Robust Features，快速鲁棒特征）算法应运而生。SURF算法不仅具备SIFT算法在尺度和旋转不变性方面的优势[4]，而且由于其采用盒式滤波器与原图像卷积的计算方式，比SIFT算法相比，速度有了较大提升。

ORB算法相对于SIFT算法更满足实时性的要求，该算法比SIFT快上百倍[4]，比SURF快一个数量级。大多数国内外人士基于ORB算法的优势展开了一系列研究，例如任结在复杂环境中利用ORB的快速性检测运动目标[5]，文献[6-7]利用随机采样一致性方法对ORB进行改进等等。本文针对ORB算法的不足之处，利用SURF和ORB组合生成改进算法，并将其定义为SUORB（Speed-Up ORiented Brief，快速方向描述符）。改进后的组合算法SUORB在匹配速度方面与ORB算法相当，而匹配的准确度与ORB算法相比有很大提高，弥补了ORB算法在图像尺度发生变化时的不足。

1 ORB特征点匹配算法

1.1特征点提取

（1）特征点的检测

FAST检测特征点:以某像素点为圆心，在其圆形区域内，比较中心点和圆周上各像素点灰度值的差值，通过差值判断该中心点为特征点[8-10]。

图1　FAST特征点检测示意图

FAST具体计算过程：

由图1所示，以p点为中心点，比较P点与以P点为圆心3个像素为半径的邻域内圆周上各像素灰度值的差值，若差值的绝对值大于某个阈值数εd，记录圆周上像素点的个数[11]。角点响应函数N为：

I（p）表示中心像素点的灰度值，I（i）表示该圆形邻域内第i个像素点的灰度值，取N0为阈值，N0定为12[12]。当N＞N0时，认为p点为角点[13]。

（2）求取特征点质心方向

ORB采用角点定向方法——灰度质心法来计算特征点方向，求取特征点的质心坐标，将特征点坐标设为起点，质心坐标设为终点，构造向量，该向量表示此处特征点的方向，其中特征点质心坐标由邻域矩求得[14]。邻域矩由式（2）定义。

其中，0阶矩（M00）为物体的质量；（M10，M01）代表1阶矩，f（x，y）为灰度值[15]，质心坐标如式（3）所示。

特征点与质心的夹角定义为FAST特征点的方向，由式（4）所示：

1.2特征点的描述

ORB算法利用BRIEF二进制码串的形式描述特征点，其核心思想是围绕关键点选择n个点对，把这n个点对组合起来作为描述子。n可为128，256，512等。这里，假设n=4，则4个点分别标记为：P1（x，y）、P2（x，y）、P3（x，y）、P4（x，y）、点P的τ准则如式（5）所示。

P点在x方向上的像素灰度值，记为p（x）。对点对进行操作。例如：

则最终的描述子为1011。

BRIEF方法生成的二进制描述子[16]如式（7）所示。

式（7）得到的描述子不具有方向性，通过求取描述子的质心方向，来获得描述子的方向[17-18]。

描述子向量由式（8）所示，式（8）生成了相关性较大的描述子向量点对，从而加大了匹配难度。解决方法是利用贪婪穷举思想对测试点对进行约束，减小点对之间的相关性[19]。贪婪穷举算法的思路是利用5×5的子窗口内像素灰度平均值来代替31×31窗口内的所有点对[20]，具体步骤如图2所示。

图2　ORB算子获取描述子流程图

1.3特征点匹配

由于生成的特征点描述子为二进制码串形式，因此使用汉明距离对特征点匹配较为简单。匹配点与非匹配点的汉明距离有着明显的不同，以此设定阈值，实现匹配。

2通过算法组合改进ORB

由于ORB算法中基于FAST算子检测到的特征点不具备尺度不变信息，因而在后续的特征点匹配中产生一定的误匹配；而SURF算法在提取特征点时，建立多尺度空间，保证了特征点的尺度不变性特征[22]。因此，本文基于SURF和ORB组合算法组合的思路展开研究，将组合算法定义为SUORB。

2.1尺度空间检测极值点

要在尺度空间中检测极值点，首先要建立具有多尺度空间的图像金字塔；SURF算法利用尺度逐渐递增的盒式滤波器与原图像卷积创建图像金字塔生成多尺度空间，该算法与SIFT算法在建立图像金字塔的过程有所不同[23-24]。

图3　SIFT与SURF建立金字塔对比图

SURF算法将金字塔分为多个组（Octave），每组包含若干层（Level），两层之间的最小尺度变化量由l0表示；每组中的若干层代表了一系列响应图，响应图是同一输入图像与逐渐递增的模板序列卷积的结果，盒式滤波的模板尺寸大约为最小尺度变化量的3倍左右[25]；若l0为3，则该盒式滤波模板尺寸为9×9；若l0为5，则该盒式滤波模板尺寸为15×15，若l0为7，则该盒式滤波模板尺寸为21×21；若l0为9，则该盒式滤波模板尺寸为27×27[26]。第二组滤波器的尺寸分别为5×15、27× 27、39×39、51×51，第三组滤波器的尺寸分别为27×27、51×51、75×75、99×99，如图4所示。

图4　递增的盒式滤波器

图5　滤波器尺寸和尺度关系示意图

2.2提取稳定的极值点

为了提取稳定的特征点，需要在某一尺度下提取极值点，SURF算法采用式（9）来判断极值点，其中Dxx、Dyy、Dxy分别代表高斯函数在（x，y）处的二阶偏导数；当det（Happrox）的值为正时，可以认定该点为极值点[27]。

其中ω为权重系数，根据经验一般取为ω=0.9接着利用非极大值抑制的方法，在3×3×3的立体邻域中比较26个像素点的灰度值；若某一个像素点的灰度值大于或小于剩余像素点的灰度值，认定该点为特征点[28]。

本文基于SURF算法建立图像金字塔，在尺度空间中检测极值点，并在不同的尺度下提取极值点，采用非极大值抑制的方法提取特征点；然后，利用1.1.2小节中介绍的ORB角点定向方法，为特征点定义质心方向，最后采用BRIEF二进制码串的形式对特征点进行描述。

3　实验结果分析

本文使用Visual Studio 2010进行编程，计算机系统是Windows7[Intel Core Duo CPU2.20 GHz，2G内存]。

3.1尺度不变性对比实验

为了验证本文提出的SUORB算法能够有效弥补ORB算法在尺度不变性方面的不足，采用尺度发生变化的一组测试图像进行实验对比，下图所示的是盘古图像的实验结果。图6（a）的匹配效果比较杂乱，原因是ORB算法缺少尺度不变性信息，从而导致误匹配程度较高。图6（b）的结果表明利用本文提出的基于算法组合的SUORB方法，得到了相对理想的效果。

（a）ORB算法匹配效果　　（b）SUORB算法匹配效果图6　ORB和SUROB算法匹配效果对比图

如表1所示，采集了6组实验数据，比较两种算法的匹配准确率。

表1　 ORB和SUORB算法的准确率

由表1可知，当图像尺度发生变化时，SUORB算法的匹配准确率（Ransac表示的是消除误匹配后匹配点个数与消除误匹配前匹配点个数的比值）高于ORB算法。

由图7可知，SUORB算法的匹配效果要优于ORB算法，证明了SUORB算法在尺度不变性方面的优势。

图7　两种算法准确度对比

3.2计算时间对比实验

为了验证SUORB算法的实用性，还需要针对各算法的匹配时间作对比实验。选取上述实验中10组测试图像，统计各算法的匹配时间，如表2所示。

表2　 ORB和SUORB算法的匹配时间

由表2可知，当ORB算法与SUORB算法的匹配点数相同时，SUORB平均匹配时间约为1286.9ms，比ORB的匹配时间长约387ms，可认为SUORB与ORB的运算速度很相近，表明本文提出的算法SUORB的快速优越性。

4　结语

本文结合SURF思想对ORB进行改进，提出的SUORB算法有效地解决了ORB不具备尺度不变性的缺陷，同时保留了ORB快速性的优点。通过实验分析得出以下结论:

（1）在图像尺度发生变化时，SUORB可以有效地、准确地进行特征点匹配，其平均匹配准确度相比于ORB有显著提高。

（2）SUORB平均匹配时间与ORB的运算速度很相近，表明了SUORB的快速优越性。

参考文献：

[1]张红源，陈自力.图像匹配经典算法及其改进方法研究[J].兵工自动化，2008，09:91-94.

[2]赵亮亮.一种基于左右视线的立体图像匹配算法[J].计算机仿真，2010，03:220-223.

[3]时磊，谢晓方，乔勇军.基于SURF算法的人脸跟踪技术研究[J].计算机仿真，2010，12:227-231.

[4]周军太，龙永红.一种改进SURF算法的图像配准[J].湖南工业大学学报，2011，02:95-99.

[5]任结，周余，于耀，都思丹，王自强.基于ORB自然特征的AR实时系统实现[J].计算机应用研究，2012，09:3594-3596.

[6]李小红，谢成明，贾易臻，张国富.基于ORB特征的快速目标检测算法[J].电子测量与仪器学报，2013，05:455-460.

[7]张云生，邹峥嵘.基于改进ORB算法的遥感图像自动配准方法[J].国土资源遥感，2013，03:20-24.

[8]刘铭.基于ORB算法的双目视觉测量与跟踪研究[D].哈尔滨工业大学，2014.

[9]谢成明.基于ORB特征的目标检测与跟踪的研究[D].合肥工业大学，2013.

[10]索春宝，杨东清，刘云鹏.多种角度比较SIFT、SURF、BRISK、ORB、FREAK算法[J].北京测绘，2014，04:23-26+22.

[11]张万华.基于区域SURF的图像匹配算法研究[D].华东理工大学，2011.

[12]石雅笋.改进的SURF图像配准算法研究[D].电子科技大学，2011.

[13]陈艺虾，孙权森，徐焕宇，耿蕾蕾. SURF算法和RANSAC算法相结合的遥感图像匹配方法[J].计算机科学与探索，2012，09:822-828.

[14]国飞飞.基于SURF算法的多幅图像三维模型重建方法研究[D].北京理工大学，2011.

[15]冯嘉. SIFT算法的研究和改进[D].吉林大学，2010.

[16]汪淑梦.基于改进的SIFT算法的图像配准技术的研究与实现[D].中国地质大学（北京），2013.

[17]李耀云.基于SIFT算法的双目立体视觉定位研究[D].太原理工大学，2013.

[18]张宁丽，马燕，李顺宝，徐衍鲁，程玮. FKPCA-SIFT算法在图像匹配中的应用[J].电视技术，2015，07:21-24+42.

[19]傅卫平，秦川，刘佳，杨世强，王雯.基于SIFT算法的图像目标匹配与定位[J].仪器仪表学报，2011，01:163-169.

[20]丁尤蓉，王敬东，邱玉娇，俞海波.基于自适应阈值的FAST特征点提取算法[J].指挥控制与仿真，2013，02:47-53.

[21]薛金龙.基于角点的图像特征提取与匹配算法研究[D].大连理工大学，2014.

[22]Roberts L G, Machine Perception Of Three-Dimensional Solids [C]. In Optical and Electroptical Information Processing, Cambridge: MIT Press, 1965:159-197

[23]Aloimonos J, Weiss I,Bandopadhay A. Active Vision [J]. International Journal Of Computer Vision,1988,1（4）:333-356.

[24]ZHANG WeiLong,LIU LeiBo,YIN ShouYi,ZHOU RenYan,CAI ShanShan,WEI ShaoJun. An Efficient VLSI Architecture Of Speeded-Up Robust Feature Extraction For High Resolution And High Frame Rate Video[J]. Science China（Information Sciences）,2013,07:136-149.

[25]QIN Yue-ming, CAO Zhi-guo,Wen Zhuo, YU Zheng-hong. Robust Key Point Descriptor For Multi-Spectral Image Matching[J]. Journal of Systems Engineering and Electronics,2014,04:681-687.

Research on Feature Points Matching Algorithm of Sequence Image

LIN Ting
（Key Laboratory of Optoelectronic Measurement Technology，Beijing Information Science & Technology University，Beijing 100192）

Abstract：Feature point matching is an important subject in computer vision field, for the lack of scale invariance characteristics of ORB algorithm, proposes an improved method based on the combination of SURF and ORB, which name is SUORB. Firstly，builds the scale spaces，in which the stable extreme points are detected in order to get the feature points with scale invariance information. Then, describes the feature points by the ORB descriptors with rotation invariance. Finally, Hamming distance is used to finish the final matching task. The experimental results show that SUORB has solved the deficiencies that ORB has little scale invariance. SUORB improves the matching accuracy, compared to ORB when images have scale changes. At the same time，the matching speeds of SUORB and ORB are almost the same.

Keywords：Feature Points; Matching; Multi Scale Space; the Combination of Algorithms

收稿日期：2016-01-12修稿日期：2016-02-26

作者简介：林汀（1990-），男，北京人，硕士研究生，研究方向为机器视觉

文章编号：1007-1423（2016）10-0028-05

DOI：10.3969/j.issn.1007-1423.2016.10.007

基金项目：国家自然科学基金项目（No.51475047）、教育部“长江学者与创新团队”发展计划资助项目（No.IRT1212）、北京市属高等学校创新团队建设提升计划项目（No.IDHT20130518）