一种基于改进动态规划的最佳拼接线搜索方法

陈丹丹 方发明 刘惠燕

1(华东师范大学计算机科学与技术系 上海 200062)2(中国华艺广播公司 福建 福州 350000)

0 引 言

图像拼接[1]技术是将一组在空间上存在重叠部分的小视野图像序列进行处理，组合成一幅自然无缝的高分辨率图像。图像拼接是图像处理领域里的一个研究热点，在计算机视觉、摄影测量学、医学影像分析等领域均有着广泛的应用价值。

经典的图像拼接流程包括图像配准[2]和图像融合[3]两个重要步骤。图像配准指根据图像重叠区域的特征点对[4]，计算出两幅图像之间的投影变换关系[5]，用于将待匹配图像映射到同一坐标系下。此时，若拼接图像在重叠区域的像素值直接取两幅原图对应像素之间的线性加权值[6]或者基于多波段融合的值[7]，很容易致使拼接好的图像在重叠区域出现目标错位或者伪影等影响拼接质量的问题。为了使得图像拼接技术能够适应视角偏差较大、重叠部分有移动物体等难以配准的图像场景，基于最佳拼接线[8-11]缝合待拼接图像的方法得到了广泛的应用。最佳拼接线是由重叠区域的一系列坐标点连接而成，一条好的拼接线会消减甚至避免纹理差异或者移动目标等造成的拼接后影像上的重影、模糊效果。基于最佳拼接线的图像拼接流程如图1所示。

图1 基于本文改进的最佳拼接线的图像拼流程图

当前，国内外对图像拼接过程中的寻找最佳拼接线的方法已有较为深入的研究。2003年，方贤勇等[12]提出基于动态规划原理来寻找最佳拼接线的方法。该方法在计算能量函数时过分强调了图像的颜色差异，而忽略了图像结构纹理的重要性，使得拼接线两侧灰度过渡不是很连续。Tang等[13]提出了一种基于贪婪算法的最佳拼接线搜索方法，但由于拼接线搜索路径由上至下，加上搜索方向的限制，往往找到的都是局部最佳路径，导致拼接线经常从移动物体上切过。2013年，文献[14]提出了一种新颖的最佳拼接线搜索方法，根据相似性准则分别为图像中的像素分配两个不同的标签，并据此将图像分成两个部分。虽然该方法可以避过较大的移动目标，但计算量相对于动态规划的时间复杂度较大。

针对上述问题，本文主要做了以下两点改进：(1)根据颜色和纹理的相似性构造了一个新的用于搜索最佳路径节点的能量函数，其充分考虑了像素邻域信息。(2)本文对传统动态规划算法中只搜索当前点在其下一行正对的三个相邻点，改为搜索它下一行中的所有点，从而能够在构造的能量函数上找出一条全局最佳拼接线。沿着该拼接线将两幅初配准好的图像缝合到一起，便可以实现无伪影的图像拼接。实验表明，由本文算法找到的最佳拼接缝可以成功地绕过重叠区域中较大的物体。

1 传统的动态规划拼接算法

最佳拼接线搜索主要包括两个步骤：

(1) 计算能量函数：根据重叠区域图像的颜色和纹理的相似性信息，构建出一个能量函数，用于最佳拼接线的搜索。

(2) 最佳拼接线搜索：利用一种搜索算法在能量函数上找出一系列坐标点(能量值越小的点说明该点对应的颜色和纹理越相似)，组成一条能量值之和最小的拼接线。

1.1 计算能量函数

1.1.1 相似性准则定义

通常，较好的拼接线应该使得缝合线上的点对应的两幅图像差异最小，即选择两幅图像之间对应内容相同或者极为相似的地方走。文献[8]中将相似性准则概括为以下两点：

(1) 在颜色强度上，缝合线上的点在两幅原图上对应点的亮度差异最小。

(2) 在几何结构上，缝合线上的点在两幅原图上对应点的结构最相似。

1.1.2 本文提出的能量函数

根据美国国家电视制式委员会，在NTSC制式下，亮度通道Y与RGB空间中的红(R)、绿(G)、蓝(B)三色光的关系可用如下的方程描述：

Y=0.3R+0.59G+0.11B

(1)

