一種基于分割的立體匹配算法

孫東亮，余貞俠，魏 敏

(成都信息工程學院計算機學院，四川成都610225)

0 引言

當人們逐漸意識到“視覺應該是簡單的事情”是一種誤解時，對計算機視覺的研究也成為獨立的研究領域，而關于立體匹配的主題作為這一領域研究最廣和最基礎的問題之一，仍是最活躍的研究方向之一。立體匹配過程嘗試尋找兩幅或者多幅圖像間的匹配像素點，然后將它們的2D位置轉化為3D深度，從而可以估計出場景的一個3D模型，這使立體匹配成為眾多研究方向的基礎，例如攝影測地學關注的航空影像、人視覺系統建模、視圖差值和基于圖像渲染等。

Scharstein和Szeliski[1]將稠密立體匹配算法分為局部算法和全局算法兩部分。局部(基于窗口的)算法主要針對圖像每個像素點，在局部有限窗口內計算其亮度差異等代價函數，并以窗口內聚合后具有最小代價的視差作為最佳視差。Tomvari，Mattoccia等[2]比較的所有局部聚集方法中，Yoon與 Kweon[3]的局部加權方法在平衡性能和速度兩方面具有突出的效果。全局算法通常不進行聚集操作，而是在初步得到視差值后，最小化一個包含數據項和平滑項的全局代價函數，不同算法間的主要區別在于使用的尋找最小值過程。其中基于動態規劃的算法，圖割的算法，基于置信度傳播的方法等均取得很好的效果。

基于分割的立體匹配算法，主要是基于場景分段平滑性假設，根據色彩和邊界信息將場景分割為一系列區域，并嘗試給每個區域標記一個視差。Tao等[4]首先利用局部的方法估計逐像素的視差，然后將圖像的分割結果應用到匹配過程中，使用一個平面模型表示每個分割區域，最后加入相鄰區域的平滑性約束，以全局匹配能量最小化的形式精化得到視差。在Tao等提出的框架基礎上，發展了非常多的基于圖像分割的立體匹配算法，并且取得不錯的效果[5－11]。

1 算法設計

提出的基于分割的立體匹配算法，使用均值漂移算法進行圖像的分割，改進Yoon等的算法進行初始視差圖的求取，并使用兩次不同的能量函數對平面模板參數進行求取與最優選擇。具體流程如圖1所示。

圖1 算法流程圖

1.1 圖像分割

均值漂移(Mean Shift)算法[12]的實質是核密度估計，核心是對特征空間的樣本點進行聚類，應用到彩色圖像分割中就是對圖像的色彩信息進行聚類，以不同的色彩類表示不同的物體。在具體實現中如文獻[12]所表述，將圖像看作是五維向量，其中顏色信息占3個分量，像素位置信息占2個分量，其核函數的具體形式為

其中hs、hr為控制空間域和顏色域的平滑解析度，C為歸一化常數。

以Middlebury大學計算機視覺研究室網站的標準測試數據“Tsukuba”圖作為研究對象，Tsukuba在左視點的圖像如圖2所示，設置參數hs=7，hr=5.6，分割區域最小像素個數為20，以文獻[12]的方法對Tsukuba圖進行分割得到分割結果如圖3所示。

圖2 Tsukuba左視圖

圖3 Tsukuba分割圖

1.2 基于自適應權值的匹配及雙向檢測

1.2.1 基于自適應權值的匹配

Yoon和Kweon從人類視覺出發，利用格式塔心理學的接近性原則和相似性原則設計窗口匹配加權系數，這個權值由兩個像素間的空間相近性和顏色相似性計算得來，所以權值大小具有自適應性，其計算方式為

其中Δ cpq和Δ gpq分別為p和q兩個像素點間的顏色差異和空間距離差異，k為比率常數。其中顏色差異是在CIELab顏色空間下計算得到，空間距離差異由兩個像素之間空間距離作為度量，又由于顏色接近性和空間接近性是相互獨立的，且選取了基于拉普拉斯核函數的權值度量，于是有

