區(qū)域生長和C-均值聚類結(jié)合的圖像分割方法?

李 媛,王浩全,張 培

(中北大學(xué)信息與通信工程學(xué)院,山西太原 030051)

圖像分割是指在一幅圖像中分離出具有相同或相似的較為感興趣的目標(biāo)區(qū)域,即把目標(biāo)區(qū)和背景區(qū)區(qū)分開來,實(shí)現(xiàn)圖像描述方式的轉(zhuǎn)換,給圖像的后續(xù)處理提供重要的依據(jù)[1-4].圖像分割方法主要有:基于邊緣的圖像分割、基于閾值的圖像分割、基于聚類的圖像分割、基于神經(jīng)網(wǎng)絡(luò)的圖像分割[5]和基于區(qū)域的圖像分割等.

區(qū)域生長分割[4]是由若干種子點(diǎn)按一定的生長準(zhǔn)則,對相鄰像素點(diǎn)進(jìn)行判別連接,直到所有像素點(diǎn)連接完成為止.但由于有具有主觀性的顏色相似度和空間相近度的影響,對有陰影區(qū)域的圖像產(chǎn)生欠分割或過生長的現(xiàn)象.模糊C均值聚類分割[6]是一種無監(jiān)督的聚類算法,運(yùn)用了迭代優(yōu)化目標(biāo)函數(shù),對色彩或灰度相似度較高的圖像進(jìn)行分割會得到很好的效果.但因?yàn)榉磸?fù)迭代,運(yùn)行時間比較長.

本文根據(jù)區(qū)域生長的分割算法與聚類分析具有較為相近的思想,提出了一種基于區(qū)域生長和C均值聚類相結(jié)合的圖像分割方法.運(yùn)用聚類中的集合思想,確定生長區(qū)域的種子點(diǎn)并給出生長半徑;把所有合并到區(qū)域中的點(diǎn)必須與區(qū)域中至少一個像素點(diǎn)具有8鄰接性,作為聚類中模糊集合的一個限制條件,最后得到分割結(jié)果.

1 算法描述

1.1 模糊C均值聚類分割算法[7]

模糊C-均值聚類算法是根據(jù)最小二乘法對目標(biāo)函數(shù)進(jìn)行迭代優(yōu)化并獲得最終的數(shù)據(jù)劃分.在圖像分割應(yīng)用中,是根據(jù)分割圖像中的像素及C個聚類中心的每一中心的加權(quán)隸屬度,對目標(biāo)函數(shù)進(jìn)行迭代優(yōu)化的.

設(shè)圖像中所有像素的集合為X,c為聚類的類別數(shù),取像素的灰度值作為聚類特征.C-均值聚類的目標(biāo)函數(shù)為

聚類中心

隸屬矩陣

更新聚類中心

式中:m＞l為加權(quán)指數(shù);vi為第i個聚類中心;c滿足2≤c≤n,表示模糊聚類的類別數(shù);μij代表第j個樣本xj隸屬于第i類的程度.

傳統(tǒng)的模糊C-均值聚類算法中,分割結(jié)果僅僅和聚類中心與特征空間中的像素點(diǎn)之間的距離有關(guān).

模糊C-均值聚類方法運(yùn)用于圖像分割的步驟為:①模糊加權(quán)指數(shù)m、聚類類別數(shù)c、迭代停止條件 ε、最大迭代次數(shù)U(0)及初始化劃分矩陣V(0)的確定;②根據(jù)公式(4)計算更新聚類中心;③根據(jù)公式(3)計算新的隸屬矩陣;④對隸屬函數(shù)矩陣進(jìn)行判定,是否滿足迭代終止條件 ‖U(γ+1)-U(γ)‖ ≤ε,或達(dá)到給定的迭代次數(shù)停止迭代;否則返回步驟(2),重復(fù)步驟,直到聚類中心收斂.

1.2 區(qū)域生長算法

區(qū)域生長的基本思想是通過一個初始種子,將具有相似性質(zhì)的像素集合在種子像素所在的區(qū)域.在圖像分割中最重要的就是種子點(diǎn)的確定和區(qū)域生長準(zhǔn)則的建立.

