改进的尺度不变特征转换匹配算法

茅正冲，王 丹，唐雨玉

（江南大学 轻工过程先进控制教育部重点实验室，江苏 无锡214122）

0 引 言

近年来，许多学者提出了不同的SIFT （scale－invariant feature transform algorithm）［1，2］改进算法。文 献 ［3］提 出了Contourlet－SIFT 特征匹配算法，对尺度空间下旋转不变特征进行Contourlet变换后再进行匹配，但是计算量偏大，不满足实时性要求；文献 ［4］提出了基于D2OG 特征点检测算子的改进SIFT 特征匹配算法，适用于图像信息丰富且对实时性要求较高的场合，但是算法提取的匹配点对数相对较少，限制了此算法处理的图像类型；文献 ［5］提出了以街区距离代替欧氏距离作为特征描述符之间的相似性度量，降低了相似性度量公式的时间复杂度，但是没有提高鲁棒性；文献 ［6］提出了一种基于图像Radon变化的改进的SIFT 特征匹配算法，降低了SIFT 特征向量的维数，提高了特征匹配效率，但是在实际场景使用时性能有待提高；文献 ［7］提出了多尺度特征提取的双目视觉匹配，虽然匹配率得到了提高，但是匹配耗时较长，时效性较差。

本文针对SIFT 算法运行时间过长，匹配率不高的问题，提出了一种改进的SIFT 算法。在原SIFT 算法基础上，引入了二维Mallat快速小波变换算法，对待匹配图像进行预处理，重建图像的低频成分，以提高匹配速度；对高斯金字塔组数进行调整，减少降采样次数和高斯金字塔层数；通过优化的随机抽样一致算法 （RANSAC）剔除误匹配点。实验结果表明，改进后的算法优于原来的SIFT 算法，匹配率也有所提高。

1 二维Mallat小波变换

在利用小波变换进行图像处理的研究中，由于受到塔式算法的启发，Mallat提出了一种快速的小波分解与重构算法，即为马拉特 （Mallat）算法［8］。

使用两个相同的一维小波函数和一维尺度函数的乘积构造二维小波基，生成的尺度函数和3个小波函数分别为

假设f ＝f（x，y）∈V2j为待分析的图像信号，它的二维逼近图像为下式所示

其中

然后再利用小波函数和尺度函数的正交性，可以得出

上式说明，j＋1尺度空间的尺度系数cj＋1（m，n）可以由j尺度空间的尺度系数cj（k，l）经二维滤波器系数进行加权求和得到。又

再引入一种矩阵算子，可以得出二维Mallat分解算法为

其中：Gr、Gc——用小波滤波器系数对行和列作用的算子，Hr、Hc——用尺度滤波器系数对行和列作用的算子。

而二维Mallat重构算法为

通过二维Mallat小波变换分解后，得到了待配准图像的低频成分和高频成分。其中，低频成分包含了大部分的图像信息，而高频成分主要包含的是噪声，仅含有少量的信息，在进行重构时去掉高频成分会使图像匹配的鲁棒性提高。实验结果表明，利用小波对图像进行多层分解时，2层以上的低频成分的匹配点的数量非常少，分解层数越多，反而会增加匹配时间，所以本文采用的是2尺度分解。经二维小波变换处理后的待配准图像，一方面可以减少每次参与匹配的像素点，提高了匹配速度，另一方面减少了弱匹配点，从而使误匹配率下降。

2 尺度空间的构造

SIFT 特征表征的不是图像的全局特征，而是局部特征，在平移、旋转、亮度变化和尺度缩放等方面具有良好的不变性［9］。SIFT 算法主要包括图像特征点的提取以及特征点的匹配两个方面［10］。特征点提取是指在不同的尺度空间上查找出图像的关键点，并且计算出这些关键点的方向和大小，最后生成关键点描述子。SIFT 特征点的提取可分解为4个步骤，如图1所示。

图1 SIFT 算法步骤

一幅二维图像I（x，y）的尺度空间L（x，y，σ）定义为一个变化尺度的高斯函数与原图像的卷积［12］，即

式中：σ——尺度空间的空间尺度因子，G（x，y，σ）——高斯核函数，其定义为

为了能在尺度空间中检测到稳定的关键点，使用高斯差分 （DoG）算子近似尺度归一化的拉普拉斯——高斯（LoG）算子。通过图像与不同尺度的高斯差分卷积核生成

