多分量權(quán)值的樹結(jié)構(gòu)立體匹配算法

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

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

0 引 言

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

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

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

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

圖1 算法框架

1.1 匹配代價計算

匹配代價計算是計算左圖和右圖的視差值，即將左圖作為參考圖像，計算參考圖在視差范圍內(nèi)與右圖的匹配值。建立匹配代價函數(shù)是整個匹配算法的基石，其結(jié)果最終將影響視差圖的匹配效果。匹配代價函數(shù)的計算采用的是像素截斷的絕對強(qiáng)度差(truncated absolute intensity diffe-rence，TAD)與圖像梯度(gradient)相結(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)

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

1.2 匹配代價聚合

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

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

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

(4)

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

(5)

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

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

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]， 主要計算過程如下

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)性將像素點的色彩信息更加具體展現(xià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)值的計算中所起的作用。在獲取到邊權(quán)值的大小后，利用克魯斯卡爾算法將權(quán)值較大的邊進(jìn)行逐一去除，進(jìn)行最小生成樹的構(gòu)建，為代價聚合提供有力條件。

1.2.2 基于樹形濾波算法的代價聚合

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

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

(14)

S(p,q) 是用來表示兩個像素點之間的相似度，其計算公式如下

(15)

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

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

(16)

1.3 視差計算及其精化

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

(17)

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

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

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

(18)

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

(19)

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

2 實驗結(jié)果及性能分析

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

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

2.1 本文算法的實驗結(jié)果

本文算法實驗結(jié)果如圖2所示。

圖2 本文算法實驗結(jié)果

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

2.2 視差圖求取及分析

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

圖3 誤匹配像素點對比

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

2.3 視差結(jié)果分析

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

(20)

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

表2為不同的算法用上面4組標(biāo)準(zhǔn)測試圖像進(jìn)行評估的結(jié)果，實驗結(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百分點。在Venus上，本文算法比CS-MST、CS-ST-1和CS-ST-2算法在深度不連續(xù)區(qū)域分別降低了3.75、4.68、3.81個百分點。

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

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

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

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

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

表2(續(xù))

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

表4 運行時間對比/s

3 結(jié)束語

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

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