遵循1.1.1节描述的相似性准则，本文根据重叠区域的内容提出了新的能量函数。在度量亮度差异和纹理差异时均充分利用了其8邻域像素的信息。首先，我们定义重叠部分对应的亮度差异：

z(x,y)=|z1(x,y)-z2(x,y)|

(2)

式中:(x,y)表示像素坐标，z1和z2分别表示经式(1)计算得到的重叠区域的灰度图，z表示两幅灰度图之间的亮度差异图(如图2所示)。从图2中可以得知重叠区域中大部分图像内容的亮度和结构是非常相近的，因为像素值非常小甚至为0 的地方占了很大一部分(图2中黑色的部分所示)，而白色或者可见的部分则是两幅图像在重叠部分的亮度或者纹理的差异所致。

图2 亮度差异图

根据亮度差异图，我们通过梯度算子(Roberts算子)计算出重叠部分的结构差异图e:

(3)

为了将亮度差异和结构差异关联到一起，我们使用如下公式为重叠部分的每个像素点计算一个权重F:

(4)

式中:Ci表示p点的8邻域像素，第一项和第二项分别为p点周围八个像素的亮度差异之和与结构差异之和。然后分别给它们乘以一个系数，进而得到重叠部分每个点的权重F(p)。根据相似性准则的定义，结构差异对能量函数的影响需要远远大于亮度差异的影响，因此我们取ω1=0.1、ω2=0.9。

最后，我们为重叠区域的每个像素都利用式(4)计算出对应的权值，并将它们与式(3)得到的结构差异图相乘，得到最后的能量函数E：

E=e∘F

(5)

式中:∘ 表示矩阵的点对点相乘。

图3为根据式(5)得到的能量函数对应的图像，和图2对比，发现此图更强调目标的边缘和结构而更加清晰而弱化了颜色亮度的差异，符合相似性准则中规定的结构差异的影响更重要。本文提出的能量函数主要是通过设置ω1和ω2的值来控制这二者所占的比例。

图3 能量函数图

1.2 传统的动态规划搜索策略

在1.1节得到的能量函数图(图3)上，使用传统动态规划算法检索出一条可以尽量避免切割重叠区域内物体的拼接线。其具体实现步骤如下：

1) 假设能量函数图中第一行各列像素点都对应一条缝合线，其能量值大小均初始化为其对应的当前点能量值。

2) 从第二行开始，为其每一个点在上一行中选取一个最佳路径节点。选取的具体方法是比较当前点正对的上一行中3个相邻点的能量值，将其中的最小值对应的列记录下来，并将该最小值与当前点对应的能量值相加来更新缝合线的能量值：

M(i,j)=E(i,j)+

min(M(i-1,j-1),M(i-1,j),M(i-1,j+1))

(6)

式中：M(i,j)表示缝合线当前的能量值;E(i,j)表示当前点对应的能量值。

3) 如果缝合线当前点为图中最后一行的点，则进行步骤4，否则返回步骤2，进行下一次扩展。

4) 选择能量值最小的路线作为最佳缝合线：如果重叠区域中的每一列都已经按照上述步骤计算出一条拼接线，便可从这些拼接线中选择出最小能量值对应那条拼接线作为最佳拼接线。

但是，由于传统动态规划算法在查找拼接线时，拼接节点只能在当前节点上一行中正对的三个相邻的点中选取(如图4(a)中的三个小圆圈所示)，并且每一行只能选择一个点作为拼接点，这极大地限制了拼接线的走向，很容易导致得到拼接线从重叠区域内较大的目标上穿过。图4(c)中模拟的输入图像在重叠区域存在障碍物的场景，黑色虚线为传统的动态规划算法得到的拼接线，根据传统方法的算法思想，该拼接线必然会穿过图中的障碍物。

图4 两种动态规划拼接算法示意图的比较

2 改进的动态规划拼接算法及其实现

传统查找拼接线的动态规划算法在搜索方向上有所限制，容易使得分割线从物体上切割过去，从而破坏了物体的完整性。为了得到一条走向更加灵活的拼接线，我们对传统查找最佳拼接线的动态规划算法在搜索方向上做了改进。

2.1 改进的动态规划算法

