基于小基高比的快速立體匹配方法

邊繼龍 門朝光 李 香

(哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150001)

1 引言

立體匹配是計(jì)算機(jī)視覺領(lǐng)域中的一個(gè)研究熱點(diǎn)，它通過匹配兩幅或者多幅同一場景在不同視角下的圖像來獲得對應(yīng)點(diǎn)視差，然后根據(jù)三角測量原理計(jì)算出景物的深度信息。立體匹配方法可分為大基高比立體匹配方法和小基高比立體匹配方法。根據(jù)文獻(xiàn)[1]的分類標(biāo)準(zhǔn)，大基高比立體匹配方法又可分為局部立體匹配方法[2-7]和全局立體匹配方法[8-11]。在局部立體匹配方法中，由于自適應(yīng)權(quán)重[2-4]及其快速實(shí)現(xiàn)[5-7]的提出使局部算法具有了較高的匹配準(zhǔn)確率和匹配效率。在全局立體匹配方法中，由于動(dòng)態(tài)規(guī)劃(Dynamic Programming)[8]、置信傳播(Belief Propagation)[9]和圖割(Graph Cut)[10,11]等全局優(yōu)化算法的成功應(yīng)用，使視差圖的質(zhì)量得到了明顯的改善，并較好地解決了低紋理區(qū)域和遮擋像素的匹配。雖然大基高比立體匹配算法無論在速度方面還是在準(zhǔn)確率方面都取得了一定的進(jìn)展，但這些算法對立體像對中的遮擋、輻射差異和幾何畸變的魯棒性很差，經(jīng)常導(dǎo)致大量的誤匹配，致使計(jì)算結(jié)果難以滿足實(shí)際應(yīng)用的要求。為減弱上述因素對匹配的影響，小基高比條件下的立體匹配技術(shù)[12-17]應(yīng)運(yùn)而生。然而小基高比會造成深度精度的損失，為此在小基高比立體匹配中視差精度必須達(dá)到亞像素級別以彌補(bǔ)這部分損失。小基高比立體匹配方法的難點(diǎn)在于以下兩個(gè)方面：(1)拒絕錯(cuò)誤匹配以獲得精確可靠的視差；(2)獲得高精度的亞像素級視差。雖然目前的小基高比立體匹配方法[12-14]一定程度上解決了小基高比匹配中的可靠性問題，但該類算法的缺點(diǎn)在于匹配速度慢而且亞像素精度較低。

為了提高立體匹配效率同時(shí)獲得高精度的亞像素級視差，本文提出一種快速的小基高比立體匹配方法。該方法主要有以下幾點(diǎn)貢獻(xiàn)：提出利用積分圖像(integral image)加快自適應(yīng)窗口和規(guī)范互相關(guān)度量的計(jì)算；根據(jù)可靠性約束進(jìn)一步拒絕錯(cuò)誤匹配以提高后續(xù)區(qū)域擬合的準(zhǔn)確性；提出一種基于迭代二倍重采樣的亞像素級匹配方法以補(bǔ)償小基高比所造成的深度精度的損失。

2 算法框架

本文提出的快速小基高比立體匹配方法處理的是經(jīng)極線校正的立體像對，并最終獲得稠密的亞像素級視差圖。該方法首先根據(jù)自適應(yīng)窗口技術(shù)計(jì)算匹配窗口大小同時(shí)確定可信點(diǎn)和不可信點(diǎn)，再根據(jù)匹配窗口大小和規(guī)范互相關(guān)度量為可信點(diǎn)計(jì)算初始視差，然后利用可靠性約束進(jìn)一步確定不可信點(diǎn)，在經(jīng)過初始窗口選擇和可信估計(jì)之后可以濾掉初始視差圖中不可信視差。在獲得可信視差的基礎(chǔ)上，采用基于迭代二倍重采樣的亞像素級匹配方法獲得亞像素級視差，最后利用基于圖分割的視差平面擬合方法獲得稠密的亞像素級視差圖。

3 算法的關(guān)鍵步驟及實(shí)現(xiàn)

3.1 局部匹配的數(shù)學(xué)分析

假設(shè)立體像對滿足經(jīng)典立體模型：

式中代表參考圖像，u(x)代表匹配圖像，ε(x)代表視差函數(shù)，gb(x)代表圖像噪聲。該模型僅在小基高比條件下才能滿足，而且基高比越小模型越精確。基于小基高比的立體匹配方法[12]假設(shè)立體像對滿足該模型并通過最大化支撐窗口間的互相關(guān)系數(shù)為參考圖像中的每一點(diǎn)計(jì)算視差，其計(jì)算公式如下：

