基于改进SIFT的图像特征匹配算法

谭光兴 张伦

摘 要：鉴于传统尺度不变特征变换（scale invariant feature transform，SIFT）算法特征描述子维度过高、匹配时间长和误匹配率较高的问题，提出一种改进SIFT的图像特征匹配算法。首先，将SIFT特征点邻域的方形区域改为十字形分区来简化特征描述子，降低描述子的维度，减少匹配计算量;然后，在由欧式距离获取初始匹配点对的基础上，结合余弦相似度约束条件过滤伪匹配;最后，利用渐进一致采样（progress sample consensus，PROSAC）算法进一步优化匹配结果，实现精准匹配。实验结果表明，该算法在模糊、光照、仿射、尺度旋转等变化条件下均显著提高了正确匹配率，并缩短了匹配耗时，有效提升了在复杂场景下的匹配性能。

关键词：尺度不变特征变换;特征描述子;欧氏距离;余弦相似度;渐进一致采样

中图分类号：TP391.41            DOI：10.16375/j.cnki.cn45-1395/t.2022.02.006

0    引言

图像匹配是图像处理技术中的一项重要内容，是将两幅或多幅图像的某种性质进行对比，并通过一定的规则识别出图像之间的相似部分。图像匹配已被广泛应用于图像拼接[1]、同步定位与建图（视觉SLAM，simultaneous localization and mapping）[2]和对象识别[3]等诸多领域。目前图像匹配的方法主要分为两大类：基于灰度的匹配方法和基于特征的匹配方法[4]。其中，利用图像灰度进行匹配的方法操作简单，匹配率较高，但计算量太大，匹配耗时较长，且对光照变化比较敏感。而利用图像的特征信息进行匹配的方法以其速度较快、精度高和鲁棒性好等特点成为近年来图像匹配技术研究的热点。

基于特征匹配的算法中，最具有代表性的是由Lowe[5]在2004年提出的传统尺度不变特征变换（scale invariant feature transform，SIFT）算法。该算法不仅提取特征能力强，对图像的旋转、尺度变化、光照变化和噪声等也具备较高的稳定性，但仍存在一些缺陷：特征描述子维数太大，导致计算复杂度高，时间成本大，对实时性的应用具有局限性。针对SIFT算法的不足，国内外许多学者做了相关改进。文献[6]通过主成分分析法（principal component analysis，PCA）有效降低了SIFT算法的描述子维数，缩短了匹配时长，但会导致匹配率下降。文献[7]提出了加速稳健特征（speeded up robust features，SURF）算法，该算法通过积分图技术能够快速检测关键点和获取描述子，运算速度明显提升;不过，该算法在尺度旋转变化下的匹配性能不如SIFT。文献[8]提出的基于余弦距离匹配规则的SIFT特征匹配方法，提高了匹配精度，却降低了速度。文献[9]提出的Harris角点提取和SIFT特征描述相结合的匹配算法，删除了冗余的特征点，提高了正确匹配率，但检测特征点失去了尺度不变特征，导致该方法无法适用于尺度缩放太大的图像。文献[10]将SIFT算法特征点描述子的矩形改为圆形，提高了匹配精度与速度，但实时性有待 提高。

本文在SIFT算法的基础上，通过建立十字形分区的特征描述子，将描述子的维数从128降低至64，减少匹配时的计算量，缩短匹配耗时。为提高匹配精度，在由欧式距离比值法得出的初始匹配点对上，使用特征向量之间的余弦相似阈值有效去除不可靠、不理想的匹配点，最后采用渐进一致采样（progress sample consensus，PROSAC）算法进一步提纯。

1    SIFT算法基本原理

1.1   极值点检测

建立图像尺度空间是检测极值点的首要任务，一幅二维图像的尺度空间[L（x， y， σ）]可由一个变化尺度的高斯函数[G（x， y， σ）]与原图像[I（x， y）]卷积而来，如下所示：

