王衛(wèi)星，石紅玉

（1.福州大學(xué)物理與信息工程學(xué)院，350000福州；2.皇家工學(xué)院，斯德哥爾摩，瑞典）

結(jié)合閉合解摳圖及最小生成樹(shù)的圖論分割算法

王衛(wèi)星1，2，石紅玉1

（1.福州大學(xué)物理與信息工程學(xué)院，350000福州；2.皇家工學(xué)院，斯德哥爾摩，瑞典）

針對(duì)圖像目標(biāo)物體與背景邊界交錯(cuò)在一起或兩者之間邊界不明晰以及背景與目標(biāo)紋理相似的情況，進(jìn)行圖像分割非常困難.為此，提出了一種基于圖論（graph theory）及閉合解摳圖思想的圖像分割算法.首先，利用閉合解摳圖算法對(duì)圖像進(jìn)行預(yù)分割，粗糙地將圖像分為前景和背景兩部分；其次，提取目標(biāo)及背景的細(xì)節(jié)，再分別用改進(jìn)的圖論分割算法細(xì)分割目標(biāo)物體及背景，從而得到最終圖像分割結(jié)果.實(shí)驗(yàn)結(jié)果表明，摳圖算法避免了前景和背景的混疊，改進(jìn)的圖論算法可有效提高6%～12%的分割精度.與傳統(tǒng)的區(qū)域合并、通常的圖論及閾值算法相比，該算法精度高、效果好，具有顯著優(yōu)越性.

閉合解摳圖；圖論；最小生成樹(shù)；圖像分割

自1971年Zahn［1］最早將圖論應(yīng)用于圖像分割和數(shù)據(jù)聚類以來(lái)，由于圖論方法良好的數(shù)學(xué)基礎(chǔ)及應(yīng)用的擴(kuò)展，基于圖論的圖像分割成為國(guó)內(nèi)外研究的熱點(diǎn)，并產(chǎn)生了多種基于圖論的圖像分割算法.主要包括:圖切割相關(guān)算法［2-7］，活動(dòng)線（live wire）方法［8］，隨機(jī)游走與等周算法［9-11］，最小生成樹(shù)算法［12］.

值得一提的是2006年Sharon等［4］在《Nature》上提出的一種基于圖方法的至上而下的分層分割方法，分割結(jié)果精準(zhǔn)且效率高.另外，F(xiàn)elzenszwalb等［12］提出了“小而并之”的最小生成樹(shù)分割算法，即當(dāng)區(qū)域的內(nèi)部差異大于區(qū)域之間的像素差異時(shí)，就認(rèn)定兩區(qū)域?qū)儆谕|(zhì)區(qū)域而將它們合并.該分割方法能夠部分地根據(jù)不同的圖像特性進(jìn)行不同分割且效率較快，本文就以此方法為基礎(chǔ)進(jìn)行改進(jìn).

上述最小生成樹(shù)方法不足之處在于隨著設(shè)置參數(shù)的增大，丟失了圖像的很多細(xì)節(jié)，而參數(shù)設(shè)置過(guò)小容易產(chǎn)生過(guò)分割，無(wú)法正確把握分割尺度.為了解決這一問(wèn)題，可以考慮結(jié)合預(yù)（粗）分割算法來(lái)進(jìn)行補(bǔ)充，可能的預(yù)分割算法之一是摳圖算法［13］.摳圖算法雖然不能檢測(cè)出圖像中目標(biāo)物體的詳細(xì)細(xì)節(jié)，但可以將整體目標(biāo)物體從復(fù)雜背景圖像中分割出來(lái)，彌補(bǔ)了圖論方法在此方面的不足.Levin等［14］所提出來(lái)的closed-form solution算法通過(guò)用戶的交互輸入計(jì)算全局最優(yōu)值，得到高質(zhì)量的摳圖結(jié)果.因此，本文方法結(jié)合圖論和此算法，各取其長(zhǎng)，在閉合解摳圖算法粗分割的基礎(chǔ)上用改進(jìn)的圖論方法對(duì)圖像進(jìn)行細(xì)分割，得到較為理想分割效果.

