區域生長和C-均值聚類結合的圖像分割方法?

李 媛,王浩全,張 培

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

圖像分割是指在一幅圖像中分離出具有相同或相似的較為感興趣的目標區域,即把目標區和背景區區分開來,實現圖像描述方式的轉換,給圖像的后續處理提供重要的依據[1-4].圖像分割方法主要有:基于邊緣的圖像分割、基于閾值的圖像分割、基于聚類的圖像分割、基于神經網絡的圖像分割[5]和基于區域的圖像分割等.

區域生長分割[4]是由若干種子點按一定的生長準則,對相鄰像素點進行判別連接,直到所有像素點連接完成為止.但由于有具有主觀性的顏色相似度和空間相近度的影響,對有陰影區域的圖像產生欠分割或過生長的現象.模糊C均值聚類分割[6]是一種無監督的聚類算法,運用了迭代優化目標函數,對色彩或灰度相似度較高的圖像進行分割會得到很好的效果.但因為反復迭代,運行時間比較長.

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

1 算法描述

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

模糊C-均值聚類算法是根據最小二乘法對目標函數進行迭代優化并獲得最終的數據劃分.在圖像分割應用中,是根據分割圖像中的像素及C個聚類中心的每一中心的加權隸屬度,對目標函數進行迭代優化的.

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

聚類中心

隸屬矩陣

更新聚類中心

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

傳統的模糊C-均值聚類算法中,分割結果僅僅和聚類中心與特征空間中的像素點之間的距離有關.

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

1.2 區域生長算法

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

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

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

1.3 基于區域生長與聚類分析相結合的分割方法

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

目標函數

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

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

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

2 實驗結果及分析

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

圖1 實驗圖像Fig.1 Experimental image

圖2 分割結果Fig.2 Segmentation result

圖1(a)為原始目標圖像,圖中矩形和橢圓形為目標區域,圖1(b)為經過超聲CT重建后的圖像.

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

2.1 運行時間的對比

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

2.2 目標區位置準確性的對比

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

圖3 目標區位置圖Fig.3 Location plan of target area

表2 原始圖像中目標區的位置信息Tab.2 Target zone’s position information of the original image

表3 分割后得到的目標區位置信息Tab.3 Target zone’s position information after segmentation

3 結 論

本文將區域生長和模糊C均值聚類分割方法存在的優缺點有機結合在一起,提出了一種基于區域生長與C均值聚類圖像相結合的分割方法,并通過仿真軟件實現了這種圖像分割的方法.結果表明:通過本算法預先設置的參數,實現了無監督的圖像分割.結合不同的圖像分割算法,充分利用各自的優點,揚長避短,達到較為理想的分割效果.

[1]馬英輝,韓焱.彩色圖像分割方法綜述[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]杜宇慧,桂志國,李晉華.基于類別方差的三維醫學圖像分割新方法[J].中北大學學報(自然科學版),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].長沙:國防科技大學出版社,1992:178-186.

[8]章毓晉.圖像工程(中冊)圖像分析(第二版)[M].北京:清華大學出版社,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]李明,李云松.改進的快速模糊C均值聚類的圖像分割方法[J].蘭州理工大學學報 ,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)