基于图像自相关矩阵的改进SIFT算法研究

刘光鑫

【摘要】 针对尺度不变特征变换（SIFT）匹配算法存在计算量大、复杂性等问题，本文提出了一种基于图像自相关矩阵的迹的改进SIFT匹配算法。首先，将特征点的邻域划分为两个同心圆，再以特征点的主方向为基准方向，每次逆时针旋转度，将特征点邻域图像划分了多个区域；其次，为每个区域图像计算自相关矩阵的迹，按逆时针方向组合形成SIFT特征描述符；最后，对生成的特征描述符进行归一化处理，得到较低维数的特征描述符，新的特征描述符提高了图像匹配的效率。实验结果表明，与传统算法相比，改进的算法在保持较高匹配精度的情况下显著提高了匹配的速度。

【关键词】 SIFT算法 自相关矩阵 特征描述符 图像匹配

一、引言

近年来，许多学者对图像匹配问题做了大量的研究。按图像匹配的不变特征分类，匹配方法可分为基于全局特征和基于局部特征的两大类匹配方法。Hu不变矩，Hausdorff距离等是常用的全局匹配特征，基于这些特征的匹配方法要在整幅图像内进行搜索，计算量较大，且没有考虑局部特征，因此匹配的效果不太好。基于局部特征的匹配方法主要是基于特征点的匹配，其已成为图像配准技术的主流方向和发展趋势。目前最成功的局部匹配算子是Lowe在1999年提出的尺度不变特征变换（Scale Invariant Feature Transform），该算法较好的解决了场景部分遮挡、旋转缩放、视点变化引起的图像变形的等问题，但是算法存在因特征描述符维数过高而使匹配计算过于复杂、匹配时间过长等问题。针对生成SIFT高维特征描述向量的耗时性和匹配计算的复杂性，国内许多研究者对SIFT算法提出改进。改进算法的思想主要是在较好的保持特征描述向量的稳定性上，降低特征描述向量的维数，减少生成特征描述符计算量和提高特征匹配效率。姚文伟等[1]提出的在以特征点为中心的圆形区域内构造4个圆环，在每个圆环内分别计均匀分布的12个方向上的梯度直方图，最终生成维的特征描述向量；丁灿等[2]提出的计算以特征点为中心的8个同心方环内8个方向的梯度累加值，形成维的特征描述向量；YanKe[3]等使用PCA 对SIFT特征描述符进行降维，但该算法是在SIFT计算结果的基础上，对于可以预先计算的离线情况是有用的，但对于实时情况，反而增加了计算量。针对SIFT算子存在的计算量大等问题，本文提出了基于图像自相关矩阵的迹的改进SIFT算法。该算法降低了SIFT特征描述符的维数，提高了匹配的效率。

二、SIFT算法原理

SIFT算法通过高斯滤波保证检测出的特征点不受噪声影响，在DoG图像上寻找极值点消除了亮度变化对特征点检测的影响，基于特征点邻域梯度统计思想建立的特征描述子具有较强的抗噪声能力，最后对特征描述向量的归一化处理去除了光照的影响。上述步骤建立的特征描述算子对光照变化、噪声、图像旋转、部分遮挡等具有一定不变性、稳定性。该算法的主要步骤如下：（1）建立尺度空间和DoG金子塔；（2）关键点定位；（3）关键点主方向确定；（4）生成关键点的SIFT特征矢量。

三、改进SIFT算法

为了对SIFT算法进行改进，对上节SIFT算法各步骤在整个匹配过程所占用的时间进行了统计，结果大致如下：（1）建立图像的DOG金字塔： 3%～5%；（2）求局部极值确定关键点：3%～17%；（3）计算关键点方向：4%～15%；（4）计生成特征描述符：42%～55%。SIFT算法的（1）～（3）步骤保证了特征点对噪声、光照及旋转有较高的鲁棒性，是后续匹配效果的稳固基石，只占整个匹配过程的约一半时间，可优化的空间很少。因此改进算法主要是在特征点描述符上优化。