其中γc和γp分別為顏色差異參數和距離差異參數。設p是左視點圖中的像素，pd是視差為d時p點在右視點圖中的對應像素，那么相關窗內的匹配代價累計公式為

其中q是在左視點圖中p的相關窗內的像素，而qd是在右視點圖中pd的相關窗內的像素

最后在一定視差范圍內，對每個像素采用贏者通吃(winner-take-all，WTA)策略選擇使累計代價 E(p，pd)最小的d值作為其視差。

文獻[13]對此方法進行詳細的分析，并提出利用分割結果，對同一區域內的兩個像素點將距離權值設為1，從結果看修正了原方法的很多錯誤，所以文中方法也借鑒此改進，將像素點p和q之間的權值度量方法更改為

仍然以“Tsukuba”圖作為實驗對象，設置參數如下:窗口大小31×31，比率常數k=1.0，顏色差異參數γg=7.0，空間距離差異參數γc=36.0，視差浮動范圍0～15。需要注意的是，結果圖中便于觀察，所有視差圖中的視差值均乘16，以左視點圖像為參考圖，右視點圖像為匹配圖，得到左視點圖像的視差圖如圖4所示。

圖4 Tsukuba初始視差圖

1.2.2 雙向檢測

可以看到在WTA策略下每個像素一定會得到一個在匹配代價準則下的最優視差值，然而對于圖像內的遮擋區域的像素，其在一幅圖中可見而在另一幅圖中不可見，是不應該找到最佳匹配的。

雙向檢測可以準確地找到不可信視差值，具體實現方式是，首先利用基于自適應權值的方法分別將左右視圖看做參考圖得到各自的視差圖，然后定義一個錯誤允許值Tc(Tc≥1)，以左視差圖為參考，遍歷左視差圖的所有像素點，在每一點(x，y)處的視差值為dL(x，y)，可以得到匹配圖右視差圖中坐標為 (xdL(x，y)，y)處的視差值dR(x－ dL(x，y)，y)。認定當滿足

則認為左視差圖中坐標為(x，y)處的視差值是可信的，不然就將該坐標處的視差值置為不可信，用視差0進行填充標記，遍歷完成得到可信的左視差圖，如圖5所示。

依據相同的原理，以右視差圖為參考圖像，遍歷右視差圖的所有像素點，在每一點(x，y)處的視差值為dR(x，y)，可以得到匹配圖右視差圖中坐標為 (x+dR(x，y)，y)處的視差值dL(x+dR(x，y)，y)。當滿足

則認為右視差圖中坐標為(x，y)處的視差值是可信的，不然就將該坐標處的視差值置為不可信，用視差0進行填充標記，遍歷完成得到可信的右視差圖。

圖5 Tsukuba雙向檢測后視差圖

1.3 平面模型求取與優化

在場景分段平滑性假設中，對于區域內平滑過渡的視差可以通過擬合平面或曲面的方法計算分塊內的視差。平面或曲面模型能較好的改善無紋理區域在局部匹配下的錯誤，對于遮擋區域可以認為是相鄰可見區域視差的光滑過度，從而可以利用擬合得到的視差平面直接計算得到遮擋區域的視差值。

1.3.1 基于局部評價函數的遺傳算法求取可信區域平面模型

最小二乘法是平面擬合中最常用的方法，其本質是求取均方代價最小問題，體現的是全局最優性，但是其對奇異值非常敏感，對最終結果的影響較大。遺傳算法是一種模擬自然進化過程搜索最優解或次優解的方法，主要包括編碼初始化、種群評價、選擇、交叉、變異等步驟[14]。

借鑒全局匹配中能量最小化框架，首先為每個區域i定義一個能量函數

這個能量函數包括兩部分，其中第一部分為數據能量被定義為

其中VL、VR分別代表左右圖當前區域可見像素，像素pd與像素p為一對兒匹配像素，pd由p在當前平面參數下求得的視差d計算而來，r、g、b代表像素顏色分量。

