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

孫東亮，余貞俠，魏 敏

(成都信息工程學(xué)院計(jì)算機(jī)學(xué)院，四川成都610225)

0 引言

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

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

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

1 算法設(shè)計(jì)

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

圖1 算法流程圖

1.1 圖像分割

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

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

以Middlebury大學(xué)計(jì)算機(jī)視覺研究室網(wǎng)站的標(biāo)準(zhǔn)測試數(shù)據(jù)“Tsukuba”圖作為研究對象，Tsukuba在左視點(diǎn)的圖像如圖2所示，設(shè)置參數(shù)hs=7，hr=5.6，分割區(qū)域最小像素個(gè)數(shù)為20，以文獻(xiàn)[12]的方法對Tsukuba圖進(jìn)行分割得到分割結(jié)果如圖3所示。

圖2 Tsukuba左視圖

圖3 Tsukuba分割圖

1.2 基于自適應(yīng)權(quán)值的匹配及雙向檢測

1.2.1 基于自適應(yīng)權(quán)值的匹配

Yoon和Kweon從人類視覺出發(fā)，利用格式塔心理學(xué)的接近性原則和相似性原則設(shè)計(jì)窗口匹配加權(quán)系數(shù)，這個(gè)權(quán)值由兩個(gè)像素間的空間相近性和顏色相似性計(jì)算得來，所以權(quán)值大小具有自適應(yīng)性，其計(jì)算方式為

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

其中γc和γp分別為顏色差異參數(shù)和距離差異參數(shù)。設(shè)p是左視點(diǎn)圖中的像素，pd是視差為d時(shí)p點(diǎn)在右視點(diǎn)圖中的對應(yīng)像素，那么相關(guān)窗內(nèi)的匹配代價(jià)累計(jì)公式為

其中q是在左視點(diǎn)圖中p的相關(guān)窗內(nèi)的像素，而qd是在右視點(diǎn)圖中pd的相關(guān)窗內(nèi)的像素

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

文獻(xiàn)[13]對此方法進(jìn)行詳細(xì)的分析，并提出利用分割結(jié)果，對同一區(qū)域內(nèi)的兩個(gè)像素點(diǎn)將距離權(quán)值設(shè)為1，從結(jié)果看修正了原方法的很多錯(cuò)誤，所以文中方法也借鑒此改進(jìn)，將像素點(diǎn)p和q之間的權(quán)值度量方法更改為

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

圖4 Tsukuba初始視差圖

1.2.2 雙向檢測

可以看到在WTA策略下每個(gè)像素一定會得到一個(gè)在匹配代價(jià)準(zhǔn)則下的最優(yōu)視差值，然而對于圖像內(nèi)的遮擋區(qū)域的像素，其在一幅圖中可見而在另一幅圖中不可見，是不應(yīng)該找到最佳匹配的。

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

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

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

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

圖5 Tsukuba雙向檢測后視差圖

1.3 平面模型求取與優(yōu)化

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

1.3.1 基于局部評價(jià)函數(shù)的遺傳算法求取可信區(qū)域平面模型

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

借鑒全局匹配中能量最小化框架，首先為每個(gè)區(qū)域i定義一個(gè)能量函數(shù)

這個(gè)能量函數(shù)包括兩部分，其中第一部分為數(shù)據(jù)能量被定義為

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

第二部分為遮擋能量，λocc表示遮擋懲罰常量，Eocclude是區(qū)域內(nèi)當(dāng)前平面參數(shù)下求得的視差值，經(jīng)雙向檢測后不滿足條件的像素個(gè)數(shù)。

可以看到，這個(gè)能量函數(shù)的數(shù)據(jù)能量部分，用相對應(yīng)的像素色彩差異反映了區(qū)域內(nèi)像素在所選視差下的匹配準(zhǔn)確程度，而遮擋能量則反映遮擋現(xiàn)象引起的錯(cuò)誤對匹配的影響，所以要做的就是尋找能夠使能量函數(shù)最小的視差平面，這樣得到的結(jié)果才具有高的匹配精度。

具體實(shí)現(xiàn)步驟如下:

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

種群評價(jià):以Ei作為區(qū)域的評價(jià)函數(shù)，對每條染色體進(jìn)行評價(jià)獲得適應(yīng)度值;

選擇:選用輪盤賭策略依據(jù)最適應(yīng)概率選擇進(jìn)行交叉的染色體;

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

生成新的種群:迭代進(jìn)行選擇和交叉步驟后可得到一個(gè)新的種群，對新的種群進(jìn)行適應(yīng)度值評價(jià)后，將當(dāng)前最好染色體替代新種群中最差染色體保存在當(dāng)代種群中;

最后將種群中最佳平面參數(shù)作為得到的區(qū)域平面模型。

1.3.2 優(yōu)化區(qū)域平面模型

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

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

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

其中Bc為當(dāng)前區(qū)域邊界的可見點(diǎn)集合，q為p的4鄰域可見像素。

2 實(shí)驗(yàn)結(jié)果和分析

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

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

圖6 Tsukuba最終視差圖

圖7 Tsukuba的真實(shí)視差圖

圖8 Tsukuba的錯(cuò)誤匹配圖

表1 誤匹配率結(jié)果對比

3 結(jié)束語

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

致謝:感謝成都信息工程學(xué)院人才基金(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] 鄭志剛，高精度攝像機(jī)標(biāo)定和魯棒立體匹配算法研究[D].合肥:中國科學(xué)技術(shù)大學(xué)，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.