[L（x， y， σ）=G（x， y， σ）∗I（x， y）]   ，             （1）

[G（x， y， σ）=12πσ2e-x2+y22σ2]  ，                （2）

式中：[（x， y）]为像素坐标，[σ]为尺度空间因子。

为了检测稳定的关键点，需构建高斯差分金字塔[D（x， y， σ）]，其實质是2个相邻尺度图像的差，计算公式为：

[D（x， y， σ）=L（x， y， kσ）-L（x， y， σ）]  ，          （3）

式中：[k]为相邻尺度因子的比值。

在高斯差分金字塔上，将每个像素点与上层、下层及同尺度层的邻域共26个点进行比较，由此确保能够检测到支持尺度不变性的极值点。

1.2   关键点精准定位

尺度空间的各层之间并不连续，即上一步得到的极值点并不能代表关键点的真实尺度和位置。为了得到更准确的关键点，需要利用高斯差分金字塔函数在尺度空间的泰勒级数展开式进行插值查找，同时去除对比度低的关键点，展开式如式（4）所示：

[DX=D+∂DT∂XX+12XT∂2D∂X2X] ，         （4）

其中：[X=（x， y， σ）T]。由于提取关键点的过程会产生边缘响应，根据边缘响应点具有较大的主曲率比的特性，可借助主曲率比阈值过滤掉边缘响应点。

1.3   关键点方向分配

经过1.1、1.2两个步骤后，此时关键点还不具备方向。利用关键点邻域像素的梯度方向特性，为每个关键点指定方向参数，使特征描述子具有旋转不变性。对于窗口内每一个采样点[L（x， y）]，其梯度值[m（x， y）]与方向[θ（x， y）]的计算公式为：

[m（x， y）=]

[（L（x+1， y）-L（x-1， y））2+（L（x， y+1）-L（x， y-1））2]，          （5）

[θ（x， y）=arctan[L（x， y+1）-L（x， y-1）L（x+1， y）-L（x-1， y）]].  （6）

用直方图统计关键点一定邻域内的梯度方向，而直方图最高峰所对应的方向则作为关键点的主 方向。

1.4   特征描述子的生成

SIFT算法通过生成描述子向量来描述特征点，并用于后续的匹配环节。特征描述子的生成如图1所示，首先，以特征点为中心选取周围16×16网格的方形像素区域;其次，将4×4网格划分为一个子区域;最后，在每个子区域计算得到8个方向（每45°取一个方向）的梯度累加值，则每个特征点均可生成4×4×8=128维的特征描述子。

1.5   特征点匹配

一旦获取了特征点描述子，便能利用它们实现特征数据的对比，从而辨别特征点之间是否具有相似性。

一般可通过欧式距离进行判断，特征点之间的距离越小，表示它们越相似。欧式距离的定义     式为：

[d（x， y）=||M， N||=i=1n（Mi-Ni）2].       （7）

SIFT算法利用描述子向量计算出参考特征点与所有待匹配特征点的欧氏距离，采用最近邻比值法进行匹配：若最近邻与次近邻的距离比值小于设定阈值T，则特征点与最近邻点相匹配。T的选取会影响初始匹配的效果，T太大，会存在较多的匹配数，但是误匹配数也会相应增多;T过小，匹配效果会变好，而匹配数会减少。阈值T的选取范围一般为0.4～0.8。

2    SIFT算法的改进

2.1   简化特征描述子

原SIFT算法具有128维，是高维度的特征描述子且包含了冗余数据，导致其形成花费时间长，计算成本大，匹配计算复杂度高，因此，本文对描述子进行简化，提高匹配效率。

