SURF和RANSAC的特征图像匹配

王卫兵　白小玲　徐倩

摘要：针对图像匹配过程中存在匹配运行时间长、匹配正确率低的问题，采用随机采样一致性（random sample consensus， RANSAC）算法优化加速鲁棒特征（speed up robust features， SURF）的方法，提出一种适应性强的优化匹配算法。首先使用SURF算子进行特征检测和特征描述，再使用邻近算法对特征点进行预匹配，最后使用随机采样一致性（RANSAC）算法优化匹配结果。在相同的实验环境中通过对尺度不变特征变换（scale invariant feature transform， SIFT）算法、SURF算法和提出的优化算法进行比较，优化算法较SIFT算法和SURF算法分别减少匹配点对数38对和18对，剔除了误匹配点，提高了匹配正确率并减少了算法的运行时间。

关键词：特征提取；加速鲁棒特征；随机采样一致性

DOI：10.15938/j.jhust.2018.01.021

中图分类号： TP391.4

文献标志码： A

文章编号： 1007-2683（2018）01-0117-05

Abstract：Aiming at the problem of long running time and low matching accuracy in image matching process， random sample consensus （RANSAC） algorithm is used to optimize the speedup of robust features （SURF） optimization algorithm. As a result， an adaptable algorithm is proposed to optimize image matching. Firstly， the SURF operator is used for feature detection and feature description. Then the neighbor algorithm is used to prematch the feature points. Finally， the random sampling consistency （RANSAC） algorithm is used to optimize the matching results. The scale invariant feature transform （SIFT） algorithm， SURF algorithm， and the proposed optimization algorithm are compared in the same experimental environment. Compared with the SIFT algorithm and the SURF algorithm， the optimization algorithm reduces the number of matching point pairs to 38 and 18 pairs， excluding mismatched points， improving the matching accuracy， and reducing the running time of the algorithm.

Keywords：feature matching；speed up robust features；random sample consensus

0引言

特征点检测、特征描述和特征匹配是基于局部特征点的图像匹配技术的三个主要组成部分，广泛地应用在医疗、图像检索、目标识别和增强现实技术中[1-5]。

目前，研究人员提出了许多不同的特征点检测、描述算法，但由于图像成像时往往会受到光照、模糊、角度等各种因素的影响，导致匹配速度慢、匹配精度差等问题。

DavidLowe在1999年发表了SIFT（scale invariant feature transform）算法[6-7]，并在2004年对其进行完善。SIFT算法在空间尺度中寻找极值点，通过直方图确定主方向，使其具有旋转不变形，同时对光照、缩放等变换也有一定的鲁棒性。但由于SIFT算法在检测和描述过程中使用的算法复杂度高，使得算法的匹配速度慢，达不到实时的要求。在2006年，Bay和Ess等人对SIFT算子进行改进，提出了加速鲁棒特征—SURF（Speed Up Robust Features）算法[8-10]，该算法通过H矩阵判别式的值来获得极值点，并在不同尺度上计算近似Harr小波特征，即使是在多幅图片下也可以具有良好的稳定性。索春宝等人针对现有的几种常用特征检测和描述算子进行性能对比，实验结果表明，SURF算法是性能最为鲁棒的局部特征算法[11-13]。对比于SIFT算法，该算法的描述符的维度下降了一倍，在二阶微分模板的构建过程中得以简化，使得程序的运行时间被缩短[14]。

本文通过SURF算法进行图像的检测、描述，使用KNN（KNearest Neighbor）[15]算法进行预匹配，在匹配过程中出现的错误匹配使用Ransac算法进行优化，更准确的完成图像匹配的整个过程。Ransac算法可以做到在匹配过程中降低不可靠的匹配点对数，确保匹配的正确率。

1.2SURF尺度空间及特征向量提取

在計算机视觉领域中，尺度空间需要对输入图像函数反复与高斯函数核进行卷积并反复对其进行二次抽样，这种方法被称为一个图像金字塔。在SIFT算法的特征检测过程中，构建的金字塔中是有很多层的，并且在每个层中会有几张尺度不同的图片，下一组的图像是由通过将上一组图像按照隔点降采样得到。这样就使得每层图像都要依赖于前一层的图像，因此，在不断的隔点采样过程中会使得运算量比较大，这样在特征点的检测过程中也就需要花费更长的时间。而在SURF算法中是保持图像的大小是一直不变的，SURF的不同层的图像是通过改变高斯模糊的尺寸得到的，在尺度空间中可以实现多层图像同时被处理，不需要对图像进行二次抽样，减少了特征点检测过程中的繁琐过程，加快了检测的速度。SIFT算法的金字塔结构变化的是图像的尺寸，通过不断的隔点降采样实现整个金字塔结构，并且为了消除噪音，还需要反复使用高斯函数对子层进行平滑处理，而SURF算法只是改变滤波器的大小，却可以使原始图像保持不变。其金字塔图像如图2所示。