第二部分為遮擋能量，λocc表示遮擋懲罰常量，Eocclude是區域內當前平面參數下求得的視差值，經雙向檢測后不滿足條件的像素個數。

可以看到，這個能量函數的數據能量部分，用相對應的像素色彩差異反映了區域內像素在所選視差下的匹配準確程度，而遮擋能量則反映遮擋現象引起的錯誤對匹配的影響，所以要做的就是尋找能夠使能量函數最小的視差平面，這樣得到的結果才具有高的匹配精度。

具體實現步驟如下:

編碼初始化:這里采用實數編碼，將平面參數看作是遺傳因子，每一條染色體就是一組平面參數。首先對有足夠可信點的分割區域，隨機選取可信點由最小二乘法獲取一組平面參數作為一條染色體，重復N次得到一個大小為N的初始種群;

種群評價:以Ei作為區域的評價函數，對每條染色體進行評價獲得適應度值;

選擇:選用輪盤賭策略依據最適應概率選擇進行交叉的染色體;

交叉:在一定交叉概率下進行交叉操作，交叉操作選用均勻交叉算子即在滿足一定概率的情況下對相對應的基因進行交叉，由此可得到兩條新的染色體;

生成新的種群:迭代進行選擇和交叉步驟后可得到一個新的種群，對新的種群進行適應度值評價后，將當前最好染色體替代新種群中最差染色體保存在當代種群中;

最后將種群中最佳平面參數作為得到的區域平面模型。

1.3.2 優化區域平面模型

對于圖像中區域過小或者因雙向檢測后可信視差值不足的區域，可以使用已經得到的平面模型，依據使能量函數最小的策略，為它們選擇一個最適應的平面模型。

這里重新定義能量函數，在原有能量函數的基礎上增加了平滑項能量，平滑能量反映出相鄰像素間視差的變化差異，使它最小則可以保證區域內像素的平滑過渡。重寫能量函數如下所示

其中第三部分為平滑能量，λs表示平滑懲罰常量

其中Bc為當前區域邊界的可見點集合，q為p的4鄰域可見像素。

2 實驗結果和分析