1 基于閉合解摳圖算法的預(yù)分割

摳圖是從圖像背景中提取出前景目標(biāo)的技術(shù).對(duì)于輸入圖像I，存在以下顏色組合方程

式中:F、B分別為前景色和背景色；α為不透明度，表征前景色所占的比重，0≤α≤1．關(guān)于α，本文進(jìn)行四舍五入，即其取值非0即1，因?yàn)閷?duì)于圖論方法，為了進(jìn)一步將對(duì)前景分割與背景分割得到的結(jié)果相加，本文設(shè)定對(duì)圖像黑色像素點(diǎn)不進(jìn)行處理．若α在0～1之間，則無(wú)論是前景還是背景都會(huì)對(duì)此部分像素進(jìn)行基于圖論的分割，最后相加時(shí)會(huì)產(chǎn)生前景和背景的重復(fù)疊加．

根據(jù)閉合解摳圖理論對(duì)本文研究圖像進(jìn)行處理，選取了兩幅各具特色的自然景象（非人造目標(biāo)）圖像，圖像中目標(biāo)物體及背景的組合及紋理均復(fù)雜.如圖1所示為閉合解摳圖的結(jié)果與高效隨機(jī)游走算法［15］分割結(jié)果的比較.由圖1可以明顯看出本文方法可以準(zhǔn)確地將前景目標(biāo)從背景圖像中分割出來(lái)，包括前景和背景交錯(cuò)的部分，比如小鹿的身體與草叢、帆船的倒影等；而隨機(jī)游走算法雖然能大致將前景與背景之間的邊界描繪出來(lái)，但是對(duì)于邊界點(diǎn)較為模糊或者前景與背景之間灰度值較為接近的情況，找到的邊界并不準(zhǔn)確.

圖1 閉合解摳圖結(jié)果與高效隨機(jī)游走算法比較

2 基于改進(jìn)分割準(zhǔn)則的圖論算法的細(xì)分割

在以上閉合解摳圖結(jié)果的基礎(chǔ)上，對(duì)圖像前景進(jìn)行基于圖論的細(xì)分割.即將圖像映射成一個(gè)加權(quán)圖G（V，E），采用基于合并策略的Krusal算法進(jìn)行分割，主要涉及3個(gè)參數(shù):1）高斯濾波參σ；2）閾值函數(shù)參k，用來(lái)控制分割程度；3）再合并參數(shù)min-size.若兩鄰域其中一個(gè)的區(qū)域大小小于min-size，則將兩區(qū)域合并.此方法分割效果好、算法結(jié)構(gòu)簡(jiǎn)單且計(jì)算效率高，但它仍然有許多缺點(diǎn)，本文針對(duì)以上3個(gè)參數(shù)分別加以改進(jìn).

2.1 圖論算法的具體改進(jìn)

2.1.1 最小生成樹(shù)中區(qū)域內(nèi)部和區(qū)域間差異函數(shù)的改進(jìn)

如果僅僅用區(qū)域內(nèi)的最大邊權(quán)代表區(qū)域的差異程度，對(duì)某些圖像而言，容易受噪聲和孤立點(diǎn)的影響，分割效果也會(huì)變差，因此可以重新定義區(qū)域內(nèi)部差異和區(qū)域間差異為

式中N為最小生成樹(shù)的邊數(shù)，即N=｜C｜-1．此舉雖然在一定程度上降低了敏感度，原方法中可以合并的兩區(qū)域可能因此將不能合并，但可以通過(guò)調(diào)節(jié)參數(shù)k控制分割尺度．

2.1.2 邊權(quán)函數(shù)設(shè)計(jì)的改進(jìn)

原方法的權(quán)重函數(shù)僅僅是灰度值的絕對(duì)差異，而沒(méi)有考慮到各像素的空間位置.若兩像素空間位置較遠(yuǎn)，其相關(guān)性一般也會(huì)變?nèi)?，理?yīng)加大邊權(quán)懲罰.因此可定義權(quán)重函數(shù)為

