一種改進的基于BP的立體匹配算法

武翠芳，王永芳，劉 靜，2，張兆楊，2，宋允東，2

(1.上海大學通信與信息工程學院，上海 200072;2.新型顯示技術及應用集成教育部重點實驗室，上海 200072)

0 引言

近年來，隨著多媒體、Internet等技術的發展，普通二維觀感的圖像、視頻越來越無法滿足人們的觀賞需求。接近真實場景的三維成像及環視的視覺體驗已越來越被大眾所期待。隨之，立體視覺系統作為一種新興的媒體系統，能夠在很大程度上滿足人們的視覺體驗，而受到越來越多的研究者和商業機構的關注。視差信息是立體視覺系統的基礎，而立體匹配技術是獲取視差信息的主要手段。故而，雙目立體匹配問題作為立體視覺的關鍵成為計算機視覺領域研究的熱點。20世紀70年代末，MIT的Marr教授首次從信息處理的角度綜合了圖像處理、心理物理學、神經生物學及臨床神經病學的研究成果，提出了第一個較為完善的視覺系統框架［1］。大大促進了立體視覺技術的發展，立體匹配問題一直扮演著至關重要的角色。

目前存在的立體匹配算法，由于立體匹配方法的不確定性，并沒有一種統一的方式來解決立體匹配的問題。根據不同匹配基元及算法依據等有著不同的分類標準。目前廣泛認可的一種分類即局部匹配算法和全局匹配算法兩大類［2］。全局算法依賴圖像的全局約束信息進行匹配，目前比較流行的全局算法如動態規劃(DP)、graphcuts、BP(Belief Propagation)等。局部匹配算法利用對應點本身以及鄰近區域約束信息來進行匹配。局部算法按照匹配基元不同，可分為3類:特征匹配、區域匹配和相位匹配。特征匹配算法［3－4］根據點、線、面、角點等作為匹配基元進行匹配，此算法在匹配運算速度上最為理想，而由于其匹配基元的稀疏性而無法得到稠密視差圖，進而嚴重影響最終效果。但對于其稀疏視差的插值運算亦相當復雜，反而得不償失;基于區域的局部立體匹配算法［5－7］，在算法并不復雜的前提下，能夠獲取稠密視差圖而受到越來越多研究者的青睞。其不足之處在于對于遮擋及紋理單一區域易造成誤匹配，這也是近年來針對區域匹配算法的重點改進之處;相位匹配算法［8－10］對帶通濾波信號的相位信息進行處理而得到視差圖。此算法對于圖像的高頻噪聲有很好的抑制作用，同時對幾何畸變和輻射畸變有很好的抑制作用，能獲得亞像素級的稠密視差圖。

全局匹配算法較比局部匹配算法在算法精確度和噪聲敏感度上有很大優勢，從最初的遺傳算法、貪婪算法到動態規劃算法，以及目前廣泛采用的BP算法、graph－cuts算法等，全局算法得到了很大的發展。但全局算法復雜度非常高，消耗的運算成本太大，在很多應用環境中并不適用。局部匹配算法在精確度上沒有全局算法更優秀，但運算速度上更勝一籌。本文算法結合全局匹配算法和局部匹配算法的優缺點，在圖像分割基礎上，對文獻［11］的BP算法進行改進，利用BP對初始視差進行處理和優化，進而得到優于全局匹配算法精度的視差圖。

1 改進BP算法

本算法框架如下圖1。首先對輸入的參考圖像進行Mean－shift彩色分割，以左圖像為參考圖像進行匹配代價計算并獲取初始視差;接著對初始視差進行交叉檢測，并結合分割信息，將分割區域分為可靠和非可靠區域;然后利用本文的改進BP算法進行優化，為非可靠區域尋找最優視差值;最后得到最終視差圖。

圖1 算法流程圖

1.1 獲取初始視差

Comaniciu D［13］等人將 mean －shift方法首次應用于圖像分割，并驗證了其在特征空間的穩健性。mean－shift分割算法是一種利用概率分布地圖尋找分布峰值的穩健型較高的非參數估計算法［13］，是一種比較有效的統計迭代算法，使得每個點能夠“漂移”到密度函數的局部極大點。該算法在處理物體邊界方面更為理想，且具有精度高和實時性好等優點［14］。

