一種改進的動態(tài)場景拼接算法

徐光著，朱冰蓮，豐建軍

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

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

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

1 最佳縫合線搜索算法

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

圖1 源圖像

1.1 配準

使用特征點的配準方式，用匹配的特征點確定投影變換矩陣。

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

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

(3)使用Ransac算法對配準的特征點進行篩選提純，找到精確匹配的特征對。

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

1.2 縫合線搜索

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

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

1.2.1 曝光校正

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

為了做曝光校正，做如下的線性估計

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

1.2.2 計算灰度差

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

1.2.3 計算梯度差

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

1.2.4 搜索最佳縫合線的準則式

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

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

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

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

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

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

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

圖2 最佳縫合線

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

其中，opt為max或min，“*”為運算符號。對于求解最短路徑問題，opt取min，“*”取“+”，以表示階段相加和最小。

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

(1)初始化，第一行各列像素點均對應(yīng)一條縫合線，其強度值初始化為各個點的準則值，該縫合線的當(dāng)前點為其所在的列值。

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

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

圖3 縫合線的初始化及擴展

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

圖4 縫合線

1.3 圖像融合

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

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

2 實驗結(jié)果分析

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

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

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

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

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

2.2 效果圖的比較

效果圖如圖5所示，文獻［2］的效果圖如圖6所示。

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

3 結(jié)束語

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

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