简化后描述子的具体划分如图2所示。与SIFT算法划分的方形区域相比，首先，舍去了4个角落的4×4网格像素，主要依据是距离特征点越远的像素对描述子的贡献越小，在匹配环节中发挥的作用就越小，而整个描述子数据的权重分布又类似为高斯核，由此舍去了对特征描述子贡献较低、影响匹配效果较小的部分像素信息。其次，将特征点周围8×8的网格像素邻域划分成4个三角子区域[4]，并与SIFT算法保持一致，在每个三角子区域统计8个方向上的梯度累加值，得到4×8=32维的特征描述子。然后，将三角子区域的上下2个4×8的网格像素、左右2个8×4的网格像素共划分为4个矩形子区域，同理统计每个矩形子区域内8个方向上的梯度累加值，得到4×8=32维的特征描述子。由于2种区域划分的大小不同，形状与方向也有差异，需要均衡这2种描述子的梯度值。同时为了满足距离特征点越近作用越大的原则，需对这2种区域描述子的梯度值进行加权计算。最后，将这2种描述子进行拼接，获得一个32+32=64维的特征描述子，可将原SIFT算法的描述子维数减少50%，节省了特征点描述的花费时长，有效降低了算法的计算复杂度与计算量，虽然丢弃了少量的特征信息，但提高了描述子的独特性，使得同名特征点的匹配更加稳定。

若[R=（r1， r2， …， r64）]是某一特征点64维的特征描述子，为去除光照变化的影响，需要将其按式（8）进行归一化处理：

[R=Ri=164r2i=（r1， r2， …， r64）].          （8）

再将归一化后特征描述子中的最大值移至向量的第一个位置，可进一步确保旋转不变性。具体操作为：通过循环左移整个向量元素的方式进行验证，直到最大值处在当前向量的第一个位置。例如向量中的最大值为[r11]，则最终形成的特征描述子向量为[R=（r11， r12， …， r64， r1， …， r10）]。

2.2   余弦相似度过滤

SIFT算法通過单一的欧式距离匹配规则会存在大量的伪匹配点，导致较高的误匹配率。这主要是因为欧氏距离只在向量的数值特征上体现出不同，因此，当图像特征相似的区域较多时，多个特征向量之间的距离是近似相等的，此时因向量分量之间的相关性被忽视，体现单一特征的多个分量会干扰匹配结果，从而影响到匹配的精度。

衡量向量之间的相似性除了距离测度法还有相似性函数法[11]。向量间的余弦相似度就是常见的相似性函数，它在方向特征上体现出了向量之间的差异，若向量间的余弦相似度越大，表明这对向量在方向上就越接近。其余弦相似度[S（x， y）]表达式为：

[S（x， y）=x⋅y||x||×||y||=i=1nxiyii=1nx2ii=1ny2i].         （9）

为此，本文通过添加余弦相似度约束条件来减少伪匹配点对数。具体方法是：在特征点之间的欧式距离比值小于T的基础上，再验证特征向量之间的余弦相似度是否大于某一阈值，若大于某一阈值才能认定为匹配成功。为满足误匹配率较低而匹配点对数尽量多的要求，根据文献[12]的建议，本文余弦相似度经验阈值设定为0.93。

2.3   PROSAC算法提纯

虽然通过余弦相似度约束条件对欧氏距离粗匹配的结果进行过滤后，改善了匹配效果，却依然存在精度不够的匹配点对，需采取相应算法进一步提纯。目前常用的提纯算法是随机抽样一致（random sample consensus，RANSAC）算法[13]，该算法的基本原理是：在匹配点对数据集的基础上，不断抽取数据并计算出模型参数，通过多次迭代，获取一个最适合匹配点对集的估计模型。但RANSAC算法每次从整个数据集中随机采样的质量高低不等，导致得到模型的参数达不到最佳效果，同时计算时间与样本量的平方成正比，不适合对大规模的数据集进行计算。而PROSAC算法[14]是对数据集按质量高低排序后再进行采样，然后估计模型参数，与RANSAC算法相比，减少了迭代次数，使模型最佳参数较早出现，提升了效率。因此，本文采用PROSAC算法对余弦相似度阈值过滤后的匹配结果进一步优化，实现的步骤为：

