基于改进SIFT算法的图像匹配方法研究

夏 杰，李奇安，李 悦，单海欧

（辽宁石油化工大学 信息与控制工程学院，辽宁 抚顺 113001）

图像匹配就是运用算法将不同条件下摄取的两幅或多幅图像在空间上进行相互匹配。目前图像匹配已经广泛地运用于社会多种领域，比如空间物体三维重建、模式识别以及目标物运动分析等。

传统的图像匹配算法计算量较大，在图像目标发生旋转、缩放、光照等参数发生变化时适应力不强。近年来，在计算机视觉领域中，基于局部不变量描述符的算法在图像匹配方面取得了令人瞩目的进展。

David G.Lowe教授提出一种基于尺度空间的、对图像缩放、旋转甚至仿射变换保持不变性的图像局部特征描述算子——SIFT算法[1]。

SIFT算法可以很好地解决旋转和缩放在图像匹配过程中的影响，但在实时性上存在不足。许多研究人员对该算法进行了改进，例如，Yan Ke的 PCA-SIFT方法[2]；Mikolajczy的GLOH算法[3]；刘立等人用圆形窗口的12维向量作为特征描述子的方法[4]；刘健等人采用对数极坐标变换、信息熵原理提取SIFT特征和不变矩特征，构造新型特征描述符进行匹配的方法[5]；王晓华等人以街区距离和棋盘距离的线性组合代替欧式距离作为特征描述符之间的相似性度量的方法[6]。改进的算法很多，大多是改进特征向量的计算方法，提高算法速度的方法，但效果不太理想。笔者针对SIFT算法的不足，提出了以街区距离代替欧式距离的新方法来提高SIFT特征匹配效率。

1 SIFT算法简介

SIFT算法分为4步，即检测尺度空间中的极值点，精确定位检测到的极值点位置，为极值点分配方向，生成描述极值点的SIFT特征向量。

1.1 检测尺度空间极值点

一幅二维输入图像 I（x，y）和尺度可变高斯函数 G（x，y，σ）卷积可得到该输入图像的尺度空间 L（x，y，σ）如式（1）。

其中，（x，y）是每个像素在输入图像中的空间坐标，符号*表示卷积，σ是高斯正态分布的方差，也是尺度空间因子，σ越小，图像被平滑的越少，尺度也就越小。

不同尺度空间的差分生成高斯差分尺度空间（DOG scale-space），即 D（x，y，σ），DOG 空间可以有效的在尺度空间内检测到稳定的关键点。尺度空间域上的图像特征点由常数乘性尺度因子k的相邻尺度高斯差分与图像卷积生成：

DOG空间检测极值时，将关键点在同尺度周围的邻域8个像素和上下相邻对应尺度位置的周围邻域9×2个像素总共26个像素相互比较。

1.2 精确定位极值点

DOG算子会产生较强的边缘响应，对DOG算子进行检验后，精确定位为特征点。剔除对噪声很敏感的点和不稳定的边缘响应点后，剩余的特征点匹配能力和抗噪声能力都比较强。低对比度的点用拟合三维二次函数滤除，得到亚像素精度关键点的位置和尺度。

1.3 极值点方向分配

关键点邻域像素的梯度方向分布特性为图像中的任一关键点确定方向，使算子具备旋转不变性。

像素点的梯度表示为：

式（4）、（5）分别是像素（x，y）处梯度的模值和方向，L 为每个极值点各自所在的尺度。

1.4 生成SIFT特征向量

任一尺度内，以关键点为中心的邻域内进行像素采样，计算出像素梯度方向的直方图，转换为128维的特征向量。实际操作是，以关键点为中心取一个正方形块，平均分为8×8的小格，计算每4×4的小块上8个方向的直方图，产生128个数据，即128维的SIFT特征向量。SIFT特征向量长度归一化，可以去除尺度变化、旋转等几何变形和光照因素的影响。

2 对特征匹配算法的改进

原SIFT算法在特征向量的计算过程中，采用主方向旋转并统计梯度直方图的方式，生成128维特征向量。图像特征匹配时计算量相当庞大，占算法全部时间的50%左右，直接影响SIFT算法的实时性。文中改进算法的主要思想是减少特征向量的计算量，提高特征匹配速度。

原SIFT算法匹配图像时，需要一幅图像中的特征点和另外一幅图像中的所有特征点进行匹配，每一个特征点有128维数据，计算量之大可想而知。改进的SIFT算法是在特征向量匹配中，通过街区距离代替欧式距离，通过极限几何约束消除多的错误匹配点对，减少匹配时间，提高算法的匹配效率，尽可能地提高SIFT的实时性。

