田 元， 王 乘， 管 濤

（華中科技大學數(shù)字化工程與仿真中心，湖北 武漢 430074）

交互式圖像分割在醫(yī)學圖像處理、圖像合成、影視技術(shù)、運動跟蹤等領(lǐng)域具有廣泛的用途。將人們對圖像中的感興趣的部分稱為目標或前景，其他部分稱為背景，交互式圖像分割的目的就是把用戶感興趣的目標從圖像中提取出來，以便作進一步的處理和分析。近年來，隨著各學科許多理論和新方法的提出，人們也提出了一些新的分割方法，其中基于圖論的交互式分割方法[1-3]引起了人們越來越多的興趣。它的基本原理是將圖像的分割問題轉(zhuǎn)化為圖的分割問題。首先，對用戶選取的前景和背景分別進行分析，然后將未標記的點與前景和背景的相似性作為相似能量函數(shù)，用未標記點與其相鄰點的相關(guān)性表示先驗能量函數(shù)，將這兩個能量函數(shù)作為判斷該點屬于前景或者背景的約束條件，最后利用最大流/最小割的方法求解能量函數(shù)的最優(yōu)解。Boykov[1]等人提出利用灰度直方圖的方法對前景背景的顏色分布進行分析，該方法對于前景背景顏色差別較大的圖像的分割效果較好，但是當前景背景顏色相似時，其分割效果卻不夠令人滿意。Li Yin[2]等人則提出了Lazy Snapping 方法，該方法利用K 均值聚類算法對前景和背景進行聚類分析。但是，為了獲得更好的分割效果，該方法需要對分割后的圖像進行進一步處理，即通過用戶手動調(diào)整提取的圖形的邊界輪廓來獲得更好的分割效果。

本文提出一種基于模糊C 均值聚類和圖割的交互式圖像分割方法，利用模糊C 均值聚類方法具有更好、更穩(wěn)定的聚類性能，對用戶選取的前景和背景分別進行分析，挖掘用戶交互所提供的隱藏的提示信息，達到更準確的對未標記點進行分類的目的。同時，采用分水嶺方法對圖像進行預處理，將圖像劃分為多個區(qū)域，用區(qū)域代替像素點進行處理。與未經(jīng)過手動調(diào)整的Lazy Snapping 方法相比，在相同的用戶交互情況下，本文具有更好的分割性能，當圖像中前景背景顏色相似時，更能體現(xiàn)本文算法的優(yōu)越性。

1 基于圖論的交互式圖像分割方法

圖1 3×3 圖像分割示例

判斷未標記的點屬于F 類還是屬于B 類，可以利用最大流/最小割算法求一個割集 EC ? ，使割集中所有邊的權(quán)值的和最小，其表達式為

通過求圖的最小割，圖像中的像素被分為兩類，且每個像素滿足下列條件

2 基于FCM 和圖割的交互式圖像分割方法

2.1 用分水嶺算法對圖像進行預處理

基于圖割的圖像分割方法的運行速度與圖的節(jié)點數(shù)有密切的關(guān)系，圖的節(jié)點數(shù)越少，分割速度越快。因此，本文采用分水嶺算法對圖像進行預處理，分水嶺算法可以把圖像中圍繞區(qū)域極小點的像素聚類為一個一個的區(qū)域[4]。本文利用分水嶺算法具有準確分割和精確定位圖像邊緣的特性，將圖像分成多個小區(qū)域，然后，用區(qū)域代替像素點進行進一步分析，如圖2 所示。這樣，對于一幅大小為 N =Width ×Height 的圖像，未經(jīng)過預處理時，其節(jié)點數(shù)為N ，用分水嶺算法對圖像進行預分割后，圖的節(jié)點數(shù)為M (M N? )，大大提高了算法的運行速度。

圖2 用區(qū)域代替像素點進行分析

本文采用Vincent 等人給出的一種新的分水嶺變換方法，此方法速度快、結(jié)果準確，具有實用價值[5]。Vincent 算法分為兩步[4]：

（1） 排序 在逐漸淹沒過程中，并非每次均需處理全部像素。為了能直接訪問需要處理的像素，按像素灰度值的升序排列像素，得到一個排序后的像素矩陣，這樣可以加速計算。

（2） 淹沒 通過利用排序后的圖像按圖像像素灰度值升序地訪問每一個像素來執(zhí)行。對每一聚水盆地分配不同的標記，從整個圖像的最小像素值開始，分配標記，依次淹沒，利用先進先出的數(shù)據(jù)結(jié)構(gòu)，即循環(huán)隊列來擴展標記過的聚水盆地。通過一定的規(guī)則，分配分水嶺標記，可以得到準確的結(jié)果。

2.2 用模糊C 均值方法對標記區(qū)域進行分析