SIFT算子的旋转不变性是特征点的重要特性，SIFT通过统计梯度直方图来确定特征点的主方向，在主方向确定后，依据其旋转就可以确保旋转不变性。梯度直方图是按照每10度一个柱，这样就可以统计36个柱中的直方图最大值来作为特征点的主方向。在SURF算法中，特征点的主方向确定是以特征点为圆心、6s（s为特征点的尺度）为半径的邻域内构建的一个扇形面，得到x和y方向的Harris小波响应，将不同的高斯权重系数赋给这些响应值，这样越靠近特征点，响应的贡献也就越大；然后以60°为基准进行统计扇形内所有的点的水平方向harrx小波特征和垂直方向的harry小波特征的总和，Harris小波的尺寸变为4s，这样扇形得到了一个值。然后60°扇形以一定间隔旋转，最后扇形方向最大值就是作为特征点的主方向。

确定了特征点的主方向后，就可以进行特征描述符的提取。在SIFT算法中计算关键点周围16×16的窗口中每一个像素的梯度，在每个4×4的1/16象限中，直方图有8个方向区间，将加权梯度值加到其中的一个方向区间上，计算出一个梯度方向直方图。这样就可以最后得到4×4×8=128维的向量作为该点的SIFT描述子。而在SURF中，是在特征点周围取一个边长为20s（s是所检测到该特征点所在的尺度）的正方形框。该框的方向作为检测出的主方向，正方框被分成为16个子区域，去统计每个区域25个像素的水平方向和垂直方向的Harris小波特征，分别记为dx和dy，再将权重系数通过高斯窗口函数赋给响应值，得到一个四维的矢量：V=∑dx，∑dx，∑dy，∑dy，这样就可以得到SURF的描述维数是4×4×4=64维。最后，对向量进行归一化处理，就进一步去除了光照的影响，得到特征描述符，如图3所示。

2特征匹配

根据上文，采用Hessian矩阵提取出适量特征点并得到其主方向，再通过Harris小波特征得到SURF的64维描述子。在匹配过程中，首先采用FLANN（Fast Library for Approximate Nearest Neighbors）算法，对特征点对进行预匹配，匹配过程中出现的误匹配再通过Ransac算法进行剔除。

2.1特征点对预匹配

在OpenCv开源库中，有两种二维的特征点匹配常见的办法，分别是Brute Force匹配和FLANN匹配，而本文采用的是FLANN匹配[17-18]。它们分别对应BFMatcher和FlannBasedMatcher。之所以会选择FLANN匹配是因为前者总是尝试所有可能的匹配，从而使得它总能找到最佳匹配，但是会使得算法运行时间长；而后者是一种近似法，算法更快。同时为了进行高效匹配，本文还采用邻近算法（KNN），选取与当前点距离最小的n个点，本文中经测试选定n值为2效果佳。

2.2RANSAC匹配

RANSAC算法[19-20] 最早由Fischler和Bolles于1981年提出，是一种鲁棒的参数估计方法。该算法的数学模型参数估计是通过迭代方式完成的，即使在参数中会有包含“局外点”的数据集。本文中的“局外点”可能是在检测、描述和预匹配过程中所产生的错误匹配或者误差比较大的匹配所产生的。该算法可以接受在构建金字塔过程中产生的图像噪音，能较好的剔除误匹配点，SURF匹配对通过RANSAC几何校验后可以有效滤除错误匹配，从而使得集合RANSAC的SURF性能更加优良，应用更加广泛[21-22]。但它也有缺点，该算法是一种不确定的算法，是否可以得到合理的结果是未知数，所以为了提高得到合理结果的概率就需要提高迭代次数。该算法在计算参数的迭代次数时是没有上限的，因为如果设置迭代次数的上限，可能会导致得到的结果不是最优的结果，还可能得到错误的结果。在匹配过程中，迭代次数应按照实际情况进行选择。为进一步提高RANSAC的准确度，可以对RANSAC算法进行简化。在简化的过程中会减少匹配点数，提高匹配的正确率，本文采用的是双向匹配。

匹配的过程是首先要分别读入两幅图像1、2，对两幅图像分别进行特征点检测，得到特征点数组points1和points2。然后对每个points1中的点j在points2中找出对应的点k，并在points2中的每个点m在points1中找对应点n。判断是否匹配的依据是在points1中的点j，如果在points2中的匹配点是k，并且points2中点k在points1中的匹配点也是j，那么判断为匹配成功，这样匹配的点对数会有所减少，但是匹配的准确率会得到提高。

3仿真实验

本文的算法对比结果均在CPU为英特尔i53470，3.20GHz，内存为4.00GB的Lenovo 64位工作站上运行得到。操作系统为Windows7，开发工具为VS2012 IDE，并采用Opencv2.4.10图像处理库。

本文使用两组匹配图像，图4是老鼠图形测试图像，该图像对存在一定的缩放变换，图5是建筑物图形的测试图像，该图像对存在一定的视角变换。文中通过对初始图像作尺度、旋转变化来观察图像在SIFT、SURF和本文算法中的图像匹配结果。下面列出2组不同图像的匹配结果。

