基于ＰＳＯ的快速模糊Ｃ均值圖像分割算法

 收稿日期：2007-11-15；

修回日期：2008-01-15

基金項目：國家自然科學基金資助項目（60574025）; 河南省教育廳自然科學基金資助項目（2008A520021）； 信陽師范學院青年骨干教師計劃資助項目（20080619）



作者簡介：李艷靈（1975-），女，河南新鄉(xiāng)人，博士研究生，主要研究方向為圖像處理和計算機算法(lyl75@163.com).

（1.華中科技大學 控制科學與工程系， 武漢 430074； 2.信陽師范學院 計算機科學系， 河南 信陽 464000）

摘要：

利用粒子群算法全局性和魯棒性的特點，可以解決模糊C均值算法（FCM）用于圖像分割時對初始值敏感、容易陷入局部極小值的問題。但是設(shè)定粒子群算法的初始搜索范圍依賴于人的經(jīng)驗，并且所設(shè)范圍往往過大，影響算法的執(zhí)行速度，為此提出用收斂速度快的K均值聚類法得到的聚類中心作為粒子群算法初始搜索范圍的參考，縮小粒子群算法的搜索范圍，提高算法執(zhí)行速度。實驗表明該算法具有較高的分割速度和良好的抑制噪聲的能力。

關(guān)鍵詞：圖像分割； 模糊C均值； K均值算法； 粒子群算法

中圖分類號：TP391.4

文獻標志碼：A

文章編號：1001-3695(2008)10-3053-03

Fast fuzzy C-means algorithm for image segmentation based on PSO

LI Yan-ling1，2， LI Gang2

(1.Dept.of Control Science Engineering， Huazhong University of Science Technology， Wuhan 430074， China;

2.Dept.of Computer-Science， Xinyang Normal University， Xinyang Henan 464000， China)

Abstract:

The fuzzy C-means algorithm is sensitive to noise and always converges to the local infinitesimal value， which is-overcome by PSO algorithm with the feature of overall robustness. But the initial searching scope of PSO was selected by human experience， and the selected searching scope was always too big， which influenced the velocity of algorithm. This paper used the clustering centers obtained by K-means algorithm as the reference of the searching scope of PSO algorithm， which reduced the search scope and improved the velocity of algorithm. The experimental results show that new algorithm can converge more quickly than the standard FCM algorithm and suppress the noise effectively.

Key words：image segmentation; fuzzy C-means(FCM); K-means algorithm; particle swarm optimization(PSO) algorithm

圖像分割是將圖像分割成互不相交的區(qū)域，使每個區(qū)域內(nèi)的像素具有相似的特征，以便對圖像進行后續(xù)處理。它是模式識別和計算機視覺中的經(jīng)典研究課題，至今沒有一個通用且有效的圖像分割方法能滿足不同的需求。在眾多的圖像分割方法中，由Dunn[1]提出，后經(jīng)Bezdek[2]推廣的FCM算法因其實現(xiàn)簡單、結(jié)果較優(yōu)而得到廣泛應(yīng)用。然而該算法對初始值敏感，容易陷入局部極小值。FCM算法在用于基于灰度圖像分割時，由于聚類數(shù)目較大，這一缺點尤為明顯。對于FCM算法來說，選擇一個好的初始聚類中心集是非常重要的。如果選擇一個好的初始聚類中心集，算法能夠很快收斂于實際的聚類中心[3]。選擇與實際聚類中心近似的初始類中心能夠減少算法的迭代次數(shù)和改善系統(tǒng)的性能。粒子群優(yōu)化算法是一種基于種群操作的優(yōu)化技術(shù)，由Eberhart等人[4]和Kenned等人[5]發(fā)明。其源于對鳥群捕食的行為研究，目前已廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓練、模糊系統(tǒng)控制等領(lǐng)域。

1模糊C-均值（FCM）算法

若將圖像像素值組成n個樣本的集合X={x1，x2，…，xn}，則圖像分割問題就轉(zhuǎn)換為將這n個樣本分成c個聚類的問題。