其中:I（vi）、I（vj）分別為像素vi和vj的灰度級(jí)；d（vi，vj）定義為vi和vj之間的空間歐式距離為

為一個(gè)自適應(yīng)的二維高斯因子

式中:μi、μj分別為方向像素灰度級(jí)的期望；σi、σj分別為其標(biāo)準(zhǔn)差；r為其協(xié)方差．

2.1.3 圖映射分割后再合并機(jī)制的改進(jìn)

算法 1）從分割S開(kāi)始，對(duì)每一條邊（vi，vj）∈E，vi∈C1，vj∈C2，如果C1≠C2并且｜C1｜＜q且｜C2｜＜q，那么就將C1和C2合并，得到新的分割Snew．2）對(duì)Snew中的每一條邊，（vi，vj）∈E，vi∈C1，vj∈C2，如果C1≠C2并且｜C1｜＜q或者｜C2｜＜q，那么就將C1和C2合并．

假設(shè)待分割圖像的分辨率為3×3，分割S中每一頂點(diǎn)為一區(qū)域，p=4．由圖2（a）可以看出，Step 1更容易得到大的區(qū)域，但一些小區(qū)域仍然存在.經(jīng)過(guò)Step 2可以保證所有區(qū)域大小大于p．而原方法直接跳到第2步，使圖像只得到一個(gè)分割區(qū)域，產(chǎn)生過(guò)合并現(xiàn)象．

圖2 再合并機(jī)制比較

2.2 改進(jìn)的圖論分割算法與其他類似分割算法的比較分析

對(duì)圖1中圖像的摳圖結(jié)果圖（目標(biāo)物體圖和背景圖），分別進(jìn)行基于改進(jìn)Graph-Based算法、基于mean-shift模型的區(qū)域合并算法［16］以及Canny邊緣檢測(cè)算法的圖像分割，試驗(yàn)結(jié)果如圖3所示.由于噪聲太多，基于邊界掃描（如Canny）的方法無(wú)法精確地勾畫出各目標(biāo)物體的輪廓及紋理等.區(qū)域合并算法有些地方過(guò)合并有些地方過(guò)分割，以下圖像都不同程度地出現(xiàn)了這一問(wèn)題.相較而言，基于改進(jìn)圖論的分割方法效果較好，小鹿身體中屬于草叢部分完全被分離出去，第2排屬于近處與遠(yuǎn)處的樹(shù)木分割開(kāi)來(lái).該方法可以有效去除孤立點(diǎn)和其他噪聲，并且將漸變區(qū)域合為同一區(qū)域.

圖3 閉合解摳圖基礎(chǔ)上分割結(jié)果比較

以上3種方法的處理速度如表1所示，其中區(qū)域合并方法未將mean shift預(yù)處理的時(shí)間計(jì)算在內(nèi)，可見(jiàn)基于圖論的分割方法效率較高.

表1 3種方法處理速度比較

3 結(jié)果與分析

經(jīng)過(guò)以上分析，本文的算法（包括粗分割和細(xì)分割）的總流程圖如圖4所示.其中:①為閉合解摳圖部分；②為基于改進(jìn)圖論算法的圖像分割部分.當(dāng)①中交互選取種子點(diǎn)時(shí)，根據(jù)本文圖像紋理特點(diǎn)，為得到好的摳圖效果與效率，選取的種子點(diǎn)像素?cái)?shù)目占整幅圖像的比率大致為3%～8%.

按照?qǐng)D4對(duì)圖像進(jìn)行分割，圖5演示了每一步的過(guò)程，此處種子點(diǎn)概率為4.53%.與原圖論方法［12］以及文獻(xiàn)［17］的改進(jìn)圖論方法進(jìn)行比較（均在摳圖基礎(chǔ)上進(jìn)行處理），調(diào)整各參數(shù)尤其是k以得到最優(yōu)的分割效果.從圖5可以看出，若沒(méi)有預(yù)分割（閉合解摳圖）步驟及圖論算法的改進(jìn)，原圖論的分割算法很難分割這些邊界模糊復(fù)雜的自然景象圖像.

圖4 算法流程圖

