田 元， 王 乘， 管 濤

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

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

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

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

圖1 3×3 圖像分割示例

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

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

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

2.1 用分水嶺算法對圖像進(jìn)行預(yù)處理

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

圖2 用區(qū)域代替像素點(diǎn)進(jìn)行分析

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

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

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

2.2 用模糊C 均值方法對標(biāo)記區(qū)域進(jìn)行分析

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

2.3 用圖割法對未標(biāo)記區(qū)域進(jìn)行分類

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

[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]. 儀器儀表學(xué)報(bào), 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]. 工程圖學(xué)學(xué)報(bào), 2007, 28(1)： 89-93.

[7] 蔡 濤, 徐國華, 徐筱龍. 基于模糊C 均值與Markov 隨機(jī)場的圖像分割[J]. 計(jì)算機(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] 邊肇祺, 張學(xué)工. 模式識別(第2 版)[M]. 北京： 清華大學(xué)出版社, 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é)果比較