高斯金字塔分成O 组、S层，其中，O 和S一般取为4和5，下一组的第一层是通过上一组的最后一层降采样得到的。在构造尺度空间之前，本文已先利用二维小波变换对待配准图像进行预处理，舍弃了高频成分，只保留了低频成分对其进行重建，包含的信息已经有所减少，所以没有必要做与原来一样的降采样次数。因此，本文通过对高斯金字塔的组数和层数进行调整，从而减少降采样次数，缩短尺度空间建立的时间。

经过二维小波变换处理过的图像，不包含图像的高频能量，即去掉了少部分的有效的信息和噪声。在对图像构建高斯金字塔时，金字塔的最后一层包含了很少的兴趣点，对最终的匹配结果没有太大的影响。所以，去除掉由高斯金字塔生成高斯差分金字塔的最后一层。文献 ［11］列出了保持其它条件不变，改变不同的降采样次数和高斯金字塔层数下的匹配结果和时间。当高斯金字塔减少2层，降采样次数减少2次时，没有足够多的匹配点保证匹配的准确性，所以本文只将最后一层高斯金字塔出除。实验结果表明，通过对降采样次数和高斯差分金字塔的层数进行调整，不仅减少了匹配特征点所需要的时间，同时一些误匹配点也可以去除，从而提高了匹配效率。

3 特征点匹配

本文采用K－近邻算法对生成的SIFT 特征向量进行匹配。假设最近邻特征点与待匹配点的距离为d1，次近邻与待匹配点的距离为d2，当d1＜0.8＊d2时，则认为最近邻特征点是正确匹配点，特征点对匹配。在计算特征点之间的欧氏距离时，采用了BBF算法来处理128维的特征向量。

在对所有特征点进行粗匹配之后，使用RANSAC 算法估计两个图像对之间的单位变换矩阵并将其作为几何约束，进而去除一些误匹配点，完成图像之间的精确匹配，提高匹配效率。

4 实验结果和分析

为了比较改进后的SIFT 算法对光照、旋转、尺度缩放均具有良好的鲁棒性，而且在正确匹配率和匹配时间上的变化，本节从光照、旋转、尺度3 个方面进行研究分析。实验平台是CPU 2.5GHz、内存4.00G 的笔记本电脑，软件平台为MATLAB2013a。实验图片分别从光照、旋转、尺度三方面选取，图像大小均为320＊320。

4.1 性能评价指标

本文采用正确匹配率和匹配耗时作为算法性能的评价指标。

正确匹配率指的是匹配正确的特征对数与所有匹配上的特征对数之比，正确匹配率越高，误匹配率就越低，则说明算法鲁棒性越好。公式表示如下

匹配耗时指的是从构建尺度空间开始一直到匹配结束。

4.2 结果分析

本文利用改进的SIFT 算法对不同类型的图片进行多次匹配实验，并与原始的SIFT方法和文献 ［7］提出的双目视觉匹配算法进行对比。图2～图4分别为不同光照下的匹配结果、不同视角下的匹配结果和不同尺度下的匹配结果。表1～表3分别为这3种情况下的正确匹配率和匹配耗时对比。

从图2、图3、图4可以看出，使用本文算法产生的匹配对相较于原始SIFT 算法减少了，同时误匹配对也相对减少了。虽然本文加入了小波变换，增加了小波变换的时间，但是最后总的匹配耗时减少了。然而相较于双目视觉匹配算法，在不同视角和不同尺度下产生的总匹配对相对多一些，误匹配对也相差无几。

图2 不同光照下的匹配结果

图3 不同视角下的匹配结果

表1 不同光照下的匹配结果对比

图4 不同尺度下的匹配结果

表2 不同视角下的匹配结果对比

表3 不同尺度下的匹配结果对比

根据图2～图4得出的数据和算法运行时间制成表1～表3。从表1、表2、表3可以看出，采用本文算法在不同条件下对图像进行匹配，正确匹配率都有明显地提高，剔除了很多错误的匹配对，并且匹配耗时也有明显地减少，优于原始的SIFT 算法，运行时间相对于原始的SIFT 算法减少了一半多。相对于双目视觉匹配算法，本文算法在不同尺度下的正确匹配率略低一些，但是本文算法匹配耗时远小于双目视觉匹配算法，运行时间明显减少了很多，大大减小了计算量，时效性得到了提高。

从实验结果可以得出，运用本文算法在光照、旋转、尺度方面均具有良好的鲁棒性和时效性。取二维Mallat快速小波变换后的图像进行匹配，图像的特征点数均有一定数量的减少，正确匹配率增加了。在构建尺度空间时，通过减少一次降采样次数使构建尺度空间的时间缩短了，提高了时效性，并且运用RANSAC 算法剔除了部分误匹配点。改进后的SIFT 算法虽然特征点减少了，但是仍有足够的特征点保证匹配的正确性，优于原来的SIFT 算法。

