柯磊　刘福强　康琦

摘 要： 针对无先验信息传统算法中普遍存在的误差累计问题，提出基于加窗尺度不变特征变换（W?SIFT）和分布式优化的多图自动拼接算法。根据多图拼接应用的特性，对尺度不变特征变换算法进行修改，提出加窗SIFT算法更高效地提取待拼接图像的特征点。运用随机抽样一致（RANSAC）算法计算出两两图像的变换矩阵。之后，建立了一个分布式优化模型，求解出多图拼接的全局最优解。实验结果表明，基于加窗SIFT和分布式优化的多图自动拼接算法能够有效地消除误差累积现象，能够得到更加精确的多图拼接结果。

关键词： 分布式优化算法； 分布式优化模型； 尺度不变特征变换； 随机抽样一致； 多图自动拼接

中图分类号： TN911.73?34； TP181 文献标识码： A 文章编号： 1004?373X（2017）07?0059?04

Multi?image automatic splicing algorithm based on windowed?SIFT

and distributed optimization

KE Lei1， LIU Fuqiang2， KANG Qi2

（1. School of Transportation and Automobile Engineering， Panzhihua University， Panzhihua 617000， China；

2. School of Information and Electronics， Beijing Institute of Technology， Beijing 100081， China）

Abstract： Aiming at the error accumulation problem existing in the traditional algorithms without prior information， a multi?image automatic splicing algorithm based on windowed scale invariant feature transformation （W?SIFT） and distributed optimization is proposed. The scale invariant feature transformation algorithm is modified according to the application characteristics of the multi?image splicing. The W?SIFT algorithm is proposed to extract the feature points of the splicing image efficiently. The random sample consensus （RANSAC） method is used to calculate the transformation matrix of two images. A distributed optimization model was established to solve the global optimal solution of the multi?image splicing. The experimental results show that the multi?image automatic splicing algorithm based on W?SIFT and distributed optimization can eliminate the error accumulation phenomenon effectively， and obtain the accurate multi?image splicing results.

Keywords： distributed optimization algorithm； distributed optimization model； scale invariant feature transformation； random sample consensus； multi?image automatic splicing

0 引 言

图像拼接是计算机视觉中的一项重要研究方向，特别是在车载场景构建和街景生成中有广泛的应用。尤其是在数字地图，数字城市和自动驾驶等日益发展和普及的背景下，自动多幅图像拼接算法更是吸引了广泛的关注和研究。

在多幅图像拼接应用领域，有两类应用广泛的技术手段：一类是依据相机的先验位置信息的算法[1]；另一类是不需要相机先验位置信息的算法[2?3]。基于相机信息的这类算法依据相机信息计算出图像的相对位置，再进行图像拼接。这类方法应用广泛，并且也有良好的精度，但时刻需要知道相机的位置信息。

对于不需要相机先验信息的多图拼接算法，是基于两幅图像的自动拼接算法，拓展到多幅图像拼接应用中。Lowe提出的尺度不变特征变换（Scale Invariant Feature Transform，SIFT）特征提取精确，被广泛的应用在自动配准、拼接领域。但依据迭代公式将其运用到多幅图像拼接算法中，会存在误差累积的问题。特别当图像数量增加时，误差明显。

针对无先验信息多图拼接算法误差累积的问题，本文基于加窗尺度不变特征变换（Windowed Scale Invariant Feature Transformation，W?SIFT）和分布式优化算法，提出一种不需要先验信息的多图自动拼接算法。首先，依据多图拼接的特性修改了传统尺度不变特征变换算法，提出W?SIFT，能够快速地提取待拼接图像的有效特征点。其次，运用随机抽样一致（Random Sample Consensus，RANSAC）算法计算出两两图像的变换矩阵。之后，建立了一个分布式优化模型用于消除误差累积。求解这个分布式优化模型便可得到全局最优多图拼接结果。最后，本文进行了一系列对比实验，实验结果说明本文的算法能够高效地实现多幅图像拼接，在精度上比传统算法有较大提高。

1 加窗尺度不变特征变换算法

Lowe 提出了尺度不变特征变换（SIFT），被广泛地应用在计算机视觉各个领域。其中，在图像拼接和图像配准应用中均取得了成功。然而，Lowe的尺度不变特征变换的算法复杂度是相对较高的，本文针对多幅图像拼接的应用背景，对SIFT进行了相应的修改，提出了加窗尺度不变特征变换（W?SIFT）算法。W?SIFT在能够满足拼接需求的基础上减少了算法的复杂度。

1.1 尺度不变特征变换

SIFT包含三个基础模块：差分高斯金字塔，兴趣点筛选和描述子生成。差分高斯金字塔（DOG）用于提取尺度不变和选择不变的特征点；极值点检测用于删除边缘的点和不显著的点，以及对特征点进行拟合；描述子生成用于生成有区别能力的描述子。如图1所示，SIFT算法中，描述子生成占用计算时间约为总体时间的73%，差分高斯金字塔占用计算时间约为24%。