原SIFT算法特征向量提取时，采用欧氏距离函数作为特征的相似性度量，欧氏距离是两个像素之间的直线距离，在二维情况下定义为：

而街区距离是二维图像中相应情形的推广距离，即

其中（x1，y1），（x2，y2）分别是两个像素的二维坐标，比较公式（6）和（7）可看出，L1比 L0计算量少。用线性组合后的 L1代替L0，可以降低图像匹配过程的计算量，同时减少计算的偏差。 定义一个参数 α，以 αL1代替 L0，即 L0=αL1。 很明显，L0要进行128次乘法和一次开平方的运算；而L1只需要一次乘法运算。如果图像中生成128维的SIFT特征点有k个，则每个特征点都减少了127 k次计算。算法改进后，图像匹配的匹配点对就是两点间距离最短的特征向量。此方法明显缩短了运算时间，提高了算法的效率。

3 仿真实验及结果分析

本次仿真利用MATLAB7.0编程，运行在配置为Pentium（R） Dual－Core CPU E5700 3.0 GHz、2.00 GB RAM、操作系统为Microsoft Windows7的微机平台上。文中选取内容和背景比较复杂的图像 a（图 1）和b（图2），经过多次反复实验，测算出错误匹配对、算法时间和匹配率。匹配的过程中，对算法中的值不断的调试，经过大量的测试，最合适的值在0.600～1.500之间。实验结果如下，图1和图2为原始图像a和b，在拍摄时进行了相机平移、转动和变焦操作；分别对原始图像a和原始图像b检测SIFT特征，图像a有1 147个特征点，图像b有1 032个特征点；图3是原SIFT算法匹配的结果，图4是改进SIFT算法的结果。图像匹配的匹配率是SIFT特征对减去错误匹配对后的值除以SIFT特征对的百分比，比较数据如表1所示。

表1 图像匹配比较数据Tab.1 Comparative data of image matching

图1 原始图像aFig.1 Original image a

图2 原始图像bFig.2 Original image b

图3 原SIFT算法匹配的结果Fig.3 Results of the original SIFT algorithm matching

图4 改进SIFT算法匹配的结果Fig.4 Results of the improved SIFT algorithm matching

对比后可明显看出改进算法在匹配率上比原SIFT算法高，匹配时间减少，虽然总的匹配特征对要少，但对匹配的结果影响不大。匹配率增大的同时，匹配的精度略有提高，图像的尺度、光照、视角以及噪声所导致的干扰也随之降低。本文提出的改进图像匹配特征向量的计算方法，减少了运算时间，提高了图像匹配算法的实时性。

4 结束语

本文研究原SIFT算法后，在特征向量匹配过程中，用街区距离代替欧式距离实现图像的匹配。实验结果达到了预定目标，在满足匹配率的同时，减少了匹配时间，提高了图像特征匹配的实时性。SIFT算法的可扩展性很强，可以轻松地与其他特征检测方法相结合，在今后的研究中，希望可以使用PCA-SIFT、CSIFT、SURF、ASIFT 等算法来实现图像匹配。

[1]Lowe D.Distinctive image features from scale-invariant key points[J].International Journal of Computer Vision，2004，60（2）:91-110.

[2]Ke Y，Sukthankar R.Pca-Sift:a more distinctive representation for local image descriptors [C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition，Washington，2004.

[3]Mikolajczyk K，Schmid C.A performance evaluation of local descriptors，pattern analysis and Machine Intelligence[J].IEEE Transactions，2005，27（10）:1615-1630.

[4]刘立，彭复员，赵坤.采用简化SIFT算法实现快速图像匹配[J].红外与激光工程，2008，37（1）:181-184.LIU Li，PENG Fu-yuan，ZHAO Kun.Simplified SIFT algorithm for fast image matching[J].Infrared and Laser Engineering.2008，37（1）:181-184.

[5]刘健，张国华，黄琳琳.基于改进SIFT的图像配准算法[J].北京航空航天大学学报，2010，36（9）:1121-1124.LIU Jian，ZHANG Guo-hua，HUANG Lin-lin.Image registration approach based on improved SIFT[J].Journal of Beijing University of Aeronautics and Astronautics，2010，36 （9）:1121-1124.

[6]王晓华，傅卫平，梁元月.提高SIFT特征匹配效率的方法研究[J].机械科学与技术，2009，28（9）:1252-1254.WANG Xiao-hua，FU Wei-ping，LIANG Yuan-yue.A Method for Improving SIFT Feature Matching Efficiency[J].Mechanical Science and Technology for Aerospace Engineering，2009，28（9）:1252-1254.