改进的sift特征匹配方法

杨维++朱文球++罗哲++李旺

摘要：sift特征匹配算法是图像匹配算法中最为经典的算法，对图像的平移、旋转、仿射变换具有很好的鲁棒性。但其128维的特征描述向量使得处理匹配特征点计算庞大，导致时效性不高。提出了一种改进的Sift特征配准方法，将128维的特征描述向量降至40维，并且像素的描述范围也由原来的16x16扩大至20x20，减少了匹配的运算次数，缩短了图像配准时间。通过实验证明了算法的有效性，与原sift算法比较，该算法匹配时间更短，精度更高。

关键词：sift；特征点检测；特征点描述；特征匹配

中图分类号：TP3 文献标识码：A 文章编号：1009-3044（2015）25-0130-03

图像匹配是指通过一定的匹配算法在两幅或多幅图像之间识别同名点的过程，主要可分为基于灰度的匹配和基于特征的匹配。特征点是图像的本质特性，与灰度特征相比，对灰度变化、图像形变以及区域遮挡等有较好的鲁棒性，因此被广泛用于图像匹配、全景拼接、目标识别等领域。

Sift[1]算法采用一种基于尺度空间的、对图像缩放、旋转甚至仿射保持不变性的图像局部特征描述算子提取特征点，在图像处理领域应用普遍。随着计算机视觉的发展，基于图像特征点的配准方法是目前图像匹配技术的主流方向和发展趋势。因此，国内外针对特征点的提取提出了很多算法。2006年Herbert Bay等人提出了SURF[2]算法，2011年Stefan Leutenegger等人提出的BRSIK[3]算法，Ethan Rublee等人提出的ORB[4]算法以及Alexandre Alahi等人提出的FREAK[5]算法，以上所述四种算法，在时间复杂度上均优于sift算法[6]，但sift算法之所以仍被广泛应用，是由于其算法的精确性在普遍情况下要优于其他算法。国内一些研究者也提出了许多特征点检测算法，杨幸芳提出了一种基于USAN的特征检测算法[8]，王立中等人发明了一种基于图像分块的多尺度Harris特征检测算法[9]，这些新的方法在耗时上要低于原sift算法，但精确度上不如原算法。基于此类原因，文章旨在提出一种保证精确性的情况下减小时间复杂度的算法，因此提出了一种改进的sift匹配算法。

1 Sift算法简介

Sift（Scale-invariant feature transform）算法是David G.Lowe在1999年提出并于2004完善的一种基于尺度不变局部特征算法，在图像特征点匹配方面具有良好的效果，整个匹配算法大概分为以下几个部分：

1.1 生成尺度空间

尺度空间的生成是模拟图像数据的多尺度特征，Lindeberg已经证明高斯卷积核是实现尺度变换的唯一线性核。因此，一幅二维图像的尺度空间定义为（1）

1.2 计算尺度空间的极值点

建立尺度空间后，需要在此基础上寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较。如图2所示，检测点和它同尺度的8个相邻点以及上下相邻尺度对应的9×2个点共26个点比较，若该点的值比其他26个相邻点都大或者都小，那么该点被认为是图像在该尺度下的一个特征点。

1.3精确定位极值点

由于DoG值对噪声和边缘较敏感，在DoG尺度空间中检测到局部极值点还要经过进一步的检验才能精确定位为特征点。为了提高关键点的稳定性，需要对尺度空间DoG函数进行曲线拟合，利用DoG函数在尺度空间的泰勒展开式（拟合函数）为：，其中，

2.1 原算法特征点的描述

为了使描述符具有旋转不变性，需要利用图像的局部特征为给每一个关键点分配一个主方向。 利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。

处梯度的模值和方向。完成关键点的梯度计算后，使用直方图统计邻域内像素的梯度和方向，直方图的范围是0～360度，其中每10度一柱，共36 柱，随后对于直方图采取高斯平滑，以区分各像素点的影响值，离中心点越近，权值越大。直方图中最大值作为该关键点的主方向，为了增强鲁棒性，将大于主方向峰值80%的方向作为辅方向。

获得关键点主方向后，每个关键点有位置、尺度和方向三个信息[7]，取以特征点为中心的16x16像素大小的邻域，将此邻域均匀地分为4x4个子区域，对每个子区域计算梯度方向直方图。然后，对4x4个子区域的8方向梯度直方图根据位置依次排序，这样就构成了一个4x4x8=128维的特征向量，该向量就作为sift特征的描述子。

a）邻域梯度方向图 b）特征点向量图

图2 以特征点为中心取8x8的窗口

2.2 改进的sift特征描述

