一种改进的基于SIFT特征的快速匹配算法

唐红梅，张 恒，高金雍，王 霞，韩力英

(河北工业大学，天津 300401)

责任编辑:时 雯

图像匹配就是通过对图像内容、特征、结构、纹理及灰度等对应关系、相似性和一致性进行分析，寻求相同图像目标的方法。目前，图像匹配技术被广泛应用于医学、生物、军事、遥感和航空航天等领域，是图像处理应用中不可或缺的技术。

基于SIFT(Scale Invariant Feature Transform)的匹配算法［1］是一种稳定的特征匹配算法。SIFT特征是图像的局部特征，对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性，具有良好的独特性、多量性及可扩展性。该算法在同类特征匹配算法中速度较快，但对于某些实时性要求较高的场合(如汽车匹配导航)，则无法满足要求。

由于SIFT匹配算法复杂度高，尤其生成的特征向量是128维，使得算法效率受到影响。针对效率上的不足，不少国内外研究学者做了不同的改进，这些改进主要集中在以下几个方面:在对SIFT描述简化上，如Mikolajczyk提出的GLOH(Gradient Location and Orientation Histogram)［2］及刘力等提出的 SSIFT 算法［3］;在降低 SIFT 向量维数上，如 Ke提出的 PCA－SIFT［4］，马莉、韩燮将 PCASIFT技术应用在图像匹配中［5］，赵启兵等提出为同心圆环划分特征点邻域的改进算法［6］;在尺度空间简化构造上，如张羽等提出的基于DoM空间的SIFT改进算法［7］，吕冀等基于Zoser金字塔的改进算法［8］;在与其他算法结合上，如郑永斌等的SIFT和旋转不变LBP相结合的匹配算法［9］。然而这些算法在提高算法效率的同时，造成了算法精度和鲁棒性的下降。

本文提出了一种改进的基于SIFT特征的快速匹配算法，改进算法首先使用D2OG算子［10］的过零检测来生成特征向量，并针对此时可能导致匹配精度下降的问题，使用改进的RANSAC(Random Sample Consensus)算法对匹配点对进行二次消除错配。改进算法用过零点检测极值点代替经典算法的局部极值点检测，在保证了精度的同时，提高了SIFT匹配算法的实时性。

1 基于SIFT的匹配算法原理

SIFT匹配算法主要有3个步骤:特征点的检测;特征向量的生成;特征向量的匹配。

1.1 特征点的检测

高斯核被证明为唯一的可以用来产生尺度空间的线性卷积核。特征点检测是在高斯差分尺度空间DOG(Difference of Gaussian)上进行的，DOG是由不同尺度高斯核与图像卷积构造图像的尺度空间函数相邻层相减得到，即

如图1所示，为了得到局部极值点，每组除底层和顶层的图像，其他同组图像的每个像素点都要进行检测，具体做法是每个待检测像素点跟同层相邻的8个像素点及其上一层和下一层相邻的各9个像素点总共26个像素点相比较，若其比较结果都大于或都小于这26个像素点，则该点被看作一个空间局部极值点，并记录该点所在的位置和尺度。对检测到的初始极值点进行三维二次函数曲线拟合以及一个2×2的Hessian矩阵来去除低对比度以及边缘响应点，以精确极值点的位置和尺度。利用邻域像素梯度方向分布统计特性作为每一个特征点指定方向参数，以确保算子的旋转不变性。至此提取的特征点具有位置、尺度、方向三个参数，且具有尺度和旋转不变性。

图1 DOG金字塔的构造及局部极值点检测

1.2 特征向量的生成

用特征描述符对特征点进行描述，增加特征点的稳定性与独特性，使其对亮度、视角等变化保持不变，最终形成128维的特征向量。

1.3 特征向量的匹配

算法采用优先k－d树近似的BBF(Best Bin First)搜索算法快速搜索每个特征点的最近邻与次近邻，并计算它们的比值进行匹配，最后利用RANSAC算法消除错配。

2 改进的SIFT特征匹配算法

在特征点检测的过程中，LOG与DOG的构造占据80%左右的时间，简化金字塔结构、简化特征点检测方法，可以有效减少检测时间，提高算法运行速度。文献［10］结合几何学理论，提出了基于D2OG的特征点检测算子。然而该算法在提高速度的同时，匹配精度有所下降，为此本文先用D2OG进行极值点检测，然后采用改进的RANSAC算法来确保匹配的精度。这样在保证算法精度的同时达到了提高算法速度的目的。

2.1 基于D2OG的过零检测

2.1.1 D2OG过零检测的理论依据