式中φx0=φ(x0-x)代表支撐窗口，代表內(nèi)積，代表范數(shù)，τmu代表位移圖像u(x-m)。

式(2)表明互相關(guān)函數(shù)的極值點(diǎn)所對應(yīng)的視差值即為對應(yīng)點(diǎn)視差，而且極值點(diǎn)即為導(dǎo)數(shù)為零的點(diǎn)，通過令連續(xù)互相關(guān)函數(shù)的導(dǎo)數(shù)為零可得

式中

式(3)表明根據(jù)互相關(guān)系數(shù)計(jì)算的視差并不是該點(diǎn)的真實(shí)視差而是支撐窗口內(nèi)所有真實(shí)視差的權(quán)重平均與圖像噪聲之和。依據(jù)式(3)匹配誤差可分為兩部分：一部分是由于支撐窗口違背了前視平坦假設(shè)造成的；另一部分是由圖像噪聲造成的。在匹配過程中，可通過減少第2部分噪聲誤差來提高算法的匹配精度。通過對匹配中第2部分噪聲誤差應(yīng)用Schwarz不等式可得

根據(jù)式(4)第2部分噪聲誤差近似為

式(5)表示噪聲所引起的匹配誤差上界，在給定測量精度的情況下，可通過該式確定參考圖像中每一點(diǎn)的匹配窗口大小。如果期望計(jì)算視差能足夠精確地近似真實(shí)視差，應(yīng)該選擇滿足誤差精度的最小匹配窗口，其窗口選擇公式為

式中α表示匹配誤差精度。在窗口大小選擇范圍內(nèi)滿足式(6)的那些點(diǎn)稱為可信點(diǎn)，否則稱為不可信點(diǎn)。匹配過程中僅對可信點(diǎn)進(jìn)行匹配，在獲得可信點(diǎn)視差之后再推理獲得那些不可信點(diǎn)視差。在實(shí)際應(yīng)用中誤差精度α的設(shè)定與所能接受的高程誤差相關(guān)，例如，當(dāng)基高比為0.01，允許高程誤差為10 cm時(shí)，此時(shí)誤差精度α應(yīng)設(shè)置為0.01×10=0.1個(gè)像素左右。

3.2 積分圖像加速

算法在實(shí)現(xiàn)過程中需要多次在矩形窗口上計(jì)算函數(shù)的權(quán)重和，若直接計(jì)算這些權(quán)重和，其復(fù)雜度同窗口大小成正比。為提高算法效率，需要加快這些求和運(yùn)算。目前，實(shí)施快速求和運(yùn)算的技術(shù)主要有以下幾種方式：基于FFT的快速卷積技術(shù)、盒式濾波技術(shù)和積分圖像技術(shù)，它們廣泛地應(yīng)用于立體匹配中的成本累積階段。由于本文算法在匹配過程中每一點(diǎn)的支撐窗口大小都不同，因此積分圖像[18]比較適合對本文算法進(jìn)行加速。

為提高算法效率，本文首先將式(5)簡化為

證明

根據(jù)式(7)，計(jì)算式(5)僅需要在矩形窗口上進(jìn)行3次求和運(yùn)算，再加上規(guī)范互相關(guān)函數(shù)式(2)的3次求和運(yùn)算，窗口選擇和成本計(jì)算一共需要6次求和運(yùn)算。為了利用積分圖像加快這些求和操作，本文使用常數(shù)函數(shù)作為支撐窗口函數(shù)。為此，式(7)的離散形式可表達(dá)為

相應(yīng)的規(guī)范互相關(guān)系數(shù)的離散形式為

3.3 可信視差估計(jì)

雖然匹配過程僅處理那些在窗口選擇階段確定的可信點(diǎn)，但在匹配過程中還會存在一些誤匹配。為進(jìn)一步拒絕錯(cuò)誤匹配提高后續(xù)區(qū)域擬合的準(zhǔn)確性，本文對匹配過程施加了類似于文獻(xiàn)[19]中的可靠性約束。

3.4 基于迭代二倍重采樣的亞像素級匹配

