一种基于SIFT和改进RANSAC的稳健图像拼接算法

姜小会 陈清奎　何强　栾飞　董志强

摘要：针对图像间因存在旋转以及采集图像时光线强度的差异等现象而导致的拼接效果不理想和拼接速度慢的问题，作者提出了一种基于SIFT和改进RANSAC的稳健图像拼接算法，具体包括SIFT特征提取、图像配准以及图像的加权平均融合等步骤。其中，该文重点研究了图像配准这一阶段，此阶段包括图像的初始匹配和精确配准两步，实验证明该拼接算法不仅可以很好的拼接存在平移、旋转、尺度缩放、视角以及光照变化的图像，而且较之传统的RANSAC算法，改进的RANSAC算法迭代次数变少了并且运行时间也减少了，拼接效率得到了明显的提高。

关键词：图像拼接；SIFT算法；图像配准；改进RANSAC算法；图像融合

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）01-0127-03

A Steady Image Stitching Algorithm Based on SIFT and Improved RANSAC

JIANG Xiao-hui， CHEN Qing-kui， HE Qiang， LUAN Fei， DONG Zhi-qiang

（School of Mechanical and Electrical Engineering， Shandong Jianzhu University， Jinan 250101， China）

Abstract： Taking into account the problem of poor effect and slow matching in image mosaic caused by phenomena such as the rotation and the differences in light intensity， a steady image stitching algorithm based on SIFT and improved RANSAC is proposed， specifically including SIFT feature extraction， image registration and the weighted average image fusion. Among them， the paper focuses on the image registration at this stage， this phase includes an initial matching and accurate alignment. Experimental results show that the proposed image mosaic method can not only yield good results for images with overlap region that existence translation， rotation， image scaling， image viewing angle and illumination changes， and compared with the original RANSAC algorithm， the improved method has lower computational complexity， less stitching time， and splicing efficiency has been significantly improved.

Key words： image mosaic； SIFT； image registration； RANSAC； image fusion

近年来，计算机视觉已作为重点研究的领域之一，而其中的图像拼接技术受到了人们的广泛关注。图像拼接就是将同一场景拍摄到的一組相互关联的图像序列通过配准与融合，并最终拼接为一幅完整的、宽视角的、分辨率较高的新图像。

图像配准[1]作为图像拼接技术的关键与核心，它是依据两幅图像重叠区域的一致性求解出图像间的几何变换模型，即将一幅图像经几何模型变换到另一幅图像的坐标平面上并将图像的重叠区域对准。目前，基于特征[2]的图像配准方法是研究的主要趋势，该方法是通过对特征属性的直接比较来实现的，即通过两幅图像的特征来判断它们之间的相似程度，该方法不仅计算量较小，而且具有仿射不变性与稳定性等优点。因此，该文选用特征配准中的SIFT算法来实现特征点的提取与匹配。

在图像的配准阶段，人们常采用RANSAC随机采样一致性算法[3]来计算几何变换矩阵，但是传统的RANSAC算法因迭代次数多而导致计算效率低，而且当匹配点对的“内点”（正确匹配点对）所占比例较小时，也将会对拼接算法的效率产生直接的影响。针对上述缺点，该文提出了一种改进的RANSAC算法，能快速而精确的估算变换矩阵。首先使用SIFT算法提取出特征点并对特征点对进行初始匹配，然后采用改进的RANSAC算法对初始匹配点对提纯，利用提纯后的正确匹配点对估算出变换矩阵并进行配准，最后使用加权平均法[4]对图像进行融合并最终完成图像的拼接。

1 特征点提取

SIFT（Scale Invariant Feature transform，尺度不变特征变换）算法[5][6]最早是由David G.Lowe在1999年提出，并于2004年对其总结并加以完善。SIFT算法提取出的特征不仅对图像的平移、旋转、尺度缩放具有不变性，而且对图像所受到的光照、投影与仿射的变化具有一定的鲁棒性。

1.1 尺度空间的建立

尺度空间理论是将原始图像与不同尺度因子的高斯核函数进行卷积以生成多个层次高斯金字塔，而特征点的检测就在所生成的高斯金字塔上完成。

对于一幅二维图像[I（x，y）]，在不同尺度下该图像的尺度空间函数可以定义为：

