一種改進(jìn)的動(dòng)態(tài)場(chǎng)景拼接算法

徐光著，朱冰蓮，豐建軍

(重慶大學(xué)通信工程學(xué)院，重慶400030)

圖像拼接是將多個(gè)有重疊視場(chǎng)的攝影圖像結(jié)合，生成一個(gè)全景圖的過(guò)程。圖像拼接可分為靜態(tài)場(chǎng)景和動(dòng)態(tài)場(chǎng)景拼接兩大類(lèi)。對(duì)于靜態(tài)場(chǎng)景來(lái)說(shuō)，到目前為止，已有多種算法可以獲得非常精確的結(jié)果。然而對(duì)于動(dòng)態(tài)場(chǎng)景來(lái)說(shuō)，圖像拼接的主要問(wèn)題是曝光差異和物體的運(yùn)動(dòng)。

動(dòng)態(tài)場(chǎng)景中存在的運(yùn)動(dòng)物體問(wèn)題，最簡(jiǎn)單的方法是像素值加權(quán)平均法，但這樣會(huì)產(chǎn)生灰度變化明顯的拼接縫。如果攝相機(jī)的移動(dòng)不是純粹的轉(zhuǎn)動(dòng)或在兩次曝光間運(yùn)動(dòng)物體的位移很微小就有可能產(chǎn)生鬼影。消除鬼影的方法，是選擇一條縫合線將兩幅圖像重疊區(qū)域劃分成兩部分，一個(gè)部分來(lái)自一幅圖像。文獻(xiàn)［1］使用了色彩強(qiáng)度差和梯度差建立縫合線的準(zhǔn)則式，使用狄杰斯特拉算法搜索縫合線，對(duì)圖像的曝光差異進(jìn)行了補(bǔ)償，最后使用多分辨率樣條算法進(jìn)行圖像融合。該算法的不足之處是狄杰斯特拉算法相對(duì)復(fù)雜，多分辨率樣條會(huì)造成合成后的圖像變暗和模糊以及局部的瑕疵。文中提出改進(jìn)的縫合線搜索準(zhǔn)則式，使用復(fù)雜度較低的動(dòng)態(tài)規(guī)劃算法來(lái)搜索最佳縫合線，應(yīng)用泊松融合算法來(lái)代替多分辨率樣條融合算法。該算法可以較好地實(shí)現(xiàn)對(duì)動(dòng)態(tài)場(chǎng)景的拼接。

1 最佳縫合線搜索算法

算法的流程:第一步進(jìn)行圖像之間的配準(zhǔn);第二步搜索縫合線;第三步通過(guò)泊松融合得到最終拼接結(jié)果。圖1是兩幅源圖像。

圖1 源圖像

1.1 配準(zhǔn)

使用特征點(diǎn)的配準(zhǔn)方式，用匹配的特征點(diǎn)確定投影變換矩陣。

(1)每幅圖片都有確定的SIFT特征點(diǎn)。這些特征點(diǎn)包括每幅圖像上的圖像金字塔，旋轉(zhuǎn)，位置以及描述符。

(2)這些特征點(diǎn)的描述符通過(guò)最近鄰搜索算法實(shí)現(xiàn)匹配。

(3)使用Ransac算法對(duì)配準(zhǔn)的特征點(diǎn)進(jìn)行篩選提純，找到精確匹配的特征對(duì)。

(4)利用精確匹配的特征對(duì)完成映射變換，把其中一幅圖像映射到另一幅圖像上。

1.2 縫合線搜索

通過(guò)圖像的配準(zhǔn)之后，可以確定圖像間交疊的準(zhǔn)確位置。在圖像的交疊區(qū)間搜索縫合線，把兩幅圖像拼接在一起。定義具有如下特征的一條理想縫合線對(duì)配準(zhǔn)后的圖像區(qū)域進(jìn)行分割［2］:(1)顏色強(qiáng)度上要求縫合線上的像素點(diǎn)在兩幅源圖像顏色值之差最小。(2)幾何結(jié)構(gòu)上要求縫合線上的像素點(diǎn)在兩幅源圖像上的鄰域最相似。

對(duì)于實(shí)際圖像，很難得到同時(shí)滿足上述兩個(gè)要求的縫合線，因此需要尋找較好的滿足上述兩個(gè)條件的縫合線。文中，顏色值之差使用源圖像之間的灰度差來(lái)代替;鄰域的相似性則通過(guò)源圖像的梯度圖像之間的梯度差來(lái)體現(xiàn)。建立縫合線搜索的新準(zhǔn)則式的具體過(guò)程如下:

1.2.1 曝光校正

光照強(qiáng)度真正固定不變的場(chǎng)景在實(shí)際生活中是不可能存在的且現(xiàn)代全自動(dòng)化的相機(jī)會(huì)導(dǎo)致明顯的光照強(qiáng)度的變化。為了做曝光校正，假設(shè)在重疊區(qū)域內(nèi)，物體的反射特性保持不變。這樣可以計(jì)算重疊區(qū)域的平均光照強(qiáng)度。

為了做曝光校正，做如下的線性估計(jì)

式中，圖像之間的增益α和偏置β通過(guò)Ransac［3］算法修正，只把圖像靜態(tài)區(qū)域做曝光校正。

1.2.2 計(jì)算灰度差

以源圖像之間顏色強(qiáng)度點(diǎn)對(duì)點(diǎn)的差異作為相似性度量。文獻(xiàn)［4］提出兩幅圖像像素之間顏色強(qiáng)度差異(δI)的計(jì)算方法:即取每個(gè)像素差異的絕對(duì)值除他們的最大值。計(jì)算公式如(2)所示，顏色強(qiáng)度差利用灰度差來(lái)代替。

1.2.3 計(jì)算梯度差

如果兩幅圖像之間的曝光差異呈現(xiàn)明顯的非線性，曝光校正就會(huì)失去作用。在這種情況下，源圖像之間的灰度差則不能很好地描述兩幅圖像之間的相似性。此時(shí)，需要另一個(gè)差異矩陣。為得到這個(gè)差異矩陣，先把源圖像轉(zhuǎn)換成梯度圖像，然后通過(guò)點(diǎn)對(duì)點(diǎn)之間的差異計(jì)算梯度圖像之間的梯度差。梯度圖像之間的梯度差(δ▽)的計(jì)算方法與兩幅源圖像之間的灰度差相同。

1.2.4 搜索最佳縫合線的準(zhǔn)則式

搜索最佳縫合線的準(zhǔn)則式由源圖像的灰度差和梯度圖像的梯度差來(lái)組成，如式(3)所示

權(quán)值w1，w2的選擇用文獻(xiàn)［2］提出的權(quán)值選擇的辦法，令w1，w2分別取如下的值:

(1)w2=(abs(In(α))+abs(β))2，式中w2是梯度差異的比重。在曝光差異比較大的圖像拼接中，曝光校正中的線性估計(jì)準(zhǔn)確性變低，灰度圖像可靠性降低。因此賦予梯度圖像更大的權(quán)值。

(2)w1=1－w2，式中，w1是灰度差異的比重。如果這個(gè)值為負(fù)值，那么在計(jì)算代價(jià)函數(shù)的時(shí)候把該值賦為0。因此，搜索最佳縫合線的準(zhǔn)則式為

1.2.5 應(yīng)用動(dòng)態(tài)規(guī)劃搜索最佳縫合線

動(dòng)態(tài)規(guī)劃是一種用于多階段決策問(wèn)題處理的優(yōu)化方法，它是基于如下的Bellman最優(yōu)化原理:作為整個(gè)過(guò)程的最優(yōu)策略，無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)前面的決策形成狀態(tài)而言，余下的諸決策必構(gòu)成最優(yōu)策略。

如圖2所示，若M是從A到B的最佳路線上的任意一點(diǎn)，那么從M到B的路線也必然是最佳路線。

圖2 最佳縫合線

假定共n個(gè)階段，第i階段的數(shù)量指標(biāo)為ri(Si，Xi)，其中Si是第i階段決策的起點(diǎn)，Xi表示第i階段的終點(diǎn)，同時(shí)又是下一個(gè)階段決策的起點(diǎn)，那么動(dòng)態(tài)規(guī)劃實(shí)際上是求解下面的策略指標(biāo)值

其中，opt為max或min，“*”為運(yùn)算符號(hào)。對(duì)于求解最短路徑問(wèn)題，opt取min，“*”取“+”，以表示階段相加和最小。

文中把式(4)作為求解策略指標(biāo)值的準(zhǔn)則式，用動(dòng)態(tài)規(guī)劃的思想從重疊區(qū)域的第一行出發(fā)，建立該行上每一個(gè)像素為起點(diǎn)的縫合線，最后從這些縫合線中尋找一個(gè)最佳的縫合線。具體的步驟如下:

(1)初始化，第一行各列像素點(diǎn)均對(duì)應(yīng)一條縫合線，其強(qiáng)度值初始化為各個(gè)點(diǎn)的準(zhǔn)則值，該縫合線的當(dāng)前點(diǎn)為其所在的列值。