圖像分割應(yīng)用區(qū)域生長法,需解決三個問題[8]:①選擇或確定可以正確代表目標(biāo)區(qū)的種子像素;②確定生長過程中能將相鄰像素包括進(jìn)來的生長準(zhǔn)則;③制定讓生長停止的條件或規(guī)則.

區(qū)域生長分割的具體算法描述為:首先在目標(biāo)區(qū)中選取初始種子點(diǎn)像素,其次根據(jù)某一生長準(zhǔn)則,從種子點(diǎn)像素鄰域(8鄰域)中尋找與種子點(diǎn)相同或相似的像素,并入種子點(diǎn)像素所在區(qū)域,然后將新的像素作為閑的種子點(diǎn)子像素重復(fù)以上過程,直到找不到符合規(guī)則的像素為止.

1.3 基于區(qū)域生長與聚類分析相結(jié)合的分割方法

區(qū)域生長中首先確定種子點(diǎn)并給出生長半徑,這也正符合了聚類中的集合思想;與此同時,所有合并到區(qū)域中的點(diǎn)必須與區(qū)域內(nèi)至少一個像素點(diǎn)具有8鄰接性,作為聚類中模糊集合的一個限制條件.這正表明了區(qū)域生長的分割算法與聚類分析有著較為相近的思想.

目標(biāo)函數(shù)

Nikhil[10,11]等人研究指出,加權(quán)指數(shù)m=2是較為理想的取值;c代表類別數(shù),一般取2≤c≤n,本文中取2,即目標(biāo)區(qū)和背景區(qū);n表示圖像中的像素數(shù).

式(5)中:A是對稱的正定矩陣,本文中的A為單位矩陣,當(dāng)A為單位矩陣時,di,k恰好是歐式距離.xk在式(5)中代表論域中的數(shù)據(jù)點(diǎn),vi表示第i類模糊集Xi的聚類中心.

U[μi,k]是一個c×n的矩陣;J(U,V)代表各類中聚類中心到樣本數(shù)據(jù)點(diǎn)的加權(quán)距離平方和,J(U,V)的值反映的是:在某種差異定義下的類內(nèi)統(tǒng)一程度.它的值越小,表示所得到的分割效果越好.

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

依據(jù)上述幾種圖像分割方法,針對實(shí)驗(yàn)圖像(圖 1),分別用模糊C-均值分割算法、區(qū)域生長分割算法以及本文算法對其進(jìn)行分割處理,得到的處理結(jié)果如圖2所示.

圖1 實(shí)驗(yàn)圖像Fig.1 Experimental image

圖2 分割結(jié)果Fig.2 Segmentation result

圖1(a)為原始目標(biāo)圖像,圖中矩形和橢圓形為目標(biāo)區(qū)域,圖1(b)為經(jīng)過超聲CT重建后的圖像.

圖2(a)為模糊C-均值分割結(jié)果,圖2(b)為區(qū)域生長分割結(jié)果,圖 2(c)為本文算法的分割結(jié)果.以上結(jié)果對比顯示:目標(biāo)區(qū)的面積、位置及輪廓等方面的信息比較準(zhǔn)確.本文提出的新算法對目標(biāo)區(qū)的分割是比較平滑的、完整的,顯示了較好的分割效果.

2.1 運(yùn)行時間的對比

本文就聚類分割算法、區(qū)域生長分割算法與本文提出的方法在運(yùn)行時間上作了比較,本文方法在得到較好分割效果的同時消耗時間較其它兩種算法要長一些.實(shí)驗(yàn)的硬件環(huán)境為Pentium(R)Dual-Core CPU E5300 2.60GHz,2.00GB內(nèi)存.仿真軟件為Matlab7.0.

2.2 目標(biāo)區(qū)位置準(zhǔn)確性的對比

