結合閉合解摳圖及最小生成樹的圖論分割算法

王衛星，石紅玉

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

結合閉合解摳圖及最小生成樹的圖論分割算法

王衛星1，2，石紅玉1

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

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

閉合解摳圖；圖論；最小生成樹；圖像分割

自1971年Zahn［1］最早將圖論應用于圖像分割和數據聚類以來，由于圖論方法良好的數學基礎及應用的擴展，基于圖論的圖像分割成為國內外研究的熱點，并產生了多種基于圖論的圖像分割算法.主要包括:圖切割相關算法［2-7］，活動線（live wire）方法［8］，隨機游走與等周算法［9-11］，最小生成樹算法［12］.

值得一提的是2006年Sharon等［4］在《Nature》上提出的一種基于圖方法的至上而下的分層分割方法，分割結果精準且效率高.另外，Felzenszwalb等［12］提出了“小而并之”的最小生成樹分割算法，即當區域的內部差異大于區域之間的像素差異時，就認定兩區域屬于同質區域而將它們合并.該分割方法能夠部分地根據不同的圖像特性進行不同分割且效率較快，本文就以此方法為基礎進行改進.

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

1 基于閉合解摳圖算法的預分割

摳圖是從圖像背景中提取出前景目標的技術.對于輸入圖像I，存在以下顏色組合方程

式中:F、B分別為前景色和背景色；α為不透明度，表征前景色所占的比重，0≤α≤1．關于α，本文進行四舍五入，即其取值非0即1，因為對于圖論方法，為了進一步將對前景分割與背景分割得到的結果相加，本文設定對圖像黑色像素點不進行處理．若α在0～1之間，則無論是前景還是背景都會對此部分像素進行基于圖論的分割，最后相加時會產生前景和背景的重復疊加．

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

圖1 閉合解摳圖結果與高效隨機游走算法比較

2 基于改進分割準則的圖論算法的細分割

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

2.1 圖論算法的具體改進

2.1.1 最小生成樹中區域內部和區域間差異函數的改進

如果僅僅用區域內的最大邊權代表區域的差異程度，對某些圖像而言，容易受噪聲和孤立點的影響，分割效果也會變差，因此可以重新定義區域內部差異和區域間差異為

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

2.1.2 邊權函數設計的改進

原方法的權重函數僅僅是灰度值的絕對差異，而沒有考慮到各像素的空間位置.若兩像素空間位置較遠，其相關性一般也會變弱，理應加大邊權懲罰.因此可定義權重函數為

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

為一個自適應的二維高斯因子

式中:μi、μj分別為方向像素灰度級的期望；σi、σj分別為其標準差；r為其協方差．

2.1.3 圖映射分割后再合并機制的改進

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

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

圖2 再合并機制比較

2.2 改進的圖論分割算法與其他類似分割算法的比較分析

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

圖3 閉合解摳圖基礎上分割結果比較

以上3種方法的處理速度如表1所示，其中區域合并方法未將mean shift預處理的時間計算在內，可見基于圖論的分割方法效率較高.

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

3 結果與分析

經過以上分析，本文的算法（包括粗分割和細分割）的總流程圖如圖4所示.其中:①為閉合解摳圖部分；②為基于改進圖論算法的圖像分割部分.當①中交互選取種子點時，根據本文圖像紋理特點，為得到好的摳圖效果與效率，選取的種子點像素數目占整幅圖像的比率大致為3%～8%.

按照圖4對圖像進行分割，圖5演示了每一步的過程，此處種子點概率為4.53%.與原圖論方法［12］以及文獻［17］的改進圖論方法進行比較（均在摳圖基礎上進行處理），調整各參數尤其是k以得到最優的分割效果.從圖5可以看出，若沒有預分割（閉合解摳圖）步驟及圖論算法的改進，原圖論的分割算法很難分割這些邊界模糊復雜的自然景象圖像.

圖4 算法流程圖

圖5 本文方法分割步驟

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

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

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

精度計算為

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

圖7 期望分割結果

根據上述粗分割和細分割的結合方法，本文選取了40多幅具有不同代表性的邊界模糊圖像進行了試驗，參照圖6和表2的分析，本文提出方法可有效提高6%～12%的分割精度.

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

4 結 論

1）本文針對目標邊界不清楚的圖像難以用常規圖像分割算法進行分割的問題，提出了一種結合閉合解摳圖和改進圖論的分割方法.對閉合解摳圖得到的背景和前景圖像分別用改進的圖論方法進行處理，再將兩個結果合并得到最終分割結果.

2）此方法不會產生前景與背景的錯分割，亦可保留圖像細節.

3）將前景和背景分開處理，在用基于改進的圖論方法進行分割時，具有可以分別根據前景和背景紋理特點設置不同分割尺度的優點，這在一定程度上避免了欠分割和過分割.

4）從區域內部和區域間差異函數、邊權函數和圖映射分割后再合并機制3方面對圖論方法進行改進，降低噪聲對分割結果的影響，提高分割準確性.與原圖論和區域合并方法相比，本文方法錯分率小，具有良好的分割效果.

參考文獻

［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，FUNKA-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］侯葉.基于圖論的圖像分割技術研究［D］.西安:西安電子科技大學，2011.

［7］EGGER J，FREISLEBEN 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］.計算機輔助設計與圖形學學報，2011，23（11）:1875-1881.

［11］汪云飛，畢篤彥，黃飛.一種用于圖像分割的等周算法改進［J］.西安電子科技大學學報，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，FITZGIBBON 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，Fuzhou 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.

國家自然科學基金資助項目（61170147）.

王衛星（1959—），男，教授，博士生導師.

王衛星，znn525d＠qq.com.