基于廣度優(yōu)先視差優(yōu)化的雙目立體匹配

吳志偉

（四川大學(xué)計算機學(xué)院，成都 610065）

基于廣度優(yōu)先視差優(yōu)化的雙目立體匹配

吳志偉

（四川大學(xué)計算機學(xué)院，成都 610065）

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

雙目立體匹配；視差優(yōu)化；廣度優(yōu)先搜索

0 引言

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

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

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

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

1 自適應(yīng)支持權(quán)值雙目立體匹配

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

2 左右一致性檢測

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

圖1 左右視差圖

圖2 左右一致性檢測結(jié)果

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

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

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

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

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

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

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

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

3 視差填補

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

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

4 實驗結(jié)果與分析

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

圖3 AW算法

圖4 本文算法

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

參考文獻：

[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.算法導(dǎo)論[M].潘金貴,顧鐵成.北京:機械工業(yè)出版社出版，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

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