基于廣度優先視差優化的雙目立體匹配

吳志偉

（四川大學計算機學院，成都 610065）

基于廣度優先視差優化的雙目立體匹配

吳志偉

（四川大學計算機學院，成都 610065）

雙目立體匹配屬于三維重建的重要環節，匹配所獲得的視差圖很大程度上影響著模型的重建質量。在原有局部特征的雙目立體匹配算法的基礎上，提出一種基于廣度優先搜索的視差優化后處理方法；在左右一致性檢測之后添加視差優化過程，結合局部特征的雙目立體匹配算法，計算出的視差準確率有進一步的提升。使用通用計算進行并行優化，提高實時三維重建的精度。

雙目立體匹配；視差優化；廣度優先搜索

0 引言

三維重建屬于計算機視覺中的熱門話題。基于雙目立體匹配的三維重建近年來被國內外研究人員廣泛研究。雙目立體匹配算法利用仿生學原理，依據雙目生物立體視覺成像原理，對左右雙目圖像對進行掃描線搜索匹配得到視差圖，從而還原真實三維場景。

雙目立體匹配算法主要分為兩大類：局部特征匹配和全局優化匹配。前者具有強紋理區域精確度高、可并行優化等優點，常見為自適應支持權值方法（AW）[1]。但是該算法使用局部特征進行掃描線搜索，在弱紋理區域，使用Winner-Takes-All策略將很難找到真實匹配點對。后者使用動態規劃（DP）、圖割（GC）、置信度傳播（BP）等全局優化方法[2～3]，將視差圖的計算轉化為以代價函數作優化目標的最優化問題，保證了圖像上臨近點之間的約束關系，同時在弱紋理區域能夠得到較準確視差。但是全局優化過程會消耗大量的計算時間，在現今的計算機硬件條件下還很難實現實時處理。

立體匹配算法可以分別計算出左右圖視差，再對兩視差圖進行左右一致性檢測，找到視差非一致性的區域進行填補[1]。通常通過搜索非一致點左右臨近的可信視差中較小值作為該點的視差，并沒有進一步考慮輸入圖像中的色塊特性加以優化。

針對以上提到的問題，本文提出一種基于廣度優先搜索的視差優化算法對自適應支持權值算法的視差圖進行后處理。結合局部算法的可并行特性，實現實時高精度三維重建。

1 自適應支持權值雙目立體匹配

自適應支持權值[1]的雙目立體匹配是局部立體匹配常用方法之一。該方法首先使用SAD算子獲得初始代價，再對局部窗口的初始代價進行聚合。代價的聚合其實就是對窗口內代價進行加權平均。其中，同時使用色彩和結構的距離來確定窗口中每一個點的權重，確保自適應的代價聚合。本文使用三次聚合迭代進一步提高算法精度。對于聚合后的新代價，使用Winner-Takes-All策略進行匹配，即可求得視差圖。圖1為Middlebury雙目數據集[4]中的Teddy像對左右視差圖。

2 左右一致性檢測

如圖1所示，立體匹配得到的左右視差圖中，存在許多噪聲點，可以通過左右圖像素位置關系找到視差不一致區域，進行修補。

圖1 左右視差圖

圖2 左右一致性檢測結果

在左視差圖LD中進行遍歷，對每一個遍歷點P，通過該點視差LD[P]可得到右圖中該點對應位置Q，在右視差圖RD中對應位置得到視差RD[Q]，比較LD[P]與RD[Q]絕對值差是否在一個可接受的范圍內。當LD [P]與RD[Q]差距較大（本文取絕對差大于1）時，記錄當前點為一個左右不一致點，本文定義為A類不一致點。

視差的值與景深成反比，對于現實場景的三維重建問題，視差值通常在一個可預測的范圍，這就使得視差結果不能太小。視差圖中，視差凡是小于最小值（本文取為3個像素）的點，被標記為B類不一致點。由于雙目圖像邊緣存在遮擋，視差圖的邊緣部分只能使用啟發式的方式進行填補，與邊緣相連的A類不一致點也將調整為B類不一致點。這時需要使用廣度優先搜索算法[5]對不一致區域進行連通檢測，具體步驟如下：

①初始化已訪問數組，全部置為未被訪問狀態，令計數變量i為0；

