陳丹丹 方發(fā)明 劉惠燕

1(華東師范大學(xué)計算機科學(xué)與技術(shù)系 上海 200062)2(中國華藝廣播公司 福建 福州 350000)

0 引 言

圖像拼接[1]技術(shù)是將一組在空間上存在重疊部分的小視野圖像序列進行處理，組合成一幅自然無縫的高分辨率圖像。圖像拼接是圖像處理領(lǐng)域里的一個研究熱點，在計算機視覺、攝影測量學(xué)、醫(yī)學(xué)影像分析等領(lǐng)域均有著廣泛的應(yīng)用價值。

經(jīng)典的圖像拼接流程包括圖像配準[2]和圖像融合[3]兩個重要步驟。圖像配準指根據(jù)圖像重疊區(qū)域的特征點對[4]，計算出兩幅圖像之間的投影變換關(guān)系[5]，用于將待匹配圖像映射到同一坐標系下。此時，若拼接圖像在重疊區(qū)域的像素值直接取兩幅原圖對應(yīng)像素之間的線性加權(quán)值[6]或者基于多波段融合的值[7]，很容易致使拼接好的圖像在重疊區(qū)域出現(xiàn)目標錯位或者偽影等影響拼接質(zhì)量的問題。為了使得圖像拼接技術(shù)能夠適應(yīng)視角偏差較大、重疊部分有移動物體等難以配準的圖像場景，基于最佳拼接線[8-11]縫合待拼接圖像的方法得到了廣泛的應(yīng)用。最佳拼接線是由重疊區(qū)域的一系列坐標點連接而成，一條好的拼接線會消減甚至避免紋理差異或者移動目標等造成的拼接后影像上的重影、模糊效果。基于最佳拼接線的圖像拼接流程如圖1所示。

圖1 基于本文改進的最佳拼接線的圖像拼流程圖

當前，國內(nèi)外對圖像拼接過程中的尋找最佳拼接線的方法已有較為深入的研究。2003年，方賢勇等[12]提出基于動態(tài)規(guī)劃原理來尋找最佳拼接線的方法。該方法在計算能量函數(shù)時過分強調(diào)了圖像的顏色差異，而忽略了圖像結(jié)構(gòu)紋理的重要性，使得拼接線兩側(cè)灰度過渡不是很連續(xù)。Tang等[13]提出了一種基于貪婪算法的最佳拼接線搜索方法，但由于拼接線搜索路徑由上至下，加上搜索方向的限制，往往找到的都是局部最佳路徑，導(dǎo)致拼接線經(jīng)常從移動物體上切過。2013年，文獻[14]提出了一種新穎的最佳拼接線搜索方法，根據(jù)相似性準則分別為圖像中的像素分配兩個不同的標簽，并據(jù)此將圖像分成兩個部分。雖然該方法可以避過較大的移動目標，但計算量相對于動態(tài)規(guī)劃的時間復(fù)雜度較大。

針對上述問題，本文主要做了以下兩點改進：(1)根據(jù)顏色和紋理的相似性構(gòu)造了一個新的用于搜索最佳路徑節(jié)點的能量函數(shù)，其充分考慮了像素鄰域信息。(2)本文對傳統(tǒng)動態(tài)規(guī)劃算法中只搜索當前點在其下一行正對的三個相鄰點，改為搜索它下一行中的所有點，從而能夠在構(gòu)造的能量函數(shù)上找出一條全局最佳拼接線。沿著該拼接線將兩幅初配準好的圖像縫合到一起，便可以實現(xiàn)無偽影的圖像拼接。實驗表明，由本文算法找到的最佳拼接縫可以成功地繞過重疊區(qū)域中較大的物體。

1 傳統(tǒng)的動態(tài)規(guī)劃拼接算法

最佳拼接線搜索主要包括兩個步驟：

(1) 計算能量函數(shù)：根據(jù)重疊區(qū)域圖像的顏色和紋理的相似性信息，構(gòu)建出一個能量函數(shù)，用于最佳拼接線的搜索。