目標(biāo)區(qū)像素數(shù)相等不足以說明分割后目標(biāo)區(qū)分割的準(zhǔn)確性,在目標(biāo)區(qū)分割后位置信息具有一定偏差的情況下,依舊可得到與原始目標(biāo)區(qū)像素數(shù)相吻合的結(jié)果,故對本文提出的算法就目標(biāo)區(qū)分割前后的位置信息做了詳細(xì)對比,如圖3所示.表2給出的是重建后圖像中兩個目標(biāo)區(qū)上下左右邊界點(diǎn)的位置信息,表3給出的是本文提出算法得到的分割圖中兩個目標(biāo)區(qū)上下左右邊界點(diǎn)的位置信息.對比可知,二者位置信息完全相同,很大程度上說明了分割的準(zhǔn)確性,即此方法分割的完整性和準(zhǔn)確性均達(dá)到了100%.

圖3 目標(biāo)區(qū)位置圖Fig.3 Location plan of target area

表2 原始圖像中目標(biāo)區(qū)的位置信息Tab.2 Target zone’s position information of the original image

表3 分割后得到的目標(biāo)區(qū)位置信息Tab.3 Target zone’s position information after segmentation

3 結(jié) 論

本文將區(qū)域生長和模糊C均值聚類分割方法存在的優(yōu)缺點(diǎn)有機(jī)結(jié)合在一起,提出了一種基于區(qū)域生長與C均值聚類圖像相結(jié)合的分割方法,并通過仿真軟件實(shí)現(xiàn)了這種圖像分割的方法.結(jié)果表明:通過本算法預(yù)先設(shè)置的參數(shù),實(shí)現(xiàn)了無監(jiān)督的圖像分割.結(jié)合不同的圖像分割算法,充分利用各自的優(yōu)點(diǎn),揚(yáng)長避短,達(dá)到較為理想的分割效果.

[1]馬英輝,韓焱.彩色圖像分割方法綜述[J].科技情報開發(fā)與經(jīng)濟(jì),2006,16(4):158-159.

Ma Yinghui,Han Yan.Overview of the methods for color image segmentation[J].Sci-Tech Information Development&Economy,2006,16(4):158-159.(in Chinese)

[2]杜宇慧,桂志國,李晉華.基于類別方差的三維醫(yī)學(xué)圖像分割新方法[J].中北大學(xué)學(xué)報(自然科學(xué)版),2007,28(2):166-170.

Du Yuhui,Gui Zhiguo,LI Jinhua.A new method of 3D medical images segmentation based on class variance[J].Journalof North University of China(Natural Science Edition),2007,28(2):166-170.(in Chinese)

[3]Jar-Ferr Yang,Shu-Sheng Hao,Pau-Choo Chung.Color image segmentation using fuzzy C-means and eigenspace projections[J].Signal Processing,2002,82:461-472.

[4]Cheng H D,Jiang X H,Sun Y,et al.Color image segmentation:advances and prospects[J].Pattern Recognition,2001,34(12):2259-2281.

[5]Wangenheima A,Bertoldir,Abdala D,et al.Color image segmentation using an enhanced gradient network method[J].Pattern Recognition Letters,2009,30(15):1404-1412.

[6]Cinque L,Foresti G,Lombardi L.A clustering fuzzy approach for image segmentation[J].Pattern Recognition,2004,37:1797-1807.

[7]郭桂蓉.模糊模式識別[M].長沙:國防科技大學(xué)出版社,1992:178-186.

[8]章毓晉.圖像工程(中冊)圖像分析(第二版)[M].北京:清華大學(xué)出版社,2005:102-104.

[9]Nikhil R.Pal,James C.Bezdek,Richard J.Hathaway.Sequential competitive learning and the fuzzy C-means clustering algorithms[J].Neural Networks,1996,9:787-796.

[10]李明,李云松.改進(jìn)的快速模糊C均值聚類的圖像分割方法[J].蘭州理工大學(xué)學(xué)報 ,2007,(3):95-99.

Li Ming,Li Yunsong.A modified method for image segmentation with fast fuzzy C-mean clustering[J].Journal of Lanzhou University of Technology,2007,(3):95-99.(in Chinese)