一种改进的动态场景拼接算法

徐光著，朱冰莲，丰建军

(重庆大学通信工程学院，重庆400030)

图像拼接是将多个有重叠视场的摄影图像结合，生成一个全景图的过程。图像拼接可分为静态场景和动态场景拼接两大类。对于静态场景来说，到目前为止，已有多种算法可以获得非常精确的结果。然而对于动态场景来说，图像拼接的主要问题是曝光差异和物体的运动。

动态场景中存在的运动物体问题，最简单的方法是像素值加权平均法，但这样会产生灰度变化明显的拼接缝。如果摄相机的移动不是纯粹的转动或在两次曝光间运动物体的位移很微小就有可能产生鬼影。消除鬼影的方法，是选择一条缝合线将两幅图像重叠区域划分成两部分，一个部分来自一幅图像。文献［1］使用了色彩强度差和梯度差建立缝合线的准则式，使用狄杰斯特拉算法搜索缝合线，对图像的曝光差异进行了补偿，最后使用多分辨率样条算法进行图像融合。该算法的不足之处是狄杰斯特拉算法相对复杂，多分辨率样条会造成合成后的图像变暗和模糊以及局部的瑕疵。文中提出改进的缝合线搜索准则式，使用复杂度较低的动态规划算法来搜索最佳缝合线，应用泊松融合算法来代替多分辨率样条融合算法。该算法可以较好地实现对动态场景的拼接。

1 最佳缝合线搜索算法

算法的流程:第一步进行图像之间的配准;第二步搜索缝合线;第三步通过泊松融合得到最终拼接结果。图1是两幅源图像。

图1 源图像

1.1 配准

使用特征点的配准方式，用匹配的特征点确定投影变换矩阵。

(1)每幅图片都有确定的SIFT特征点。这些特征点包括每幅图像上的图像金字塔，旋转，位置以及描述符。

(2)这些特征点的描述符通过最近邻搜索算法实现匹配。

(3)使用Ransac算法对配准的特征点进行筛选提纯，找到精确匹配的特征对。

(4)利用精确匹配的特征对完成映射变换，把其中一幅图像映射到另一幅图像上。

1.2 缝合线搜索

通过图像的配准之后，可以确定图像间交叠的准确位置。在图像的交叠区间搜索缝合线，把两幅图像拼接在一起。定义具有如下特征的一条理想缝合线对配准后的图像区域进行分割［2］:(1)颜色强度上要求缝合线上的像素点在两幅源图像颜色值之差最小。(2)几何结构上要求缝合线上的像素点在两幅源图像上的邻域最相似。

对于实际图像，很难得到同时满足上述两个要求的缝合线，因此需要寻找较好的满足上述两个条件的缝合线。文中，颜色值之差使用源图像之间的灰度差来代替;邻域的相似性则通过源图像的梯度图像之间的梯度差来体现。建立缝合线搜索的新准则式的具体过程如下:

1.2.1 曝光校正

光照强度真正固定不变的场景在实际生活中是不可能存在的且现代全自动化的相机会导致明显的光照强度的变化。为了做曝光校正，假设在重叠区域内，物体的反射特性保持不变。这样可以计算重叠区域的平均光照强度。

为了做曝光校正，做如下的线性估计

式中，图像之间的增益α和偏置β通过Ransac［3］算法修正，只把图像静态区域做曝光校正。

1.2.2 计算灰度差

以源图像之间颜色强度点对点的差异作为相似性度量。文献［4］提出两幅图像像素之间颜色强度差异(δI)的计算方法:即取每个像素差异的绝对值除他们的最大值。计算公式如(2)所示，颜色强度差利用灰度差来代替。

1.2.3 计算梯度差

如果两幅图像之间的曝光差异呈现明显的非线性，曝光校正就会失去作用。在这种情况下，源图像之间的灰度差则不能很好地描述两幅图像之间的相似性。此时，需要另一个差异矩阵。为得到这个差异矩阵，先把源图像转换成梯度图像，然后通过点对点之间的差异计算梯度图像之间的梯度差。梯度图像之间的梯度差(δ▽)的计算方法与两幅源图像之间的灰度差相同。

1.2.4 搜索最佳缝合线的准则式

搜索最佳缝合线的准则式由源图像的灰度差和梯度图像的梯度差来组成，如式(3)所示

权值w1，w2的选择用文献［2］提出的权值选择的办法，令w1，w2分别取如下的值:

(1)w2=(abs(In(α))+abs(β))2，式中w2是梯度差异的比重。在曝光差异比较大的图像拼接中，曝光校正中的线性估计准确性变低，灰度图像可靠性降低。因此赋予梯度图像更大的权值。

(2)w1=1－w2，式中，w1是灰度差异的比重。如果这个值为负值，那么在计算代价函数的时候把该值赋为0。因此，搜索最佳缝合线的准则式为

