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

邊繼龍 門朝光 李 香

(哈爾濱工程大學計算機科學與技術學院 哈爾濱 150001)

1 引言

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

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

2 算法框架

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

3 算法的關鍵步驟及實現

3.1 局部匹配的數學分析

假設立體像對滿足經典立體模型：

式中代表參考圖像，u(x)代表匹配圖像，ε(x)代表視差函數，gb(x)代表圖像噪聲。該模型僅在小基高比條件下才能滿足，而且基高比越小模型越精確?；谛』弑鹊牧Ⅲw匹配方法[12]假設立體像對滿足該模型并通過最大化支撐窗口間的互相關系數為參考圖像中的每一點計算視差，其計算公式如下：

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

式(2)表明互相關函數的極值點所對應的視差值即為對應點視差，而且極值點即為導數為零的點，通過令連續互相關函數的導數為零可得

式中

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

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

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

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

3.2 積分圖像加速

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

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

證明

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

相應的規范互相關系數的離散形式為

3.3 可信視差估計

雖然匹配過程僅處理那些在窗口選擇階段確定的可信點，但在匹配過程中還會存在一些誤匹配。為進一步拒絕錯誤匹配提高后續區域擬合的準確性，本文對匹配過程施加了類似于文獻[19]中的可靠性約束。

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

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

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

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

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

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

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

(2)根據對應點和窗口大小計算偏移窗口集。

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

式中INT(?)表示取整操作，xp表示p點的橫坐標，yp表示p點的縱坐標。

(4)根據規范互相關系數選擇最優偏移量。

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

(5)計算亞像素級對應點位置。

(6)當k≤kmax轉入步驟(2)繼續迭代。

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

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

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

4 實驗結果

4.1 時間復雜度分析

現假設圖像共有M個像素，窗口最大值為Wmax，最小值為Wmin，則直接實現窗口選擇公式的時間復雜度為當使用積分圖像對該公式加速時，計算窗口選擇公式的時間復雜度僅為像的時間復雜度為O(M)，總共的時間復雜度為O(M)。

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

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

4.2匹配精度分析

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

圖2 Toulouse立體像對

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

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

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

圖3 實驗結果對比

表1 均方根誤差和運行時間

5 結論

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

[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 的立體視覺匹配的高性能實現[J].電子與信息學報,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]黎俊,彭啟民,范植華.亞像素級圖像配準算法研究[J].中國圖象圖形學報,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.