一种基于SIFT特征的快速图像匹配算法

摘要：针对SIFT算法运行速度较慢、时间效率不高的问题，本文提出了一种与Harris角点检测算法相结合的快速图像匹配算法。该方法利用Harris角点检测算法计算量小，运行速度快的优点，并改进SIFT算法描述子，通过调整描述子的结构达到特征向量降维的目的，进一步提高算法的时间效率。实验结果证明，该算法既保留了SIFT算法的稳定性以及旋转不变性，也提高了SIFT算法的运行速度。

关键词：图像匹配；SIFT特征；Harris角点检测

中图分类号：TP391.41

文献标识码：A

DOI：10.3969/j.issn.1003-6970.2015.06.011

本文著录格式：任忠良，一种基于SIFT特征的快速图像匹配算法[J].软件，2015，36（6）：53-57

AFastImageMatchingAlgorithmBasedonSIFTFeatures

RENZhong-liang[Abstract]：AnewalgorithmisproposedcombinedwithHarriscornerdetectionalgorithm，inordertoimprovetheefficiencyofSIFTwhichrunsslowlyandhaslowefficiencyonfeaturesextracting.ItmakesfulluseofHarris'lowcalculationfastoperation.BychangingtheSIFTdescriptor，itachievesthegoalofdecreasingtheeigenvectorthroughimprovingthestructureofthedescriptor.Astheexperimentalresultsshow，thisalgorithm，notonlyretainsthestabilityandrotationinvarianceofSIFT，butalsoimprovesthespeedofSIFTalgorithm.

[Keywords]：Imagematching；SIFTfeatures，Harriscornerdetection

0引言

随着人T智能的不断发展，图像匹配技术逐渐成为模式识别领域中一项非常重要的技术，其在诸多领域有着广泛的应用，如遥感卫星地图和地形匹配、医学诊断、人脸识别等等。基于图像局部特征的匹配算法是图像匹配技术中较为常见的算法，该类算法的思想是将图像映射为包含该图像局部特征信息的集合，以此来进行图像匹配。其中，SIFT（Scale-invariantfeaturetransform，尺度不变特征转换）算法是一种较为经典的利用图像局部特征的匹配算法。SIFT算法[1-2]由Lowe于1999年提出，它基于尺度空间理论，具有稳定性好、特征点准确性强等优点，对旋转、尺度、光照等保持较好的不变性。

但SIFT算法也有其一些弊端，其中建立尺度空间需要较大的系统开销，时间效率较低。国内外基于SIFT算法的改进也有大量的研究。如KeandSukthankar[3]提出的PCA-SIFT算法，利用PCA（Principlecomponentanalysis，主要成分分析）将特征点描述向量降至36维；MikolajczykandSchmid[4]提II+Il-种SIFT变体描述子-GLOH（TheGradientLocation-OrientationHistogram，梯度定位方向直方图），利用对数极坐标代替Lowe使用的坐标象限；HerbertBay等人[5]提出的SURF（Speed-upRobustFeatures，快速鲁棒特征）算法选用二阶标准高斯函数作为滤波器，通过改变滤波器大小来建立尺度空间，可以有效提高算法的效率；张春美等人[6]对SIFT描述子进行改进，利用同心网环描述特征点，保持旋转不变性的前提下降低了描述子的维度；陈抒珞等人[7]提出Contourlet-SIFT变换，对特征及其邻域先进行Contourlet变换，构建全局纹理描述向量，以提升匹配速度；范志强等人[8]将SIFT与数据聚类做结合，提高了特征匹配的鲁棒性。本文主要针对SIFT算法提取特征点时效性差这一缺点进行改进，结合Harris角点[9]提取算法，能够有效的提高关键点的提取速度，并适当降低描述子维度，以此来降低算法运行所需的时间，增强算法的实时性。

1SIFT算法原理

SIFT算法基于Lindeberg等人[10]提出的尺度空间理论，利用高斯核建立尺度金字塔，在尺度空间寻找极值点，并赋予该点对尺度、旋转保持不变性的特征向量，并利用这些特征向量间的欧氏距离来进行匹配，以达到图像匹配的目的。

1.1查找关键点

文献[10]证明了高斯卷积核是生成尺度空间的唯一变换核。一幅图像/（x，y）的尺度空间定义为L（x，y，б），是由不同尺度的高斯函数与原图像卷积运算生成的[10]。

L（x，y，б）=G（x，y，б，）*（x，y）

（1）

其中，

高斯核的尺度б是连续变化的，将其与原图像进行卷积运算，得到一组尺度空间图像。将得到的图像进行降采样作为相邻组高斯图像的基准图像，继续与高斯核进行卷积运算得到新一组尺度空间图像。如此反复直至图像大小小于某个预定值。将相邻层的高斯图像进行相减便得到DOG（DifferenceofGaussian）图像D（x，y，б）。

