变环加权SIFT算法的图像拼接

张盼　阮俊　王雅继

摘 要： 针对传统SIFT匹配算法数据量大、时间复杂度高的问题，提出基于尺度不变特征变换（SIFT）特征提取方法获得特征点，并采用变换步长的圆形区域选区对特征点进行描述，改进了SIFT特征的64维描述符和88维描述符的不足。将改进后的算法应用到图像拼接过程中，通过实验验证了改进后的方法在时间复杂度方面有所改善。

关键词： 特征点； SIFT描述符； 图像配准； 图像拼接

中图分类号： TN911.73?34 文献标识码： A 文章编号： 1004?373X（2015）19?0072?04

Abstract： Since the traditional scale invariant and feature transform （SIFT） algorithm has large data size and high time complexity， a feature extraction method based on SIFT is proposed to acquire the feature points. The region in circular area with step?conversion is adopted to describe the feature points， and the insufficient of 64?dimensional descriptor and 88?dimensional descriptor of SIFT feature is improved. The improved algorithm was applied to image mosaic process. The experiment results verify that this method has great improvement in the aspect of time complexity.

Keywords： feature point； SIFT descriptor； image registration； image mosaic

特征的提取在图像配准及拼接过程中起着关键性作用，SIFT算法[1]是David G. Lowe在1999年首先提出的用于目标识别的一个方法[2]。首先对两幅图像进行尺度和灰度空间检测，确定关键点位置和所处尺度，然后用特征点邻域梯度的主方向作为方向特征生成关键的SIFT特征向量进行匹配，然而这种算法仍然存在误匹配。2004年Lowe提出了基于SIFT（Scale Invariant and Feature Transform）尺度不变特征变换，其对尺度空间、图像缩放、仿射变换、噪音等具有不变性。随后，基于特征点不变性和区域选择的图像配准及拼接方法被广泛应用并多次改进，降低特征描述符向量的维数，提高匹配效率已成为近几年的研究热点。文献[3]提出了一种将SIFT算法结合Canny算子进行96维的特征点匹配，其维数仍然较高。

1 基于SIFT的特征描述符

SIFT算法要在尺度空间和二维平面空间中同时进行极值检测以找出局部极值点，并对提取出的特征点进行精确定位，然后根据此特征点所处位置周围邻域点的梯度方向计算出该特征点的主方向，以实现算子对几何变换和旋转的不变性。一般生成SIFT特征描述符需要以下几个步骤：生成尺度空间及检测极值点；进行特征点定位和确定特征点的方向；生成特征点描述符。

1.1 生成尺度空间及检测极值点

1.3 生成特征点描述符

如图1所示，其中每一个小方格代表一个像素点，对于每一个特征点均以该特征点为中心，在该特征点周围选取[16×16]的区域，然后将此区域平均分成[4×4]个子区域，对每个子区域计算16个像素点的主方向，这样总共计算的像素点为[S=16×16个，]同时获得[4×4×8=128]维的向量，记为SIFT 128。

1.4 SIFT 64

Tang C M等人采用环形区域取代SIFT的矩形区域[7]，以减少计算SIFT中主方向产生的时间消耗量，从而降低时间复杂度，其采用固定一个像素的步长来对特征点进行描述，如图2所示。取8个子环，每个子环像素共有8个特征向量，故该[8×8=64]维向量就定义为该特征点的特征描述符，本文中记为SIFT 64。其最外层环所在区域为[16×16]像素的方形区域中，所计算的总像素量[S8<][S<16×16]（[S8]指半径为8个像素的圆形区域的像素总数）。

1.5 SIFT 88

