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

冯文斌，刘宝华

1.燕山大学 河北省并联机器人与机电系统实验室，河北 秦皇岛 066004

2.燕山大学 机械工程学院，河北 秦皇岛 066004

1 引言

图像匹配是指通过对图像进行对比，得到不同图像之间的相似度。图像匹配在物体识别、影像缝合和追踪、机器视觉[1]及虚拟现实等领域应用广泛。

目前图像匹配算法主要分为两大类：基于灰度的匹配方法和基于特征的匹配方法。基于灰度的匹配方法主要用空间一维或二维滑动模板进行图像匹配，此方法不需对图像进行复杂的预处理，而是利用图像本身具有的灰度信息来度量图像的相似程度，具有操作简单、匹配率高等特点，但是运算量巨大，耗时较长。基于特征的匹配方法是在原始图像中提取出具有显著特征的点、线、面等匹配单元，并将这些匹配单元用于特征匹配，一般匹配速度很快，但是精度较低[2]。现在对图像进行特征提取最好的方法是由哥伦比亚大学的Lowe教授于1999年提出的SIFT算法[3]。SIFT算法是将尺度不变特征子与梯度方向描述子相结合，从而能对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换和噪声也保持一定程度的稳定性。但是SIFT的特征描述子向量是128维[4]的，导致运算量过大，计算过于复杂，这对于实时性要求比较高的情况，如目标在线识别、机器人单目视觉等存在一定的局限性。为降低特征描述子维数并提高匹配精度，科研人员提出了多种基于SIFT的改进算法[5]。将主成分分析法（Principal Component Analysis，PCA）与SIFT算法相结合[6]，可以对SIFT算子进行降维，特征描述子的维数可以从128维降到20维，但是匹配精度较差；国外的Mikolajczyk等人[7]及国内的戴金波等人[8]都认为采用圆形进行区域划分比矩形具有更好的定位功能，用扇形构建272维的梯度位置方向直方图描述符，并用主成分分析法将其降为128维，提高匹配精度。

本文将在SIFT算法的基础上采用新的关键点邻域划分方法，用分级的放射状分区代替棋盘格式的块状分区[9]，构造新的特征描述子[10]。进行关键点匹配时用马氏距离双向匹配方法代替欧氏距离匹配[11]，并利用RANSAC方法[12]进行特征匹配的优化，提高匹配率。

2 SIFT算法

SIFT算法是在尺度空间的基础上建立的，在图像的尺度空间上找出图像的局部极值点作为待选关键点，这些极值点并不全是稳定的关键点，需要剔除低对比度的关键点和不稳定的边缘响应点，以增强匹配稳定性，提高抗噪能力，然后为每个观点分配方向，生成关键点的特征描述子，使每个关键点包含有位置、尺度和方向信息，最后用特征描述子向量之间的欧氏距离对两幅图像中关键点的相似性进行判定，当距离小于预设的阈值时判定这两个关键点已匹配成功。

2.1 高斯尺度空间的建立

尺度空间思想最早是由Iijima在1962年提出的，经Witkin和Koenderink等的改进和推广逐渐得到关注。尺度空间将传统的单尺度图像信息处理技术纳入尺度不断变化的动态分析框架中，易于获取图像的本质特征，并且能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。尺度空间需要使用高斯模糊来获取，高斯卷积核是实现尺度变换的唯一变换核，并且是唯一的线性核[13]。

二维图像I(x ,y)的尺度空间L(x ,y,σ)是一个变化尺度的高斯函数G(x ,y,σ)与原函数I(x ,y)的卷积：

代表图像的像素位置，σ是尺度空间因子，值越小，图像被平滑越少。

2.2 尺度空间极值点检测

为在尺度空间检测稳定的关键点，需要建立图像的高斯差分（Difference-of Gaussian，DOG）金字塔D( )x,y,σ，它是两个相邻尺度图像的差：

在尺度空间中，一个点与本层和上下两层中相邻尺度共8+9×2=26个点进行比较，如果该点是最大值或最小值，则该点就是图像上的一个极值点，在图像空间和尺度空间都能检测到。

2.3 关键点定位及方向分配

2.3.1 精确定位关键点

通过拟合一个三维二次函数能够更精确地确定关键点的位置和尺度，去掉对比度低的关键点，同时通过主曲率设定阈值去掉DOG算子产生的不稳定的边缘响应点。

2.3.2 关键点方向分配