1.2 加窗算法

在多幅图像拼接的应用中，尺度变换并不是显著的，而旋转和仿射变换情况较显著；拼接与配准不同，拼接的有效区域在图像周边，而图像内部区域的作用并不显著。基于上述两点特性，对传统的SIFT算法进行改进，提出W?SIFT算法，在保证拼接有效性的基础上，降低了算法的复杂度。

W?SIFT算法流程如图2所示。首先，利用高斯尺度空间替代原始算法中的高斯金字塔，这样一方面节省了建立高斯金字塔的时间，另一方面也减少了一部分低分辨率（高层级）的特征点。低分辨率的特征点在拼接中是较少用到的，并且生成这些低分辨率特征点的描述子需要更复杂的计算。减少低分辨率特征点会节约更多的计算时间。

高斯空间和差分高斯空间的构建方式如下：

[L（x，y，σ）=12πσ2e-（x2+y2）2σ2*I（x，y）] （1）

[D（x，y，σ）=L（x，y，kσ）-L（x，y，σ）] （2）

式中[Ix，y]代表输入图像。

在差分高斯空间中引入理想窗函数，限制特征点的空间范围，理想窗函数如下：

[f（x，y）=1， x<τ，A-x<τ，y<τ，B-y<τ0， other] （3）

式中：[x，y]為像素坐标；[A，B]为图像尺寸；[τ]为有效拼接特征点的区域范围。

通过上述手段，W?SIFT生成的特征点较原始SIFT的特征点大幅度减少，同时又保证了拼接应用具备足够的有效特征点。并且，W?SIFT不需要在大范围进行特征点的描述，这样也大大减低了描述子生成的算法复杂度。

1.3 仿射变换与图像拼接

仿射变换能很恰当地表征图像拼接的坐标变换关系，仿射变换公式[4]如下：

[x=a1x+b1y+c1y=a2x+b2y+c2] （4）

式中：[x，y]和[x，y]分别代表待拼接图像和基准图像。

设[X=x，y，1T，][X′=x′，y′，1T，]式（4）可写成向量形式，具体如下：

其中：[X′=HXH=a1b1c1a2b2c2111]

图像拼接的任务便是估计式（4）的各个参数，也就是估计式（5）中的变化矩阵[H。]

本文首先运用W?SIFT提取出待拼接图像和基准图像中的特征点，再采用欧式距离最小的原则计算特征点的匹配对，最后利用随机抽样一致（RANSAC）[5]算法来估计转换矩阵[H。]

2 分布式优化与多图拼接

提出的W?SIFT算法实现待拼接图像和基准图像的特征点提取，利用RANSAC方法实现转换矩阵估计，从而完成待匹配图像与基准图像的拼接。传统的多图拼接方法在此基础上逐级递推，这样就造成了误差的累积。本文在传统多图拼接算法的基础上，推出了一种能够消减误差累积的分布式优化算法，用于实现高精度的多图拼接。

2.1 传统的多图拼接模型

传统的多图拼接的主要思想是以某一幅图为基准，在拼接时，某一幅图与基准图像的转换矩阵为基准图像的变换矩阵，当前图像与前一幅图像的变换矩阵和前一幅图像与基准图像的转换矩阵三者的积。具体公式[3]如下：

[Hk=ΔHkHk，k-1Hk-1] （6）

式（6）展开则如下：

[Hk=ΔHkHk，k-1ΔHk-1Hk-1，k-2…ΔH1H1，0H0] （7）

式中：基准图像为第0幅，[Hk]代表第[k]幅图像与基准图像的变换矩阵；[ΔHk]携带每次拼接完成基准图像坐标产生的变化信息；[Hk，k-1]代表第[k]幅图像与第[k-1]幅图像的变换矩阵；[H0]为单位对角阵。

可见，前一幅图像拼接误差会累积到之后的图像拼接中，会对多幅图像拼接产生较大的误差，尤其是图像数目较多的情况下。

2.2 分布式优化算法

设[Hk]为第[k]幅图像到拼接结果图像变换矩阵的最优估计，[pk]为第[k]幅图像的特征点集，[p]为拼接结果图像的特征点集，则：

[Hk=argminHkp-Hkpk2] （8）

式中[p]是未知的，用式（9）对[p]进行估计。式（8）的物理意义是：[Hk]应使拼接变换后的图像与拼接变换前的图像对应位置像素保持一致。

式（8）中，[pk]是已知量，而[p]是未知量，因此需要对[p]进行估计。估计[p]的思想是：在给定部分[p]初始值为[p0]的情况下，在第[k]次迭代，将第[k-1]次的[p]的最优估计[pk-1]进行拼接变换的点，即[Hk-1pk-1]，作为第[k]次[p]点集合的扩展。具体迭代公式如下：

