李亞旋，謝紅薇，王春丹，張興忠

(太原理工大學(xué) 軟件學(xué)院，山西 太原 030024)

0 引 言

立體匹配算法[1,2]可以分為局部立體匹配算法和全局立體匹配算法。通常局部立體匹配算法包括自適應(yīng)窗口[3]、自適應(yīng)權(quán)重[4]等。然而，在弱紋理區(qū)域中局部立體匹配算法的匹配精度未達(dá)到理想效果[5]。相對(duì)于局部立體匹配算法，全局立體匹配算法[6]通過(guò)建立能量函數(shù)并最小化該函數(shù)來(lái)達(dá)到全局最優(yōu)視差值以獲得最終視差圖。該算法雖然匹配精度有很大提升，但其計(jì)算復(fù)雜度高導(dǎo)致較慢的運(yùn)行速度[7]。Yang等[8]提出了非局部代價(jià)聚合的方法。不同于之前依靠像素支持區(qū)域的方法，其在視差精度和運(yùn)行速度方面都有了很大了提升。但是由于其權(quán)值的計(jì)算只考慮了像素點(diǎn)的顏色信息，則計(jì)算出相等的邊權(quán)重會(huì)導(dǎo)致非唯一的樹結(jié)構(gòu)。Wang等[9]又提出了一種基于置信系數(shù)的非局部立體匹配算法，該算法改善了重復(fù)紋理區(qū)域的匹配精度。

上述的立體匹配算法都得到了較好的立體匹配效果，但還需要進(jìn)一步提高深度不連續(xù)區(qū)域的匹配精度。對(duì)此，本文提出多分量權(quán)值的最小生成樹匹配算法，解決了代價(jià)聚合階段相似顏色處的像素點(diǎn)錯(cuò)誤連接問(wèn)題，更準(zhǔn)確計(jì)算邊權(quán)值的大小。該方法降低了時(shí)間復(fù)雜度，并且在深度不連續(xù)區(qū)域可以得到更為準(zhǔn)確的視差圖。最后，實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性和可行性。

1 立體匹配算法實(shí)現(xiàn)

本文算法主要融合像素截?cái)鄰?qiáng)度差和圖像梯度計(jì)算匹配代價(jià)，利用改進(jìn)的顏色內(nèi)相關(guān)性和顏色信息構(gòu)建最小生成樹，采用Winner-take-all策略計(jì)算初始視差值并且使用非局部視差精化來(lái)獲取最終稠密視差圖。本文算法框架如圖1所示。

圖1 算法框架

1.1 匹配代價(jià)計(jì)算

匹配代價(jià)計(jì)算是計(jì)算左圖和右圖的視差值，即將左圖作為參考圖像，計(jì)算參考圖在視差范圍內(nèi)與右圖的匹配值。建立匹配代價(jià)函數(shù)是整個(gè)匹配算法的基石，其結(jié)果最終將影響視差圖的匹配效果。匹配代價(jià)函數(shù)的計(jì)算采用的是像素截?cái)嗟慕^對(duì)強(qiáng)度差(truncated absolute intensity diffe-rence，TAD)與圖像梯度(gradient)相結(jié)合的代價(jià)方法，其公式如下所示

C(p,d)=α·CTAD(p,d)+β·CGRAD(p,d)

(1)

式中：α和β分別為CTAD(p,d) 和CGRAD(p,d) 的合成權(quán)重，用于平衡兩種方法所占的比重。CTAD(p,d) 和CGRAD(p,d) 公式分別如下所示

(2)

(3)

上述代價(jià)函數(shù)既考慮了圖像的顏色影響，又結(jié)合了圖像的梯度大小，可以獲得更為準(zhǔn)確的匹配代價(jià)值。多特征融合計(jì)算匹配代價(jià)，很大程度上改善圖像弱紋理區(qū)域或深度不連續(xù)區(qū)域的匹配性能。

1.2 匹配代價(jià)聚合

考慮到各個(gè)像素點(diǎn)之間的匹配很容易因噪聲而受到影響，導(dǎo)致所求的匹配代價(jià)的最低值并不是所期望值，無(wú)法計(jì)算視差的最優(yōu)值，所以通過(guò)匹配代價(jià)聚合，使得聚合后的代價(jià)值能夠正確反應(yīng)像素之間的相關(guān)性，從而降低噪聲對(duì)匹配的影響。

1.2.1 多分量權(quán)值構(gòu)建最小生成樹

