一种改进的SIFT图像匹配算法

林强

（四川大学计算机学院，成都 610065）

一种改进的SIFT图像匹配算法

林强

（四川大学计算机学院，成都 610065）

针对尺度不变特征变换（SIFT）算法的匹配结果存在错误匹配点以及冗余匹配点的问题，提出一种改进的图像匹配算法。该算法将SIFT算子的尺度空间极值点作为初始特征点，用Harris角点检测算子对初始特征点进行筛选，选择高对比度的点作为最终特征点。接着设置合适的欧氏距离阈值进行粗匹配。由于SIFT得到的匹配点集存在冗余与错误匹配，改进的算法在匹配后再进行一次逆向匹配，最后，利用RANSAC算法进行纠错，得到正确的匹配特征点对。实验结果表明，在图像有旋转、平移、光照等情况下，该算法稳定、可靠。

图像匹配；SIFT特征；随机抽样一致性；欧氏距离

0 引言

图像匹配是解决很多计算机视觉问题的基础，包括目标或场景识别，目标跟踪等。图像匹配算法一般分为两种：一种是基于图像的某些区域的匹配算法，另一种则是基于图像的局部特征进行匹配的算法。

图像匹配技术发展到今天，已经有比较多的经典图像匹配算法，例如SIFT[1～3]、SURF[4]、PCA-SIFT[5]、Harris[6]、MSER[7]，等等。在众多经典的图像匹配算法中，SIFT在基于图像局部特征的匹配算法中具有里程碑的意义，它是由D.G.Lowe于1999年提出，并于2004总结发表在期刊论文上。SIFT特征点是被使用最广泛的兴趣特征点之一，它已经被成功应用到各种计算机视觉算法，中例如目标检测、目标跟踪以及大规模的图像检索中。尽管SIFT描述符对于尺度与旋转具有高度的鲁棒性，但是SIFT算法存在较高的时间复杂度，对时间要求很高的实时应用来说它有很多需要改进的地方。对于SIFT算法存在的问题，已经有很多改进的算法，例如前面提到的PCA-SIFT，还有RIT-SIFT[8]、文献[9]以及文献[10]提出的改进算法等。本文针对SIFT算法的时间复杂度问题，提出了一种改进算法。改进的SIFT算法针对SIFT算法的时间复杂度与精确度分别使用了Harris算法与RANSAC算法。实验表明，该算法相对于SIFT算法在速度和精确度上有了一定的提升。

1 SIFT算法简介

文献[1～2]中已经描述过，SIFT算法计算步骤包括四步。

1.1 尺度空间极值

为一幅图像建立高斯金字塔，在不同的尺度空间中检测极值点。尺度空间函数等于可变尺度的高斯函数G（x，y，σ）与输入图像I（x，y）的卷积，公式如下：

其中：

通过建立高斯金字塔来求取特征点的位置，高斯金字塔是通过对输入图像进行降采样形成的图像组。为了有效获取稳定的特征点位置，采用差分高斯金字塔DoG，即：

1.2 去除不可靠的特征点

在上面建立的高斯差分金字塔中检测极值，检测的范围是差分高斯金字塔中所有的图像（最上面的图像与最下面的图像除外），检测到的极值是利用金字塔中检测范围内的图像的所有像素点与相邻的26个点做比较，包括上下层图像各9个点以及自身图像的8个点。因为尺度空间极值检测产生太多的候选特征点，其中一些是不稳定的。通过拟合三维二次函数去除低对比度的特征点以及利用Hessian矩阵去除不稳定的边缘点。

1.3 特征点方向分配

每个特征点都被分配一个或多个方向基于梯度直方图。

上式（4）、（5）分别为（x，y）处梯度的模值和方向计算公式。每个特征点被指定一个主方向和一个辅方向。

1.4 生成特征描述符

局部图像梯度是在每个特征点区域已经选择好的尺度下检测的。一旦一个特征点方向被选好，特征描述符是由特征点周围的16×16邻域内计算的，将邻域分成4×4的子块，然后对每个子像素块计算8个方向的直方图。这样每个特征点的特征向量是4×4×8=128维。图1是特征向量的生成过程[11]。

图1 由关键点邻域梯度信息生成特征向量的过程

2 改进的SIFT匹配算法

2.1 Harris角点检测算法

Harris角点检测算法是基于信号特征点提取的，它使窗口w（通常是矩形区域）无穷小位移向任何方向移动，其中灰度的变化定义如下[12]：

