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

(1.上海大學(xué)通信與信息工程學(xué)院，上海 200072;2.新型顯示技術(shù)及應(yīng)用集成教育部重點(diǎn)實(shí)驗(yàn)室，上海 200072)

0 引言

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

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

全局匹配算法較比局部匹配算法在算法精確度和噪聲敏感度上有很大優(yōu)勢(shì)，從最初的遺傳算法、貪婪算法到動(dòng)態(tài)規(guī)劃算法，以及目前廣泛采用的BP算法、graph－cuts算法等，全局算法得到了很大的發(fā)展。但全局算法復(fù)雜度非常高，消耗的運(yùn)算成本太大，在很多應(yīng)用環(huán)境中并不適用。局部匹配算法在精確度上沒有全局算法更優(yōu)秀，但運(yùn)算速度上更勝一籌。本文算法結(jié)合全局匹配算法和局部匹配算法的優(yōu)缺點(diǎn)，在圖像分割基礎(chǔ)上，對(duì)文獻(xiàn)［11］的BP算法進(jìn)行改進(jìn)，利用BP對(duì)初始視差進(jìn)行處理和優(yōu)化，進(jìn)而得到優(yōu)于全局匹配算法精度的視差圖。

1 改進(jìn)BP算法

本算法框架如下圖1。首先對(duì)輸入的參考圖像進(jìn)行Mean－shift彩色分割，以左圖像為參考圖像進(jìn)行匹配代價(jià)計(jì)算并獲取初始視差;接著對(duì)初始視差進(jìn)行交叉檢測(cè)，并結(jié)合分割信息，將分割區(qū)域分為可靠和非可靠區(qū)域;然后利用本文的改進(jìn)BP算法進(jìn)行優(yōu)化，為非可靠區(qū)域?qū)ふ易顑?yōu)視差值;最后得到最終視差圖。

圖1 算法流程圖

1.1 獲取初始視差

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

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

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

得到匹配代價(jià)后，利用勝者全取(Winner－Take－All，WTA)選擇初始視差值。接著，對(duì)初始視差采用交叉檢測(cè)算法進(jìn)行可靠性檢測(cè)，并對(duì)可靠點(diǎn)和非可靠點(diǎn)分別進(jìn)行標(biāo)記，為視差估計(jì)后續(xù)處理做準(zhǔn)備。

1.2 基于區(qū)域的BP算法優(yōu)化

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

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

式中:Edata為數(shù)據(jù)項(xiàng)(匹配代價(jià)函數(shù))，Esmooth為平滑項(xiàng)(平滑約束)。s為分割區(qū)域，fs表示為區(qū)域s分配最后標(biāo)簽(即視差)?？紤]到BP算法是基于分割區(qū)域的。故式(2)中數(shù)據(jù)項(xiàng)Edata及平滑項(xiàng)Esmooth公式分別為

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

對(duì)于信息(message)函數(shù)計(jì)算及迭代，公式為

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

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

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

本文選取Middlebury網(wǎng)站的標(biāo)準(zhǔn)測(cè)試序列，實(shí)驗(yàn)平臺(tái)為VS2008。本算法與文獻(xiàn)［11］算法進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果的評(píng)估標(biāo)準(zhǔn):客觀評(píng)價(jià)為誤匹配像素百分比(Percentage of Bad Matching，PBM)(式(7))。

通常在遮擋區(qū)域(Occluded Region)和邊緣區(qū)域(Discontinuity Region)視差匹配較易發(fā)生誤匹配。在進(jìn)行區(qū)域誤差統(tǒng)計(jì)時(shí)，對(duì)于非遮擋區(qū)域，由于其在參考圖像中不存在對(duì)應(yīng)的匹配點(diǎn)，匹配中很難得到正確的視差，所以在視差匹配時(shí)利用非遮擋區(qū)域視差BO－(式8)來統(tǒng)計(jì)誤匹配率;對(duì)于邊緣區(qū)域則是視差的不連續(xù)區(qū)域，用Bd(式9)統(tǒng)計(jì)其誤匹配率。

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

表1為文獻(xiàn)［11］算法與改進(jìn)算法客觀評(píng)估結(jié)果對(duì)比。筆者給出了總體誤匹配率以及各個(gè)區(qū)域誤匹配率的詳細(xì)統(tǒng)計(jì)數(shù)據(jù)。從表中可以看到本算法在非遮擋區(qū)域?qū)eddy及cones兩幅測(cè)試序列表現(xiàn)更好，對(duì)于tsukuba及venus兩個(gè)序列誤匹配率則略有提高，主要原因在于這兩幅圖像紋理特征:少紋理區(qū)域較多。如前所述，全局算法對(duì)于少紋理區(qū)域的處理要優(yōu)于局部匹配算法。但本算法在對(duì)于邊緣區(qū)域的處理上4幅測(cè)試序列均有提高，使得誤匹配率最高可達(dá)到近13%的降低，其結(jié)果明顯優(yōu)于文獻(xiàn)［11］算法?？梢姳舅惴▽?duì)于邊緣處理，以及紋理多樣化的圖像序列處理效果尤為突出。

表1 本文算法與文獻(xiàn)［11］算法誤匹配率比較

本文算法與文獻(xiàn)［11］算法同在立體匹配測(cè)試網(wǎng)站Middlebury測(cè)試，本文算法對(duì)于4幅測(cè)試序列的平均誤差率為10.7%，文獻(xiàn)［11］算法則為16.2%。證明了本文算法的有效性。

表2為文獻(xiàn)［11］算法與本文算法耗時(shí)結(jié)果對(duì)比。從表中可以看到，本文算法和文獻(xiàn)［11］算法的計(jì)算消耗相當(dāng)，有的序列計(jì)算消耗略有提高，但在匹配效果提高的基礎(chǔ)上，還是可接受的。

表2 本文算法與文獻(xiàn)［11］算法耗時(shí)比較

圖2給出了文獻(xiàn)［11］的算法和使用本文改進(jìn)算法進(jìn)行立體匹配得到的視差圖對(duì)比。由匹配結(jié)果可以看到，本文算法在4幅測(cè)試序列中的整體匹配結(jié)果優(yōu)于文獻(xiàn)［11］算法，尤其是對(duì)于邊緣區(qū)域的匹配有著明顯優(yōu)勢(shì)。

3 小結(jié)

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

圖2 本文算法與文獻(xiàn)［11］算法視差圖比較

［1］馬爾著，姚國(guó)正，劉磊，等.計(jì)算機(jī)視覺［M］.北京:科學(xué)出版社，1998.

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

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

［4］陳文鑫，陳偉東，朱仲杰，等.基于可變特征基元的視差估計(jì)新方法［J］.計(jì)算機(jī)工程與應(yīng)用，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］鄭志剛，汪增福.基于區(qū)域間協(xié)同優(yōu)化的立體匹配算法［J］.自動(dòng)化學(xué)報(bào)，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］荊元強(qiáng).基于相位信息的立體圖像匹配研究［D］.天津:天津工業(yè)大學(xué)，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］袁惇.基于視差估計(jì)的立體視頻對(duì)象分割［D］.北京:中國(guó)傳媒大學(xué)，2007:17－26.

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