传统的动态规划查找拼接线时，路径节点只能选择当前点在相邻行的紧邻的三个点，并且每一行都只能选择一个点作为拼接缝上的点。本文将传统的只查找三个点改进为可以查找一行中所有的点(如图4(b)所示)，并且同一行中可以选择多个点作为拼接线上路径节点。改进后的拼接线可以有水平方向的走向，进而绕过重叠区域内较大的移动目标。

假设我们通过数学方法计算出了重叠区域开始的第一列C1，和重叠区域结束的最后一列C2，现在只要根据本文的动态规划算法找出C2-C1条最佳拼接线，并从中选择出能量值最小的路线作为本文要找的最佳拼接线。本文改进后的动态规划搜索最佳拼接线的详细步骤如下：

1) 初始化两个尺寸大小和E(E为1.1节中得到的能量函数图)一样的二维零矩阵M和Path，并且将E的第一行的值赋给M的第一行。

2) 从第二行开始，为第C1列到第C2列中的每一个点在上一行中选取一个或多个路径节点。选取的具体方法是比较当前点在上一行中所有点的计算值，每一个点(i-1,k)处的值由该点在M中对应的能量值与式(7)中定义的S(i-1,k,j)相加得到。尽管S(i-1,k,j)会随着k远离j而增大，但是当前缝合线对应的能量值M(i-1,k)可能是变小的，所以可能会出现距离坐标(i-1,j)越远的点对应的计算值小于距离(i-1,j)越近的点。正因如此，本文算法才可以使得上一行中任意一个点都有可能成为拼接线上的拼接节点。

(7)

式中:S(i-1,j,k)表示第i-1行中的第k列到第j列之间所有的点在E中的对应的能量值之和。

比较得到的第i-1行中每一个点的计算值，将最小值对应的列k保存在矩阵Path中(i,j)点，并将该最小值与当前点(i,j)对应的能量值E(i,j)相加来更新当前缝合线的能量值：

M(i,j)=E(i,j)+

(8)

式中:col=C2-C1，即重叠部分的列数。

3) 如果缝合线当前点为重叠区域内最后一行的点，则进行第4步，否则返回第2步，进行下一次扩展。

4) 选择能量值最小的路线作为最佳缝合线。根据得到能量值最小的那条拼接线在图像最后一行中的位置，从Path中反推出剩下的每一行中路径节点位置。将这些位置根据图4(c)示意的方法连接起来便得到一条可以沿水平方向行走的最佳拼接线。本文改进算法的具体实现步骤见算法1。

算法1本文改进的最佳拼接线搜索算法

输入: 重叠区域z1和z2,重叠区域的掩码图像mask。

初始化:

ω1=0.1

ω2=0.9

fori∈(1,2) do

zi=0.3×zi(:,:,1)+0.59×zi(:,:,2)+0.11×zi(:,:,3)

end

z(x,y)=|z1(x,y)-z2(x,y)|

∥z为重叠区域亮度差异图

∥e为重叠区域结构差异图

forpi∈maskdo

end

p=pcolor+pedge

//p为重叠区域内每个像素点的权重

forpi=maskdo

spi(x,y)=epi(x,y)×ppi(x,y)

end

forpi=maskdo

M(i,j)=E(i,j)+

end

L=min(M)

输出: 最佳拼接线L

2.2 图像缝合

首先，根据得到的最佳缝合线L分别生成两幅以拼接后图像的大小为尺寸的掩码图像。将拼接线上以及拼接线左边填充为白色(像素值全设置为1)，右边填充为黑色(像素值全设置为0)，得到掩码图图5(左)。同理，图5(右)为右图的掩码图。 然后，将两幅原图分别点乘对应的掩码图像，再叠加到一起就得到了最后拼接图。最后生成的拼接图像的像素值可以用公式表示：

(9)

图5 最佳拼接线分割后的掩码图像

3 实验结果与分析

为了说明本文算法的有效性和优越性，分别对两组实验图使用传统算法和本文改进算法进行多次最佳拼接线搜索，然后从主观视觉与客观数据两方面进行对比分析。本文实验的PC环境为Intel(R) Core(TM) i7-4770 CPU, 3.4 GHz，编程语言为MATLAB 2016a。

