多分量權值的樹結構立體匹配算法

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

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

0 引 言

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

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

1 立體匹配算法實現

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

圖1 算法框架

1.1 匹配代價計算

匹配代價計算是計算左圖和右圖的視差值，即將左圖作為參考圖像，計算參考圖在視差范圍內與右圖的匹配值。建立匹配代價函數是整個匹配算法的基石，其結果最終將影響視差圖的匹配效果。匹配代價函數的計算采用的是像素截斷的絕對強度差(truncated absolute intensity diffe-rence，TAD)與圖像梯度(gradient)相結合的代價方法，其公式如下所示

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

(1)

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

(2)

(3)

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

1.2 匹配代價聚合

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

1.2.1 多分量權值構建最小生成樹

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

(4)

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

(5)

該方法考慮了三通道的像素信息，使得邊緣權重函數的魯棒性增強。再結合改進的顏色內相關性，共同計算邊權值信息，使得獲得的色彩信息可以更準確獲取內部顏色特性，可以彌補原始邊權值的顏色分量作為單一分量的不穩定性這一問題，從而減少誤匹配的概率。

原始計算像素點的顏色內相關性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)

因此本文在原始顏色內相關性的基礎上進行改進，改進的顏色內相關性記為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)

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

(13)

式中：θ為預定義調整的參數，主要是權衡顏色內相關性和顏色信息在邊權值的計算中所起的作用。在獲取到邊權值的大小后，利用克魯斯卡爾算法將權值較大的邊進行逐一去除，進行最小生成樹的構建，為代價聚合提供有力條件。

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

基于最小生成樹結構，將代價值沿著樹結構進行兩次遍歷，從而完成代價聚合。其具體過程如下：

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

(14)

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

(15)

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

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

(16)

1.3 視差計算及其精化

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

(17)

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

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

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

(18)

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

(19)

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

2 實驗結果及性能分析

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

表1 本文立體匹配算法所用參數

2.1 本文算法的實驗結果

本文算法實驗結果如圖2所示。

圖2 本文算法實驗結果

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

2.2 視差圖求取及分析

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

圖3 誤匹配像素點對比

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

2.3 視差結果分析

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

(20)

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

表2為不同的算法用上面4組標準測試圖像進行評估的結果，實驗結果數據如下。

從表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標準圖的n-occ、all和disc區域比MST算法分別降低了0.28、0.34、0.05百分點。在Venus上，本文算法比CS-MST、CS-ST-1和CS-ST-2算法在深度不連續區域分別降低了3.75、4.68、3.81個百分點。

針對標準數據集的非遮擋區域匹配率，本文又與近年來幾種改進的非局部立體匹配算法(IST-2算法[12]、文獻[9]、IMST算法[13])進行了比較分析，結果見表3。

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

2.4 時間復雜度分析

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

表2 不同視差圖在不同算法下的誤差數據

表2(續)

表3 非遮擋區域中不同視差圖在不同算法下的誤差數據

表4 運行時間對比/s

3 結束語

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

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