基于交互式圖像分割的立體匹配方法

王雅寧，梁新剛

(1.現代教學技術教育部重點實驗室，陜西西安 710062; 2.陜西師范大學計算機科學學院，陜西西安 710119)

基于交互式圖像分割的立體匹配方法

王雅寧1，梁新剛2

(1.現代教學技術教育部重點實驗室，陜西西安 710062; 2.陜西師范大學計算機科學學院，陜西西安 710119)

立體匹配技術是三維重建系統(tǒng)以及非接觸測量的關鍵步驟，在計算機視覺領域應用廣泛。傳統(tǒng)基于全局最優(yōu)的立體匹配方法計算量大，算法框架復雜，通過引入圖像分割等手段可以有效降低立體匹配的運算量。為了克服傳統(tǒng)基于分割的立體匹配方法沒有充分利用分割信息的缺點，提出了一種融合交互式圖像分割的立體匹配方法。該方法通過引入用戶交互，設置種子點并用快速圖割算法完成感興趣區(qū)域的分割提取，由分割模板建立網絡圖，進行立體匹配。由于僅針對分割區(qū)域構建網絡圖，充分利用網絡圖信息降低了運算量，因此，和現有的對整幅圖像進行立體匹配方法相比，具有匹配準確、運算量小等優(yōu)點，并通過實驗進行了驗證。

立體匹配;圖割算法;交互;圖像分割

0 引言

立體匹配技術是近年來計算機視覺領域廣泛關注的難點和熱點，它的目的是通過匹配兩幅或多幅圖像來獲得視差圖，以便可以計算出場景中的三維信息［1］。由于圖割算法具有組合優(yōu)化的優(yōu)良性能，并且能夠有效處理低紋理區(qū)域和遮擋像素［2］，因此廣泛應用于立體匹配中。

Roy等［3］最早將圖割算法應用于立體匹配，并通過實驗表明，圖割算法能有效克服其他全局優(yōu)化算法的缺點(如動態(tài)規(guī)劃算法等生成視差圖產生的橫向條紋瑕疵)，避免了視差在臨近極線處不連續(xù)的問題。但該算法生成的視差圖輪廓邊緣模糊，視差層的區(qū)分度低。Boykov等［4］利用特定約束構造能量函數，并通過改進的最大流方法進行能量函數的最小化，將該圖割算法應用于立體匹配問題，取得了效果良好的致密視差圖。但該方法構建網絡圖時生成了大量節(jié)點，導致空間復雜度較高，同時，該算法運算過程需要多次迭代，時間復雜度高，無法達到實時計算的要求。為了提高匹配速度，Li等［5］提出基于無重疊視差區(qū)域分割的立體匹配，并用分割塊的能量最小化取代了常用圖割算法像素級的能量最小化，降低了算法的時間復雜度，但生成的視差圖邊緣處有毛刺現象。Bleyer等［6］利用圖像在每個分割塊中的視差具有光滑性的特點，提出了基于圖像分割的立體匹配算法的通用算法。但該方法無法得到像素級的最優(yōu)分配，且復雜度高，計算量大。Bleyer等［7］提出采用基于低尺度分割，將圖像分割成超像素形式從而減少圖割算法生成節(jié)點的立體匹配方法。假設相同物體具有緊湊、連接并且物體表面視差變化平滑等特性，提出了一種新的基于物體分割的立體匹配方法。該方法雖然在物體分割與視差獲取上效果良好，但是運算量大，對于物體和背景的內部區(qū)域缺少紋理的深度信息，并且物體間的區(qū)域沒有準確的視差標注。

上述文獻中基于圖像分割的立體匹配方法，由于采用自動化非交互的彩色圖像分割方法會把相同視差的區(qū)域分開或隱去了圖像的部分細節(jié)信息，導致分割誤差，而消除誤差需要引入其他方法，如初始視差估計［4-5］等，但這些方法增加了立體匹配算法的整體復雜度，而且沒有有效利用分割信息。在實際應用場景中，為了獲取感興趣區(qū)域的精細視差圖，針對以往基于圖像分割的立體匹配算法復雜、計算量大，沒有充分利用分割結果的信息等缺點［8］，提出一種基于交互式圖像分割的立體匹配方法。該方法在圖像分割時采用可交互的圖割方法獲得感興趣目標，只針對感興趣目標進行立體匹配，因此運算量大大減少，同時保留了原有圖割算法具有的全局最優(yōu)特性。

1 基于圖割算法的立體匹配

在立體匹配問題中，視差圖的標號問題可以等價為全局能量函數的最小化求值問題［9］，通常表示為Greig能量函數形式:

其中，f為視差標注;p為所有像素的集合;Dp為數據項;Vp，q(fp，fq)為平滑項;I1為待匹配圖像;M?P*P為相鄰像素對集合。

數據項一般可寫成:

平滑項普遍選用Potts模型:

根據圖割算法，利用式(1)構造由節(jié)點和連接節(jié)點的有向邊組成的網絡圖G=＜V，E＞。網絡圖如圖1所示［10］。

圖1中，S點表示源點，T點表示匯點，視差邊對應于能量函數式(1)中的第一項，平滑邊對應于能量函數第二項。求解式(1)的能量函數的最小值可以等價為求解圖的最小割問題，獲得全局最優(yōu)的視差圖。

2 交互式快速圖像分割

傳統(tǒng)基于圖割算法的圖像分割將圖像信息轉化為求解對應加權圖的最大流/最小割問題［4］，對于低分辨率的簡單圖像交互分割效果良好但是計算復雜度較高［11-12］，內存開銷大。為了提高分割速度并且適用于高分辨率圖像，需要減少分割網絡中的節(jié)點個數，通過添加輔助顏色索引節(jié)點［13］，重新定義能量函數為:

其中，θs與θs-表示前景物體跟背景的非歸一直方圖;σ為圖像中所有ΔI的均值。

該方法提高了圖割算法圖像分割的計算時間，并且能夠得到精準的分割結果。

3 基于交互式圖像分割的立體匹配

為了減少立體匹配的運算量，文中根據交互式分割的結果得到感興趣物體與分割模版，由分割模版構建網絡圖，使用圖割算法進行立體匹配，有效利用了分割信息。

綜上所述，該算法可以概括為兩大步驟:感興趣目標的提取;利用網絡圖進行立體匹配。算法流程圖如圖2所示。

相對于傳統(tǒng)方法，根據每個像素構建網絡圖的算法有所不同。對于圖G=＜V，E＞，在兩端分別添加源點S、匯點T之后，只在S到I1中每個屬于左視圖分割模版中標記為目標的像素點之間添加邊，在T到集合{(px，py，qn)|(px，py)∈ I1}即立方體網絡上與OXY平面相對的另一個面上的節(jié)點，添加對應到匯點的邊。通過上述方法，可以大大減少計算量。

為了進一步優(yōu)化匹配結果，文中在對網絡圖中視差邊的處理上，針對彩色圖像采用RGB三通道分開處理，用線性最近鄰插值算法在圖像的橫坐標方向添加了亞像素信息，即將式(2)擴展為:

其中，ΔR，ΔB，ΔG為彩色圖像各個通道的權值。

按照上述方法構造網絡圖G=＜V，E＞，并給各個邊賦相應的權值，采用基于增廣路的最大流算法進行求解［14-15］，得到全局最小值，即為最優(yōu)視差匹配。

4實驗

為了驗證文中方法的有效性，在Windows 7 64位系統(tǒng)，CPU為2.5 GHz，內存8 G，編譯器為Visual Studio 2010的測試環(huán)境下進行實驗。實驗圖像來自Middlebury提供的立體匹配圖像庫:vision.middlebury. edu/stereo/data/。文中采用錯誤匹配率衡量算法的匹配性能，其定義如下［16］:

其中，M為整個圖像的像素數;dC(x，y)為計算出的視差圖;dT(x，y)為真實的視差圖，在比對中，標準的真實視差圖只取跟分割模板相同的部分，其余全部設置為背景;δ為誤差容許值，取1。

利用上述圖像庫中提供的圖像對，文中利用原始圖割算法和SAD［16］算法分別對Tsukaba圖像進行立體匹配，結果如圖3所示。

從圖3的視差圖可以看出，相對于局部算法SAD［10］和圖割算法，文中算法取得了較好的效果，并且最接近于標準視差。由于文中算法分割效果準確，并通過加權分通道處理、添加亞像素信息等手段，不但保證了視差圖邊緣的準確性，也保留了感興趣區(qū)域內部的視差標注。

圖3 立體匹配結果對比圖

同時，為了進一步驗證文中算法對遮擋，深度不連續(xù)，光照變化，低紋理、無紋理區(qū)域等的匹配性能，對Middlebury平臺提供的部分標準圖像進行實驗，結果如圖4所示。

從圖4中可以看出，文中方法對于遮擋，深度不連續(xù)，光照變化，低紋理、無紋理區(qū)域等情形取得了較好的效果。同時，使用錯誤匹配率對實驗結果進行定量分析，結果如表1所示。

從表1可以看出，與局部SAD算法、原始圖割算法相比，文中算法具有相當高的精度。同時，為了比較算法的運算速度，文中統(tǒng)計了各個算法的運行時間，如表2所示。

從表2可以看出，由于相對于傳統(tǒng)圖割算法，文中算法只對分割出的感興趣區(qū)域生成了立體網格，所以避免了多余的計算，因此，相對于全局優(yōu)化的圖割算法減少了運算時間。雖然文中算法運算時間大于局部算法，但是精度遠高于局部算法，因為文中算法為了獲取全局最優(yōu)的視差標注進行了迭代運算，而SAD算法根據鄰域窗進行橫向匹配，僅能得到局部視差的近似解。