吴建等人在Tang的基础上对SIFT 64进行了改进，提出变步长的方法计算特征描述符[8]，如图3所示，其仍采用8环即（4，4，3，3，2，2，1，1）的环数对特征点进行描述，但其在每环的8个特征向量的基础上增加了正负灰度差累积值和灰度累加值，总维数为[8+2+1×8=88，]本文记为SIFT 88。其最外层环所在区域为[40×40]像素的方形区域中，所计算的像素量[S20

综上所述，两种算法中SIFT 64将传统SIFT 128从128维降低至64维，时间复杂度有所降低；SIFT 88虽将SIFT 64进行改进，但仍存在如下不足：

（1） SIFT 88算法中采用变步长进行采样，解决了离散像素的采样偏移，但对像素点的计算量过大，其S值远远大于SIFT 64的S值，导致时间复杂度高的问题。本文将采用另一种算法解决该问题，大大减小了S的计算量，降低了时间复杂度。

（2） SIFT 88算法采用最小值移位方法解决误匹配，但在实际中不仅存在误匹配，也存在着重复匹配的问题，其采用的算法无法去除重复匹配。本文综合穷举搜索方法并利用圆形区域的旋转不变特征同时去除重复匹配和误匹配的问题，确保了精准度。

2 改进的特征描述符

针对传统的SIFT算法、SIFT 64以及SIFT 88存在的问题，本文提出更好的改进方法：

（1） 如图4所示。本文采用变换环数代替SIFT 64的固定环数，即子环步长不是固定值，而是逐渐减小步长，越靠近中心区域，步长越大。增大亚像素的权重，尽量减少误匹配。但由于环数增多则会加大时间开销量，因此，本文在采用变换步长的基础上也对总环数进行了控制，以减小时间复杂度，即从靠近中心像素算起依次为（3，3，2，2，1，1）的环数，这样总环数为3+3+2+2+1+1=12环，像素计算量为半径为12的圆形区域，设总像素量为[S，]则[S12

（2） 新增一个权重系数（[weight1，][weight2，][weight3，] [weight4，][weight5，][weight6]），分别控制（3，3，2，2，1，1）各层对中心像素点的影响度。使得越靠近中心点，其影响度越大，越远离中心点，影响度越小。

（3） 采用变尺度滑动窗口的方法累加灰度差。即将整个环作为一个大的区域[R，]每环产生一个正的灰度累积值及一个负的灰度累积值（[HRi+，HRi-]），在累积值计算时采用大小为两个环的滑动窗口进行累加，即第2环的灰度累加值为第1环和第2环的灰度累加值之和；第3环的灰度累加值为第2环和第3环的灰度累加值之和，以此类推。计算出每环的灰度累计值，故每环描述符为二维向量。

（5） 本文采用穷举搜索方法除去误匹配和一些重复的匹配点：在基于欧式距离的初步匹配基础上进行双向匹配，并使用随机抽样一致性算法RANSAC进一步除去误匹配和一些重复的匹配点，其主要思想是两个特征集[Keypoint1i]和[Keypoint2i，]其中[Keypoint1i]中已经匹配出来的特征集为[Keypoint1m]，[Keypoint2i]已匹配的特征集[Keypoint2n]的交集，只需保留交集[Unioni=Keypoint1m?Keypoint2n]即可，再采用最小值移位法去除误匹配点。这样便可消除重复匹配点和误匹配点。

（6） 为避免光照产生的影响，本文对特征向量做归一化处理。本文改进后的特征描述符共由3部分组成：第一部分为特征描述符的8个方向（0，45，90，135，180，225，270，315）上的加权梯度大小及方向累计值；第二部分为正负灰度差累计直方图（[HRi+，][HRi-]）；第三部分为特征点周围各环的灰度累加值gray。

综上所述，局部描述子每一环的维数为8+2+1=11，总维数为[11×6=66]，在本文记为SIFT 66。最后对图像进行自动拼接[9?10]。

3 实验结果及分析

3.1 图像信息

本文采用图像为保定地质调查中心调度楼拍摄照片，图像大小为512×384像素并使用不同算法对两组图像的整体拼接时间做实验分析。在图像特征提取阶段，本文也对公认测试图像进行了验证。

3.2 实验环境

本文采用的实验环境为：CPU为Intel?CoreTMi5?2430M 2.40 GHz，内存为4.0 GB，显存为1.0 GB，操作系统为Windows 7旗舰版，仿真平台为Matlab R2012b。

3.3 实验结果

由表1～表4可以看出，本文改进后算法在保持了原算法的配准精度的基础上提高了配准的时间效率，也可以从数据分析得知，增加采样像素可以提高精度，但对于不同的特征点的邻域也会有相似邻域像素的干扰，使得过多的变换环数（即过多的采样像素）不仅增加了时间开销，并且配准精度未能得到提高。同时，由于SURF算法本身受光照和旋转的影响较大，鲁棒性不强，在特征点描述过程中也没有使用本文的加权方法，在特征点提取阶段出现的误匹配较多。在原图像配准过程中虽然时间消耗优于本文算法，但配准精度只达到了50%左右，后续对图像的拼接不能达到本文的拼接效果，并且原图像旋转和增加噪声之后其配准时间没有文中改进后的算法配准时间短。

4 结 语

将改进后的SIFT算法应用到图像拼接中，在图像的特征提取阶段将维数从128维降低至66维，提高了运行速度，并且保持了SIFT 88的稳定性和精确性。本文在拼接过程中未作更详细的处理，仍存在细微的拼接缝隙，将作为后续深入研究的方向。

参考文献

[1] LOWE D G. Object recognition from local scale?invariant features [C]// Proceedings of 1999 IEEE International Conference on Computer vision. Corfu： IEEE， 1999： 1150?1157.

[2] LOWE D G. Distinctive image features from scale?invariant key points [J]. International Journal of Computer vision， 2004， 60（2）： 91?110.

[3] 刘辉，申海龙.一种基于改进SIFT算法的图像配准方法[J].微电子学与计算机，2014，31（1）：38?42.

[4] 周峰.基于尺度不变特征变换（SIFT）的图像配准技术研究[D].昆明：昆明理工大学，2010.

[5] 冯嘉.SIFT算法的研究和改进[D].长春：吉林大学，2010.

[6] 章毓晋.图像工程：图像处理和分析[M].北京：清华大学出版社，1999.

[7] TANG Chunming. Automatic registration based on improved sift for medical microscopic sequence images [C]// 2008 Second IEEE International Symposium on Intelligent Information Technology Application. [S.l.]： IEEE， 2008， 1： 580?583.

[8] 吴建，马跃.一种改进的SIFT算法[J].计算机科学，2013，40（7）：270?272.

[9] CHALECHALE A，NAGHDY G， MERTINS A. Sketch?based image matching using angular partitioning systems [J]. IEEE Transactions on Man and Cybernetics， Part A， 2005， 35（1）： 28?41.

[10] 陈虎.基于特征点匹配的图像拼接算法研究[J].海军工程大学学报，2007，19（4）：94?97.