内含动态目标的图像拼接算法与优化

孙光灵

(安徽建筑大学 信息网络中心，安徽 合肥 230601)

在计算机图像领域，为了得到宽幅的全景图像(panoramic picture)必须将多个图像拼在一起。

图像拼接技术(image mosaic)是采用图像配准和图像融合技术，解决如何将小幅的照片拼接成一张宽幅照片的问题，以满足用户全景摄影的要求，被广泛应用于遥感图像处理、虚拟现实技术等领域。

作为研究热点领域之一，相关的研究人员和学者对这个领域作了探索，取得了一些进展。Barnea提出了一种配准的算法[1]，是最早发表有关图像配准的文章。1981年，研究者Lucas等运用(Newton-Raphson)图像迭代法进行有效的匹配[2]，提出了一种从图像强度估计曝光强度参数和配准参数的一般方法[3]，然后对图像进行配准和校正。尽管避免了因曝光差异造成的视差问题，但是整体效果并不理想。

增益补偿也被用在图像拼接过程中[4]，即取每个图像中的平均像素值乘以一个常系数得到的点积来实现，意图减小补偿时函数的误差。该方法在提高增益同时，也带来了新的问题。两幅图像会因亮度的不同而留下肉眼可见的接缝，由此产生了鬼影或视差。

传统的图像拼接算法都是基于静止背景的[5-6]，多张图像中的背景是静止不变。对于具有运动物体的图像拼接中，Alec Mills等提出的基于缝合线融合方法可以解决拼接具有运动物体后出现的鬼影现象[7]，但是却丢失了很多运动的目标。基于运动区域单元概念随后被提出[8]，但是对于多张图像中出现同一个运动物体并在该物体的位置发生变化时仍然出现鬼影现象。本文基于最佳缝合线的基础之上进一步完善，通过判断物体冲突与否来处理物体保留后可能会发生鬼影现象，最后根据非冲突运动物体所处的位置进行缝合线修正。

1 Sift匹配与RANSAC原理

1.1 Sift匹配及原理

Sift称为尺度不变特征变换，用来把图像数据转化局部特征，转化过程中尺度坐标不发生变化。由于Sift特征是基于图像的局部特征，具有如下优点：

1) 鲁棒性强，对视角变化、仿射变换、噪声能保持一定的稳定性，对旋转、尺度缩放、亮度变化也保持不变性；

2) 信息量很大，独特性也较好，比较适用于数据库中含有大量特征进行匹配的情形。

3) 多量性，即使少数的几个物体也可以产生大量Sift特征向量。

Sift主要流程如图1所示。

图1 Sift工作过程

其中，在第4步的匹配过程中，一般采用的是欧氏距离进行计算，找到对应的匹配点。

1.1.1 关键点检测方法

二维Gauss函数：

(1)

式中σ称为高斯核，与尺度坐标相对应。

一幅二维图像，可以定义为图像函数I(x,y)与高斯核G(x,y,σ)卷积得到：

(2)

其中，图像的尺度空间用L表示，。图像用不同的尺度表示，如同给图像变换了坐标系，新的坐标值愈小则表明该图像被平滑的也越小，这时候的尺度值也越小。

1.1.2 描述子

首先必须计算读取点8邻域最大梯度值作为主方向。在完成关键点的梯度计算后，统计邻域内像素的梯度和的直方图，如图2所示，关键点的主方向就是直方图的峰值方向。

图2 梯度方向的计算

描述子生成均以此主方向为基础，确保新生成的描述子具有旋转不变的特性。

描述子的生成方式如下：

1) 对任意一个关键点，在其所在的尺度空间，取以关键点为中心的8×8的窗口。

2) 再将每个领域分为16在个子区域,对每个子区域内统计并计算梯度直方图。

3) 对16个子区域进行排序，排序规则是根据每个子区域的8邻域梯度直方图的位置先后，生成了一个128维的向量，得到Sift描述子。

当两幅图像的Sift描述子生成后，需要对两幅图像中关键点的相似性进行度量，准则是采用关键点特征向量的欧氏距离进行判定。首先选取待拼接图像1中的某个关键点，搜索其与待拼接图像2中距离最近的前两个关键点。在这两个关键点中，如果最近的距离除以次近的距离小于某个阈值Q，则搜索出的最近匹配点正确，否则是错误匹配。

1.2 RANSAC原理及分析

RANSAC是根据样本数据集，数据集包括了有效数据和异常数据，通过数据的模型参数计算，得到有效样本的算法。