根據(jù)圖像中像素和聚類中心的加權(quán)相似測度，對目標函數(shù)進行迭代優(yōu)化以確定最佳聚類。FCM的目標函數(shù)如下：



Jm(U，V)=∑ni=1∑cj=1umijd2ij

（1）

約束條件為

∑cj=1uij=1， 1≤i≤n;

uij∈[0，1]， 1≤i≤n， 1≤j≤c（2）

其中：m∈(1，∞)為加權(quán)指數(shù)；uij是第j類中樣本xi的隸屬度；U=[uij]n×c為模糊劃分矩陣；dij=‖xi-vj‖為樣本xi與聚類中心vj的歐氏距離。利用拉格朗日乘子法，可推導出式（1）的兩個優(yōu)化迭代公式：

uij=[∑ck=1(d2ij/d2ik)1/(m-1)]-1

（3）

vj=∑ni=1umijxi/∑ni=1umij（4）

圖像的優(yōu)化分割就是通過迭代尋找聚類中心vj與隸屬度值uij，使目標函數(shù)Jm(U，V)取最小。

2基于PSO的FCM分割算法及其改進

2.1粒子群算法

粒子群優(yōu)化算法（PSO）模擬鳥群的捕食行為。在PSO中，每個優(yōu)化問題的解都是搜索空間中的一只鳥，稱之為粒子。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應(yīng)值（fitness-value），每個粒子還有一個速度決定它飛翔的方向和距離。然后粒子們就追隨當前的最優(yōu)粒子在解空間中搜索。PSO初始化為一群Nd維空間的隨機粒子（隨機解），在每一次迭代中，粒子通過跟蹤兩個極值來更新自己：第一個就是粒子本身所找到的最優(yōu)解pid；另一個極值是整個種群目前找到的最優(yōu)解pgd。找到這兩個最優(yōu)值后，粒子根據(jù)如下的公式來更新自己的速度和位置：



vi，k(t+1)=wvi，k(t)+c1r1，k(t)(pbesti，k(t)-

xi，k(t))+c2r2，k(t)(gbestk-xi，k(t))（5）

xi(t+1)=xi(t)+vi(t+1)（6）

其中：xi表示粒子當前的位置； vi，k表示粒子當前的速度；-pbesti，k表示粒子本身到達過的最好位置pid;gbestk表示整個種群目前的最優(yōu)位置pgd；r1，k、r2，k產(chǎn)生[0，1]的隨機數(shù)；c1、c2為學習因子；w是慣性權(quán)重，為非負數(shù)。w較大時，算法具有較強的全局搜索能力；w較小時算法傾向于局部搜索。一般的做法是將w從wmax隨迭代次數(shù)的增加線性遞減至wmin，由如下式子確定：w=wmax-[(wmax-wmin)/itermax]×iter。其中：wmax、wmin分別為w的最大值和最小值；iter、itermax分別為當前迭代次數(shù)和最大迭代次數(shù)。

2.2基于PSO的FCM的基本思想

算法的基本思想是：用向量V=(v1，v2，…，vc)來表示一個聚類中心，也就是一個粒子。其中vi表示第i類聚類中心的編碼。每類n維聚類中心采用實數(shù)編碼，這樣向量V就成了c×n列的一維行向量。通過式（3）計算適應(yīng)度矩陣U(t)=(uij)，令PSO的適應(yīng)度函數(shù)為

fitness=1/(1+∑ni=1∑cj=1[uij]m‖xi-vj‖2)（7）

粒子通過改變每一維不同的取值即簇中心的取值從而產(chǎn)生多種聚類結(jié)果，直到找到可接受的簇中心即適應(yīng)度函數(shù)達到終止條件或整個循環(huán)達到最大循環(huán)次數(shù)。最終求得的V就表示最優(yōu)解。然后，F(xiàn)CM算法利用上述得到的最優(yōu)解對應(yīng)的粒子作為初始聚類中心進行圖像分割。

2.3基于PSO的FCM分割算法及其改進