1.2.5 应用动态规划搜索最佳缝合线

动态规划是一种用于多阶段决策问题处理的优化方法，它是基于如下的Bellman最优化原理:作为整个过程的最优策略，无论过去的状态和决策如何，对前面的决策形成状态而言，余下的诸决策必构成最优策略。

如图2所示，若M是从A到B的最佳路线上的任意一点，那么从M到B的路线也必然是最佳路线。

图2 最佳缝合线

假定共n个阶段，第i阶段的数量指标为ri(Si，Xi)，其中Si是第i阶段决策的起点，Xi表示第i阶段的终点，同时又是下一个阶段决策的起点，那么动态规划实际上是求解下面的策略指标值

其中，opt为max或min，“*”为运算符号。对于求解最短路径问题，opt取min，“*”取“+”，以表示阶段相加和最小。

文中把式(4)作为求解策略指标值的准则式，用动态规划的思想从重叠区域的第一行出发，建立该行上每一个像素为起点的缝合线，最后从这些缝合线中寻找一个最佳的缝合线。具体的步骤如下:

(1)初始化，第一行各列像素点均对应一条缝合线，其强度值初始化为各个点的准则值，该缝合线的当前点为其所在的列值。

(2)扩展，已经计算过缝合线强度的一行向下扩展，直到最后一行为止。扩展的方法是对每一个缝合线的当前点分别与该点紧邻下一行中的3个像素准则值相加，然后进行比较，取最小强度值的列作为该缝合线的扩展方向，更新此缝合线的强度值为最小强度值，并将缝合线的当前点更新为得到最小强度值所对应的下一行中的列。

(3)选择最佳缝合线，从所有的缝合线中选取强度值最小的作为最佳缝合线。

图3 缝合线的初始化及扩展

图3说明生成缝合线开始的两步。图中的圆点代表像素点，图3(a)表示初始化一组缝合线;图3(b)表示缝合线初始化之后开始第一次扩展，其中经过第一行每个像素点的缝合线发出3根线段指向下一行紧邻的3个像素点，是线段表示缝合线的最小的扩展方向。这样可以计算到最后一行是得出最佳缝合线，搜索到的缝合线如图4所示。

图4 缝合线

1.3 图像融合

图像拼接过程中，图像融合的任务就是把配准后的两幅图像，根据对准的位置合并为一幅图像，并消除图像光强或色彩的不连续性，使拼接达到无缝的要求。常用的图像融合方法有:加权平均法，多分辨样条法和泊松融合法。

加权平均法相对简单，但是容易造成明显的拼接缝，达不到无缝拼接的效果。多分辨率样条法涉及到高斯塔和拉普拉斯塔的构造问题，因此是一种基于塔型结构的颜色融合方法。虽然该方法质量较高，但其计算工作量非常大，计算时间长。泊松融合算法可以较好地解决源图像之间曝光差异比较大的问题。文中选用泊松融合算法实现图像的融合。

2 实验结果分析

2.1 算法的复杂度比较

提出的最佳缝合线搜索准则是，使用源图像之间的灰度差来构造，复杂度比文献［2］中使用源图像之间的颜色强度差小。

文献［2］使用的Dijkstra算法进行缝合线的搜索，Dijkstra算法的时间复杂度为0(n2)，而使用的动态规划算法的时间复杂度为0(n)，很明显本算法复杂度要低于文献［2］的算法复杂度。

文献［2］采用的多分辨率样条的算法复杂度和文中采用的泊松融合的算法复杂度均为0(n3)。

由以上分析可以得出，文中算法的复杂度低于文献［2］的算法复杂度。

2.2 效果图的比较

效果图如图5所示，文献［2］的效果图如图6所示。

由效果图可以看出，文中算法与文献［2］算法都能很好地找到缝合线，并把图像拼接在一起。但文献［2］采用多分辨率拼接技术进行融合，需要进行高斯滤波，导致图像变暗和模糊，文中提出的算法使用泊松融合，一定程度上改进了图片的效果。

3 结束语

提出了把图像的灰度差异和梯度差异结合起来组成代价函数，通过动态规划搜索最佳缝合线的方式，实现动态场景拼接，成功地解决了动态场景拼接中存在的鬼影以及曝光差异的问题，具有实用意义。

［1］ ALEC MILLS，GREGORY DUDEK．Image stitching with dynamic elements［J］．Image and Vision Computing，2009，27(10):1593－1602．

［2］ UPLAQUET M L D．Building large image mosaics with invisible seam－lines［M］．Orlando，USA:SPIE Aeor Sence，1998:369－377．

［3］ 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．

［4］ DAVIS J．Mosaics of scenes with moving objects［C］．In:Computer Vision and Pattern Recognition，1998 IEEE Computer Society Conference on，1998:354－360．