根据平面几何学理论，原函数的极值点就是该函数一阶导数等于零的点。由此可见，经典算法在DOG金字塔中检测的局部极值点对应于DOG函数的一阶导数的过零点。

对DOG进行一次差分运算得到D2OG函数，即

式中，D2(x，y，σ)为高斯二阶差分函数。

由于

则

且 kσ － σ ≠0 ，故可知:D2(x，y，σ)=0⇔=0可见，D2OG函数的过零点就是DOG函数一阶导数为零的点，也就是DOG的局部极值点。

2.1.2 D2OG 特征检测过程

D2OG金字塔构建如图2所示。

图2 D2OG金字塔构造过程

同DOG构建相同，每一组的DOG相邻层相减得到一层D2OG图像，该层的尺度为DOG层中减数的尺度。可见，D2OG金字塔拥有相同的组数，但每组层数比DOG少一层。

在D2OG每层中检测零点时需要设一个阈值T，对每一层的绝对值与T进行比较，小于等于T的像素点作为特征点，记录该点的信息(x，y，σ)。阈值T的选择是关键，过大或过小都可能会影响匹配的精度，还会带来程序运行时间的增加。考虑算法精度和速度两个因素，T在［200，500］内可实现较好的折中。精确定位时，为了获得亚像素级精度，需要将D2OG中检测到的特征点映射回DOG空间中。

采用改进算法构造金字塔时，每组可减少一层高斯滤波图像，构建几组就可以减少几层，前面提到，在特征检测环节，金字塔的构造占据80%的时间，因此改进算法简化了金字塔的构造。另外，D2OG算子的二维平面检测在算法复杂度上也低于经典算法的三维空间局部检测。因此，理论上改进算法实时性高于经典算法。

2.2 改进的RANSAC算法

当提供的特征点数目较少时，RANSAC性能可能有所降低。由于受本文D2OG中阈值T的选取影响，特征点数目少于经典算法从而生成的匹配点对数目减少，而匹配点对数目的减少可能导致匹配中存在误匹配对，导致的匹配精度降低。

针对以上问题，采用改进的RANSAC算法进行特征点对提纯，消除误匹配对，从而提高匹配精度。改进算法的具体步骤如下:

1)在n个数据点集中随机抽取4对特征点对，并将其设为初始内点集合，计算出变换矩阵H。将集合外的n－4个点看作外点，依次计算经过H变换后到对应匹配点的距离，小于阈值距离，则将当前点纳入内点集合。记录在此H下的内点数量。

2)重复步骤1)操作k次，选择具有内点数量最多的集合并将该集合的内点作为估计的初始值，再使用RANSAC算法将新求出的内点集合与原来的内点集合并集为新的内点集合。

3)选取两次内点并集后内点数量最多的集合作为最佳集合，将该集合下的变换矩阵作为最佳估计的变换矩阵。

改进的RANSAC算法对提取的匹配点进一步检验并消除误匹配点对，以消耗小部分时间为代价，保证了匹配的精度。

下文通过实验对经典算法与改进算法的性能进行比较，以验证上述思路。

3 实验结果与分析

在进行实验之前，为了表述方便，将经典算法称为SIFT，将基于D2OG检测算子的 SIFT匹配算法称为DSIFT，并将继续加入改进RANSAC算法后的改进算法称为DRSIFT。所有的程序实验都是以VC++6.0为平台，在操作系统为Windows7，主频为Inter(R)Core(TM)2 Duo CPU T6600 2.2 GHz，内存为4 Gbyte的PC机上完成。实验所用图像均由笔者使用手机数码相机实际拍摄。

3.1 程序流程图

改进算法程序流程图如图3所示。

图3 改进算法流程图

3.2 基于D2OG算子的阈值选取

基于D2OG检测算子在过零点检测过程中引入阈值T，阈值大小的选取是检测的关键。阈值过大会引入错误的特征点并增加算法运行时间;阈值过小，会漏掉部分正确的特征点，影响匹配精度。下面以一张大小为371×352的图像为实验对象，为了选取合适的阈值，实验以经典算法作对比，分别在T=200，T=400，T=500时统计极值点数及运行时间，如图4所示。

图4 不同阈值下的DRSIFT与SIFT极值点检测对比

实验数据如表1所示，分析表1数据可以发现:阈值T的选取决定了极值点的数目和运行时间。阈值为500时，引入错误特征点，同时增加运行时间;阈值为200时，检测的极值点数目很少，特征点是从极值点中得到的，因此，不能提供足够的极值点会影响后期的匹配工作，影响匹配精度。由此可见，阈值选取由小到大，匹配精度是先升后降的过程。本文在综合考虑算法的精度和速度两个因素后，认为T=400时可实现较好的折中。