用与每个关键点相邻的邻域点的梯度方向为每个关键点分配方向信息，使特征描述子具备旋转不变性，梯度值和方向如下：

将关键点邻域像素的梯度方向绘制成直方图，直方图的峰值方向就代表该关键点的方向，使得每一个关键点都包含有位置、尺度及方向三种信息。

2.4 生成特征描述子

特征描述子是对关键点的描述，通过对关键点周围的像素区域进行划分并得到各个区域的梯度直方图，进而生成关键点的特征描述子，其是对图像信息的一种抽象，方便进行图像匹配。Lowe教授推荐的特征描述子是一个128维的向量。在关键点周围取一个16×16大小的区域，以4×4大小的区域为一个种子点，得到16个种子点，如图1（a），在每个种子点区域划分有8个方向（每45°取一个方向），如图1（b），将8个方向的梯度值累加并绘制梯度方向直方图，得到一个128维的描述子向量。

图1 像素窗口划分和关键点梯度方向分配

2.5 特征匹配

图像之间的匹配也就是对得到的图像关键点进行匹配，采用最近邻算法计算得到的最近邻关键点的特征向量的欧式距离与次近邻关键点的特征向量的欧氏距离的比值，并与设定的阈值比较，若比值小于设定阈值，则关键点匹配成功。

3 算法改进

3.1 特征描述子简化

原算法的特征描述子是128维的，因为维数太高，使得构建特征描述子以及最后进行匹配都需要很长时间，而且随着关键点的增加错误匹配概率上升，剔除错误匹配的耗时增加，这对实时性的要求是不利的。又因距离关键点越近的像素对关键点特征描述子的贡献越大，所以还要考虑像素与关键点距离的影响，对各个区域与关键点的距离进行加权，得到新的特征描述子。

本文对特征描述子的改进是在关键点区域大小不变的前提下，重新划分16×16大小的矩形像素区域，将以前的棋盘格式的块状分区变成分级的放射状分区，减少划分的区域（既是减少种子点数量）。首先将关键点周围8×8的矩形邻域划分成1×4=4个三角子邻域，以45°为单位取每个三角区域8个方向上的梯度累加值，得到4×8=32维的特征描述子。然后将16×16大小的矩形像素区域的外围依据对角线划分为1×4=4个梯形邻域，计算每个梯形邻域内8个方向上的梯度累加值，得到4×8=32维的特征描述子。最后将得到的两个描述子叠加起来，但因两种邻域形状不同、大小不同、方向尺度也有大的差别，需对两种描述子梯度值进行平衡，同时为突出距离关键点越近，作用越大的思想，对两类邻域的梯度值进行加权。这样总的特征描述子由这两部分描述子构成，用放射状邻域代替棋盘格式的方形邻域，并进行加权计算，与SIFT算法的特征描述子相比，这样得到的特征描述子更加全面，更能体现关键点的特征，也即是对图像造成的信息损失更小，具体划分如图2所示。从而得到一个32+32=64维的特征描述子，比原算法的128维特征描述子减少了50%，必能降低SIFT算法的计算复杂度。为了保证旋转不变性，需将最大的梯度值移到所得的64维特征描述子向量的第一个元素。描述子生成具体流程如图3所示。

图2 关键点邻域分级放射划分

图3 简化的特征描述子生成流程

为了保证光照的不变性，需将生成的64维特征描述子进行归一化处理，归一化方法为：

3.2 匹配算法改进

原算法采用欧氏距离来进行关键点匹配，匹配是单向进行的，即是从待匹配图像中寻找与匹配图像关键点相对应的点，这种匹配简单、快捷，但易产生误配点，同时由于一个关键点能有多个方向，匹配时可能产生重复匹配。欧氏距离计算公式为：

而马氏距离考虑了特征向量间的相关性，匹配时性能优于欧氏距离。因此拟采用马氏距离二次匹配算法。二次匹配在初始匹配后进行，基本思想是：

（2）ai和 bj间距离为 L(ai,bj)，bj和ai间距离为L(bj,ai)。

（3）当L(ai,bj) L(ai,bx)＜R1，1≤x≤n，并且L(bj,ai)/L(bj,ax)＜R2，1≤x≤m，x≠j，x≠i时R1为正向匹配阈值，R2为反向匹配阈值。

