吳志偉

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

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

吳志偉

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

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

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

0 引言

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

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

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

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

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

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

2 左右一致性檢測(cè)

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

圖1 左右視差圖

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

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

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

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

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

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

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

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

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

3 視差填補(bǔ)

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

圖3 AW算法

圖4 本文算法

圖3為原自適應(yīng)支持權(quán)值算法，圖4為本文算法?？梢钥闯霰疚乃惴ǜ纳屏撕芏嗍苋跫y理影響的視差缺陷，并且解決了原有算法對(duì)于Teddy雙目像對(duì)玩具小熊輪廓不分明等問(wèn)題；在Middlebury上的排名[4]也有所增加。使用CUDA[7]進(jìn)行GPU通計(jì)算減少本算法運(yùn)行時(shí)間到毫秒級(jí)別，進(jìn)而實(shí)現(xiàn)了實(shí)時(shí)三維重建。

參考文獻(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].潘金貴,顧鐵成.北京:機(jī)械工業(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-），男，四川眉山人，碩士，研究方向?yàn)橛?jì)算機(jī)視覺(jué)與圖像處理

2014-11-13

2014-12-16

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