傳統(tǒng)的非局部立體匹配算法是通過(guò)構(gòu)建最小生成樹(minimum spanning tree，MST)進(jìn)行代價(jià)聚合，從而得到圖像中每個(gè)像素點(diǎn)對(duì)待匹配像素點(diǎn)的作用，考慮到近點(diǎn)和遠(yuǎn)點(diǎn)的影響，例如，對(duì)于距離待匹配像素點(diǎn)遠(yuǎn)的像素點(diǎn)，該點(diǎn)的權(quán)重值很小，這使得可以更準(zhǔn)確計(jì)算待匹配像素點(diǎn)的代價(jià)聚合值。但是該方法在構(gòu)建最小生成樹的過(guò)程中，邊的權(quán)值定義為圖像中兩個(gè)像素點(diǎn)的灰度值之差的3通道最大值，如下面公式所示

(4)

傳統(tǒng)方法可能導(dǎo)致相似顏色處的像素點(diǎn)錯(cuò)誤連接，且忽略了其它兩個(gè)通道的邊緣重量對(duì)最終邊緣重量的影響。在此基礎(chǔ)上提出一種計(jì)算最小生成樹邊權(quán)重的方法，如式(5)所示

(5)

該方法考慮了三通道的像素信息，使得邊緣權(quán)重函數(shù)的魯棒性增強(qiáng)。再結(jié)合改進(jìn)的顏色內(nèi)相關(guān)性，共同計(jì)算邊權(quán)值信息，使得獲得的色彩信息可以更準(zhǔn)確獲取內(nèi)部顏色特性，可以彌補(bǔ)原始邊權(quán)值的顏色分量作為單一分量的不穩(wěn)定性這一問(wèn)題，從而減少誤匹配的概率。

原始計(jì)算像素點(diǎn)的顏色內(nèi)相關(guān)性Iln=[IRtG,IGtB,IBtR]僅僅取決于3個(gè)通道的差值，其公式為

IRtG=IR(x,y)-IG(x,y)

(6)

IGtB=IG(x,y)-IB(x,y)

(7)

IBtR=IB(x,y)-IR(x,y)

(8)

因此本文在原始顏色內(nèi)相關(guān)性的基礎(chǔ)上進(jìn)行改進(jìn)，改進(jìn)的顏色內(nèi)相關(guān)性記為I′ln=[I′RtG,I′GtB,I′BtR]， 主要計(jì)算過(guò)程如下

I′RtG=|IR(x,y)-IG(x,y)|2

(9)

I′GtB=|IG(x,y)-IB(x,y)|2

(10)

I′BtR=|IB(x,y)-IR(x,y)|2

(11)

(12)

改進(jìn)的顏色內(nèi)相關(guān)性將像素點(diǎn)的色彩信息更加具體展現(xiàn)出來(lái)，考慮了像素點(diǎn)顏色通道的取值情況，更充分權(quán)衡了邊權(quán)值的大小。由此，將改進(jìn)的顏色內(nèi)相關(guān)性和顏色信息共同決定邊權(quán)值的多分量權(quán)值信息如式(13)所示

(13)

式中：θ為預(yù)定義調(diào)整的參數(shù)，主要是權(quán)衡顏色內(nèi)相關(guān)性和顏色信息在邊權(quán)值的計(jì)算中所起的作用。在獲取到邊權(quán)值的大小后，利用克魯斯卡爾算法將權(quán)值較大的邊進(jìn)行逐一去除，進(jìn)行最小生成樹的構(gòu)建，為代價(jià)聚合提供有力條件。

1.2.2 基于樹形濾波算法的代價(jià)聚合

基于最小生成樹結(jié)構(gòu)，將代價(jià)值沿著樹結(jié)構(gòu)進(jìn)行兩次遍歷，從而完成代價(jià)聚合。其具體過(guò)程如下：

(1)將葉節(jié)點(diǎn)的原始代價(jià)自下而上的聚合到MST的根節(jié)點(diǎn)，其公式表示如下

(14)

S(p,q) 是用來(lái)表示兩個(gè)像素點(diǎn)之間的相似度，其計(jì)算公式如下

(15)

式中：D(p,q)=D(q,p) 表示MST中p和q之間的距離，即邊的權(quán)值。σ主要用來(lái)調(diào)整兩個(gè)節(jié)點(diǎn)之間的相似性。

(2)將根節(jié)點(diǎn)的原始代價(jià)自上而下的聚合到MST的葉節(jié)點(diǎn)，其公式表示如下

(16)

1.3 視差計(jì)算及其精化

視差計(jì)算采用WTA策略，公式如下所示

(17)

將計(jì)算出的每個(gè)像素點(diǎn)的最小代價(jià)聚合值選取出來(lái)，作為該像素的視差值，從而得到整幅圖像的初始視差圖。其中，D表示可能的視差范圍，并且視差圖具有與左參考圖相同的大小，并存儲(chǔ)每個(gè)像素的視差值，如果在已知雙目攝像機(jī)的情況下，視差圖可以通過(guò)計(jì)算轉(zhuǎn)化為深度圖，獲取每個(gè)像素在空間中位置信息。