表1 DRSIFT阈值T的选取及与经典算法的比较

3.3 改进算法的综合性能比较

为了检验改进算法的匹配性能，本文将SIFT，DSIFT和DRSIFT进行比较。实验使用的图片包括不同尺度缩放图片、不同的旋转图片、不同视角变化的图片以及添加了噪声和光照等复杂变化的图片。为了较全面地验证算法的性能，实验以特征点数、特征点检测时间、匹配点对数、错配点对数、正确匹配率以及运行总时间6个方面对SIFT，DSIFT和DRSIFT进行比较。其中，特征点数是指基准图像的特征点数目;特征点检测时间是基准图像特征点检测所消耗的时间;匹配点对数是SIFT与DSIFT经过RANSAC算法以及DRSIFT经过改进RANSAC算法后保留的匹配点对数。

实验匹配效果如图5～8，其中线段端点分别是基准图像与待匹配图像对应的匹配点。

实验数据如表2所示，算法中的参数均为Lowe原文中推荐的参数。DISFT与DRSIFT选取的阈值为T=400。

分析实验数据可以发现:在不同几何变换或光学畸变下，DRSIFT算法特征点检测时间要低于SIFT算法，可见，D2OG算子实时性优于DOG算子。DRSIFT算法总运行时间低于SIFT算法，可见DRSIFT算法复杂度低于SIFT算法，速度更快。DRSIFT算法正确匹配率与SIFT算法相当，DRSIFT算法匹配点对数少于SIFT算法，错误匹配点对数少于SIFT算法，可见采用改进的RANSAC算法在进行二次估计时消除了部分误匹配。DRSIFT算法与DSIFT算法总运行时间相差不大，可见改进RANSAC算法运行时间与初始匹配点对数有关并且时间消耗很少，以牺牲小部分时间为代价，提高了匹配精度。

表2 SIFT，DSIFT和DRSIFT性能比较

由此可以得出DRSIFT算法的优点在于:在基本保持高精度、几何形变、光照等不变性的基础上，降低算法的复杂度和时间代价，提高了算法的运行速度。

与SIFT经典算法相比，DRSIFT算法的缺点在于:尽管引入改进RANSAC算法提高匹配精度，但当DRSIFT算法在图像轮廓边界信息较少或存在复杂畸变时，匹配精度与经典算法相比仍然有所下降。

4 结论

本文提出了一种改进的基于SIFT特征的快速匹配算法。改进算法通过简化金字塔结构、降低特征检测算子复杂度，二次筛选匹配点对，在保证算法高精度的同时提高了算法的速度。改进算法适用于图像信息较丰富且对实时性有一定要求的场合。改进算法的缺点在于匹配点对数目相对较少，限制了算法处理的图像类型(如边缘轮廓较少的图像)。因此，如何提高匹配点对数目以及在匹配点对数目较少的情况下如何进行更准确的参数估计是需要进一步学习研究的问题。

［1］LOWE D G.Distinctive image from scale－invariant keypoint［J］.International Journal of Omputer Vision，2004，60(2):20.

［2］MIKOLAJCZYK K，SCHMID C.A performance evaluation of local descriptors［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，2005，27(10):1615－1630.

［3］刘力，彭复员，赵坤，等.采用简化SIFT算法实现快速推向匹配［J］.红外与激光工程，2008，37(1):186－189.

［4］KE Y ，SUKTHANKAR R.PCA－sift:A more distinctive representation for local image descriptors［C］//Proc.CVRP 2004.［S.l.］:IEEE Press，2004:506－513.

［5］马莉，韩燮.主成分分析法(PCA)在SIFT匹配算法中的应用［J］.电视技术，2012，36(1):129－132.

［6］赵启兵，王养柱，胡永浩.基于改进SIFT算法的无人机遥感影像匹配［J］.光电与控制，2012，19(3):36－39.

［7］张羽，朱丹，王玉良.一种改进的快速SIFT特征匹配算法［J］.微计算机信息，2008，24(33):226－228.

［8］吕冀，高洪民，汪渤，等.图像制导的目标匹配算法与系统设计［J］.弹箭与制导学报，2009，29(5):43－45.

［9］郑永斌，黄新生，丰松江.SIFT和旋转不变LBP相结合的图像匹配算法［J］.计算机辅助设计与图形学学报，2010，22(2):286－292.

［10］曹娟，李兴玮，林伟廷，等.SIFT特征匹配算法改进研究［J］.系统仿真学学报，2010，22(11):2760－2763