②初始化一個待訪問隊列，從左視差圖邊緣的每一個像素點出發，當前遍歷點如果未被訪問，且為不一致點，則插入到隊列中；

③如果隊列已經為空則進行步驟5，否則從隊列中彈出隊首元素像素點K，標記為已訪問，將其記錄到B類不一致點集合Seti（N為Set集合個數，且0≤i≤N-1）中，獲得其四個方向的鄰居像素點N[4]；

④對四個鄰居點中的每一個N[j]進行邊緣檢測，如果N[j]在原圖中不屬于顏色梯度較大的點，且為不一致點，則將之插入到隊列中，對四個點都處理完畢后進行③；

⑤計數變量i增加1并回到②，直到邊緣像素全部遍歷完，結束算法。

A類、B類不一致點統稱為不一致點，如圖2黑色（像素值為0）區域所示。

3 視差填補

對不一致點進行視差填補操作。A類不一致點，一般出現在視差可信區域，由于一些噪聲或者局部弱紋理區域造成的，直接選擇距離當前點最近的左右兩個一致點的視差進行填充。

B類不一致點通常是弱紋理區域造成的，針對這樣的點，使用上文提到的方法在一些圖像邊緣區域信息量不足的情況下將無法進行合理的填補。本文通過廣度優先搜索找到所有的B類點集Seti（0≤i≤N-1），對與點集直接相鄰的一致點的視差進行K-means聚類[6]。再找出視差出現個數最多的前K個類（本文K取1），使用這K個類中所有點進行平面擬合，得到一個平面方程，將B類點集中的坐標代入方程即為該坐標點處的視差。

4 實驗結果與分析

編程對Middlebury的Stereo雙目圖像數據集[4]進行對比實驗，平均誤差相對于原自適應支持權值算法（AW）有了一定的提升，實驗結果的視差圖如圖3和圖4所示。

圖3 AW算法

圖4 本文算法

圖3為原自適應支持權值算法，圖4為本文算法。可以看出本文算法改善了很多受弱紋理影響的視差缺陷，并且解決了原有算法對于Teddy雙目像對玩具小熊輪廓不分明等問題；在Middlebury上的排名[4]也有所增加。使用CUDA[7]進行GPU通計算減少本算法運行時間到毫秒級別，進而實現了實時三維重建。

參考文獻：

[1] K.-J.Yoon and I.-S.Kweon.Adaptive Support-Weight Approach for Correspondence Search[J].PAMI，,2006，28(4):650～656

[2] D.Scharstein and R.Szeliski.A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms[C].IJCV 2002

[3] Q.Yang,L.Wang,R.Yang,S.Wang,M.Liao,D.Nistér.Real-time Global Stereo Matching Using Hierarchical Belief Propagation[C]. BMVC，2006

[4] Middlebury Stereo Vision Page.http://vision.middlebury.edu/stereo/

[5] Thomas H.Cormen and Charles E.Leiserson.算法導論[M].潘金貴,顧鐵成.北京:機械工業出版社出版，2006：324

[6] J.B.MacQueen.Some Methods for classification and Analysis of Multivariate Observations,Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability[J].Berkeley,University of California Press,1:281～297

[7] CUDA Parallel Computing Platform.http://www.nvidia.com/object/cuda_home_new.html

Binocular Stereo Matching Based on Breadth-First Disparity Optimization

WU Zhi-wei
(College of Computer Science,Sichuan University,Chengdu 610065)

Binocular stereo matching is the most important part of 3D reconstruction.The quality of the reconstruction is greatly influenced by the disparity map.Based on the raw local methods,proposes a breadth-first optimization algorithm for the post processing of disparity.Adds parallax optimization process after the consistency checking,combined with the binocular stereo matching algorithm of local characteristics.With the local stereo matching,the result shows the increased accuracy.

Binocular Stereo Matching;Disparity Optimization;Breadth First Search

1007-1423（2015）02-0055-03

10.3969/j.issn.1007-1423.2015.02.014

吳志偉（1990-），男，四川眉山人，碩士，研究方向為計算機視覺與圖像處理

2014-11-13

2014-12-16

四川省科技創新苗子工程（No.2014-033、No.2014-034）