設(shè)定粒子群算法的初始搜索范圍時，需要依賴于人的經(jīng)驗。這樣設(shè)定的范圍太大，本文采用K均值聚類算法以減小該范圍。一般來講，粒子群的初始位置是在設(shè)定的編碼范圍內(nèi)隨機產(chǎn)生的，往往與最終迭代結(jié)果相差較大，因此迭代時間較長。如果選擇的初始值和最終迭代結(jié)果很接近，就可以大大減少迭代次數(shù)。K均值聚類算法（模糊指數(shù)m=1）的收斂速度比模糊聚類算法快很多，而兩者的聚類中心十分接近[6]。因此，本文先用K均值聚類法進行迭代得到聚類中心，然后將之作為參考值，上下浮動一個小的范圍，在該范圍內(nèi)隨機生成基于PSO的FCM算法粒子群的初始值，則可以減少迭代次數(shù)，從而提高算法的聚類速度。具體算法步驟如下：

a)利用K均值算法產(chǎn)生初始聚類中心。

b)給定類別數(shù)c，群體規(guī)模N，學習因子c1、c2，慣性權(quán)重wmax、wmin，迭代的最大次數(shù)itermax。

c)以K均值算法產(chǎn)生初始的聚類中心為參考，上下浮動一個小的范圍，在該范圍內(nèi)初始化粒子群。

d)

for t=0 to max-iteration do

for 每一個粒子 do

用式（3）計算隸屬度矩陣U(t)；

用式（7）計算適應(yīng)度值fitness；

根據(jù)適應(yīng)度值修改pbesti，k、gbestk；

根據(jù)式（5）修改粒子速度；

根據(jù)式（6）修改粒子位置；

end for

end for

e)輸出取得gbestk的粒子，根據(jù)式（3）得到樣本集的隸屬度矩陣。

f)根據(jù)PSO得到的結(jié)果作為FCM算法的初始聚類中心，利用FCM算法進行圖像聚類分割。

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

3.1算法的有效性評價函數(shù)

本文采用兩種不同的方法對圖像分割結(jié)果進行評定，這兩種方法相互補充，具有良好的評定功能和魯棒性。一種是模糊聚類后從給定的聚類中心數(shù)和隸屬度矩陣定義劃分系數(shù)和劃分熵；另一種是根據(jù)模糊劃分后類間的關(guān)聯(lián)度來判別。劃分系數(shù)定義為



Vpc=(∑ci=1∑nj=1u2ij)/n（8）

劃分熵

Vpe=-(∑ci=1∑nj=1(u2ij log uij))/n（9）

當聚類達到最佳效果時，劃分系數(shù)的值達到最大，而劃分熵的值最小。但是這兩個函數(shù)對像素的空間幾何特性缺少直接聯(lián)系，因此根據(jù)像素點模糊劃分的類間關(guān)聯(lián)度定義聚類有效性評價函數(shù)