5 结束语

由于SIFT 算法计算时间过长，在实际应用中，不能满足实时性的要求，针对这一问题，本文提出了一种改进的SIFT 算法。实验结果表明，该算法不仅保留了原来SIFT算法在光照、旋转、尺度等方面具有很好的鲁棒性的特点，而且缩短了匹配时间，提高了正确匹配率，具有良好的匹配效果。但是，需要指出的是，为了使SIFT 算法能够更好地运用于实际中，时效性还有待提高，而且在匹配时还存在少量的误匹配对。因此还需要在时效性和匹配率上对本文的算法进行改进，这将是下一步的研究方向，并为运动目标跟踪等方面做好准备。

［1］Liao Kaiyang，Liu Guizhong，Hui Youshi.An improvement to the SIFT descriptor for image representation and matching ［J］.Pattern Recognition Letters，2013，34 （11）：1211－1220.

［2］LIU Pingping，ZHAO Hongwei.A fast local feature description algorithm ［J］.Acta Automatica Sinica，2010，36 （1）：40－45 （in Chinese）.［刘萍萍，赵宏伟.一种快速局部特征描述算法 ［J］.自动化学报，2010，36 （1）：40－45.］

［3］CHEN Shurong，LI Bo，DONG Rong.Contourlet－SIFT feature matching algorithm ［J］.Journal of Electronic ＆Information Technology，2013，35 （5）：1215－1221 （in Chinese）.［陈抒瑢，李勃，董蓉.Contourlet－SIFT 特征匹配算法 ［J］.电子与信息学报，2013，35 （5）：1215－1221.］

［4］CAO Juan，LI Xingwei，LIN Weiting，et al.Study on improved SIFT feature matching algorithm ［J］.Journal of System Simulation，2010，22 （11）：2760－2763 （in Chinese）.［曹娟，李兴玮，林伟廷，等.SIFT 特征匹配算法改进研究［J］.系统仿真学报，2010，22 （11）：2760－2763.］

［5］YANG Xingfang，CAO Yumei，HAN Xuzhao，et al.A method for improving matching efficiency of SIFT feature ［J］.China Mechanical Engineering，2012，23 （11）：1297－1301（in Chinese）. ［杨幸芳，曹玉美，韩旭炤，等.一种提高SIFT 特征匹配效率的方法 ［J］.中国机械工程，2012，23（11）：1297－1301.］

［6］YU Lili，DAI Qing.Improved SIFT feature matching algorithm ［J］.Computer Engineering，2011，37 （2）：210－212（in Chinese）.［于丽莉，戴青.一种改进的SIFT 特征匹配算法 ［J］.计算机工程，2011，37 （2）：210－212.］

［7］KONG Jun，TANG Xinyi，JIANG Min.Matching algorithm of binocular vision based on multi－scale feature extraction ［J］.Computer Engineering and Applications，2010，46 （33）：1－5（in Chinese）.［孔军，汤心溢，蒋敏.多尺度特征提取的双目视觉匹配 ［J］.计算机工程与应用，2010，46 （33）：1－5.］

［8］HOU Yi，ZHOU Shilin.Invariant feature with multi－characteristic scales using gabor filter bank ［J］.Acta Electronica Sinica，2013，41 （6）：1146－1152 （in Chinese）. ［候毅，周石琳.基于Gabor滤波器组的多特征尺度不变特种证提取方法［J］.电子学报，2013，41 （6）：1146－1152.］

［9］Zhang Qi，Rui Ting，Fang Hushang.Particle filter object tracking based on Harris－SIFT feature matching ［J］.Procedia Engineering，2012，29：924－929.

［10］Zhong Sheng，Wang Jianhui，Yan Luxin.A real－time embedded architecture for SIFT ［J］.Journal of Systems Architecture，2013，59 （1）：16－29.

［11］LI Ming.Research on object tracking algorithm based on SIFT feature－points matching ［D］.Hefei：Hefei University of Technology，2008 （in Chinese）.［李明.基于SIFT 特征点匹配的目标跟踪算法研究［D］.合肥：合肥工业大学，2008.］

［12］DONG Wenhui，CHANG Faliang，LI Tianping.Adaptive fragments－based target tracking method using color histogram and SIFT features［J］.Journal of Electronics ＆Information，2013，35 （4）：770－776 （in Chinese）.［董文会，常发亮，李天平.融合颜色直方图及SIFT 特征的自适应分块目标跟踪方法 ［J］.电子与信息学报，2013，35 （4）：770－776.］