(2) 最佳拼接線搜索：利用一種搜索算法在能量函數(shù)上找出一系列坐標點(能量值越小的點說明該點對應(yīng)的顏色和紋理越相似)，組成一條能量值之和最小的拼接線。

1.1 計算能量函數(shù)

1.1.1 相似性準則定義

通常，較好的拼接線應(yīng)該使得縫合線上的點對應(yīng)的兩幅圖像差異最小，即選擇兩幅圖像之間對應(yīng)內(nèi)容相同或者極為相似的地方走。文獻[8]中將相似性準則概括為以下兩點：

(1) 在顏色強度上，縫合線上的點在兩幅原圖上對應(yīng)點的亮度差異最小。

(2) 在幾何結(jié)構(gòu)上，縫合線上的點在兩幅原圖上對應(yīng)點的結(jié)構(gòu)最相似。

1.1.2 本文提出的能量函數(shù)

根據(jù)美國國家電視制式委員會，在NTSC制式下，亮度通道Y與RGB空間中的紅(R)、綠(G)、藍(B)三色光的關(guān)系可用如下的方程描述：

Y=0.3R+0.59G+0.11B

(1)

遵循1.1.1節(jié)描述的相似性準則，本文根據(jù)重疊區(qū)域的內(nèi)容提出了新的能量函數(shù)。在度量亮度差異和紋理差異時均充分利用了其8鄰域像素的信息。首先，我們定義重疊部分對應(yīng)的亮度差異：

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

(2)

式中:(x,y)表示像素坐標，z1和z2分別表示經(jīng)式(1)計算得到的重疊區(qū)域的灰度圖，z表示兩幅灰度圖之間的亮度差異圖(如圖2所示)。從圖2中可以得知重疊區(qū)域中大部分圖像內(nèi)容的亮度和結(jié)構(gòu)是非常相近的，因為像素值非常小甚至為0 的地方占了很大一部分(圖2中黑色的部分所示)，而白色或者可見的部分則是兩幅圖像在重疊部分的亮度或者紋理的差異所致。

圖2 亮度差異圖

根據(jù)亮度差異圖，我們通過梯度算子(Roberts算子)計算出重疊部分的結(jié)構(gòu)差異圖e:

(3)

為了將亮度差異和結(jié)構(gòu)差異關(guān)聯(lián)到一起，我們使用如下公式為重疊部分的每個像素點計算一個權(quán)重F:

(4)

式中:Ci表示p點的8鄰域像素，第一項和第二項分別為p點周圍八個像素的亮度差異之和與結(jié)構(gòu)差異之和。然后分別給它們乘以一個系數(shù)，進而得到重疊部分每個點的權(quán)重F(p)。根據(jù)相似性準則的定義，結(jié)構(gòu)差異對能量函數(shù)的影響需要遠遠大于亮度差異的影響，因此我們?nèi)ˇ?=0.1、ω2=0.9。

最后，我們?yōu)橹丿B區(qū)域的每個像素都利用式(4)計算出對應(yīng)的權(quán)值，并將它們與式(3)得到的結(jié)構(gòu)差異圖相乘，得到最后的能量函數(shù)E：

E=e°F

(5)

式中:° 表示矩陣的點對點相乘。

圖3為根據(jù)式(5)得到的能量函數(shù)對應(yīng)的圖像，和圖2對比，發(fā)現(xiàn)此圖更強調(diào)目標的邊緣和結(jié)構(gòu)而更加清晰而弱化了顏色亮度的差異，符合相似性準則中規(guī)定的結(jié)構(gòu)差異的影響更重要。本文提出的能量函數(shù)主要是通過設(shè)置ω1和ω2的值來控制這二者所占的比例。

圖3 能量函數(shù)圖

1.2 傳統(tǒng)的動態(tài)規(guī)劃搜索策略