[p={H0p0，H1p1，H2p2，…，Hk-1pk-1}] （9）

式中[p]在求取[Hk]时是变化的。

式（8），式（9）是利用优化的方法来尽可能消减误差累积，之所以不是避免误差累积的原因是：在不给定初始值的情况下，分布式优化会成为一个不适定问题（ill?posed problem）。因此在解决上述问题时给定一个初始值，即为[p0]。

3 实 验

本文进行了一系列实验来验证上述算法的有效性。实验是在Matlab R2013a下进行仿真，计算机性能参数为：Intel[?] Core[?] i5?3470 CPU，4 GB RAM，64位操作系统。实验仿真使用的图像均为[728×408]的24位深图。

3.1 特征提取实验

本文分别用SIFT以及W?SIFT方法实现特征点提取，并对其性能进行比较，实验结果如图3，图4所示。

对比图3，图4可以发现，W?SIFT算法对于有效特征点的提取更加高效，省略了在拼接中较少使用的特征点。在图3，图4中，黄圈面积代表待生成特征点描述子的遍历范围，W?SIFT算法遍历范围小，运算量下降。

3.2 多图拼接实验

利用W?SIFT算法提取特征点后，采取分布式优化算法实现多图拼接，对20幅图像进行多图拼接后的实验结果如图5所示。

利用W?SIFT以及分布式优化算法实现多图拼接，利用均方根误差衡量拼接精度，并结合算法使用时间衡量多图拼接算法的性能，对比结果如表2所示。

均方根误差的计算公式如下：

在表2中，W?SIFT+（8）表示W?SIFT分布式优化算法，W?SIFT+（7）表示W?SIFT传统拼接算法，SIFT+（7）表示SIFT传统拼接算法，“手动”代表手动拼接方法。

通过对比可知：W?SIFT分布式优化算法从算法所需时间上远小于SIFT传统拼接算法，主要是由于W?SIFT算法节省运算量，算法效率高。W?SIFT分布式优化算法与W?SIFT传统拼接算法有微小差别，是因为分布式优化需要进行迭代计算，然而作为多图拼接算法，算法精度的优劣直接影响着拼接图像的质量；从算法性能角度来看，W?SIFT分布式优化算法性能较其余算法有了很大的提升，可以完成高精度多图拼接。

4 结 语

本文主要提出了基于W?SIFT的图像配准方法和分布式优化算法的多图拼接算法，实现了无先验信息的实际场景图像的高精度多图拼接。提出的W?SIFT分布式优化算法从运算时间以及图像拼接性能上得到全面的优化。W?SIFT算法为加窗SIFT算法，通過在差分高斯空间加理想窗函数完成，W?SIFT算法在不影响性能的基础上大幅降低了运算量，使得算法的实现效率更高；而分布式优化算法可以大幅度消减传统拼接算法带来的误差累积问题。

本文算法虽然大幅度消减了误差累积现象，但依然存在一定误差。并且，本文算法依然需要一幅图像提供分布式优化的初始值，也就造成了拼接结果依然是以一幅图像为基准。上述两方面问题需要未来进一步的研究。

参考文献

[1] ZITOVA B， FLUSSER J. Image registration methods： a survey [J]. Image and vision computing， 2003， 21（11）： 977?1000.

[2] 黄大坤，陆冬良，严志明，等.多图无缝拼接的配准算法[J].微型电脑应用，2014（2）：62?65.

[3] SAWHNEY H S， KUMAR R. True multi?image alignment and its application to mosaicing and lens distortion correction [J]. IEEE transactions on pattern analysis and machine intelligence， 1999， 21（3）： 235?243.

[4] SANSOSTI E， BERARDINO P， MANUNTA M， et al. Geometrical SAR image registration [J]. IEEE transactions on geoscience and remote sensing， 2006， 44（10）： 2861?2870.

[5] FISCHLER M A， BOLLES R C. 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] DE CASTRO E， MORANDI C. Registration of translated and rotated images using finite Fourier transforms [J]. IEEE transactions on pattern analysis and machine intelligence， 1987， 9（5）： 700?703.

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

[8] BARNEA D I， SILVERMAN H F. A class of algorithms for fast digital image registration [J]. IEEE transactions on compu?ters， 1972， 21（2）： 179?186.

[9] 吴乐富，丁广太.基于区域的图像拼接算法[J].计算机工程与设计，2010（18）：4044?4046.

[10] 严格.基于灰度相关特征点的图像拼接算法[J].包装工程，2009（4）：82?83.

[11] 李利军，李云伟.基于图像灰度的拼接技术研究[J].计算机与数字工程，2007（9）：128?130.

[12] REDDY B S， CHATTERJI B N. An FFT?based technique for translation， rotation， and scale?invariant image registration [J]. IEEE transactions on image processing， 1996， 5（8）： 1266?1271.