視差精化是將上述所得到的初始視差圖更進(jìn)一步優(yōu)化為高質(zhì)量的稠密視差圖。采用非局部視差精化法作為優(yōu)化初始視差圖的方式。具體過(guò)程是依次以左圖像和右圖像作為參考圖像來(lái)運(yùn)行非局部成本聚合方法，以獲得兩個(gè)對(duì)應(yīng)的視差圖，利用等式(18)將所有像素劃分為穩(wěn)定或不穩(wěn)定的像素

dL(x,y)=dR[x-max(dL,0),y]

(18)

式中：dL和dR為左右初始視差圖。滿足該式的視為穩(wěn)定點(diǎn)，否則為異常點(diǎn)。使用左右一致性檢測(cè)(left-right consistency check，LRC)的方法重新計(jì)算新的匹配代價(jià)值。計(jì)算公式如下

(19)

式中：D(p) 表示左視差圖，并且對(duì)于穩(wěn)定像素，針對(duì)每個(gè)視差水平d的每個(gè)像素p計(jì)算新的匹配代價(jià)值，對(duì)于所有不穩(wěn)定像素(由于遮擋、缺乏紋理、鏡面反射等)，匹配代價(jià)值為零。最后采用代價(jià)聚合的方法重新聚合新的匹配代價(jià)值，進(jìn)而得到最終高質(zhì)量視差圖。

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

本次實(shí)驗(yàn)是在具有2.40 GHz的CPU和內(nèi)存為4 GB的筆記本電腦上進(jìn)行的。運(yùn)行環(huán)境為Microsoft Studio 2010，并導(dǎo)入OpenCV函數(shù)庫(kù)，使用c++語(yǔ)言進(jìn)行實(shí)驗(yàn)，來(lái)驗(yàn)證算法的有效性。所提算法是在Middlebury平臺(tái)上進(jìn)行并測(cè)試，測(cè)試數(shù)據(jù)集包括4幅標(biāo)準(zhǔn)數(shù)據(jù)集：Tsukuba，Venus，Teddy和Cones，以可靠地評(píng)估本文提出的方法和其它近年來(lái)的前沿非局部立體匹配方法在準(zhǔn)確性方面的性能。算法中使用的參數(shù)見表1。根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)，θ的取值范圍應(yīng)該在[0.2，0.5]之間。

表1 本文立體匹配算法所用參數(shù)

2.1 本文算法的實(shí)驗(yàn)結(jié)果

本文算法實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 本文算法實(shí)驗(yàn)結(jié)果

從圖2可以看出，本文算法得到的視差圖更平滑，類似于與標(biāo)準(zhǔn)視差圖，在邊緣部分有很好的效果，比如Tsukuba的桌子邊緣區(qū)域；在豐富的紋理區(qū)域，比如Cones的木板區(qū)域，有清晰的匹配效果。

2.2 視差圖求取及分析

為了更好展現(xiàn)對(duì)比的實(shí)驗(yàn)效果圖，將非遮擋區(qū)域錯(cuò)誤像素點(diǎn)標(biāo)白，比較各個(gè)算法的白色區(qū)域的覆蓋范圍，結(jié)果如圖3所示。圖中從上到下依次是MST算法、ST-1算法[10]、ST-2算法、CS-MST算法[11]、CS-ST-1算法、CS-ST-2 算法和本文算法分別對(duì)4幅標(biāo)準(zhǔn)圖Tsukuba、Venus、Teddy和Cones求取的不同視差結(jié)果圖。MST是首次提出的基于最小生成樹的非局部立體匹配算法，ST是在MST的基礎(chǔ)上構(gòu)建分割樹并且ST-2在二次迭代時(shí)采用了顏色信息和深度信息，CS算法(CS-MST、CS-ST)考慮了多尺度的圖像信息，構(gòu)建了一種代價(jià)聚合模型，可以融合多種匹配算法。

圖3 誤匹配像素點(diǎn)對(duì)比

由圖3可以看出本文算法在測(cè)試圖像的深度不連續(xù)和弱紋理區(qū)域的白色區(qū)域明顯減少，比如Venus圖的平滑度比其它算法都要平滑，并且Teddy熊貓頭部的誤匹配像素點(diǎn)比ST-1算法少；Tsukuba書架背景的平滑度和連續(xù)性比CS-MST和CS-ST算法效果更精確；Cones的邊界處更加清晰明顯。

2.3 視差結(jié)果分析