小基高比立體匹配要獲得與大基高比立體匹配相同的深度精度，則需要視差精確到1/m個(gè)像元精度，其中m為大基高比與小基高比的比值。為此，在小基高比立體匹配當(dāng)中需要在整數(shù)級匹配之后加入亞像素級匹配以彌補(bǔ)小基高比對深度精度的影響。目前，亞像素級匹配方法主要包括圖像重采樣法[20]、擬合法[1]和相位法[15]。在這些方法當(dāng)中，圖像重采樣法的亞像素精度最高，但該方法的計(jì)算復(fù)雜度較高。為了能獲得高精度的亞像素級視差同時(shí)具有較高的匹配效率，本文提出一種基于迭代二倍重采樣的亞像素級匹配方法。該方法每次迭代時(shí)僅對匹配圖像中的支撐窗口進(jìn)行二倍采樣，然后在此分辨率上搜索最佳的亞像素級匹配位置。在下次迭代時(shí)，對最佳匹配位置的像素再次進(jìn)行二倍采樣，然后在這更高的分辨率上搜索最佳匹配位置。這個(gè)過程一直迭代直到達(dá)到想要的匹配精度為止。圖1顯示了 3×3窗口進(jìn)行 3次迭代時(shí)的亞像素級匹配過程，匹配過程的每次迭代只是對最佳匹配點(diǎn)及其窗口內(nèi)其它對應(yīng)點(diǎn)進(jìn)行二倍采樣。

亞像素級匹配方法的詳細(xì)過程如下：

(1)(x,y)的初始對應(yīng)點(diǎn)為ql=(x+m(x,y),y)，其中，m(x,y)為整數(shù)視差，迭代次數(shù)k=1，位置偏移集為

圖1 亞像素匹配的迭代過程

以(x,y)為中心的參考窗口T(x,y)為

式中w表示窗口大小，wx,wy表示整型變量。

(2)根據(jù)對應(yīng)點(diǎn)和窗口大小計(jì)算偏移窗口集。

(3)利用雙線性插值計(jì)算匹配窗口Sr中每一元素的灰度值。

式中INT(?)表示取整操作，xp表示p點(diǎn)的橫坐標(biāo)，yp表示p點(diǎn)的縱坐標(biāo)。

(4)根據(jù)規(guī)范互相關(guān)系數(shù)選擇最優(yōu)偏移量。

式中p∈Sr,s∈T(x,y)。

(5)計(jì)算亞像素級對應(yīng)點(diǎn)位置。

(6)當(dāng)k≤kmax轉(zhuǎn)入步驟(2)繼續(xù)迭代。

3.5 基于圖分割的視差平面擬合

到目前為止，匹配算法獲得的僅是稀疏的亞像素級視差圖。為獲得稠密視差圖，本文采用了視差平面擬合法。該方法首先采用Mean Shift算法對參考圖像進(jìn)行過分割，然后根據(jù)每一分割塊中的可信點(diǎn)的視差和坐標(biāo)，利用最小二乘技術(shù)估計(jì)出視差平面參數(shù)：

式中(ai,bi,ci)是分割塊Ri對應(yīng)視差平面的法量，m代表像素(x,y)的視差。在獲得平面參數(shù)后再根據(jù)式(18)計(jì)算那些不可信點(diǎn)的視差值進(jìn)而可以獲得稠密視差圖。

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

4.1 時(shí)間復(fù)雜度分析

現(xiàn)假設(shè)圖像共有M個(gè)像素，窗口最大值為Wmax，最小值為Wmin，則直接實(shí)現(xiàn)窗口選擇公式的時(shí)間復(fù)雜度為當(dāng)使用積分圖像對該公式加速時(shí)，計(jì)算窗口選擇公式的時(shí)間復(fù)雜度僅為像的時(shí)間復(fù)雜度為O(M)，總共的時(shí)間復(fù)雜度為O(M)。

利用積分圖像計(jì)算規(guī)范互相關(guān)函數(shù)式(9)也會節(jié)省大量的時(shí)間。計(jì)算式(9)需要計(jì)算1項(xiàng)建立積分圖像需要的時(shí)間復(fù)雜度為O(M×d)，其中d為視差范圍；第2,3項(xiàng)建立積分圖像需要的時(shí)間復(fù)雜度僅為O(M)，總計(jì)時(shí)間復(fù)雜度為O(M×(d+1))。利用這些積分圖像計(jì)算式(9)的時(shí)間復(fù)雜度僅為O(1)，一共需要的時(shí)間復(fù)雜度為O(M×(d+1))。直接實(shí)現(xiàn)式(9)的時(shí)間復(fù)雜度為O(M×W2(x)×d)，其中，W(x)表示每一點(diǎn)的窗口大小，該時(shí)間復(fù)雜度要遠(yuǎn)遠(yuǎn)大于O(M×(d+1))。