基于區域的匹配算法往往假設不同的顏色邊緣與視差的跳躍是一致的(即假設區域內視差相等)，為使這一假設成立，實際操作中通常要采用“過分割”算法來得到盡量多的分割區域。在進行立體匹配時，首先用meanshift算法對圖像進行過分割，得到分割圖像后，計算初始匹配代價進而獲取圖像的初始視差。在進行匹配代價計算時，采用絕對誤差和(Sum of Absolute Difference，SAD)并加入梯度約束，即:SAD+GRAD，如式(1)所示。

ω為梯度權重;N(x，y)為中心點(x，y)處支持窗口;Nx(x，y)為x方向窗口大小;Ny(x，y)為y方向窗口大小;I1(i+d，j)為參考圖像當前點像素，I2(i+d，j)為目標圖像當前點像素，(i，j)為當前點坐標，d為視差值。本算法中采用的是拉普拉斯梯度算子來計算梯度。

得到匹配代價后，利用勝者全取(Winner－Take－All，WTA)選擇初始視差值。接著，對初始視差采用交叉檢測算法進行可靠性檢測，并對可靠點和非可靠點分別進行標記，為視差估計后續處理做準備。

1.2 基于區域的BP算法優化

BP算法采用消息傳遞機制實現能量的極小化，根據能量函數中每個因子的取值設定相應的消息(message)和置信度(belief)［15］。為每個分割區域選取最優視差值。這里對于初始視差值基于區域進行優化和重分配。同文獻［11］一樣，采用循環置信傳播(Loopy Belief Propagation)優化算法。不同之處在于，文獻［11］中算法是基于像素優化，而本文算法是基于mean－shift分割后的區域基礎上的優化。

算法中的能量函數定義如式(2)

式中:Edata為數據項(匹配代價函數)，Esmooth為平滑項(平滑約束)。s為分割區域，fs表示為區域s分配最后標簽(即視差)。考慮到BP算法是基于分割區域的。故式(2)中數據項Edata及平滑項Esmooth公式分別為

式中:SN表示所有相鄰區域的集合;λdisc(si，sj)是相鄰區域平滑懲罰項函數，是一個設定的經驗值;CSEG表示分割區域內匹配代價累積和;C(x，y，d)表示像素點(x，y)視差為d時的匹配代價，表達式見式(1)。可見，與原算法不同，新算法將原算法中針對相鄰像素間的置信度傳播改進為相鄰區域間的置信度傳播。

對于信息(message)函數計算及迭代，公式為

式中:si，sj表示不同的分割區域;fsj表示區域sj視差值;S(si)/sj表示除去sj外，與si相鄰的區域的集合。經T次迭代，得到每個區域的置信度如式(6)。最后，選取使得置信度函數最小的視差值f(s)，作為該區域s的最終視差值。

另本算法進一步改進:根據區域分割及交叉檢測后視差圖，將初始視差結果分為可靠區域與非可靠區域。原算法基于周圍相鄰區域間信息傳遞，而本文的算法中信息只在可靠區域與不可靠區域相互之間進行傳遞，略去可靠區域之間的信息計算和傳遞。

2 實驗結果

本文選取Middlebury網站的標準測試序列，實驗平臺為VS2008。本算法與文獻［11］算法進行對比。實驗結果的評估標準:客觀評價為誤匹配像素百分比(Percentage of Bad Matching，PBM)(式(7))。

通常在遮擋區域(Occluded Region)和邊緣區域(Discontinuity Region)視差匹配較易發生誤匹配。在進行區域誤差統計時，對于非遮擋區域，由于其在參考圖像中不存在對應的匹配點，匹配中很難得到正確的視差，所以在視差匹配時利用非遮擋區域視差BO－(式8)來統計誤匹配率;對于邊緣區域則是視差的不連續區域，用Bd(式9)統計其誤匹配率。

式中:dC(x，y)為算法得到視差估計值，dT(x，y)為真實視差值。PMB反映了算法估值所得視差值的誤差大于設定閾值的像素占整幅圖的所有像素的比例，PMB越大，表示誤匹配點越多;反之，則匹配精確度越高。O－表示非遮擋區域，d表示邊緣區域。這里選取δd=1.0。主觀評價采用對比標準視差圖法。

