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

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

0 引 言

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

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

圖1 基于本文改進(jìn)的最佳拼接線的圖像拼流程圖

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

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

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

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

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

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

1.1 計(jì)算能量函數(shù)

1.1.1 相似性準(zhǔn)則定義

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

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

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

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

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

Y=0.3R+0.59G+0.11B

(1)

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

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

(2)

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

圖2 亮度差異圖

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

(3)

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

(4)

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

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

E=e°F

(5)

式中:° 表示矩陣的點(diǎn)對(duì)點(diǎn)相乘。

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

圖3 能量函數(shù)圖

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

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

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

2) 從第二行開始，為其每一個(gè)點(diǎn)在上一行中選取一個(gè)最佳路徑節(jié)點(diǎn)。選取的具體方法是比較當(dāng)前點(diǎn)正對(duì)的上一行中3個(gè)相鄰點(diǎn)的能量值，將其中的最小值對(duì)應(yīng)的列記錄下來，并將該最小值與當(dāng)前點(diǎn)對(duì)應(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)表示縫合線當(dāng)前的能量值;E(i,j)表示當(dāng)前點(diǎn)對(duì)應(yīng)的能量值。

3) 如果縫合線當(dāng)前點(diǎn)為圖中最后一行的點(diǎn)，則進(jìn)行步驟4，否則返回步驟2，進(jìn)行下一次擴(kuò)展。

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

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

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

2 改進(jìn)的動(dòng)態(tài)規(guī)劃拼接算法及其實(shí)現(xiàn)

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

2.1 改進(jìn)的動(dòng)態(tài)規(guī)劃算法

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

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

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

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

(7)

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

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

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

(8)

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

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

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

算法1本文改進(jìn)的最佳拼接線搜索算法

輸入: 重疊區(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)每個(gè)像素點(diǎn)的權(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(右)為右圖的掩碼圖。 然后，將兩幅原圖分別點(diǎn)乘對(duì)應(yīng)的掩碼圖像，再疊加到一起就得到了最后拼接圖。最后生成的拼接圖像的像素值可以用公式表示：

(9)

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 實(shí)驗(yàn)結(jié)果主觀分析

3.1.1 實(shí)驗(yàn)1

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

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

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

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

3.1.2 實(shí)驗(yàn)2

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

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

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

(d) 基于本文改進(jìn)的拼接圖圖7 實(shí)驗(yàn)2結(jié)果

3.2 實(shí)驗(yàn)結(jié)果客觀分析

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

表1 最佳拼接線上所有點(diǎn)的能量值之和

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

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

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

4 結(jié) 語

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