其中X和Y是一个有序的灰度层次的梯度，它们能够通过图像的卷积得到如下式：

为了提高抗噪声的能力，选择高斯窗口在图像中平滑，

其中：

E接近偏自相关函数，M用来描述自相关函数形成的起源。让M矩阵的特征值通过λ1和λ2来定义。λ1与λ2是自相关函数的曲率，它们构成自旋变量M。因此，可以通过λ1与λ2的值决定平面区域、角点以及边缘，有以下三种情况[13]：

（1）如果两个曲率都太小，则表明自相关函数是平的。

（2）如果一个曲率比较大，另一个曲率很小，则表明E在偏自相关函数是类似边缘的时候有一个小小的改变。

（3）如果两个曲率都很大，则表明偏自相关函数有一个峰值，并且E沿着任何方向有一个很大的改变，这里就是角点。

Harris特征点定义为局部区域的最大值：

其中Tr2（M）矩阵的迹，Det（M）是矩阵的行列式的值，k取值在0.04～0.06之间得到的结果比较好。

2.2 RANSANC算法简介

RANSAC算法是两个阶段的迭代算法，包括假设生成与假设评估。

假设生成：首先，RANSAC算法随机选取数据集，然后从样本集中估计一个参数。如果给定的模型是一条直线ax+by+c=0（a2+b2=1），M=［a，b，c］T是被评估的参数，这是一个正确的假设。RANSAC在迭代过程中生成一系列的假设。

RANSAC不是像最小二乘法以及支持向量机这样的算法一样是一种递归技术[14]。RANSAC使用的是样本数据的一部分而不是全部，如果选择的数据都是内点，这些数据将会使假设进一步接近真实。这个假设需要使用足够的迭代次数来以一个失败概率α选取样本集中所有的点至少一次，公式：

其中m是用来生成假设的数据的数量，γ是选取内点的概率，即整个数据内点的比例。然而实际上内点比例γ是不知道的，由使用者根据需要决定。

RANSAC将一个在连续域内的估计问题转换成在一个离散域内的选择问题。例如，用200个点求一条直线，使用最小二乘法每次需要两个点，200个点共有19900可供选择的点对。现在的问题是在巨大数量的点对中选择合适的点对。

假设评估：RANSAC最终选择由大部分候选的内点支持的最可能的假设。被认为是内点候选的规则是，在一个假设中点的误差在一个预先定义的阈值范围内。

RANSAC解决选择候选内点问题作为一个优化问题，用公式表示如下：

其中D是样本数据，Loss是一个损失函数，Err是一个误差函数，例如几何距离。最小二乘法的损失函数表示为Loss（e）=e2。相比之下，RANSAC使用

其中c是阈值。RANSAC在大的误差条件下有恒定的损失，而最小二乘法有巨大误差。外点干扰最小二乘法因为它们通常有巨大的误差。

2.3 改进的SIFT算法

在SIFT算法步骤中，当精确定位特征点位置获得初步特征点后，用Harris角点检测算子对初始特征点进行筛选。选择具有高对比度的点作为最终的特征点。接着利用所求的特征点集，设置合适的SIFT描述符向量之间的欧氏距离最小值与次小值比值的阈值，对特征点集进行粗匹配。由于SIFT匹配得到的匹配点集存在大量的冗余与错误匹配，改进的算法在SIFT算法匹配之上对两幅图像进行一次逆向匹配，即若测试图像中存在一个点对应原始图像的多个点，求出原始图像中的每个点到测试图像中的这点的距离，选择距离最小的两个点作为匹配点，去除其余原始图像的特征点。最后，利用随机抽样一致性（RANSAC）算法进行处理，选择正确的匹配特征点对。因为在提取特征点的时候减少了特征点的数量，而且在SIFT匹配完后进一步对匹配后的特征点对做了一次RANSAC算法处理，因此改进的算法不仅在速度上快于SIFT算法，而且在精度上高于SIFT算法。

3 实验结果

为了检测本文提出的改进的SIFT算法在速度和精度上都高于原始的SIFT算法。实验采用了三组图像，分别用于测试改进的算法中旋转、缩放，以及光照变化的不变性。实验使用不同的场景不同的图像进行测试，以避免随机性带来的误差。

图1 用于进行实验的组图

图2 SIFT与改进SIFT在图像旋转后的匹配结果

图3 SIFT与改进SIFT在图像缩放后的匹配结果