Vxb=(∑ci=1∑nj=1u2ij‖xj-vi‖2)/(n(mini≠k{‖vk-vi‖2})（10）

對于一個好的聚類分割結(jié)果，類內(nèi)的像素點分布是緊湊的，類與類之間的模糊關(guān)聯(lián)度應(yīng)盡可能小。因此當像素聚類達到最佳效果時，Vxb的值應(yīng)達到最小。

3.2實驗結(jié)果與分析

為驗證本文方法的有效性，對模擬腦圖、測試圖像和添加了高斯噪聲的測試圖像分別用標準的FCM算法、基于PSO的FCM算法和本文提出的改進的基于PSO的FCM算法（以下簡稱為新算法）進行實驗，比較了幾種算法的圖像分割速度和效果。

實驗環(huán)境為：Pentium4 2 GHz CPU，256 MB內(nèi)存，MATLAB 7.04編程工具仿真實現(xiàn)。實驗中有關(guān)參數(shù)作如下設(shè)置：模糊指數(shù)m=2，ε=1e-5，群體規(guī)模N=50，最大進化代數(shù)itermax=50，PSO中的學習因子c1=c2=2.0，慣性權(quán)重wmax=0.9；wmin=0.4。

表1、2給出了對三幅測試圖像和加入（0~0.2）高斯噪聲的三幅測試圖像分別用FCM分割方法和基于PSO的FCM分割方法進行圖像分割的實驗結(jié)果對比。

FCM算法320.885 80.195 40.045 3

基于PSO的FCM算法300.885 80.195 40.045 3

256×256的cameraman圖

FCM算法180.925 10.135 40.028 4

基于PSO的FCM算法140.925 10.135 40.028 4

128×128的MRI圖

FCM算法180.944 80.093 60.018 7

基于PSO的FCM算法150.944 80.093 60.018 7

表2對加入2%高斯噪聲的圖像的實驗結(jié)果對比

圖像算法迭代次數(shù)VpcVpeVxb

512×512的woman圖

FCM算法430.850 90.250 40.068 6

基于PSO的FCM算法250.851 30.250 00.068 2

256×256的cameraman圖

FCM算法300.859 50.238 10.062 6

基于PSO的FCM算法250.860 80.236 10.062 1

128×128的MRI圖

FCM算法280.879 80.203 40.054 4

基于PSO的FCM算法250.881 10.201 40.054 0

從表1和2的比較結(jié)果來看，對于一般的測試圖像，基于PSO的FCM算法的圖像分割質(zhì)量與基本的FCM算法的圖像分割質(zhì)量一樣。然而，基于PSO的FCM算法的迭代次數(shù)比基本的FCM算法少。對于含有高斯噪聲的圖像，基于PSO的FCM算法的迭代次數(shù)少，而且圖像分割結(jié)果比基本的FCM算法的圖像分割結(jié)果好，表明基于PSO的FCM算法具有良好的抑制噪聲的能力。

圖1~3給出了三幅圖分別用FCM分割方法、基于PSO的FCM分割方法和新算法進行圖像分割的結(jié)果。表3給出了基于PSO的FCM算法和本文提出的新算法的實驗結(jié)果對比。

圖像算法VpcVpeVxb算法執(zhí)行時間/s

模擬腦圖

基于PSO的FCM算法0.93400.13200.001776.413 47

新算法0.93400.13200.00174.843 85

cameraman圖

基于PSO的FCM算法0.92510.13540.0284166.530 0

新算法0.92510.13540.02849.907 73

含有2%高斯噪聲的cameraman圖

基于PSO的FCM算法0.859730.23770.0626165.310 0

4結(jié)束語

本文對基于PSO的FCM算法進行改進，利用收斂速度快的K均值聚類法得到的聚類中心作為粒子群算法初始搜索范圍的參考，在此基礎(chǔ)上定義一個較小的范圍作為粒子群算法的初始搜索范圍，然后利用基于PSO的FCM算法進行圖像分割。實驗表明新算法在保持了基于PSO的FCM算法迭代次數(shù)少、收斂速度快和良好的抑制噪聲的能力的同時，使算法的執(zhí)行速度得到了較大的提高。

參考文獻：

[1]DUNN J C. A fuzzy relative of the ISODATA process and its use in detecting compact， well-separated clusters[J]. J Cybern， 1974，3:32-57.

[2]BEZDEK J C. Pattern recognition with fuzzy objective function algorithms[M]. New York:[s.n.]， 1981.

[3]HUNG M C， YANG D L. An efficient fuzzy C-means clustering algorithm[C]//Proc of IEEE International Conference on Data Mining(ICDM 2001). California:[s.n.]， 2001:225-232.

[4]EBERHART R， KENNED Y J. A new optimizer using particle swarm theory[C]//Proc of the 6th International Symposium on Micro Machine and Human Science. Nagoya:[s.n.]， 1995:39-43.

[5]KENNED Y J， EBERHART R. Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks. Perth:[s.n.]， 1995:1942-1948.

[6]吳林，郭大勇，施克仁，等.改進的FCM在人腦MR圖像分割中的應(yīng)用[J].清華大學學報:自然科學版，2004，44(2):157-159.