对有m个样本的样本空间S={s1,s2,…,sm}其任意的样本点si=(xi,yi)(i =1,2,…,m)到样本均值μ=(μx,μy)的马氏距离表示为：

式中，S为协方差矩阵，μ为样本均值，且

对比欧氏距离和马氏距离计算公式可以看出马氏距离计算较欧氏距离复杂。在一次计算中欧氏距离需要64次乘法和一次开平方，而在马氏距离的一次计算中需要128次乘法和一次开平方，运算所用时间相对较长。但是马氏距离排除了量纲的影响，具有尺度无关性，同时排除了特征向量之间相关性的干扰，在进行关键点匹配时不会产生一点多配现象，匹配准确度提高，消除错误匹配时间减少，整体效果优于欧氏距离匹配。

3.3 消除错误匹配

运用马氏距离双向匹配算法虽然提高了匹配率，但是仍有不少误配点，为了进一步滤除错误匹配，采用RANSAC（随机抽样一致性）算法，其突出优点是能鲁棒地估计模型参数，即是能从包含大量局外点的数据中估计出高精度的参数。

3.3.1 RANSAC算法原理

RANSAC算法是一种鲁棒估计模型参数算法，通过迭代方式估计数学模型参数，对一组观测数据集进行数学模型拟合，去除不属于模型的局外点及噪声[14-15]。RANSAC算法消除错误匹配即是寻找一个大小为3×3的单应性矩阵H，使满足该矩阵的数据点个数最多，有

对矩阵H进行归一化时令h33=1。

此时的单应性矩阵H有8个未知参数，至少需要8个线性方程来求解，对应到匹配点上，因为一组点可得到2个方程，则至少需要4组点才能求出矩阵H，其对应关系为：

其中(x ,y)表示原图角点位置，(x ′,y′)表示匹配图角点位置，σ为尺度系数。

RANSAC算法从数据集中随机抽取4个不共线的样本，计算出单应性矩阵H并利用得到的模型测试所有数据，计算满足模型数据点的个数及代价函数J（即投影误差），若模型为最优模型，则对应代价函数J最小，其公式为：

3.3.2 RANSAC算法具体过程

RANSAC算法通过不断选择数据集中的一组随机子集来计算模型参数，被选取的子集被假设为局内点。具体过程为：

（1）估计一个适用于假设的局内点的模型，使所有的未知参数都能在此模型下从假设的局内点计算得到。

（2）用估计的模型去验证数据集中的其他数据，如果某个点适用于估计模型，则该点也是局内点。

（3）如果有足够多的点被认为是假设的局内点，则估计的模型就是合适的。

（4）用所有假设的局内点重新估计模型。

（5）估计局内点与模型的错误率来评估模型。

（6）重复执行上述过程，每次估计的模型如果局内点太少，则被舍弃，如果比现有模型好，则保留。

迭代次数k可以从理论上进行推断。用p表示算法产生有用结果的概率，用w表示从数据集中选取一个局内点的概率。假设估计模型时需要n个点，则wn表示所有n个点均为局内点的概率，1-wn表示n个点中至少有一个为局外点的概率，而(1 -wn)k则表示算法永远选不到n个点均为局内点的概率，则有：

迭代次数k的标准偏差为：

4 结果与分析

本次实验的计算机配置为：联想G470笔记本电脑，Intel酷睿i5-2430M处理器，频率2.4 GHz，内存4 GB。程序编制与运行平台是Matlab R2012a。

为保证实验结果更加具有说服力，测试图像选用牛津大学机器人实验室图像库中的一组图像，图像库中包含有模糊图像、旋转和缩放图像、视角图像、光照图像和JPEG压缩图像等典型的变换图像。为使实验结果不受因图像大小的不同而产生的影响，将各幅图像大小均调整为320像素×240像素。

4.1 匹配性能测试

运用SIFT算法和改进的SIFT算法对测试图像进行匹配，匹配结果如图4所示，红色为SIFT算法匹配结果，亮蓝色为改进的SIFT算法匹配结果。

对各测试图像匹配后得到的匹配点对进行统计、分析后得到图5。

用正确匹配率作为评价算法好坏的一个标准，其计算公式为：

图4 匹配结果对比

图5 总匹配对数对比

计算用SIFT算法和改进的SIFT算法得到的匹配图形的正确匹配率，绘制图6。

图6 正确匹配率对比