原SIFT算法统计特征点邻域内所有像素梯度信息，生成的SIFT特征描述子具有良好的稳定性。本文改进的SIFT算法首先使用SIFT特征检测算法前3步检测出特征点，再在每个特征点邻域内统计像素梯度直方图确定特征点的主方向，然后以特征点主方向为基准方向，每次旋转，将像素点的邻域划分为多个区域，计算每个区域的，生成的特征描述符有效避免了图像旋转而使特征描述子的改变，最后的归一化处理减少了光照变化对特征描述子的影响。改进SIFT特征描述子生成的具体步骤：

（1）使用前文介绍的SIFT算法的前3步检测出特征点并确定特征点的主方向。

（2）生成2d维的特征描述子。将特征点的邻域划分为两个同心圆，再以（1）中计算出的特征点主方向为参考方向，每次逆时针旋转角度，确定其它d-1条直线，，…，，如图1所示。计算特征点邻域每块区域的自相关矩阵M的迹Trace（M）。

选取适当的旋转角，生成相应维数的特征描述子，再对生成的特征描述子进行归一化处理。如选取，计算每个区域的自相关矩阵M的迹生成72维的特征描述符。

在匹配两幅图像过程中，把待匹配的图像称为基准图像，另一幅图像称为后续图像。使用SIFT算法检测出来特征点并构建出了特征点描述向量后，计算特征点之间的欧式距离。

在SIFT向量匹配中，采用最近邻NN方法，即待匹配特征点与后续图像中特点的最近距离与次邻近距离之间的比值来进行匹配准则。当NN比值小于设定阈值T ，则认为匹配成功，接收匹配点对。阈值的设定对匹配的结果有很大的影响，Lowe推荐使用T=0.8可以消除90%的错误匹配，而只有5%的正确匹配被剔出。

四、实验结果分析

为了验证改进的SIFT算法在保证对光照、噪声及旋转具有较高鲁棒性的同时，较原SIFT具有更高的匹配效率，本文选取2对图片进行实验，对改进的SIFT算法进行测试，实验平台为：CPU Intel P4 2.4 GHz，内存1G，Windows 7，VS2010。比较两种算法的正确匹配率、误匹配数及匹配时间。实验中最近距离/次邻近距离的域T设为0.8。特征匹配率等于正确的匹配特征点数与两幅图像的总匹配数之比。匹配结果如表1所示，效果图如图1，图2所示。

由结果可知，在图像分别存在尺度变化及旋转的条件下，36维的改进SIFT特征描述符保持了SIFT特征匹配的较高精确度，而且匹配时间大约减少10%。因此可得出改进的SIFT算法在保持较高匹配率的同时，提高了匹配的效率。

五、总结

本文针对尺度不变特征变换（SIFT）匹配算法存在计算量大、复杂性等问题，提出了基于图像自相关矩阵M的迹的改进SIFT算法，该算法在保证较高精度的特征提取的同时，降低了特征描述字的维数；在特征匹配上，采用最近邻欧氏距离作为度量标准，Best Bin First（BBF）作为搜索策略，快速计算得到粗匹配，在极线约束未知的条件下，利用RANSAC算法估计出基础矩阵，计算得到极限约束，同时利用一致性约束、唯一性约束、互对应约束剔除虚假匹配，并通过实验验证其正确性。

参 考 文 献

[1] 姚文伟. 图像匹配算法SIFT的改进[J]. 郑州轻工业学院学报，2011（6）：67-70

[2] 丁灿，曲长文等. 改进的SIFT匹配算法[J]. 计算机科学与应用，2012（2）204-208

[3] Ke Y. PCA-SIFT： a more distinctive representation for local image descriptors. CVPR 2004， 2： 506-513.

[4] Guil N.，Villalba J.，Zapata E.L..A fast hough transform for segment detection[C].IEEE Transactions on Image Processing，1995，4（11）：1541-1548

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

[6] LOWE D G. Distinctive image features from scale-invariant key-points[J]. International Journal on Computer Vision， 2004， 60（2）： 91-110.

[7] 马颂德，马正友. 计算机视觉——计算理论与算法基础[M]. 北京：科学出版社，1998.