本文实验是在相同环境中对SIFT算法、SURF算法和本文所提出的算法從匹配的准确性和运行时间两方面进行比较。从表一中可以看出：对同一对测试图像来说，SIFT检测到的特征点总点数要多于SURF算法和本文优化算法的特征点数，其中本文算法检测到的特征点数最少；SIFT算法的运行时间也要多于SURF算法和本文算法，其中本文算法的运行时间最短。从表1中得到的结果可以反映出本文的优化算法从匹配正确性和运行时间两方面的性能更优。

图4和图5分别是老鼠和建筑物的图像匹配结果，依次为SIFT算法、SURF算法和本文算法的匹配结果。从图中可以看出：图4和图5中，本文算法较SIFT算法去除了不显著的匹配点39个，较SURF算法去除了不显著的匹配点18个，减少匹配点的数目，匹配率较SIFT算法和SURF算法分别提高了14.2%和6.4%。从表1中数据可以看出，本文算法的匹配点对数更少、匹配正确率更高并且匹配的时间有所减少。

4结论

本文首先用SURF算法进行特征检测和描述，再使用KNN算法进行预匹配，在匹配过程中产生的误匹配通过简化的Ransac算法进行剔除。通过对图像进行旋转、缩放等图像变化下的实验数据分析，本文算法要优于SIFT算法和SURF算法。未来的研究工作将在匹配效率上进行改进，图像匹配是增强现实（Augmented Reality，简称AR）技术中的一个重要环节，希望今后的工作能实现增强现实过程中更快更稳定的特征匹配。

参 考 文 献：

[1]常青，张斌，邵金玲.基于SIFT和RANSAC的特征图像匹配方法[J].华东理工大学学报：自然科学版，2012，38（6）：747-751.

[2]邱子鉴.基于改进随机蕨的增强现实跟踪注册算法的设计与实现[D].哈尔滨：哈尔滨理工大学学报，2014：8-11.

[3]邢春.基于多特征融合图像检索系统设计与实现[D].哈尔滨理工大学：哈尔滨理工大学学报，2012：13-18.

[4]王邦国.基于SIFT特征点精确匹配的图像拼接技术研究[J].大连大学学报，2015，36（3）：23-26.

[5]曹健，陈红倩，毛典辉，等.基于局部特征的图像目标三个i别问题综述[J].中南大学学报，2013，44（2）：259-262.

[6]LOWE. DAVID G.Distinctive Image Features from Scaleinvariant Key Points[J]. International Journal of Computer Vision，2004，14（5）：91-110.

[7]LOWE. DAVID G.Object Recognition from Local ScaleInvariant Features[J].Computer Science Department University of Columbia，2004，10（6）：2-8.

[8]BAY Herbert. SURF： Speeded up Robust Features[J]. European Conference on Computer Vision（ECCV），2006，17（7）：404-417.

[9]YAN Yuanhui，XIA Haiying，HUANG Siqi，etc.An Improve Matching Algorithm for Feature Points Matching[J].College of electronic engineering，2014，15（6）：241-246.

[10]蔡佳，黃攀峰.基于改进SURF和PKLT算法的特征点实时跟踪方法研究[J].航空学报，2013，34（5）：1205-1211.

[11]索春宝，杨东清，刘云鹏.多种角度比较SIFT、SURF、BRISK、ORB、FREAK算法[J].北京测绘，2014，6（4）：22-26.

[12]蒋贤明，宋树祥，王冬旭.局部图像特征提取算法的性能比较[J].广西物理，2014，35（1）：16-20.

[13]王灿进，孙涛，陈娟.基于FREAK特征的快速景象匹配[J].电子测量与仪器学报，2015，8（29）：205-214.

[14]朱俊.基于几何特征配准的图像鲁棒拼接算法[J].南京理工大学学报，2014，7（9）：31-40.

[15]蔡佳，黄攀峰.基于改进SURF和PKLT算法的特征跟踪方法研究[J].航空学报，2013，32（6）：1205-1213.

[16]潘丽芳，杨炳儒.基于簇的K最近邻（KNN）分类算法研究[J].计算机工程与设计，2009，30（18）：4260：4262.

[17]冯亦东，孙跃.基于SURF特征提取和FLANN搜索的图像匹配算法[J].图形图像学报，2015，25（7）：651-654.

[18]赵璐璐，耿国华，李康，等.基于SURF和快速近似最近领搜索的图像匹配算法[J].计算机应用研究，2013，30（3）：922-925.

[19]FISCHER MA， BOLLS RC. Random Sample Consensus： A Paradigm for Model Fitting Matching with Applications to Image Analysis and Automated Cartography[J]. ACM Graphics and Image Processing，1981，25（6）：381-395.

[20]赵烨，蒋建国，洪日昌.基于RANSAC的SIFT匹配优化[J].光电工程，2014，16（8）：59-67.

[21]陈艺虾，孙权森，徐焕宇，等. SURF算法和RANSAC算法相结合的遥感图像匹配方法[J].南京理工大学学报，2012，14（8）：823-827.

[22]谷宗运，谭红春，殷云霞，等.基于SURF和改进的RANSAC算法的医学图像配准[J].医学影像工程学学报，2014，19（6）：471-475.

（编辑：王萍）