王雅寧，梁新剛

(1.現(xiàn)代教學(xué)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，陜西西安 710062; 2.陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，陜西西安 710119)

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

王雅寧1，梁新剛2

(1.現(xiàn)代教學(xué)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，陜西西安 710062; 2.陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，陜西西安 710119)

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

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

0 引言

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

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

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

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

在立體匹配問(wèn)題中，視差圖的標(biāo)號(hào)問(wèn)題可以等價(jià)為全局能量函數(shù)的最小化求值問(wèn)題［9］，通常表示為Greig能量函數(shù)形式:

其中，f為視差標(biāo)注;p為所有像素的集合;Dp為數(shù)據(jù)項(xiàng);Vp，q(fp，fq)為平滑項(xiàng);I1為待匹配圖像;M?P*P為相鄰像素對(duì)集合。

數(shù)據(jù)項(xiàng)一般可寫(xiě)成:

平滑項(xiàng)普遍選用Potts模型:

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

圖1中，S點(diǎn)表示源點(diǎn)，T點(diǎn)表示匯點(diǎn)，視差邊對(duì)應(yīng)于能量函數(shù)式(1)中的第一項(xiàng)，平滑邊對(duì)應(yīng)于能量函數(shù)第二項(xiàng)。求解式(1)的能量函數(shù)的最小值可以等價(jià)為求解圖的最小割問(wèn)題，獲得全局最優(yōu)的視差圖。

2 交互式快速圖像分割

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

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

該方法提高了圖割算法圖像分割的計(jì)算時(shí)間，并且能夠得到精準(zhǔn)的分割結(jié)果。

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

為了減少立體匹配的運(yùn)算量，文中根據(jù)交互式分割的結(jié)果得到感興趣物體與分割模版，由分割模版構(gòu)建網(wǎng)絡(luò)圖，使用圖割算法進(jìn)行立體匹配，有效利用了分割信息。

綜上所述，該算法可以概括為兩大步驟:感興趣目標(biāo)的提取;利用網(wǎng)絡(luò)圖進(jìn)行立體匹配。算法流程圖如圖2所示。

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

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

其中，ΔR，ΔB，ΔG為彩色圖像各個(gè)通道的權(quán)值。

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

4實(shí)驗(yàn)

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

其中，M為整個(gè)圖像的像素?cái)?shù);dC(x，y)為計(jì)算出的視差圖;dT(x，y)為真實(shí)的視差圖，在比對(duì)中，標(biāo)準(zhǔn)的真實(shí)視差圖只取跟分割模板相同的部分，其余全部設(shè)置為背景;δ為誤差容許值，取1。

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

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

圖3 立體匹配結(jié)果對(duì)比圖

同時(shí)，為了進(jìn)一步驗(yàn)證文中算法對(duì)遮擋，深度不連續(xù)，光照變化，低紋理、無(wú)紋理區(qū)域等的匹配性能，對(duì)Middlebury平臺(tái)提供的部分標(biāo)準(zhǔn)圖像進(jìn)行實(shí)驗(yàn)，結(jié)果如圖4所示。

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

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

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

5 結(jié)束語(yǔ)

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

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

［2］ 伍春洪，付國(guó)亮.一種基于圖像分割及鄰域限制與放松的立體匹配方法［J］.計(jì)算機(jī)學(xué)報(bào)，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ìn)的基于圖像分割的立體匹配算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2008，20(6):808 -812.

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

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

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

［12］祝世平，楊 柳.基于自適應(yīng)分水嶺的圖割的立體匹配算法［J］.光學(xué)學(xué)報(bào)，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">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2016-08-23

陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目(2011JM8014);陜西師范大學(xué)實(shí)驗(yàn)技術(shù)研究項(xiàng)目(SYJS201314)

王雅寧(1990-)，男，碩士，研究方向?yàn)橛?jì)算機(jī)視覺(jué)。

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