Lowe在DOG尺度空间中寻找极值点，将其中每个点与相邻尺度的对应位置包括其相邻位置以及本尺度的八个相邻位置共计26个点逐个进行比较，得到的局部极值位置和尺度即为极值点的位置和对应的尺度。极值点即为后文叙述中的关键点。

1.2分配方向

SIFT算法中为每个关键点分配主方向时采用关键点邻域的梯度分布，并且在1.3章节中描述符构造也以此方向作为参照。

各像素梯度的模与方向的计算公式如下：

1.3生成描述符

生成描述符时，为保证其旋转不变性，首先将关键点周围区域旋转顺时针旋转θo，与主方向相同。在旋转后的区域内，对关键点周围16x16矩形窗口采样。Lowe建议将其分成16个4x4的子区域，并在每个子区域中将方向投影至8个方向的梯度累加值，则共生成4x4x8共计128维向量，该向量即为SIFT算法的128维描述符，如图1（以其中8x8为例）所示。

至此，SIFT特征描述符已具有尺度、旋转不变性，将描述符进一步做归一化处理后可去除光照影响。并且SIFT算法中的邻域方向也提供了较好的稳定性，使得SIFT算法具有较高的鲁棒性。

1.4特征向量的匹配

Lowe在原文中建议利用两幅图像检测到的特征向量之间的欧式距离之间的比值作为匹配依据，具体步骤如下：在其中一幅图像取关键点，并在另一幅图像中根据欧式距离选取最近的前两个关键点，若最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。欧氏距离定义及判定阈值公式如下：

根据公式（7）不难看出，将比例阈值Threshold增大，SIFT算法的匹配点对会增多。反之，降低比例阈值Threshold，匹配点对会减少，但匹配更加稳定。文献[2]中建议该阈值取值为0.8，本文算法根据经验值将该阈值设为0.75。

2改进的快速SIFT图像匹配算法

由于在1.1章节中介绍的尺度空间中查找极值点的系统开销较大，导致算法效率较低，其目的是为了能够找到较多、较为稳定的极值点，并且保证其尺度不变性。但是在实际应用中，若图像获取设备能够保证较好的对焦情况，则进行匹配的图像尺度就不需进行过多考虑，因此我们考虑与较为快速的犄征点提取算法做结合，以提高SIFT算法的效率。

2.1Harris角点提取算法

Harris算法是以Moravec算法[11]为基础的，而其原理是将以目标像素点（x，∥）为中心的窗口向任何方向移动（μ，v）后计算灰度变化，Harris在此基础上，利用微分运算和白相关矩阵来检测角点，能够有效区分角点与边缘。Harris算法具有计算简单的特点，所以运行速度较快，并且算法具有较高的稳定性和鲁棒性，能够在图像旋转、灰度变化以及噪声干扰等情况下准确的检测特征点，具有较高的点重复度和较低的误检率。

2.2改进的SIFT描述符

在经过Harris角点提取算法提取特征点，计算并分配方向，以及对齐主方向之后，在关键点周围15x15的区域上采样计算方向，其中将每个Sx5的区域方向投影到八个方向上，这样生成的描述子有3x3x8共计72维向量，代替原文的128维向量，以达到降维的目的，如图2（以其中一个5x5的区域为例）所示。

通过对新的描述符的分析我们可以发现，改进后的描述符在尽可能多的保留采样区域（16x16改为15x15）的前提下，通过改进描述符的结构来对描述符降维。这样做既有利于保持SIFT算法的鲁棒性，又能够进一步提高后续匹配的速度。

2.3改进的SIFT算法过程

根据2.2章节的分析，我们现对SIFT算法做如下改进：首先利用Harris角点提取算法对图像进行关键点查找，接着对得到的关键点进行主方向分配，并生成72维的改进SIFT描述符，最后利用欧氏距离对两幅图像进行匹配，得到匹配结果。算法过程如图3所示：

3实验结果与分析

采用MATLABR2013a构建实验平台，将本文算法与SIFT算法在匹配效果与时效性方面进行了比较与分析。算法运行环境为CPU：InteI（R）Xeon（R）E3-1230v33.3GHz，内存：8GB。

3.1具有一般场景的图像匹配

图4为使用SIFT算法进行匹配的效果图，而图5为使用本文算法的匹配效果图。经分析，不难发现本文方法在特征点的提取方面更接近于视觉角点，特征点的数量虽然较少，但匹配正确率较高，效果较好。使用SIFT算法与本文算法进行图片匹配的运行时间如表1所示。