Step 1  将过滤后的匹配点对按照距离进行升序排序。

Step 2  选取前n个样本数据，并随机删除m个，估计出模型参数。

Step 3  利用该模型对所有的匹配点对计算出误差，误差小于阈值的匹配点对视为内点，同时记录内点的数目;反之则视为外点并剔除。

Step 4  重复Step 2、Step 3，继续迭代，直到满足终止条件时，输出模型与匹配结果。

算法终止条件为：

1）内点数目大于阈值或者已至最大迭代次数。

2）K次取样后，内点数并没有明显变化，或者模型对匹配点计算出的误差之和没有变小。

3    实验结果与分析

3.1   测试图像与实验环境

为验证本文算法的匹配性能并使实验结果更具有说服力，实验测试图像选自牛津大学机器人实验室标准数据集中的4组图像，如图3所示，包括了发生模糊变化、光照变化、仿射变化和尺度旋转变化的图像，其中各图像的分辨率均调整为800×640。实验的硬件平台为Intel（R） Core（TM） i5-9400F CPU，频率为2.9 GHz，内存为8 G。编程平台为PyCharm2019，算法使用Python代码在操作系统为64位的Windows10环境下实现。

3.2   匹配结果对比

将本文算法与SIFT算法在图像模糊、光照、仿射以及尺度旋转变化下分别进行了4组实验。2种算法在4组测试图像上的匹配效果对比如图4所示，表1为2种算法的匹配结果对比。

对比2种算法的匹配效果可以看出，本文算法对于4组不同变化的图像均能够进行准确的匹配，并且匹配效果较SIFT算法更好，剔除了一些不理想的匹配点对。可见本文采用十字形分区取代SIFT特征描述子的矩形区域，使其特征描述能力更强;在欧氏距离粗匹配的基础上，通过余弦相似度阈值有效去除了在匹配集中的伪匹配;最后利用PROSAC算法对过滤后的匹配效果再次进行优化。

根据表1的数据可知，相比SIFT算法，本文算法减少了匹配总数，误匹配数也明显减少，主要是由于建立十字形分区描述子的同时引入余弦相似匹配规则，增强了匹配的抗干扰能力，限制了不可靠特征点之间的匹配能力。实验结果表明，本文算法针对图像的模糊、光照变化、仿射变换和尺度旋转等复杂变化均具有较强的适应能力，充分反映了对于复杂场景下的图像，本文提出的算法依然能够实现精准匹配。

3.3   匹配性能对比

将正确匹配率与匹配时间视为衡量算法匹配性能优劣的标准。本文算法和SIFT算法的匹配性能对比如图5所示，横坐标均为4组测试图像，正确匹配率=（匹配总数-误匹配数）/匹配总数×100%。

如图5（a）所示，本文算法对4组不同变化的测试图像均能够得到明显高于SIFT算法的正确匹配率，表明本文算法提高了在图像复杂变化下的稳定性。这说明对特征描述子的改进有效增强了对特征点描述的独特性，提高了待匹配中相同特征点的描述子相似性程度。之后又增加了余弦相似度匹配约束条件，剔除了向量方向差异过大的伪匹配。同时本文算法对4组不同变化的测试图像均能达到90%以上的正确匹配率，其中对光照和仿射变化的匹配率提高程度较大，这表明对描述子进行归一化以及考虑到特征向量之间的相关性后，降低了对光照和仿射变化的敏感性，从而显著提高了匹配精度。

如图5（b）所示，本文算法对4组测试图像的匹配时间均低于SIFT 算法。这表明本文提出的算法由于改变了描述子的邻域区域，使得特征向量维数大幅度减少，计算复杂度极大程度降低，有效节省了运算时间，提高了匹配速率;另外由于匹配数相对减少，匹配花费时长也随之缩短。因此，本文算法不仅显著提高了匹配精度，还有效缩短了匹配耗时，表明本文算法的匹配性能优于SIFT算法。

4    结语