為檢驗提出的算法的效果，在VS2010上編程對算法進行實現，展示的結果圖為對測試平臺(http://vision.middlebury.edu/stereo)內的數據之一 Tsukuba場景圖的處理結果。初始視差求取時參數為窗口大小31×31而顏色差異參數為γc=7，距離差異參數為γp=30，而在能量函數中遮擋懲罰常量為λocc=20，平滑懲罰常量為λs=10，平面擬合是可信區域需最少具有100個可信點，遺傳算法中種群大小為50，交叉概率為0.5，均勻交叉算子內交叉概率為0.5，迭代次數為20。在這些參數下對圖5所示的視差圖，進行平面模型的求取與優化步驟，得到如圖6所示的Tsukuba的最終視差圖，另外從Middlebury網站上獲取Tsukuba圖的真實視差圖如圖7所示，于是得到文中算法得到的視差圖與真實視差圖相比發生錯誤的地方，如圖8所示。

文中算法是在經過校對的標準雙目系統下對獲取到的圖片進行處理的，在標準測試平臺提供的測試數據集下，上傳處理結果經過在線測試得到的誤匹配率結果如表1所示，其中包括 Tsukuba、Venus、Teddy和Cones 4個場景圖，并將每個場景圖下的非遮擋區域誤匹配率、整體誤匹配率和視差邊緣處誤匹配率作為評價標準。在與 Scharstein和 Szeliski提出的圖割(Graph-cut，GC)算法和動態規劃(Dynamic programing，DP)算法及Qingxiong Yang提出的置信度傳播(Belief-propagation，BP)算法[15]的比較中，可以看到文中算法在視差不連續區域，及無紋理區域的視差求取的視差具有相對較高的準確度，但是從圖8所示的誤匹配圖及圖2所示的分割結果圖中可以分析出，由于分割錯誤造成的區域邊界的視差結果錯誤，文中算法并沒有很好的解決這一問題。

圖6 Tsukuba最終視差圖

圖7 Tsukuba的真實視差圖

圖8 Tsukuba的錯誤匹配圖

表1 誤匹配率結果對比

3 結束語

在圖像分割的基礎上提出一種新的立體匹配算法。首先使用mean-shift算法對左右原始圖像進行分割，再利用局部的基于窗的自適應權值的方法得到初始視差圖，經雙向檢測后對可信區域采用基于能量函數最小化的遺傳算法進行平面擬合，并經平面模型再分配過程得到最終的視差圖。實驗結果表明，文中算法可以有效地處理深度不連續區域，及無紋理區域匹配精度高，得到了更為準確的稠密視差圖。但是從結果中也看到，對于分割錯誤造成的像素點的錯誤匹配仍有提高的余地。

致謝:感謝成都信息工程學院人才基金(J201212)對本文的資助

[1] Scharstein D，R Szeliski.A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms[J].International Journal of Computer Vision，2002，47(1－3):7－42.

[2] Tombari F.Classification and evaluation of cost aggregation methods for stereo correspondence[C].in ComputerVision and Pattern Recognition，CVPR 2008.IEEE Conference on，2008.

[3] Kuk-Jin Y，K In-So.Locally adaptive supportweight approach for visual correspondence search[C].in Computer Vision and Pattern Recognition，CVPR 2005.IEEE Computer Society Conference on，2005.

[4] Hai T，H S Sawhney，R Kumar.A global matching framework for stereo computation.in Computer Vision[C].ICCV 2001.Proceedings.Eighth IEEE International Conference on，2001.

[5] Zeng-Fu W，Z Zhi-Gang.A region based stereo matching algorithm using cooperative optimization[C].in Computer Vision and Pattern Recognition，CVPR 2008.IEEE Conference on，2008.

[6] Klaus A，M Sormann，K Karner.Segment-Based Stereo Matching Using Belief Propagation and a Self-Adapting Dissimilarity Measure[C].in Pattern Recognition，2006.ICPR 2006.18th International Conference on，2006.

[7] Yang Q.Stereo matching with color-weighted correlation，hierarchical belief propagation，and occlusion handling[J].IEEE Trans Pattern Anal Mach Intell，2009，31(3):492－504.

[8] 鄭志剛，高精度攝像機標定和魯棒立體匹配算法研究[D].合肥:中國科學技術大學，2008.

[9] Zitnick C L，Kang S B，Uyttendaele M，et al.High-quality video view interpolation using a layered representation[J].ACM Transactions on Graphics(Proc.SIGGRAPH 2004)，2004，23(3):600－608.

[10] Zitnick C L，Kang S B.Stereo for image-based rendering using image over-segmentation[J].International Journal of Computer Vision，2007，75(1):49－65.

[11] Taguchi Y，Wiburn B，Zitnick C L.Stereo reconstruction with mixed pixels using adaptive oversegmentation[C].IEEE Computer Society Conference on Computer Vision and Pattern Recognition(CVPR 2008)，2008.

[12] Comaniciu D，P Meer.Mean shift analysis and applications[C].in Computer Vision，1999.The Proceedings of the Seventh IEEE International Conference on，1999.

[13] Tombari F，S Mattoccia，L Stefano.Segmentation-Based Adaptive Support for Accurate Stereo Correspondence，in Advances in Image and Video Technology[M].Springer Berlin Heidelberg.

[14] Chaiyaratana N，A M S Zalzala.Recent developments in evolutionary and genetic algorithms:theory and applications[C].in Genetic Algorithms in Engineering Systems:Innovations and Applications，1997.GALESIA 97.Second International Conference On(Conf.Publ.No.446)，1997.

[15] Qingxiong Y，W Liang，N Ahuja.A constantspace beliefpropagation algorithm forstereo matching[C].in Computer Vision and Pattern Recognition(CVPR)，2010 IEEE Conference on，2010.