[Lx，y，σ=Gx，y，σ*I（x，y）] （1）

其中[Gx，y，σ]为二维高斯核函数表示为：

[Gx，y，σ=12πσ2e-（x2+y2）2σ2] （2）

式中：[（x，y）]表示图像I上像素点的位置；*为卷积符号；[σ]为尺度空间因子。

同时，将高斯差分尺度空间表示为：

[Dx，y，σ=Gx，y，kσ-Gx，y，σ*Ix，y=Lx，y，kσ-L（x，y，σ）] （3）

1.2 尺度空间极值点检测

在高斯差分尺度空间上检测到局部极值点，待检测的每个采样点要与其所有临近点进行比较，待检测的特征点总共需要与26个点（其中包括它同尺度的8个相邻点以及上下相邻尺度所对应的2*9个点）进行比较，这样可以确保检测到的点在尺度空间与二维图像空间都是极值点。

1.3 精确定位局部极值点

精确定位极值点包括去除低对比度的特征点和不稳定的边缘响应点。我们可以将尺度空间图像看作一个曲面，根据特征点周围的像素点的梯度分布状况，通过拟合三维二次函数来精确确定特征点的尺度和位置，以使特征点达到亚像素级精度。

1.4 生成特征向量描述符

通过式（4）和（5）计算以特征点为中心半径为R的邻域内的每个点的梯度模值[mx，y]及方向[θx，y]：

[mx，y=（Lx+1，y-Lx-1，y）2+（Lx，y+1-Lx，y-1）2] （4）

[ θx，y=tan-1（Lx，y+1-Lx，y-1Lx+1，y-Lx-1，y）] （5）

以特征点为中心的领域窗口内进行采样，并利用梯度方向直方图统计出特征点邻域内的梯度方向。在梯度方向直方图中，极值表示该特征点邻域内的梯度方向，将方向直方图中的最大值作为该特征点的主方向，并将大于直方图最大值的80%的极值保留下来作为该特征点的辅方向。当每个特征点的尺度、位置及方向确定后，以特征点为中心取16[×]16的矩形窗口区域，此区域中一个特征点由4[×]4个种子点组成，且每个种子点有8个梯度方向向量，即，每个特征点可以用一个4[×]4[×]8=128维的特征向量来精确的描述。

2 图像配准

2.1 图像间几何变换关系