模糊C 均值聚類算法是一種結(jié)合無監(jiān)督聚類和模糊集合概念的方法[6]。不同于K 均值聚類算法將樣本硬性的劃分到某個類，模糊C 均值聚類方法允許某個樣本不同程度同時歸屬于所有類，能更真實的反映自然界的模糊性和不確定 性[7]。因此，模糊C 均值聚類算法與傳統(tǒng)的分級聚類算法、K 均值聚類算法相比，顯示出更好、更穩(wěn)定的聚類性能[8]。它的基本原理是，采用迭代法優(yōu)化聚類損失函數(shù)來獲得對數(shù)據(jù)集的模糊分類，在數(shù)學上可以表示為對目標函數(shù)求極值的問題。對于一幅大小為 Width× Height 的圖像，其像素總數(shù)為 N =Width ×Height ，將整個圖像分為C 類，即求下式中聚類損失函數(shù)J 的最小值[9]

2.3 用圖割法對未標記區(qū)域進行分類

用圖割法對未標記的點進行分類，可以轉(zhuǎn)化為利用最大流/最小割算法求解Gibbs能量函數(shù)[10]的全局最優(yōu)解，其表達式為

其中 E1(vi)為相似能量函數(shù)，表示未標記區(qū)域的顏色與前景或背景顏色的相似程度，E2(vi,vj)為先驗能量函數(shù)，表示未標記區(qū)域與其鄰域的相關(guān)性。

本文中，相似能量函數(shù) E1(vi)定義為

其中jv 為iv 的鄰域， ),(jivvdis 為第i 個區(qū)域中心到第j 個區(qū)域中心的空間距離，σ 為攝像機噪聲。區(qū)域iv 與其鄰域jv 的顏色差別及空間距離越大，這兩個區(qū)域被劃分為同一類的可能性越小。反之，區(qū)域iv 與其鄰域jv 的顏色差別及空間 距離越小，這兩個區(qū)域被劃分為同一類的可能性越大。

最后，利用最大流/最小割算法[11]求能量函數(shù)式(3)的全局最優(yōu)解，達到將圖像中的每個像素唯一的劃分為前景或背景的目的。

3 實驗結(jié)果及分析

本文算法在1.9GB 微處理器、512MB 內(nèi)存、Windows XP 操作系統(tǒng)的環(huán)境下，使用VC6 實現(xiàn)。圖3 為采用本文算法與Lazy Snapping 算法在相同交互條件下的分割結(jié)果的比較。圖中用綠色標記前景，紅色標記背景。圖3 中，第一列為標記了前景和背景的圖像，第二列為Lazy Snapping算法得到的分割結(jié)果，第三列為本文方法得到的分割結(jié)果，第四列為局部放大圖。從分割效果可以看出，本文方法較Lazy Snapping 方法具有更好的分割性能，用戶只需要在圖像中分別選取感興趣的物體和背景區(qū)域，就能從圖像中提取目標物體，而且，當前景背景顏色相似時，本文的算法也能得到較好的分割效果。

[1] Yuri Y Boykov, Marie-Pierre Jolly. Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images [C]//Proceedings of Internation Conference on Computer Vision, Vancouver, Canada, 2001： 105-112.

[2] Li Yin, Sun Jian, Chi-Keung Tang, et al. Lazy snapping[C]//Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles, 2004： 303-308.

[3] Hosaka T, Kobayashi T, Otsu N. Image segmentation using MAP-MRF estimation and support vector machine [J]. Interdisciplinary Information Sciences, 2007, 13(1)： 33-42.

[4] 馮 林, 孫 燾, 吳振宇, 等. 基于分水嶺變換和圖論的圖像分割方法[J]. 儀器儀表學報, 2008, 29(3)： 649-653.

[5] Vincent L, Soille P. Watershed in digital spaces： an efficient algorithm based in immersion simulation [J]. IEEE Trans, PAMI, 1991, 13(6)： 538-598.

[6] 劉曉龍, 張佑生, 謝 穎. 模擬退火與模糊C－均值聚類相結(jié)合的圖像分割算法[J]. 工程圖學學報, 2007, 28(1)： 89-93.

[7] 蔡 濤, 徐國華, 徐筱龍. 基于模糊C 均值與Markov 隨機場的圖像分割[J]. 計算機工程, 2007, 33(20)： 34-39.

[8] Mingoti S A, Lima J O. Comparing SOM neural network with fuzzy C-means, K-means and traditional hierarchical clustering algorithms [J]. European Journal of Operational Research, 2006, 174： 1742-1759.

[9] 邊肇祺, 張學工. 模式識別(第2 版)[M]. 北京： 清華大學出版社, 2000. 280-282.

[10] Geman S, Geman D. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1984, 6(6)： 721-741.

[11] Yuri Boykov, Vladimir Kolmogorov. An experimental comparison of min-cut/max-flow algorithms for energy minimization in computer vision [C]// Proceedings of “EMMCVPR”, Sopgie Antipolis, France, 2001： 359-374.

圖3 本文算法與Lazy Snapping 算法的分割結(jié)果比較