原sift算法描述子的维数为4x4x8=128维，像素范围为16x16。由于维数过高，计算量也是庞大的，因此，提出一种改进的特征描述子，将维数降低为40维。

在原算法像素搜索范围内降维可能会影响到配准的精度，文章降低描述子维数的同时保证精度，改进的算法以圆形区域代替原来的16x16特征区域，另外将区域扩大为20x20。

1）为了保持旋转不变性，首先将坐标轴调整到与特征方向一致的角度，新的描述子如图3所示，中心点代表特征点，用黑点表示，取以特征点为中心的16x16邻域像素，形成直径为16像素的圆形区域；

2）以为半径单位将圆划分为3个同心圆，分别计算圆内的梯度值形成8维的特征向量，3个圆环总共生成3x8=24维的特征向量，其中针对圆弧经过的像素块，分别计算其梯度值，然后以其梯度值的一半分别计入相邻的圆内与圆外两个圆环（图3右所示）。

3）在16x16像素范围内，计算除去圆内像素以外的所有像素梯度方向的累加值，形成一个8方向的种子点。在20x20像素范围内的计算除去16x16以外的所有像素点梯度方向的累加值，形成一个8方向的种子点。

4）统计所有种子点从而形成24+8+8=40维的特征向量，并且描述范围扩大到了20x20像素。

2.3 算法改进的可行性

待检测到两幅图像的所有特征点集合后，通常通过对比两集合的各个特征点来寻找匹配点对，其中基于纹理特征的相似性度量方法有欧氏距离和马氏距离，而欧式距离是采用最为广泛的方法，文章采用欧氏距离作为相似性度量方法。在原sift算法中，两图像的任意特征点分别表示为和，任意两特征点的相似性度量表示为

对于改进的算法，特征点描述子的维数从128维降到40维，则比对任意两个特征点所需运算次数为：减法40次，平方40次，加法39次，开方1次，相比较原sift算法来说，运算量大大减少，对于检测到的特征点越多的图像，该算法更能体现出优越性。

3 实验结果与分析

实验采用基于OpenCV的Visual Studio软件为实验平台，电脑系统为Windows7，CPU i5，主频为3.10GHz，内存4GB。实验首先选取实验数据集中的多组不同分辨率图像进行，之后通过自己录制的视频图像进行实验。

3.1 实验一

实验一首先采用两幅lena头像进行匹配，图像大小尺寸分别为256x256与512x512，实验结果如下图所示，分析如下表所示。

4 结束语

Sift算法的时效性难以与其他算法比较，但因其精度上的准确性，sift算法仍然被广泛应用。基于OpenCV的Visual Studio平台实验了原sift算法，并且在特征子描述方面对算法进行改进，将原算法特征描述符的维度由128为降为40维，像素搜索范围也扩大至20x20，在保证算法精确性不降低的同时提升了时效性，实验验证了该算法的可行性。

参考文献：

[1] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International journal of computer vision， 2004， 60（2）： 91-110.

[2] Bay H， Tuytelaars T， Van Gool L. Surf： Speeded up robust features[M].Computer vision–ECCV 2006. Springer Berlin Heidelberg， 2006： 404-417.

[3] Leutenegger S， Chli M， Siegwart R Y. BRISK： Binary robust invariant scalable keypoints[C].Computer Vision （ICCV）， 2011 IEEE International Conference on. IEEE， 2011： 2548-2555.

[4] Rublee E， Rabaud V， Konolige K， et al. ORB： an efficient alternative to SIFT or SURF[C]. Computer Vision （ICCV）， 2011 IEEE International Conference on. IEEE， 2011： 2564-2571.

[5] Alahi A， Ortiz R， Vandergheynst P. Freak： Fast retina keypoint[C].Computer Vision and Pattern Recognition （CVPR）， 2012 IEEE Conference on. Ieee， 2012： 510-517.

[6] 索春宝， 杨东清， 刘云鹏. 多种角度比较 SIFT， SURF， BRISK， ORB， FREAK 算法[J]. 北京测绘， 2014（4）： 23-26.

[7] 高健， 黄心汉， 彭刚， 等. 一种简化的 SIFT 图像特征点提取算法[J]. 计算机应用研究， 2008， 25（7）： 2213-2215.

[8] 杨幸芳， 黄玉美， 李艳，等. 一种基于USAN的特征点检测算法[J]. 机械科学与技术， 2011（30）：1120-1123.

[9] 王立中， 麻硕士， 薛河儒，等. 基于图像分块的多尺度Harris特征点检测算法[J]. 内蒙古大学学报：自然科学版， 2009， 40：326-329.