在1.1節(jié)得到的能量函數(shù)圖(圖3)上，使用傳統(tǒng)動態(tài)規(guī)劃算法檢索出一條可以盡量避免切割重疊區(qū)域內(nèi)物體的拼接線。其具體實現(xiàn)步驟如下：

1) 假設(shè)能量函數(shù)圖中第一行各列像素點都對應(yīng)一條縫合線，其能量值大小均初始化為其對應(yīng)的當前點能量值。

2) 從第二行開始，為其每一個點在上一行中選取一個最佳路徑節(jié)點。選取的具體方法是比較當前點正對的上一行中3個相鄰點的能量值，將其中的最小值對應(yīng)的列記錄下來，并將該最小值與當前點對應(yīng)的能量值相加來更新縫合線的能量值：

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)表示當前點對應(yīng)的能量值。

3) 如果縫合線當前點為圖中最后一行的點，則進行步驟4，否則返回步驟2，進行下一次擴展。

4) 選擇能量值最小的路線作為最佳縫合線：如果重疊區(qū)域中的每一列都已經(jīng)按照上述步驟計算出一條拼接線，便可從這些拼接線中選擇出最小能量值對應(yīng)那條拼接線作為最佳拼接線。

但是，由于傳統(tǒng)動態(tài)規(guī)劃算法在查找拼接線時，拼接節(jié)點只能在當前節(jié)點上一行中正對的三個相鄰的點中選取(如圖4(a)中的三個小圓圈所示)，并且每一行只能選擇一個點作為拼接點，這極大地限制了拼接線的走向，很容易導(dǎo)致得到拼接線從重疊區(qū)域內(nèi)較大的目標上穿過。圖4(c)中模擬的輸入圖像在重疊區(qū)域存在障礙物的場景，黑色虛線為傳統(tǒng)的動態(tài)規(guī)劃算法得到的拼接線，根據(jù)傳統(tǒng)方法的算法思想，該拼接線必然會穿過圖中的障礙物。

圖4 兩種動態(tài)規(guī)劃拼接算法示意圖的比較

2 改進的動態(tài)規(guī)劃拼接算法及其實現(xiàn)

傳統(tǒng)查找拼接線的動態(tài)規(guī)劃算法在搜索方向上有所限制，容易使得分割線從物體上切割過去，從而破壞了物體的完整性。為了得到一條走向更加靈活的拼接線，我們對傳統(tǒng)查找最佳拼接線的動態(tài)規(guī)劃算法在搜索方向上做了改進。

2.1 改進的動態(tài)規(guī)劃算法

傳統(tǒng)的動態(tài)規(guī)劃查找拼接線時，路徑節(jié)點只能選擇當前點在相鄰行的緊鄰的三個點，并且每一行都只能選擇一個點作為拼接縫上的點。本文將傳統(tǒng)的只查找三個點改進為可以查找一行中所有的點(如圖4(b)所示)，并且同一行中可以選擇多個點作為拼接線上路徑節(jié)點。改進后的拼接線可以有水平方向的走向，進而繞過重疊區(qū)域內(nèi)較大的移動目標。

假設(shè)我們通過數(shù)學(xué)方法計算出了重疊區(qū)域開始的第一列C1，和重疊區(qū)域結(jié)束的最后一列C2，現(xiàn)在只要根據(jù)本文的動態(tài)規(guī)劃算法找出C2-C1條最佳拼接線，并從中選擇出能量值最小的路線作為本文要找的最佳拼接線。本文改進后的動態(tài)規(guī)劃搜索最佳拼接線的詳細步驟如下：

1) 初始化兩個尺寸大小和E(E為1.1節(jié)中得到的能量函數(shù)圖)一樣的二維零矩陣M和Path，并且將E的第一行的值賦給M的第一行。