表1為文獻［11］算法與改進算法客觀評估結果對比。筆者給出了總體誤匹配率以及各個區域誤匹配率的詳細統計數據。從表中可以看到本算法在非遮擋區域對teddy及cones兩幅測試序列表現更好，對于tsukuba及venus兩個序列誤匹配率則略有提高，主要原因在于這兩幅圖像紋理特征:少紋理區域較多。如前所述，全局算法對于少紋理區域的處理要優于局部匹配算法。但本算法在對于邊緣區域的處理上4幅測試序列均有提高，使得誤匹配率最高可達到近13%的降低，其結果明顯優于文獻［11］算法。可見本算法對于邊緣處理，以及紋理多樣化的圖像序列處理效果尤為突出。

表1 本文算法與文獻［11］算法誤匹配率比較

本文算法與文獻［11］算法同在立體匹配測試網站Middlebury測試，本文算法對于4幅測試序列的平均誤差率為10.7%，文獻［11］算法則為16.2%。證明了本文算法的有效性。

表2為文獻［11］算法與本文算法耗時結果對比。從表中可以看到，本文算法和文獻［11］算法的計算消耗相當，有的序列計算消耗略有提高，但在匹配效果提高的基礎上，還是可接受的。

表2 本文算法與文獻［11］算法耗時比較

圖2給出了文獻［11］的算法和使用本文改進算法進行立體匹配得到的視差圖對比。由匹配結果可以看到，本文算法在4幅測試序列中的整體匹配結果優于文獻［11］算法，尤其是對于邊緣區域的匹配有著明顯優勢。

3 小結

本文提出一種改進的基于區域的BP立體匹配算法，與文獻［11］分層BP算法比較，本文改進BP算法在不分層的情況下，以幾乎相對等的算法復雜度，使得立體匹配中獲取的初始視差圖更為精確，特別是在邊緣區域。該算法進一步證明了局部算法可以有優于全局算法的匹配精度。從實驗結果來看，本文改進算法在少紋理區域的處理上沒有文獻［11］的算法精確。接下來的工作是針對不同區域(少紋理、遮擋、邊緣等區域)重點研究如何改善區域的誤匹配問題，以期能夠最終獲得更為準確的視差圖。

圖2 本文算法與文獻［11］算法視差圖比較

［1］馬爾著，姚國正，劉磊，等.計算機視覺［M］.北京:科學出版社，1998.

［2］于乃功，秦永鋼，阮曉剛.立體匹配算法進展［J］.計算機測量與控制，2009(5):817－819.

［3］徐奕，周軍，周源華.立體視覺匹配技術［J］.計算機工程與應用，2003，39(5):1－5.

［4］陳文鑫，陳偉東，朱仲杰，等.基于可變特征基元的視差估計新方法［J］.計算機工程與應用，2008，44(15):58－60.

［5］YOON K，KWEON I S.Adaptive support－ weight approach for correspondence search［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，2006，28(4):650－656.

［6］KLAUS A，SORMANN M，KARNER K.Segment－based stereo matching using belief propagation and a self－adapting dissimilarity measure［C］//Proc.ICPR 2006:Vol.3.［S.l.］:IEEE Press，2006:15－18.

［7］鄭志剛，汪增福.基于區域間協同優化的立體匹配算法［J］.自動化學報，2009，35(5):469－476.

［8］SANGER T D.Stereo disparity computation using Gabor filters［J］.Biological Cybemetics，1988，59:405－418.

［9］WENG J.Image matching using the windowed Fourier phase［J］.International Journal of Computer Vision，1993，11(3):211－236.

［10］荊元強.基于相位信息的立體圖像匹配研究［D］.天津:天津工業大學，2008.

［11］FELZENSZWALB P F，HUTTENLOCHER D P.Efficient belief propagation for early vision［C］//Proc.CVPR 2004.［S.l.］:IEEE Press，2004:261－268.

［12］KOSCHAN A.What is new in computational stereo since 1989:a survey of current stereo papers［R］.Berlin:Univ.of Berlin，1993.

［13］COMANICIU D，MEER P.Mean shift:A robust approach toward feature space analysis［J］.IEEE Trans.Pattern Anal.Machine Intell.，2002，24(5):603 －619.

［14］袁惇.基于視差估計的立體視頻對象分割［D］.北京:中國傳媒大學，2007:17－26.

［15］王翀，趙力，齊增義，等.基于改進 BP算法的中間視合成方法［J］.信號處理，2010，26:347－353.