當(dāng)亞像素精度精確到1/2k個(gè)像元時(shí)，本文提出的亞像素匹配方法的時(shí)間復(fù)雜度僅為O(9×K×W2(x)×M)，而圖像重采樣法的時(shí)間復(fù)雜度為O(2k×2k×W2(x)×M)。通過以上對比表明本文提出的小基高比立體匹配方法是一種快速的立體匹配方法，具有較高的匹配效率。

4.2匹配精度分析

為了驗(yàn)證本文算法的有效性，該實(shí)驗(yàn)采用了文獻(xiàn)[12-14]實(shí)驗(yàn)中所使用的航空攝影像對Toulouse(如圖2所示)，并與同類算法MARC[12],REGMARC[13],MERGE-MARC[14]的實(shí)驗(yàn)結(jié)果進(jìn)行對比。實(shí)驗(yàn)采用vc++6.0編程，其運(yùn)行環(huán)境為雙核CPU2.2 GHz，內(nèi)存為2 GB。

圖2 Toulouse立體像對

Toulouse是一幅由 CNES提供的航空攝影像對，該立體像對的分辨率為 512×512，基高比約為0.045、地面分辨率為R=0.5，視差范圍為[-2,2]，其獲取時(shí)間間隔為20 min。由于獲取時(shí)間間隔較長導(dǎo)致了立體像對中存在明顯的運(yùn)動(dòng)和陰影移動(dòng)，這增加了視差估計(jì)難度。

圖3顯示了同類算法[12-14]給出的實(shí)驗(yàn)結(jié)果和本文實(shí)驗(yàn)結(jié)果。圖3(a)顯示了真實(shí)視差圖；圖3(b)-3(d)分別顯示了文獻(xiàn)[12](MARC)，文獻(xiàn)[13](REGMARC)和文獻(xiàn)[14](MERGE-MARC)中給出的實(shí)驗(yàn)結(jié)果；圖3(e)顯示了在視差平面擬合過程中使用的圖分割結(jié)果；圖3(f)顯示了參考圖像中每一點(diǎn)的匹配窗口大小，圖中的黑色表示不可信點(diǎn)，其它像素的灰度值代表該點(diǎn)的窗口大小，灰度值越大表示窗口越大，通過該圖可以看出在物體邊界處的匹配窗口相對較小，這可以有效防止“粘合”現(xiàn)象的發(fā)生；圖3(g)顯示了可信點(diǎn)視差，圖中的黑色表示不可信點(diǎn)，這些不可信點(diǎn)一部分是在自適應(yīng)窗口階段產(chǎn)生的，另一部分則是在可信視差估計(jì)階段產(chǎn)生的，這些不可信點(diǎn)視差將在后續(xù)的視差平面擬合中獲得；圖3(h)顯示了本文算法的最終視差圖。通過視差圖的對比結(jié)果可以看出在實(shí)驗(yàn)結(jié)果圖3(b)-3(d)中物體邊緣處的視差參差不齊，未能很好地反應(yīng)物體的形狀，這會給3維重建帶來較大的誤差，然而本文實(shí)驗(yàn)結(jié)果圖3(h)在物體邊緣處的視差效果要明顯優(yōu)于其它算法，邊緣處的視差非常整齊并清晰地反應(yīng)出場景形狀及細(xì)節(jié)信息。

利用均方根誤差(Root-Mean-Squared Error,RMSE)對本文算法和文獻(xiàn)[12-14]的算法進(jìn)行了定量比較。表.1.顯示了對比結(jié)果，第1列顯示了待比較算法，第2列顯示了可信點(diǎn)的RMSE，第3列顯示了所有像素點(diǎn)的RMSE，第4列顯示了算法的運(yùn)行時(shí)間。從對比結(jié)果可以看出本文提出的小基高比算法不但具有較高的匹配精度，而且也具有較快的匹配速度。在實(shí)際應(yīng)用中視差的匹配精度會受圖像的采樣頻率、量化位數(shù)和噪聲水平等因素的影響，不同條件的立體像對在視差精度上可能會存在較大的差異。

圖3 實(shí)驗(yàn)結(jié)果對比

表1 均方根誤差和運(yùn)行時(shí)間

5 結(jié)論

