徐光著，朱冰蓮，豐建軍

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

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

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

1 最佳縫合線搜索算法

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

圖1 源圖像

1.1 配準(zhǔn)

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

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

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

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

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

1.2 縫合線搜索

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

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

1.2.1 曝光校正

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

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

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

1.2.2 計算灰度差

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

1.2.3 計算梯度差

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

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

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

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

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

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

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)值的準(zhǔn)則式，用動態(tài)規(guī)劃的思想從重疊區(qū)域的第一行出發(fā)，建立該行上每一個像素為起點的縫合線，最后從這些縫合線中尋找一個最佳的縫合線。具體的步驟如下:

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

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

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

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

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

圖4 縫合線

1.3 圖像融合

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

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

2 實驗結(jié)果分析

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

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

文獻(xiàn)［2］使用的Dijkstra算法進(jìn)行縫合線的搜索，Dijkstra算法的時間復(fù)雜度為0(n2)，而使用的動態(tài)規(guī)劃算法的時間復(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é)束語

提出了把圖像的灰度差異和梯度差異結(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．