RANSAC算法中异常数据产生的原因多种多样，错误的测量、错误的假设、错误的计算等均可产生的异常数据。RANSAC算法假设，给定一组正确的数据，存在可以计算出正确数据集的方法。

首先，由于特征点的稳定性，在等待拼接的两幅图像中寻找灰度梯度最大的点作为特征点；

然后初步建立两幅图像重叠范围内的特征点之间的对应关系，进行图像间的特征匹配。根据候选匹配特征点对，用RANSAC估计算法，计算出两幅图像之间的变换矩阵。通过变换矩阵能够确定一幅图像中的点在另一幅图像中所对应的位置，变换矩阵见式(3)。

(3)

式中mi为变换矩阵元素值，(x,y)和(x′,y′)为候选匹配点对。

RANSAC估计算法的步骤如图3所示。

图3 RANSAC估计算法

根据坐标转换关系将一幅图像变换到另一幅图像上，实现两幅图像的拼接。

2 图像拼接

为将数张有重叠部分的图像拼成一幅无缝高分辨率的宽幅图像，图像配准和图像融合是其中的两个内容，拼接的过程如下：

1) 对两幅图像利用Sift算法进行特征提取。

2) 采用欧氏距离判断两幅图像中的Sift特征的相似性，并查找出匹配的特征对。

3) 利用RANSAC对步骤2的特征对进行处理，消除错误的特征对并建立射影矩阵H。

4) 利用射影矩阵H将带拼接图像的重合区域进行融合得到拼接重构的平滑无缝全景图像。

3 搜索策略

由上述图像拼接方法可以看出，一般的图像拼接方法在处理具有运动物体时会出现图像重叠而成的鬼影现象。另一种情况也有些相似，物体虽然不是同一物体，但由于图像的叠加，使这两个物体处于同一个位置，从而产生了冲突。参考文献[1]提出了一种可行的办法，可以解决这种冲突或鬼影现象，就是在两张图像的重叠区域中找出一条缝合线，缝合线会把图像分成左右两部分，左边的部分取左图像的像素，右边部分取右图像的像素，从而解决以上的鬼影和冲突现象。

图4 实验拼接图

图5 搜索策略

文献[1]的方法对强度与梯度进行了计算。利用Dijkstra搜索缝合线的思想进行缝合线的搜索。搜索时从重叠区的第一行出发建立该行上每一个像素为起点的缝合线，然后从重叠区域中寻找出一个最佳的缝合线。详细步骤如下：

Step1：初始化。首先从第一行开始，首行的各列像素点对应为一条缝合线。缝合线的强度值赋各个点的准则值，该缝合线的列值即为初始点。

Step2：延伸扩展。从Step1中计算过强度沿缝合线不断扩展，直到尾行为止。

Step3：选择最佳缝合线。从所有计算出的缝合线中选取强度值最小的那一个，作为最佳缝合线。

这种方法虽然可以消除了鬼影和冲突的现象，但是对于一些非冲突的目标，也同时被消去了，从图5(c)中，右图中的摩托车因为缝合线偏左而被消掉了。一种改进的算法通过判断重叠区域中的景象是否冲突，如果非冲突则可以通过修改缝合线保留重叠区域的一些景象，从而使得拼接更加逼真。

4 改进的搜索策略

改进的方法中采用动态规划的方法进行缝合线的搜索，而非Dijkstra方法。首先分析重叠区域中的两幅图像的物体是否有冲突，对于没有冲突的物体进行提取，在进行拼接的时候修改缝合线，把非冲突的目标也包含进去。

首先对重叠区域的图像进行二值化，图6是对图5(c)的图像进行二值化。二值图像中的白色区域是由于两幅图像中的不同景物或同一景物位置发生了改变，从而造成叠加不一致。

图6 配准后图像二值化

其次，为了标记二值图像，可以采用的方法有很多，本文是采用了连通域标记方法，根据标记后的结果提取相应连通域的所有像素。对于得到的二值图像，对其目标可以分为三种情况加以考虑：

1) 同一个物体位置发生了变化，导致叠加时不一致。这种情况可以根据第一部分的Sift进行过滤，因为在进行匹配过程中会用到Sift算法，而对于同一个物体，一般会有很多匹配对，当发现两个连通域中对应的景物在第一步处理中有正确的匹配对，这说明了该物体是因为发生了位置变化导致叠加不一致，其中的一个连通域可以通过缝合进行切割。

2) 不同时间点拍摄的两张图像在某位置分别有两个不同的物体，在进行叠加时就会发生冲突，这种景物也可以通过缝合线进行切割。图5(a)中红色的汽车与图5(b)中白色的汽车就是这种情况。