图4 SIFT与改进SIFT在光照变化后的匹配的结果

表1 SIFT与改进的SIFT的实验结果对比

表2 SIFT与改进SIFT运行的时间对比

实验结果表明，改进的SIFT匹配算法不仅保持了原始的SIFT具有的特征，而且改进的SIFT匹配算法确实在速度与精度上超越了原始的SIFT算法，虽然在检测特征点的时候是以减少特征点数量为代价来提高运算速度，但是在总体上并不影响图像的匹配精度。

4 结语

本文分析了SIFT匹配算法的原理及其存在的缺点，提出了一种改进的SIFT匹配算法。该算法旨在提高SIFT算法匹配的速度与精度。通过利用Harris角点检测算法在求取SIFT极值点时进行进一步筛选，减少了SIFT特征点的匹配点对数，同时也相应地提高了精度。在得到匹配点后，对原始图像与测试图像进行一次逆向匹配，接着利用RANSAC对得到的匹配点进行进一步处理，删除外点，选择正确的匹配点对，使匹配精度提高。实验结果表明改进的算法相对于SIFT算法在匹配精度和匹配速度上有一定提高。

[1] D.Lowe.Object Recognition from Loca1 Sca1e Invariant Features[C].Proceedings of the ICCV.Kerkyra，Greece，1999：1150～1157

[2] D.Lowe.Distinctive Image Features from Sca1e Invariant Keypoints[J].Internationa1 Journa1 of Computer Vision，2004，60（2）：91～110

[3] Aniruddha Acharya K，R.Venkatesh Babu:Speeding up SIFT Using GPU[C].2013 4th Nationa1 Conference on Computer Vision.Pattern Recognition.Image Processing and Graphics，NCVPRIPG 2013

[4] Bay Herbert，Tuyte1aars Tinne，Goo1LucVan.SURF:Speeded Up Robust Features[J].Computer Vision and Image Understanding，2008，110（3）：346～359

[5] Y.Ke，R.Sukthankar.PCA-SIFT:“A More Distinctive Representation for Loca1 Image Descriptors”[C].Proc.Conf.Computer Vision and Pattern Recognition，2004：511～517

[6] HARRIS C，STEPHENS M.A Combined Corner and Edge Detection[J].Image Vision Computing，1998，15（6）:121～127

[7] J.Matas，O.Chum，M.Urban，T Pajd1a.Robust Wide-Base1ine Stereo from Maxima11y Stab1e Exterma1 Regions[C].Proceedings of the British Machine Vision Conference，Cardiff，UK，2002：384～393

[8] 唐朝伟，肖健，邵艳清，苗光胜.一种改进的SIFT描述子及其性能分析[J].武汉大学学报信息科学版，2012（1）:11～16

[9] 于丽莉，戴青.一种改进的SIFT匹配算法[J].计算机工程，2011（1）:210`212

[10] 赵垒，侯振杰.一种改进的SIFT图像配准方法.计算机工程，2010（6）:226～228

[11] 江道寅.基于SIFT图像配准算法的研究[D].中国科技大学，2011:45～47

[12] 王静.基于SIFT和角点检测的自动图像配准方法研究[D].华中科技大学，2010：19～24

[13] 章毓晋.图像处理（第2版）.北京:清华大学出版社，2006:270～278

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

An Improved SIFT Image Matching Algorithm

LIN Qiang
（Department of Computer Science，Sichuan University，Chengdu 610065）

Puts forwards an improved image matching a1gorithm aiming at the prob1ems of that Sca1e Invariant Feature Transform a1gorithm has a few fa1se and repeated matching feature points.The improved image matching method takes the extremum got by the SIFT descriptor as origina1 keypoints,then fi1ters the origina1 keypoints by Harris corner detection operator.Se1ects points which have a high contrast as fina1 points and match fina1 points by using the proportion of the Euc1idean distance.As there are some redundant and error matching points, converse1y matches both images based on SIFT matching.Fina11y uses RANSAC a1gorithm to se1ect the correct match keypoints.The resu1ts show that the a1gorithm is stab1e and re1iab1e under the change of rotation,trans1ation,1ight,contrast and so on.

Image Matching;SIFT Feature;RANSAC;Euc1idean Distance

1007-1423（2015）05-0058-05

10.3969/j.issn.1007-1423.2015.05.013

林强（1983-），男，四川成都人，硕士，研究方向为计算机视觉

2014-12-31

2015-01-21