由图4中的（a）、（b）、（c）、（d）及图5可以看出，改进后的SIFT算法的匹配点对数量明显少于原SIFT算法，这可以明显简化匹配时的计算复杂度，提高匹配速度。观察图4（e）和图5可以看出改进的SIFT算法对压缩图像匹配点数量的减少效果并不明显，这是由于图像的压缩并未对图像的信息造成损失，只是改变了图像本身的大小，两种算法提取出的关键点的总匹配对数基本相同。

观察图6可以看出，由于对生成特征描述子方法的改进，使生成的特征描述子独特性增强，更能进一步反应图像的局部特征信息。同时对匹配算法的改进使对待匹配的两关键点的特征描述子相似性度量更加准确，正确匹配率平均增加10%～15%。对于模糊图像，尽管总匹配对数减少较多，但正确匹配率相差不大，如图4（a）所示。这是由于特征描述子生成方法的改进使其能更准确地对关键点进行描述，减少了无效关键点数量，使正确匹配对数减少，正确匹配率提高较小。对于旋转和缩放图像，因为只改变了图像的角度和尺寸大小，改进的SIFT算法对正确匹配率的提高并不明显，如图4（b）所示。改进的SIFT算法对视角图像和光照图像的正确匹配率差异较大，如图4（c）、（d）所示。这主要是由于本文算法在匹配时采用的是马氏距离，计算时引入了特征向量之间的相关性，降低了对视角和光照变化的敏感性，从而显著提高了正确匹配率。

4.2 匹配时间测试

比较SIFT算法和改进的SIFT算法在图像模糊、旋转和缩放、视角改变、光照变化和JPEG压缩下的图像匹配所耗时间。由图7可以看出，改进后的SIFT算法由于特征描述子的简化运行速度大幅度提高，是原算法的5～10倍。并且随着待匹配点数目的减少，匹配耗时也在相应较少，故减少关键点数能明显减少匹配耗时。

图7 匹配耗时对比

5 结束语

本文算法对SIFT算法的特征描述子进行改进，将原有棋盘格式块状分区变成分级放射状分区，得到的特征描述子由128维降为64维，提高了特征描述子对图像局部特征的描述。并通过对特征描述子应用马氏距离双向匹配方法进行匹配及采用RANSAC方法消除误配点，使改进的SIFT算法在继承原SIFT算法对模糊、光照强度、视角、压缩、旋转和缩放等不变性优势外，又能提高正确匹配率，减少匹配耗时，匹配效果良好。但该改进算法在实际应用时也有不足之处，对于压缩图像如何能有效减少匹配点数量，需进一步研究。

[1]王民，刘伟光.基于改进SIFT特征的双目图像匹配算法[J].计算机工程与应用，2013，49（2）：203-206.

[2]孙正.数字图像处理与识别[M].北京：机械工程出版社，2014：185-186.

[3]Lowe D G.Distinctive image features from scale invariant key points[J].International Journal of Computer Vision，2004，60（2）：581-588.

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

[5]刘立，彭复员，赵坤，等.采用简化SIFT算法实现快速图像匹配[J].红外与激光工程，2008，37（1）：181-184.

[6]Yan 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，USA，2004：506-513.

[7]Mikolajczyk K，Schmid C.A performance evaluation of local descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1615-1630.

[8]戴金波，赵宏伟，刘君玲，等.一种针对于描述子的SIFT简化方法[J].仪器仪表学报，2012，33（10）：2255-2262.

[9]刘佳，傅卫平，王雯，等.基于改进SIFT算法的图像匹配[J].仪器仪表学报，2013，34（5）：1107-1112.

[10]曾峦，顾大龙.一种基于扇形区域分割的SIFT特征描述符[J].自动化学报，2012，38（9）：1513-1519.

[11]程德志，李言俊，余瑞星.基于改进SIFT算法的图像匹配方法[J].计算机仿真，2010，28（7）：285-289.

[12]赵烨，蒋建国，洪日昌.基于RANSAC的SIFT匹配优化[J].光电工程，2014，41（8）：58-65.

[13]Lindeberg T.Scale-space theory：A basic too for analyzing structures at different scales[J].Journal of Applied Statistics，1994，21：224-270.

[14]赵录刚，吴成柯.基于随机抽样一致性的多平面区域检测算法[J].计算机应用，2008，28（12）：154-157.

[15]Hartley R，Zisserman A.Multiple view geometry in computer vision[M].Cambridge UK：Cambridge University Press，2003：121-126.