由表1可以看出，本文算法在运行时间上相对于SIFT算法有着较为明显的提升，算法的时间效率较高，尤其是提取极值点的步骤，由于利用了速度较快的Harris算法，使得该步骤所需时间大大降低。并且由于描述子维度降低，使得匹配时间也得以缩短，同时保持较高的正确率。说明本文算法具有较强的鲁棒性。

3.2具有较大旋转角度的图像匹配

图6中，图（a）是经典的Lena图像，大小为512×512，图（b）是对其进行30。旋转后得到的。由于本文主要是针对SIFT算法的速度进行改进，所以将速度较快的经典SURF算法拿来作为参照，似验证本文所提出算法的时效性，算法运行环境同上。图6是原SIFT算法的匹配效果图，从图中可以看出原SIFT算法匹配效果较好，信息较为丰富，且正确率较高。图7是SURF算法的匹配效果图，从图中可以看出SURF算法匹配虽然信息较为丰富，但就旋转图像而言，误匹配率较高，匹配效果较差。图8是本文算法的匹配效果图，从图中可以看出本文算法匹配效果较好，正确率较高。使用SIFT算法，SURF算法与本文算法进行图片匹配的运行时间如表2所示。

由表2可以看出，SIFT算法具有旋转不变性，对于旋转图片仍有较高的正确率。而SURF算法虽然时效性强，但针对旋转图像则不能保证较高的正确率。而本文算法在保证较高正确率的前提下，依然有着较快的速度表现，表明本文算法具有时效性和旋转不变性。

4结论

本文针对SIFT算法时间效率较差这一缺陷进行改进，在极值点的提取部分针对较小尺度变换的图片，采用速度较快，算法较为简单的Harris算法来代替原有的尺度空间的极值点提取。并在描述符生成时采用新的描述符结构来达到降维的目的，从而进一步提高算法运行效率。从最终的实验结果图以及与几种算法对比的时间结果来看，本文算法既能保证稳定性与正确性，又能降低算法的时间开销。在接下来的工作中，可以尝试与一些其他模式识别与匹配算法[12-14]进行结合，以设计出更加有效的算法。

参考文献

[1]LoweDG.Objectrecognitionfromlocalscale-invariantfeatures[C]//Procofthe7thIEEEIntConfonComputerVision.Piscataway，NJ：IEEE，1999：1150-1157.

[2]LoweDG.Distinctiveimagefeaturesfromscale-invariantkeypoints[J].InternationalJournalofComputerVision，2004，60（2）：91-110。

[3]KeY，SukthankarR.PCA-SIFT：Amoredistinctiverepresentationforlocalimagedescriptors[C]//Procofthe2004IEEEComputerSocietyConfonComputerVisionandPatternRecognition.Piscataway，NJ：IEEE，2004：511-517.

[4]MikolajczykK，SchmidC.Aperformanceevaluationoflocaldescriptors[J].IEEETransonPatternAnalysisandMachineIntelligence，2005，27（10）：1615-1630.

[5]BayH，EssA，TuytelaarsT，etal.Speeded-uprobustfeatures（SURF）[J].ComputerVisionandImageUnderstanding，2008，110（3）：346-359。

[6]张春美，龚志辉，孙雷.改进SIFT特征在图像匹配中的应用[J].计算机工程与应用.2008.44（2）：95-97.

[7]陈抒珞，李勃，董蓉，等.Contourlet-SIFT特征匹配算法m.电子与信息学报，2013，35（5、：1215-1221.

[8]范志强，赵沁平.一种基于数据聚类的鲁棒SIFT特征匹配方法[J].计算机研究与发展，2012，49（5）：1123-1129.

[9]SchmidC，MohrR.Localgrayvalueinvariantsforimageretrieval[J].IEEETransactionsonPatternAnalysisandMachineIntelligence，1997，19（5）：530-534.

[10]LindebergT.Featuredetectionwithautomaticscaleselection[J].InternationalJournalofComputerVision，1998，30（2）：79-116.

[11]MoravecHP.Towardsautomaticvisualobstacleavoidance[C]//ProceedingsofInternationalJointConferenceonArtificialIntelligence.Cambridge.MA.USA：fs.n.].1977：584-590.

[12]郝春媚、杨榆.面向涉密检查系统的基于KMP思想的多模式匹配算法[J].软件.2013.34（9）：57-60.[J].[13]杨沐，王晨升，陈志强，等.复杂背景下的字符模板匹配改进算法研究[J].软件，2012.33（12）：97-100.[J].[14]陈小星，陶志强.一种基于车辆图像的Keren配准方法的改进算法[J].软件，2014，35（12）：20-25.