本文提出一種快速的小基高比立體匹配方法，該方法在匹配過程中利用積分圖像計(jì)算支撐窗口大小和規(guī)范互相關(guān)系數(shù)有效地提高了算法的匹配效率。在視差計(jì)算過程中加入可靠性約束提高了計(jì)算視差的準(zhǔn)確性。在獲得整數(shù)級視差后，利用基于迭代二倍重采樣的亞像素級匹配方法獲得高精度的亞像素級視差彌補(bǔ)了小基高比給深度重建帶來的誤差。最后采用了視差平面擬合方法估計(jì)不可信像素的視差值。實(shí)驗(yàn)結(jié)果表明本文提出的小基高比立體匹配方法不但可獲得高精度的亞像素級視差以滿足小基高比立體重建的要求，而且該方法的最大優(yōu)點(diǎn)在于匹配速度與窗口大小無關(guān)。

[1]Scharstein D and Szeliski R.A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[J].International Journal of Computer Vision,2002,47(1-3)：7-42.

[2]Yoon K J and Kweon S.Adaptive support-weight approach for correspondence search[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(4)：650-656.

[3]De-Maeztu L,Villanueva A,and Cabeza R.Stereo matching using gradient similarity and locally adaptive support-weight[J].Pattern Recognition Letters,2011,32(13)：1643-1651.

[4]Heo Y S,Lee K M,and Lee S U.Robust stereo matching using adaptive normalized cross-correlation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(4)：807-822.

[5]Li Li,Zhang Cai-ming,and Yan Hua.Cost aggregation strategy for stereo matching based on a generalized bilateral filter model[C].Proceedings of International Conference on Information Computing and Applications,Tangshan,China,2010：193-200.

[6]Richard C,Orr D,and Davies I,et al..Real-time spatiotemporal stereo matching using the dual-cross-bilateral grid[C].Proceedings of the 11th European Conference on Computer Vision Conference on Computer Vision,Crete,Greece,2010：510-523.

[7]丁菁汀,杜 歆,周文暉,等.基于 FPGA 的立體視覺匹配的高性能實(shí)現(xiàn)[J].電子與信息學(xué)報(bào),2011,33(3)：597-603.Ding Jing-ting,Du Xin,and Zhou Wen-hui,et al..High performance implementation of stereo vision matching based on FPGA[J].Journal of Electronics＆InformationTechnology,2011,33(3)：597-603.

[8]Bobick A F and Intille S S.Large occlusions stereo[J].International Journal of Computer Vision,1999,33(3)：181-200.

[9]Sun Jian,Zheng Nan-ning,and Shum H Y.Stereo matching using belief propagation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2003,25(7)：787-800.

[10]Papadakis N and Caselles V.Multi-label depth estimation for graph cuts stereo problems[J].Journal of Mathematical Imaging and Vision,2010,38(1)：70-82.

[11]Komodakis N,Paragios N,and Tziritas G.MRF energy minimization and beyond via dual decomposition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(3)：531-552.

[12]Delon J and Rougé B.Small baseline stereovision[J].Journal of Mathematical Imaging and Vision,2007,28(3)：209-223.

[13]Facciolo G.Variational adhesion correction with image based regularization for digital elevation models[D].[Master dissertation],Universidad de la Republica Oriental del Uruguay,2005：37-49.

[14]Igual L,Preciozzi J,and Garrido L.Automatic low baseline stereo in urban areas[J].Inverse Problems and Imaging,2007,1(2)：319-348.

[15]Morgan G L K,Liu Jian-guo,and Yan Hong-shi.Precise subpixel disparity measurement from very narrow baseline stereo[J].IEEE Transactions on Geoscience and Remote Sensing,2010,48(9)：3424-3433.

[16]Sabater N,Blanchet G,and Moisan L,et al..Review of low-baseline stereo algorithms and benchmarks[C].Proceedings of Image and Signal Processing for Remote Sensing XVI,Toulouse,France,2010：1-12.

[17]Robin A,Moisan L,and Le Hegarat-Mascle S.An a-contrario approach for subpixel change detection in satellite imagery[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(11)：1977-1993.

[18]Veksler O.Fast variable window for stereo correspondence using integral images[C].Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Madison,USA,2003：556-561.

[19]Wei Yi-chen and Quan Long.Region-based progressive stereo matching[C].Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Washington,D.C.,USA,2004：106-113.

[20]黎俊,彭啟民,范植華.亞像素級圖像配準(zhǔn)算法研究[J].中國圖象圖形學(xué)報(bào),2007,13(11)：2070-2075.Li Jun,Peng Qi-min,and Fan Zhi-hua.A survey of sub-pixel image registration methods[J].Journal of Image and Graphics,2007,13(11)：2070-2075.