3.1 实验结果主观分析

3.1.1 实验1

图6(a)和(b)分别为输入图像[15]，其中(a)在重叠区域有一辆车，(b)中则没有。若直接使用传统的线性融合方法或者多波段融合方法融合图像，就会导致重叠区域出现伪影或者错位。针对这种情况，通过使用最佳拼接线来缝合图像，尽量保证原有目标的完整性的同时实现无伪影的图像拼接。

图6(c)和(d)是基于最佳拼接线缝合得到的拼接图，图中的黑线表示搜索到的最佳拼接线。从(c)中可以看出，由传统的动态规划算法得到的拼接线虽然成功地绕过了重叠区域的汽车，但是却从天空中的云朵和建筑物的一角切了过去。图中两个黑色方框圈出来的地方，从右上角被放大的图中可以看出建筑物在分割线的两侧出现了错位。而本文改进的动态规划找到的最佳拼接线(如图6(d)所示)可以沿着云朵的边缘走下去，并绕过了建筑物、人群等明显的目标，使最终的拼接结果更加自然。可以看出，本文拼接线有水平方向的走向，而传统的拼接线由于搜索路径的限制，只能选择当前点下一行中正下方的紧邻的三个点中的一个，因此该拼接线最大只能沿45°方向划分。

(a) 输入图像1 (b) 输入图像2

(c) 基于传统搜索算法的拼接图

3.1.2 实验2

图7中的输入图像(a)和(b)来自(https://github.com/yihui-he/panoram)。对于这组输入图像，两种方法都得到了较好的结果，如(c)和(d)所示。尽管传统的方法找到的拼接线((c)中的黑线)从房子后面的那颗大树上穿过((c)中的黑色方框)，但这种目标场景下并看不出该拼接线有影响到图像的接质量。不过，相比之下本文改进算法找到的拼接线((d)中黑线)，依然选择绕过房子后边的大树((d)中的黑色方框)，尽可能地保留物体的完整性。

(a) 输入图像1 (b) 输入图像2

(c) 基于传统搜索算法的拼接图

(d) 基于本文改进的拼接图图7 实验2结果

3.2 实验结果客观分析

3.1节中的拼接结果展示了本文算法的有效性，相比于传统的算法可以得到更加自然的结果。接下来，我们分别对图6和图7中的输入数据进行了20次拼接实验。每次实验时分别计算本次实验中的传统方法与本文方法得到的最佳拼接线对应的能量值的和，以及拼接线上拼接点的个数。然后分别计算出它们的均值，得到如表1和表2中的数据。

表1 最佳拼接线上所有点的能量值之和

表2 最佳拼接线上所有点的个数之和

从表1中可以看出：本文算法得到最佳拼接线上点的能量值的和都小于传统的方法。仔细对比表1中的数据，可以发现每一组实验数据都显示了本文改进后的动态规划算法得到的能量值之和比传统的方法小10%。

表2中的数字表示的是最佳拼接线上所包含的拼接点的个数。表中的数据显示，本文算法得到的最佳拼接线上点的个数明显多于传统方法的。这主要是因为传统的动态规划搜索算法每一次只搜索三个点，然后从三个点中选取一个作为当前行的一个拼接点。而本文改进后的动态规划需要搜索一整行中所有的点，并且每一行中可能会有很多个点被选中为拼接点。尽管这样会带来时间复杂度的提升，但是本文方法保证能找到从上至下的一条最优的路径，而且复杂度的提升也在可容忍的范围内。传统动态规划算法的时间和空间复杂度都为N×M，本文改进后算法只有时间复杂度变为N×M×M(N和M分别为图像的行和列个数)，空间复杂度依然保持不变。

4 结 语

本文深入研究了图像拼接中用于消除伪影、错位等问题的最佳拼接线搜索算法。首先根据相似性准则定义，提出了一个考虑相邻像素信息的能量函数。然后对传统的动态规划搜索方法在搜索方向上进行了改进，能够有效避免切割重叠区域中的大部分目标，保证目标的完整性。改进后的动态规划算法可应用于拼接视差较大或者重叠区域存在较大移动物体的场景图，主要消除拼接影像中的伪影和错位，从而得到一幅更加自然的拼接图像。