2) 從第二行開始，為第C1列到第C2列中的每一個點在上一行中選取一個或多個路徑節(jié)點。選取的具體方法是比較當前點在上一行中所有點的計算值，每一個點(i-1,k)處的值由該點在M中對應(yīng)的能量值與式(7)中定義的S(i-1,k,j)相加得到。盡管S(i-1,k,j)會隨著k遠離j而增大，但是當前縫合線對應(yīng)的能量值M(i-1,k)可能是變小的，所以可能會出現(xiàn)距離坐標(i-1,j)越遠的點對應(yīng)的計算值小于距離(i-1,j)越近的點。正因如此，本文算法才可以使得上一行中任意一個點都有可能成為拼接線上的拼接節(jié)點。

(7)

式中:S(i-1,j,k)表示第i-1行中的第k列到第j列之間所有的點在E中的對應(yīng)的能量值之和。

比較得到的第i-1行中每一個點的計算值，將最小值對應(yīng)的列k保存在矩陣Path中(i,j)點，并將該最小值與當前點(i,j)對應(yīng)的能量值E(i,j)相加來更新當前縫合線的能量值：

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

(8)

式中:col=C2-C1，即重疊部分的列數(shù)。

3) 如果縫合線當前點為重疊區(qū)域內(nèi)最后一行的點，則進行第4步，否則返回第2步，進行下一次擴展。

4) 選擇能量值最小的路線作為最佳縫合線。根據(jù)得到能量值最小的那條拼接線在圖像最后一行中的位置，從Path中反推出剩下的每一行中路徑節(jié)點位置。將這些位置根據(jù)圖4(c)示意的方法連接起來便得到一條可以沿水平方向行走的最佳拼接線。本文改進算法的具體實現(xiàn)步驟見算法1。

算法1本文改進的最佳拼接線搜索算法

輸入: 重疊區(qū)域z1和z2,重疊區(qū)域的掩碼圖像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為重疊區(qū)域亮度差異圖

∥e為重疊區(qū)域結(jié)構(gòu)差異圖

forpi∈maskdo

end

p=pcolor+pedge

//p為重疊區(qū)域內(nèi)每個像素點的權(quán)重

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 圖像縫合

首先，根據(jù)得到的最佳縫合線L分別生成兩幅以拼接后圖像的大小為尺寸的掩碼圖像。將拼接線上以及拼接線左邊填充為白色(像素值全設(shè)置為1)，右邊填充為黑色(像素值全設(shè)置為0)，得到掩碼圖圖5(左)。同理，圖5(右)為右圖的掩碼圖。 然后，將兩幅原圖分別點乘對應(yīng)的掩碼圖像，再疊加到一起就得到了最后拼接圖。最后生成的拼接圖像的像素值可以用公式表示：

(9)

圖5 最佳拼接線分割后的掩碼圖像

3 實驗結(jié)果與分析

為了說明本文算法的有效性和優(yōu)越性，分別對兩組實驗圖使用傳統(tǒng)算法和本文改進算法進行多次最佳拼接線搜索，然后從主觀視覺與客觀數(shù)據(jù)兩方面進行對比分析。本文實驗的PC環(huán)境為Intel(R) Core(TM) i7-4770 CPU, 3.4 GHz，編程語言為MATLAB 2016a。

3.1 實驗結(jié)果主觀分析

3.1.1 實驗1

圖6(a)和(b)分別為輸入圖像[15]，其中(a)在重疊區(qū)域有一輛車，(b)中則沒有。若直接使用傳統(tǒng)的線性融合方法或者多波段融合方法融合圖像，就會導(dǎo)致重疊區(qū)域出現(xiàn)偽影或者錯位。針對這種情況，通過使用最佳拼接線來縫合圖像，盡量保證原有目標的完整性的同時實現(xiàn)無偽影的圖像拼接。