针对SIFT算法的高维度描述子所带来的计算量大、匹配速度慢等问题，提出了采用十字形分区取代SIFT特征点邻域方形描述区域的方法，使得特征向量维度大幅度减少，提升了运算速度，提高了特征描述子的独特性与匹配效率。根据欧式距离进行初始匹配，随后引入匹配点应满足余弦相似的规则来剔除伪匹配，最后利用PROSAC算法进一步提高匹配精度。实验结果表明，该算法在模糊、光照、仿射和尺度旋转等变化下均具有较强的适应能力，提高正确匹配率的同时压缩了匹配时间，有效提升了在复杂场景下的匹配性能。但在如何快速检测稳定特征点方面還需进一步研究。

参考文献

[1]     马兆敏，吴健玥，胡波，等.田间图像拼接中重复信息量对拼接效果的影响[J].广西科技大学学报，2017，

28（3）：83-87，96.

[2]     陈庆伟，李民东，罗川，等.视觉SLAM中图像特征点提取与匹配算法研究[J]. 现代制造工程，2019（10）：135-139，134.

[3]     薛圣利，蔡启仲，杨海林，等.基于OpenCV的火车票识别算法[J].广西科技大学学报，2016，27（2）：46-51.

[4]     冯文斌，刘宝华.改进的SIFT算法图像匹配研究[J].计算机工程与应用，2018，54（3）：200-205，232.

[5]     LOWE D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[6]     KE Y，SUKTHANKAR R.PCA-SIFT：a more distinctive representation for local image descriptors[C]//Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington DC：IEEE，2004：506-513.

[7]     BAY H，ESS A，TUYTELAARS T，et al.Speeded-up robust features（SURF）[J].Computer Vision and Image Understanding，2008，110（3）：346-359.

[8]     许钢，林园胜，江娟娟，等.改进型SIFT立体匹配算法研究[J].计算机工程与应用，2015，51（6）：134-138.

[9]     尚明姝，王克朝.一种改进的Harris与SIFT算子结合的图像配准算法[J].微电子学与计算机，2018，35（6）：132-134，140.

[10]   程德强，李腾腾，郭昕，等.改进的SIFT邻域投票图像匹配算法[J].计算机工程与设计，2020，41（1）：162-168.

[11]   张宇，刘雨东，计钊.向量相似度测度方法[J].声学技术，2009，28（4）：532-536.

[12]   白廷柱，侯喜报.基于SIFT算子的图像匹配算法研究[J].北京理工大学学报，2013，33（6）：622-627.

[13]   FISCHLER M A，BOLLES R C.Random sample consensus：a paradigm for model fitting with applications to image analysis and automated cartography[J].Communication of the ACM，1981，24（6）：381-395.

[14] CHUM O，MATAS J.Matching with PROSAC-progressive sample consensus[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition（ICCV）.Beijing：IEEE，2005：220-226.

Image feature matching algorithm based on improved SIFT

TAN Guangxing，ZHANG Lun

（School of Electrical， Electronic and Computer Science， Guangxi University of Science and Technology，

Liuzhou 545616， China）

Abstract： An improved SIFT （Scale Invariant Feature Transform） image feature matching algorithm is proposed aiming at the high dimensionality of feature descriptor， long matching time， and high         mismatching rate. Firstly， the square area of the SIFT feature points neighborhood is changed into  cross-shaped partition to reduce the dimensionality of the descriptor and amount of matching             calculation. Then， Euclidean distance is used to obtain the initial matching， and filter out mismatch by adding the constraint condition of cosine similarity. Finally， progress sample consensus （PROSAC） is used for further purification and accurate matching. Experimental results show that the algorithm not only improves the correct matching rate significantly， but also shortens the matching time under changes of blur， illumination， affine， scale rotation， and effectively improves the matching performance in complex scenes.

Key words： scale invariant feature transform; feature descriptor; Euclidean distance; cosine similarity; progress sample consensus

（責任编辑：黎   娅）