3) 某个目标在一张图像中出现，而在另一张图像中没有出现，并且该目标后面的背景与另外一张图像中对应位置的背景相一致。图5(b)中的摩托车在图5(a)中没有出现就是这种情况。图5(a)中对应位置位置是空旷的路面。这种情况可采用以下方式解决：

Step1：第一步是统计两幅图像中背景点像素值。根据图6所示的二值图像，对于像素值为0的点是左右两幅图像叠加一致的点，这些点称为背景点。

Step2：提取图像6中属于情况三的目标区域。

Step3：查找步骤二提取的目标区域对应左右图像区域是否属于背景区，如果其中一个区域是背景区，说明目标没冲突，否则按冲突处理。

5 结果与分析

本文的实验平台为Intel Core I5-4210M CPU，内存4G，实验软件为win8+matlab2012。经过实验对比，结果如图7所示。图7(a)给出的是原算法进行拼接结果，图7(b)给出的是原算法融合的缝合线。图7(c)给出的是改进算法的融合效果，从图7(c)可以看到非冲突的景物(摩托车)被包含到融合图像中并且是非常自然。图7(d)给出的是改进算法的缝合线，因为修改后的缝合线与修改前的缝合线所包含的区域没有冲突物体，所以最终缝合线通过直接水平线平移修改得到。

图7 算法比较

6 结语

笔者对具有运动物体的图像拼接方法进行了有效的改进，改进后的方法首先从重叠区域中分析两幅图像的背景像素，然后通过分析冲突目标是否存在于重叠区域中，从而确定融合图像中是否保留此目标。最后通过寻找缝合线，根据非冲突物体的状态修改缝合线得到最佳的效果。该算法相对于原算法可以生成景物更多的融合图，包含更全更多的信息，具有一定的实用价值。

参考文献：

[1]Daniel I.Barnea，Harvey F Silverman. A Class of Algorithms for Fast Digital Image Registration[J]. IEEE Transactions on Computers， 1972， 100(2): 179-186.

[2]Bruce D Lucas，TakeoKanade. An Iterative Image Registration Technique with an Application to Stereo Vision[C].// International Joint Conference on Artificial Intelligence. Morgan Kaufmann Publishers Inc. 1981:674-679.

[3]AseemAgarwala. Efficient Gradient-domain Compositing using Quadtrees[C]. ACM，2007: 94-94.

[4]Yehuda Afek，Ariel Brand. Mosaicking of OrthorectifiedAerial Images[J]. Photogrammetric Engineering and Remote Sensing， 1998，64(2): 115-124.

[5]邵聃，金立左.一种图像拼接的点特征匹配算法[J].东南大学学报(自然科学版)，2008，38(2)：150-153.

[6]Abdukholikov M, Whangbo T. Fast Image Stitching Method for Handling Dynamic Object Problems in Panoramic Images[J].Ksii Transactions on Internet & Information Systems, 2017, 11(11):5419-5435.

[7]Alec Mills，Gregory Dudek. Image Stitching with Dynamic Elements[J]. Image and Vision Computing，2009， 27(10): 1593-1602.

[8]Brown M, Lowe D G. Automatic Panoramic Image Stitching using Invariant Features[J]. International Journal of Computer Vision, 2007, 74(1):59-73.

[9]Karlinsky L, Dinerstein M, Ullman S. Unsupervised Feature Optimization (UFO): Simultaneous Selection of Multiple Features with their Detection Parameters[C]. CVPR 2009: San Francisco, CA, USA, 2009:1263-1270.

[10]AnatLevin, AssafZomet,ShmuelPeleg,et al. Seamless Image Stitching in the Gradient Domain[J]. Proc Eccv, 2004, 3024:377-389.

[11]RichardSzeliski. Image Alignment and Stitching: aTutorial[J]. Foundations and Trends in Computer Graphics and Vision， 2006，2(1): 1-104.

[12]Heung-Yeung Shum，Richard Szeliski. Systems and Experiment Paper: Construction of Panoramic Image Mosaics with Global and Local Alignment[J]. International Journal of Computer Vision， 2000，36(2): 101-130.

[13]Thomas Porter，Tom Duff. Compositing Digital Images[C]. ACM，1984:253-259.

[14]ShmuelPeleg. Elimination of Seams from Photomosaics[J]. Computer Graphics and Image Processing， 1981， 16(1): 90-94.

[15]Yang Xiong，Ken Turkowski. Registration，Calibration and Blending in Creating High Quality Panoramas[C]. IEEE，1998:69-74.

[16]潘恒辉.图像拼接中鬼影消除算法研究[J].舰船电子工程，2010，30(3)：125-127.