圖5 本文方法分割步驟

基于圖1中的圖像，圖6（a）是用本文算法處理的結(jié)果，圖6（b）、6（c）分別是在摳圖基礎(chǔ)上用原算法和文獻(xiàn)［17］算法處理的結(jié)果.兩幅圖像的種子點(diǎn)比率分別為5.67%、3.26%.

從圖1可以看出:第1幅圖像中小鹿站在草叢中，身體與草叢混雜在一起，縱向看，小鹿身體上的花紋和身處的草叢均是垂直方向的紋理，只存在顏色的差異，是分割的難點(diǎn)所在，本文方法將小鹿和草叢準(zhǔn)確分離，而原圖論方法與文獻(xiàn)［17］方法頭部分割結(jié)果均不理想；第2幅圖像中帆的顏色與水色灰度差異小，難以分辨，且近處樹(shù)葉與遠(yuǎn)處樹(shù)葉邊界模糊，以及樹(shù)葉縫隙與天空的交接等都給分割帶來(lái)困難，本文方法較好的解決了以上難點(diǎn)，而原圖論方法未將遠(yuǎn)處和近處樹(shù)木合理分割，天空云彩欠分割，文獻(xiàn)［17］方法除以上問(wèn)題外，水中的帆船同樣欠分割.針對(duì)以上兩幅圖像，根據(jù)人工繪制邊界圖7，分別比較，計(jì)算各方法的分割精度如表2所示.

圖6 本文方法與其他方法比較

精度計(jì)算為

式中:Epixel、Upixel分別為3種方法分割結(jié)果中邊界點(diǎn)的正確率與錯(cuò)誤率；λ為懲罰系數(shù)，其值越大對(duì)多余邊界像素點(diǎn)的懲罰越大，精度也越低．考慮到圖像的復(fù)雜性，本文未能將所有邊界點(diǎn)都準(zhǔn)確描繪出，且主要考量方面為正確率，因此本文取λ= 0.3；WEpixel為期望分割結(jié)果的總邊界像素點(diǎn)．

圖7 期望分割結(jié)果

根據(jù)上述粗分割和細(xì)分割的結(jié)合方法，本文選取了40多幅具有不同代表性的邊界模糊圖像進(jìn)行了試驗(yàn)，參照?qǐng)D6和表2的分析，本文提出方法可有效提高6%～12%的分割精度.

表2 本文方法與其他方法精度比較%

4 結(jié) 論

1）本文針對(duì)目標(biāo)邊界不清楚的圖像難以用常規(guī)圖像分割算法進(jìn)行分割的問(wèn)題，提出了一種結(jié)合閉合解摳圖和改進(jìn)圖論的分割方法.對(duì)閉合解摳圖得到的背景和前景圖像分別用改進(jìn)的圖論方法進(jìn)行處理，再將兩個(gè)結(jié)果合并得到最終分割結(jié)果.

2）此方法不會(huì)產(chǎn)生前景與背景的錯(cuò)分割，亦可保留圖像細(xì)節(jié).

3）將前景和背景分開(kāi)處理，在用基于改進(jìn)的圖論方法進(jìn)行分割時(shí)，具有可以分別根據(jù)前景和背景紋理特點(diǎn)設(shè)置不同分割尺度的優(yōu)點(diǎn)，這在一定程度上避免了欠分割和過(guò)分割.

4）從區(qū)域內(nèi)部和區(qū)域間差異函數(shù)、邊權(quán)函數(shù)和圖映射分割后再合并機(jī)制3方面對(duì)圖論方法進(jìn)行改進(jìn)，降低噪聲對(duì)分割結(jié)果的影響，提高分割準(zhǔn)確性.與原圖論和區(qū)域合并方法相比，本文方法錯(cuò)分率小，具有良好的分割效果.

參考文獻(xiàn)

［1］ZAHNC.Graph-theoreticalmethods for detecting and describing gestalt clusters［J］.IEEE Transactions on Computers，1971，C-20（1）:68-86.

［2］SHI J，MALIK J.Normalized cuts and image segmentation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（8）:888-905.