(2)擴(kuò)展，已經(jīng)計(jì)算過(guò)縫合線強(qiáng)度的一行向下擴(kuò)展，直到最后一行為止。擴(kuò)展的方法是對(duì)每一個(gè)縫合線的當(dāng)前點(diǎn)分別與該點(diǎn)緊鄰下一行中的3個(gè)像素準(zhǔn)則值相加，然后進(jìn)行比較，取最小強(qiáng)度值的列作為該縫合線的擴(kuò)展方向，更新此縫合線的強(qiáng)度值為最小強(qiáng)度值，并將縫合線的當(dāng)前點(diǎn)更新為得到最小強(qiáng)度值所對(duì)應(yīng)的下一行中的列。

(3)選擇最佳縫合線，從所有的縫合線中選取強(qiáng)度值最小的作為最佳縫合線。

圖3 縫合線的初始化及擴(kuò)展

圖3說(shuō)明生成縫合線開(kāi)始的兩步。圖中的圓點(diǎn)代表像素點(diǎn)，圖3(a)表示初始化一組縫合線;圖3(b)表示縫合線初始化之后開(kāi)始第一次擴(kuò)展，其中經(jīng)過(guò)第一行每個(gè)像素點(diǎn)的縫合線發(fā)出3根線段指向下一行緊鄰的3個(gè)像素點(diǎn)，是線段表示縫合線的最小的擴(kuò)展方向。這樣可以計(jì)算到最后一行是得出最佳縫合線，搜索到的縫合線如圖4所示。

圖4 縫合線

1.3 圖像融合

圖像拼接過(guò)程中，圖像融合的任務(wù)就是把配準(zhǔn)后的兩幅圖像，根據(jù)對(duì)準(zhǔn)的位置合并為一幅圖像，并消除圖像光強(qiáng)或色彩的不連續(xù)性，使拼接達(dá)到無(wú)縫的要求。常用的圖像融合方法有:加權(quán)平均法，多分辨樣條法和泊松融合法。

加權(quán)平均法相對(duì)簡(jiǎn)單，但是容易造成明顯的拼接縫，達(dá)不到無(wú)縫拼接的效果。多分辨率樣條法涉及到高斯塔和拉普拉斯塔的構(gòu)造問(wèn)題，因此是一種基于塔型結(jié)構(gòu)的顏色融合方法。雖然該方法質(zhì)量較高，但其計(jì)算工作量非常大，計(jì)算時(shí)間長(zhǎng)。泊松融合算法可以較好地解決源圖像之間曝光差異比較大的問(wèn)題。文中選用泊松融合算法實(shí)現(xiàn)圖像的融合。

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

2.1 算法的復(fù)雜度比較

提出的最佳縫合線搜索準(zhǔn)則是，使用源圖像之間的灰度差來(lái)構(gòu)造，復(fù)雜度比文獻(xiàn)［2］中使用源圖像之間的顏色強(qiáng)度差小。

文獻(xiàn)［2］使用的Dijkstra算法進(jìn)行縫合線的搜索，Dijkstra算法的時(shí)間復(fù)雜度為0(n2)，而使用的動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度為0(n)，很明顯本算法復(fù)雜度要低于文獻(xiàn)［2］的算法復(fù)雜度。

文獻(xiàn)［2］采用的多分辨率樣條的算法復(fù)雜度和文中采用的泊松融合的算法復(fù)雜度均為0(n3)。

由以上分析可以得出，文中算法的復(fù)雜度低于文獻(xiàn)［2］的算法復(fù)雜度。

2.2 效果圖的比較

效果圖如圖5所示，文獻(xiàn)［2］的效果圖如圖6所示。

由效果圖可以看出，文中算法與文獻(xiàn)［2］算法都能很好地找到縫合線，并把圖像拼接在一起。但文獻(xiàn)［2］采用多分辨率拼接技術(shù)進(jìn)行融合，需要進(jìn)行高斯濾波，導(dǎo)致圖像變暗和模糊，文中提出的算法使用泊松融合，一定程度上改進(jìn)了圖片的效果。

3 結(jié)束語(yǔ)

提出了把圖像的灰度差異和梯度差異結(jié)合起來(lái)組成代價(jià)函數(shù)，通過(guò)動(dòng)態(tài)規(guī)劃搜索最佳縫合線的方式，實(shí)現(xiàn)動(dòng)態(tài)場(chǎng)景拼接，成功地解決了動(dòng)態(tài)場(chǎng)景拼接中存在的鬼影以及曝光差異的問(wèn)題，具有實(shí)用意義。

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