一種基于改進動態規劃的最佳拼接線搜索方法

陳丹丹 方發明 劉惠燕

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 結 語

本文深入研究了圖像拼接中用于消除偽影、錯位等問題的最佳拼接線搜索算法。首先根據相似性準則定義，提出了一個考慮相鄰像素信息的能量函數。然后對傳統的動態規劃搜索方法在搜索方向上進行了改進，能夠有效避免切割重疊區域中的大部分目標，保證目標的完整性。改進后的動態規劃算法可應用于拼接視差較大或者重疊區域存在較大移動物體的場景圖，主要消除拼接影像中的偽影和錯位，從而得到一幅更加自然的拼接圖像。