由于同一场景不同视角的两幅图像间具有一一对应的几何关系，因此要将一幅图像变换到另一幅图像的坐标平面之中可以通过一个几何变换模型实现。假设基准图像和配准图像上的对应点分别为[M（x，y）]和[M'（x，y）]，那么它们之间的对应关系可以用8参数的投影变换模型（用齐次坐标表示）来描述，即：

[x'iy'i1=Hxiyi1=h1h4h7h2h5h8h3h61xiyi1] （6）

式中：[（x'i，y'i，1）]和[（xi，yi，1）]分别为[M'（x，y）] 和[M（x，y）]上第i个点的齐次坐标表示；这里的变换矩阵H有8个自由度，理论上只需4对特征点就可以估算出变换矩阵H，通过解线性方程组可得到变换矩阵H的各个参数，即可将配准图像上的各个点归一化到基准图像坐标系中，并采用最近邻特征点欧氏距离与次近邻特征点欧氏距离的比值对特征点对进行初始匹配。

2.2 改进的RANSAC算法

匹配特征点对中存在的不准确的匹配点，会对图像间几何变换模型的求解结有很大的果影响，为了提高配准的速度和准确度，该文采用改进的RANSAC算法去除所存在的不准确匹配点。具体步骤为：

1） 获取总的匹配特征点对数目M，根据公式[N=log （1-pn）log [1-（1-a）m]]确定随机采样次数N，其中[pn]=0.95，m=4，a为数据错误率。

2） 在M組匹配点对中，利用分块技术随机抽取6个不同的块并在这6块中随机选取6个特征点对，将其作为一个样本[Qi（Qi1，Qi2，Qi3，Qi4，Qi5，Qi6）] 。

3） 在样本[Qi]中随机抽取4对特征点对，并用线性方程组求出临时的变换矩阵[Hi]（[Hi1，Hi2，Hi3，Hi4，Hi5，Hi6，Hi7，Hi8，1]）。

4） 检测另外2对特征点对是否都为初始变换矩阵H内点集中的点，计算[di2（x，y）=d2（HQ，Q'）] （i=1，2，3，4，5，6）。若这2对特征点都满足[di2

5） 将[Hi]视为候选变换矩阵，计算其他的（M-6） 对特征点对到变换矩阵[Hi]距离，找到并记录下内点集[Si]中的所有内点的数目c以及变换矩阵[Hi]。

6） 判断c是否大于C=（1-a）M。若条件成立，则用[Si]重新计算变换矩阵[Hi]，否则，返回第2步。

7） 经过N次迭代随机抽样后，使用最大内点集S计算最佳变换矩阵H（[H1，H2，H3，H4，H5，H6，H7，H8，]1），结束算法。

在随机采样的过程当中可能会出现随机选取的6个特征点距离很近的现象，这将导致求解出的变换模型既不稳定也不准确，为此，该文引入了平均分块这一技术[7]。具体过程如下：首先记录所有特征点中横坐标和纵坐标的最大值与最小值，再将所有特征点所在的区域均匀的分为6*6块。第二，在目标图像所分得的6*6块中随机抽取6个不同的块；第三，在随机抽取的6个块中每块随机选取一个点并在参考图像中找到与之相对应的匹配点，就得到了6对分布较为均匀的特征点对。因此，用这样6对分布比较均匀的特征点计算出来的变换矩阵H相对会更稳定和准确。

3 实验结果与分析

为了使所提出的基于特征点的图像拼接算法得到有效的验证，该文采用普通的数码相机拍摄来自不同视角的两幅图像。实验平台为：Intel Core i3、3.30GHz、内存2GB、win7操作系统、MATLAB R2012b编程。

本文选用分辨率大小为640*480的2幅实验室内的图像进行图像的拼接如图2所示，使用MATLAB R2012b编程软件作10次拼接测试，实验流程如图1所示，最终拼接图像如图4所示。

（a）SIFT特征提取与匹配 （b）改进RANSAC提纯

通过测试计算出这两幅图像的关键特征点数、匹配点对数及平均拼接时间，待拼接图像1和图像2的关键特征点个数分别为1146和1306个，初始匹配特征点对为548对，RANSAC提纯后的匹配点对为505对，改进RANSAC提纯的匹配点对为483对，改进前后的平均拼接时间分别为4.13809s和3.17006s。

实验结果表明：采用预检测即改进的RANSAC算法有效去除了粗匹配点对中所存在的误匹配点，并提高了正确匹配点对的概率，使得该算法的迭代次数减少。因此采用改进的RANSAC算法在减少图像拼接所用时间的同时提高了拼接的速度，不仅拼接效率得到了提高而且拼接效果也较好。

4 结束语

本文研究了一种基于SIFT和改进RANSAC的稳健图像拼接算法。该算法首先使用SIFT算法提取出待拼接图像的特征点；然后将提取出的特征点进行特征匹配，其中使用了改进的 RANSAC算法提纯特征点对；最后采用简单的加权平均法进行图像融合以得到最终的拼接图像。SIFT算法保证了所要提取特征点位置的精确性及匹配的准确性，改进的RANSAC算法保证了所求取的变换矩阵的稳健性，加权平均融合法保证了图像重叠区域的平滑过渡，实现了图像的无缝拼接。实验证明运用本文方法进行图像拼接可以达到较好的效果。

参考文献：

[1] 张琳，褚龙现.基于全局拼接的航拍图像拼接算法研究[J].计算机仿真，2012（04）：282-285+300.

[2] 阮芹，彭刚，李瑞等.基于特征点的图像配准与拼接技术研究[J].计算机与数字工程，2011，39（2）：141-144，183.

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

[4] 郝飛，陈文艺.基于特征点匹配的图像拼接方法[J]. 西安邮电学院学报，2012，01：87-91.

[5] Lowe D G. Distinctive image features from scale-invariant key points. International Journal of Computer Vision， 2004， 60（2）： pp91-110.

[6] Lowe D G. Object recognition from local scale invariant features[C]//Proceeding of the Seventh International Conference on Computer Vision. Washington， DC：IEEE Computer Society， 1999：1150.

[7] 周定富，何明一，杨青，等.一种基于特征点的稳健无缝图像拼接算法[J].测控技术，2009，28（6）：32-36.