5 結束語

針對基于圖像分割的立體匹配方法沒有有效利用分割信息的問題，文中利用圖割算法實現了基于交互式圖像分割的立體匹配。該方法對于遮擋，深度不連續(xù)，光照變化，低紋理、無紋理區(qū)域均取得了良好的匹配結果。相對于以往算法，該方法得到了精確的匹配結果，并且在運算時間和計算精度上都有提高。

［1］ 肖艷青，劉黨輝，孫 朋.圖像立體匹配研究進展［J］.測控技術，2009，28(8):1-5.

［2］ 伍春洪，付國亮.一種基于圖像分割及鄰域限制與放松的立體匹配方法［J］.計算機學報，2011，34(4):755-760.

［3］ Roy S，Cox I J.A maximum-flow formulation of the ncamera stereo correspondence problem［C］//Proc of IEEE international conference on computer vision.Bombay，India: ［s.n.］，1998:492-499.

［4］ Boykov Y，Kolmogorov V.An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26(9):1124-1137.

［5］ Hong L，Chen G.Segment-based stereo matching using graph cuts［C］//Proc of IEEE conference on computer vision and pattern recognition.Washington DC，USA:IEEE，2004:74-81.

［6］ Bleyer M，Gelautz M.Graph-cut-based stereo matching using image segmentation with symmetrical treatment of occlusions［J］.Signal Processing Image Communication，2007，22(2):127-143.

［7］ Bleyer M，Rother C，Kohli P，et al.Object stereo-joint stereo matching and object segmentation［C］//Proc of IEEE conference on computer vision and pattern recognition.Colorado，USA:IEEE，2011:3081-3088.

［8］ 尹傳歷，劉冬梅，宋建中.改進的基于圖像分割的立體匹配算法［J］.計算機輔助設計與圖形學學報，2008，20(6):808 -812.

［9］ 王 年，范益政，鮑文霞，等.基于圖割的圖像匹配算法［J］.電子學報，2006，34(2):232-236.

［10］張令濤，曲道奎，徐 方.一種基于圖割的改進立體匹配算法［J］.機器人，2010，32(1):104-108.

［11］尹傳歷，向長波，宋建中，等.一種基于自適應窗口和圖切割的快速立體匹配算法［J］.光學精密工程，2008，16(6): 1117-1121.

［12］祝世平，楊 柳.基于自適應分水嶺的圖割的立體匹配算法［J］.光學學報，2013(3):221-229.

［13］Tang M，Gorelick L，Veksler O，et al.GrabCut in one cut ［C］//Proc of IEEE international conference on computer vision.Sydney，Australia:IEEE，2013:1769-1776.

［14］Kolmogorov V.Graph based algorithms for scene reconstruction from two or more views［D］.New York:Cornell University，2004.

［15］Kolmogorov V，Zabih R.Multi-camera scene reconstruction via graph cuts［C］//Proc of European conference on computer vision.Copenhagen:［s.n.］，2002:82-96.

［16］Scharstein D，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.

A Stereo Matching Method Based on Interactive Image Segmentation

WANG Ya-ning1，LIANG Xin-gang2
(1.Key Laboratory of Modern Teaching Technology of Ministry of Education，Xi’an 710062，China; 2.School of Computer Science，Shaanxi Normal University，Xi’an 710119，China)

Stereo matching technology is the key step in 3D-reconstruction system and non-contact measurement，which has a wide range of applications in computer vision.The traditional stereo matching method based on global optimization is of large computation quantity，and the framework of its algorithm is very complex.By using the method of image segmentation，it can effectively reduce the amount of computation.In order to overcome the disadvantage that traditional method cannot make use of the information of segmentation，a stereo matching method integrated human-computer interaction image segmentation is presented.Introducing the user interaction and setting the seeds，the Region Of Interest(ROI)segmentation area is obtained by a fast graph cuts algorithm.Then the stereo matching is realized based on the network map which is constructed from the segmentation template.Compared with existing stereo matching methods，the method proposed has more accurate and less computational cost，which is verified by experiment.

stereo matching;graph cuts;interaction;image segmentation

TP391.4

A

1673-629X(2016)09-0163-04

10.3969/j.issn.1673-629X.2016.09.036

2015-09-19

2016-02-24< class="emphasis_bold">網絡出版時間:

時間:2016-08-23

陜西省自然科學基礎研究計劃項目(2011JM8014);陜西師范大學實驗技術研究項目(SYJS201314)

王雅寧(1990-)，男，碩士，研究方向為計算機視覺。

http://www.cnki.net/kcms/detail/61.1450.TP.20160823.1343.034.html