為了進(jìn)一步驗(yàn)證本實(shí)驗(yàn)的有效性，針對(duì)非遮擋區(qū)域(n-occ)、所有區(qū)域(all)和深度不連續(xù)區(qū)域(disc)的誤匹配率進(jìn)行了定量分析，并對(duì)各個(gè)算法的誤差數(shù)據(jù)進(jìn)行了比較，其中avgErr表示視差圖的平均誤匹配率。其誤匹配率計(jì)算的數(shù)學(xué)公式為

(20)

式中：dC(x,y) 表示計(jì)算得到的視差值，dGT(x,y) 表示真實(shí)的視差值，δd表示視差閾值，本文取值1.0，大于該閾值則認(rèn)為誤匹配。

表2為不同的算法用上面4組標(biāo)準(zhǔn)測(cè)試圖像進(jìn)行評(píng)估的結(jié)果，實(shí)驗(yàn)結(jié)果數(shù)據(jù)如下。

從表2中可以看出，本文算法的平均誤匹配率為5.79%，比ST-1、ST-2、CS-MST、CS-ST-1和CS-ST-2算法分別低1.44%、1.04%、1.09%、0.98%和0.97%。比MST算法僅高0.31%，但是本文算法在Teddy標(biāo)準(zhǔn)圖的n-occ、all和disc區(qū)域比MST算法分別降低了0.28、0.34、0.05百分點(diǎn)。在Venus上，本文算法比CS-MST、CS-ST-1和CS-ST-2算法在深度不連續(xù)區(qū)域分別降低了3.75、4.68、3.81個(gè)百分點(diǎn)。

針對(duì)標(biāo)準(zhǔn)數(shù)據(jù)集的非遮擋區(qū)域匹配率，本文又與近年來(lái)幾種改進(jìn)的非局部立體匹配算法(IST-2算法[12]、文獻(xiàn)[9]、IMST算法[13])進(jìn)行了比較分析，結(jié)果見表3。

可以看出，本文算法在非遮擋區(qū)域的誤匹配率比IST-2算法、文獻(xiàn)[9]所提算法分別低0.24、0.01個(gè)百分比，雖然比文獻(xiàn)[9]的結(jié)果較高，但在Teddy圖的非遮擋區(qū)域本文方法效果較好。由此可見本文算法匹配準(zhǔn)確度高，改善了深度不連續(xù)區(qū)域和弱紋理區(qū)域匹配率不高的情況，具有較好的魯棒性，可獲得高質(zhì)量視差圖。

2.4 時(shí)間復(fù)雜度分析

在代價(jià)聚合階段，本文利用改進(jìn)的顏色內(nèi)相關(guān)性和顏色信息分量作為邊權(quán)值信息，充分利用的像素色彩之間的信息，相較于MST算法僅單一的選取像素顏色3通道之間的最大值作為邊權(quán)重，運(yùn)行速度慢一點(diǎn)；而ST-2算法在進(jìn)行第2次迭代時(shí)融合了顏色和深度信息，以及CS算法要考慮圖像間多尺度的交互信息，所以通過(guò)比較分析，本文算法比ST-2、CS算法運(yùn)行速度快，時(shí)間復(fù)雜度更低，其結(jié)果見表4。

表2 不同視差圖在不同算法下的誤差數(shù)據(jù)

表2(續(xù))

表3 非遮擋區(qū)域中不同視差圖在不同算法下的誤差數(shù)據(jù)

表4 運(yùn)行時(shí)間對(duì)比/s

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

本文提出一種改進(jìn)的多分量權(quán)值的非局部立體匹配算法，首先通過(guò)像素的截?cái)嘟^對(duì)差和圖像梯度融合方法來(lái)計(jì)算匹配代價(jià)值。然后利用克魯斯卡爾算法將改進(jìn)的顏色內(nèi)相關(guān)性和顏色信息相結(jié)合作為最小生成樹的邊權(quán)值，充分計(jì)算了像素之間的色彩信息，不會(huì)導(dǎo)致像素出現(xiàn)相同色彩的情況。之后運(yùn)用樹型濾波算法進(jìn)行代價(jià)聚合，最后采用WTA和非局部后處理方法生成精細(xì)視差圖。

本文降低了圖像匹配噪聲，在深度不連續(xù)區(qū)域和弱紋理區(qū)域都得到了較好的視差效果，提高了視差圖的匹配準(zhǔn)確度，由此本文算法具有一定應(yīng)用價(jià)值。由于本文主要利用像素的顏色內(nèi)相關(guān)性和顏色信息作為邊的權(quán)值，下一步還可以考慮相似顏色的邊界范圍，提高像素邊界的清晰性，使得匹配效果更準(zhǔn)確。