［3］BOYKOV Y，F(xiàn)UNKA-LEA G.Graph cuts and efficient ND image segmentation［J］.International Journal of Computer Vision，2006，70（2）:109-131.

［4］SHARON E，GALUN M，SHARON D，et al.Hierarchy and adaptivity in segmenting visual scenes［J］.Nature，2006，442（7104）:810-813.

［5］CHEN Yuke，WU Xiaoming，CAIKen，et al.CT image segmentation based in clustering and graph-cuts［J］. Procedia Engineering，2011，15:5179-5184.

［6］侯葉.基于圖論的圖像分割技術(shù)研究［D］.西安:西安電子科技大學(xué)，2011.

［7］EGGER J，F(xiàn)REISLEBEN B，NIMSKY C，etal.Templatecut:a pattern-based segmentation paradigm［J］.Nature Scientific Reports，2012，2:1-8.

［8］WIECLAWEKW，PIETKA E.Fuzzy clustering in Intelligent scissors［J］.Computerized Medical Imaging and Graphics，2012，36（5）:396-409.

［9］GOPALAKRISHNAN V，HU Y，RAJAN D.Random walks on graphs for salient object detection in images［J］.IEEE Transactions on Image Processing，2010，19（12）:3232-3242.

［10］依玉峰，高立群，郭麗.基于Mean shift隨機(jī)游走圖像分割算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2011，23（11）:1875-1881.

［11］汪云飛，畢篤彥，黃飛.一種用于圖像分割的等周算法改進(jìn)［J］.西安電子科技大學(xué)學(xué)報(bào)，2012，39（2）: 87-94.

［12］FELZENSZWALB P F，HUTTENLOCHER D P.Efficient graph-based image segmentation［J］.International Journalof Computer Vision，2004，59（2）:167-181.

［13］WEXLER Y，F(xiàn)ITZGIBBON A，ZISSERMAN A.Bayesian estimation of layers from multiple images［J］.Computer Vision，2002，2352:487-501.

［14］LEVIN A，LISCHINSKI D，WEISS Y.A Closed-form solution to natural image matting［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30（2）:228-242.

［15］ANDREWSS，HAMAMEN G，SAAD A.Fast random walker with priors using precomputation for interactive medical image segmentation［J］.Medical Image Computing and Computer-Assisted Intervention，2010，6363:9-16.

［16］PENG Bo，ZHANG Lei，ZHANG D.Automatic image segmentation by dynamic region merging［J］.IEEE Transactions on Image Processing，2011，20（12）:3592-3605.

［17］ZHANG M，ALHAJJ R.Improving the graph-based image segmentation method［C］／／Proceeding of the 18thIEEE International Conference on Tools with Artificial Intelligence.Arlington:IEEE，2006:617-624.

（編輯張 紅）

A minimum spanning tree based image segmentation algorithm w ith closed-form solution

WANGWeixing1，2，SHIHongyu1
（1.School of Physics and Information Engineering，F(xiàn)uzhou University，350000 Fuzhou，China；2.Royal Institute of Technology，Stockholm，Sweden）

For the edges between objects and background in an image are intertwined or their common boundaries are vague as well as the textures of objects and background are similar，a new method based on graph theory and closed-form solution was proposed.First，it uses closed-form solution to initially separate the objects from background roughly，then，to extract the detailed information of inter objects，it applies an improved graph-based algorithm to obtain the final image segmentation results.The test results show that the algorithm ofmatting avoids aliasing of foreground and background and the improved graph-based algorithm increases segmentation accuracy by 6%～12%effectively.Compared to the traditional algorithms such as region merging，ordinary graph，and thresholding，the new algorithm has the better accuracy and effect，therefore it has the significant superiority.

closed-form solution；graph theory；minimum spanning tree；image segmentation

TP391

A

0367-6234（2014）09-0123-06

2013-10-12.

國(guó)家自然科學(xué)基金資助項(xiàng)目（61170147）.

王衛(wèi)星（1959—），男，教授，博士生導(dǎo)師.

王衛(wèi)星，znn525d＠qq.com.