圖6(c)和(d)是基于最佳拼接線縫合得到的拼接圖，圖中的黑線表示搜索到的最佳拼接線。從(c)中可以看出，由傳統(tǒng)的動態(tài)規(guī)劃算法得到的拼接線雖然成功地繞過了重疊區(qū)域的汽車，但是卻從天空中的云朵和建筑物的一角切了過去。圖中兩個黑色方框圈出來的地方，從右上角被放大的圖中可以看出建筑物在分割線的兩側(cè)出現(xiàn)了錯位。而本文改進的動態(tài)規(guī)劃找到的最佳拼接線(如圖6(d)所示)可以沿著云朵的邊緣走下去，并繞過了建筑物、人群等明顯的目標，使最終的拼接結(jié)果更加自然。可以看出，本文拼接線有水平方向的走向，而傳統(tǒng)的拼接線由于搜索路徑的限制，只能選擇當前點下一行中正下方的緊鄰的三個點中的一個，因此該拼接線最大只能沿45°方向劃分。

(a) 輸入圖像1 (b) 輸入圖像2

(c) 基于傳統(tǒng)搜索算法的拼接圖

3.1.2 實驗2

圖7中的輸入圖像(a)和(b)來自(https://github.com/yihui-he/panoram)。對于這組輸入圖像，兩種方法都得到了較好的結(jié)果，如(c)和(d)所示。盡管傳統(tǒng)的方法找到的拼接線((c)中的黑線)從房子后面的那顆大樹上穿過((c)中的黑色方框)，但這種目標場景下并看不出該拼接線有影響到圖像的接質(zhì)量。不過，相比之下本文改進算法找到的拼接線((d)中黑線)，依然選擇繞過房子后邊的大樹((d)中的黑色方框)，盡可能地保留物體的完整性。

(a) 輸入圖像1 (b) 輸入圖像2

(c) 基于傳統(tǒng)搜索算法的拼接圖

(d) 基于本文改進的拼接圖圖7 實驗2結(jié)果

3.2 實驗結(jié)果客觀分析

3.1節(jié)中的拼接結(jié)果展示了本文算法的有效性，相比于傳統(tǒng)的算法可以得到更加自然的結(jié)果。接下來，我們分別對圖6和圖7中的輸入數(shù)據(jù)進行了20次拼接實驗。每次實驗時分別計算本次實驗中的傳統(tǒng)方法與本文方法得到的最佳拼接線對應(yīng)的能量值的和，以及拼接線上拼接點的個數(shù)。然后分別計算出它們的均值，得到如表1和表2中的數(shù)據(jù)。

表1 最佳拼接線上所有點的能量值之和

表2 最佳拼接線上所有點的個數(shù)之和

從表1中可以看出：本文算法得到最佳拼接線上點的能量值的和都小于傳統(tǒng)的方法。仔細對比表1中的數(shù)據(jù)，可以發(fā)現(xiàn)每一組實驗數(shù)據(jù)都顯示了本文改進后的動態(tài)規(guī)劃算法得到的能量值之和比傳統(tǒng)的方法小10%。

表2中的數(shù)字表示的是最佳拼接線上所包含的拼接點的個數(shù)。表中的數(shù)據(jù)顯示，本文算法得到的最佳拼接線上點的個數(shù)明顯多于傳統(tǒng)方法的。這主要是因為傳統(tǒng)的動態(tài)規(guī)劃搜索算法每一次只搜索三個點，然后從三個點中選取一個作為當前行的一個拼接點。而本文改進后的動態(tài)規(guī)劃需要搜索一整行中所有的點，并且每一行中可能會有很多個點被選中為拼接點。盡管這樣會帶來時間復(fù)雜度的提升，但是本文方法保證能找到從上至下的一條最優(yōu)的路徑，而且復(fù)雜度的提升也在可容忍的范圍內(nèi)。傳統(tǒng)動態(tài)規(guī)劃算法的時間和空間復(fù)雜度都為N×M，本文改進后算法只有時間復(fù)雜度變?yōu)镹×M×M(N和M分別為圖像的行和列個數(shù))，空間復(fù)雜度依然保持不變。

4 結(jié) 語

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