基于粒子群的改進(jìn)模糊聚類圖像分割算法

劉歡，肖根福

1.井岡山大學(xué) 電子與信息工程學(xué)院，江西 吉安 343009 2.井岡山大學(xué) 機(jī)電學(xué)院，江西 吉安 343009

基于粒子群的改進(jìn)模糊聚類圖像分割算法

劉歡1，肖根福2

1.井岡山大學(xué) 電子與信息工程學(xué)院，江西 吉安 343009 2.井岡山大學(xué) 機(jī)電學(xué)院，江西 吉安 343009

1 引言

圖像分割是圖像分析和模式識(shí)別需要解決的首要問(wèn)題和基本問(wèn)題，也是圖像處理和計(jì)算機(jī)視覺(jué)的經(jīng)典難題之一，它決定了圖像的最終分析質(zhì)量和模式識(shí)別的判別結(jié)果[1]?；谀：碚摰姆指钏惴?，特別是作為軟分類方法的模糊C均值（FCM）算法[2]可以較好地解決圖像信息的不確定性及多解性[3]，已經(jīng)被成功地應(yīng)用到圖像分割中。標(biāo)準(zhǔn)的FCM聚類算法沒(méi)有顧及像素的空間信息，對(duì)噪聲比較敏感；其次，F(xiàn)CM待聚類點(diǎn)的坐標(biāo)值與目標(biāo)函數(shù)都是離散量，迭代容易陷入局部極值，對(duì)初始值敏感，迭代過(guò)程中計(jì)算量太大，使聚類速度和性能都受到影響。為提高FCM算法的抗噪性能，近年來(lái)，許多研究提出了采用新的距離度量方法取代歐氏距離作為差異性的度量標(biāo)準(zhǔn)。文獻(xiàn)[4]提出了一種基于空間信息的可能性模糊C均值聚類算法，在一定程度上克服了FCM對(duì)噪聲的敏感性；文獻(xiàn)[5-7]把核聚類算法與FCM結(jié)合，用內(nèi)核誘導(dǎo)距離來(lái)代替?zhèn)鹘y(tǒng)FCM中采用的歐氏距離，從而把給定空間的非線性距離轉(zhuǎn)化為高維空間的線性距離；文獻(xiàn)[8]以FCM聚類中心建立網(wǎng)絡(luò)圖，通過(guò)網(wǎng)絡(luò)圖擴(kuò)展移動(dòng)求解能量函數(shù)最上值，實(shí)現(xiàn)圖像分割。這些算法依然存在對(duì)初始聚類中心數(shù)據(jù)較為敏感，運(yùn)算速度慢等缺點(diǎn)。

微粒群優(yōu)化算法（PSO algorithm）[9-10]是Kennedy和Eberhart于1995年提出的一種新興的基于群體智能啟發(fā)式全局搜索算法，具有易理解、易實(shí)現(xiàn)以及全局搜索能力強(qiáng)等特點(diǎn)。文獻(xiàn)[11]采用基于混沌粒子群的模糊C均值聚類算法，利用粒子群算法強(qiáng)大的全局尋優(yōu)能力避免算法收斂于局部極值，但并沒(méi)解決FCM對(duì)噪聲敏感等缺陷。

本文結(jié)合PSO提出了一種新的模糊聚類圖像分割方法：PSO_TDFCM。該方法利用微粒群較強(qiáng)的搜索能力搜索聚類中心，用像素點(diǎn)的灰度值和該像素點(diǎn)的空間鄰域單元熵的二維距離度量代替歐式距離，各像素領(lǐng)域單元熵體現(xiàn)了圖像局部單元的統(tǒng)計(jì)特征，不僅描述了圖像的全局特性也反映了圖像的空間分布特性；同時(shí)在目標(biāo)函數(shù)中加入鄰域距離約束項(xiàng)。與標(biāo)準(zhǔn)FCM圖像分割算法相比，本文的圖像分割算法抗噪能力更強(qiáng)，對(duì)初始聚類中心不敏感，收斂速度更快，分割效果更佳。

2 TDFCM算法

2.1 TDFCM算法原理

任何圖像都可以定義為由一系列像素點(diǎn)組成的二維數(shù)組，大小為M×N的矩形框架S={(i，j),1≤i≤M，1≤j≤N}，坐標(biāo)系由(i，j)確定，位置s=(si，sj)上的像素灰度值用xs表示。

TDFCM算法的基本思想是將普通FCM算法（一維FCM）中的像素值用（灰度值、鄰域單元熵）對(duì)代替，而聚類中心由（中心灰度值、中心鄰域單元熵）對(duì)代替；同時(shí)考慮到像素間的空間約束關(guān)系，加入鄰域距離約束項(xiàng)，它的目標(biāo)函數(shù)為：

式（1）中，Xk=[xk，exk]T，Mi=[mi，emi]T為矢量；xk為某一點(diǎn)的像素灰度值，exk為像素xk一定窗口單元Nk內(nèi)像素的熵；mi為圖像像素的聚類中心，emi為像素單元熵的聚類中心；為點(diǎn)xk的鄰域Nk中的像素的均值（不包括本身）到聚類中心mi的距離；β是正則化系數(shù)，其大小控制著后一項(xiàng)對(duì)前一項(xiàng)的相對(duì)影響。式（1）中的距離度量如式（2）所示，距離約束項(xiàng)中的如式（3）所示，單元熵計(jì)算如式（4）所示：

2.2 TDFCM算法實(shí)現(xiàn)

算法實(shí)現(xiàn)的具體步驟為：

步驟1確定聚類的數(shù)目c，設(shè)定聚類中心更新的終止條件ε=0.001。

步驟2根據(jù)二維Xk=[xk，exk]T統(tǒng)計(jì)初始化聚類中心Mi=[mi，emi]T。

步驟3由式（5）更新隸屬度矩陣。

步驟4由式（6）、（7）更新聚類中心。

步驟5計(jì)算更新前、后聚類中心的改變量為用下式計(jì)算：

步驟6采用最大隸屬度法去模糊化。

2.3 β參數(shù)的選取

β是正則化系數(shù)，其大小控制著后一項(xiàng)（鄰域信息）對(duì)前一項(xiàng)的相對(duì)影響。若β太小，則平滑效果不明顯，若β太大，則可能導(dǎo)致最后分割的錯(cuò)誤?，F(xiàn)給出一種β的選取辦法，先使用標(biāo)準(zhǔn)FCM算法對(duì)圖像進(jìn)行分割，得到最佳的劃分矩陣U和目標(biāo)函數(shù)JFCM值，再計(jì)算該劃分矩陣U對(duì)應(yīng)的下述函數(shù)值，式中：NR表示鄰域的大小。

3 微粒群優(yōu)化算法

粒子群優(yōu)化算法的基本思想源于模擬鳥(niǎo)群飛行覓食的行為，通過(guò)鳥(niǎo)之間的集體協(xié)作使群體達(dá)到最優(yōu)。粒子群算法初始化為一組隨機(jī)粒子，然后通過(guò)迭代尋找最優(yōu)解。粒子追隨兩個(gè)最優(yōu)值來(lái)更新自己，一個(gè)是粒子迄今為止尋找到的最優(yōu)值，叫做個(gè)體極值（pBest）；另外一個(gè)是整個(gè)粒子群迄今為止尋找到的最優(yōu)值，叫做全局極值（gBest）。粒子用以下公式更新自己：

其中，Vi為當(dāng)代粒子移動(dòng)速度；Vi-1為前一代粒子移動(dòng)速度；r1、r2為介于[0，1]之間隨機(jī)數(shù)；c1、c2為學(xué)習(xí)因子，一般取2；xi為當(dāng)代粒子位置；xi-1為前一代粒子位置；pb為個(gè)體最優(yōu)位置，pg為全局最優(yōu)位置；w為慣性因子。

搜索時(shí)，微粒的速度被最大速度vmax所限制。微粒的最大速度決定了解空間的搜索精度，對(duì)vmax進(jìn)行動(dòng)態(tài)調(diào)整可以使算法具有較好的自適應(yīng)尋優(yōu)效果。

4 PSO_TDFCM算法的策略和步驟

本文在對(duì)傳統(tǒng)FCM圖像分割算法存在的問(wèn)題進(jìn)行深入分析和研究的基礎(chǔ)上，提出了一種帶鄰域約束項(xiàng)的融入空間信息的改進(jìn)圖像分割算法TDFCM。由于該算法存在對(duì)初始聚類中心敏感，計(jì)算量大等問(wèn)題，因此又提出了基于微粒群優(yōu)化的PSO_TDFCM分割方法，將微粒群算法與TDFCM相結(jié)合。該算法的基本思想：整個(gè)算法分成二個(gè)階段。第一階段利用微粒群算法具有全局尋優(yōu)能力，獲得數(shù)個(gè)最佳的峰值點(diǎn)；第二階段將第一階段獲得的峰值點(diǎn)作為本階段圖像分割的初始類中心，利用TDFCM對(duì)圖像進(jìn)行分類，實(shí)現(xiàn)圖像分割。

PSO_TDFCM圖像分割算法步驟如下所示。

第一階段：

步驟1用TDFCM算法得到聚類中心作為微粒群算法的初始值，設(shè)微粒群規(guī)模N=10，誤差ε=0.001。

步驟2初始化微粒位置、速度、適應(yīng)值。

步驟3用式（10）、（11）、（12）修改微粒速度，用式（13）修改微粒的位置。

步驟4.1對(duì)于每個(gè)微粒，將其當(dāng)前適應(yīng)值與其歷史最優(yōu)位置適應(yīng)值比較，若當(dāng)前適應(yīng)值較大，則更新歷史最優(yōu)適應(yīng)值，將當(dāng)前位置作為歷史最優(yōu)好位置；

步驟4.2當(dāng)前所有粒子中最優(yōu)位置的適應(yīng)值與群歷史最優(yōu)位置適應(yīng)值比較，若當(dāng)前所有粒子最優(yōu)位置的適應(yīng)值較大，則更新群歷史最優(yōu)適應(yīng)值，將當(dāng)前所有粒子中最優(yōu)位置作為群歷史最優(yōu)好位置。

步驟5判斷循環(huán)條件是否成立，如果ε＞0.001則轉(zhuǎn)步驟3；否則步驟6。

步驟6由此獲得的最佳粒子位置作為第二階段的初始類中心，轉(zhuǎn)第二階段。

第二階段：

步驟1由第一階段得到結(jié)果初始類中心（中心灰度值，中心鄰域單元熵）對(duì)gBest。

步驟2由式（5）計(jì)算隸屬度矩陣μi(xk)。

步驟3用式（6）、（7）計(jì)算分類中心矩陣mi，emi。

步驟4判斷是否停止迭代計(jì)算，如果則轉(zhuǎn)步驟2；否則轉(zhuǎn)步驟5。

步驟5根據(jù)圖像中各像素對(duì)類中心的隸屬度對(duì)圖像去模糊化，實(shí)現(xiàn)圖像分割。

5 實(shí)驗(yàn)結(jié)果

以Lena圖像為例，圖1（a）為標(biāo)準(zhǔn)Lena圖像，圖2（a）為疊加了2%的椒鹽噪聲的Lena圖像。分別應(yīng)用三種不同的分割算法，即標(biāo)準(zhǔn)的FCM算法、本文的TDFCM算法和基于PSO_TDFCM的算法進(jìn)行圖像分割實(shí)驗(yàn)，并對(duì)三種方法獲得的結(jié)果進(jìn)行比較。本文使用PSOT粒子群優(yōu)化工具箱里的標(biāo)準(zhǔn)PSO算法，在MATLAB2012a中進(jìn)行優(yōu)化實(shí)驗(yàn)。PSO算法的參數(shù)采用默認(rèn)值：加速系數(shù)c1=2.0，c2=2.0，最小慣性權(quán)值ω=0.4，最大慣性權(quán)值ω=0.9。綜合粒子維數(shù)、算法的精度、穩(wěn)定性和運(yùn)行時(shí)間等多個(gè)因素，考慮選擇粒子群規(guī)模為10，誤差精度ε=0.001，算法最大迭代次數(shù)30，粒子速度限制在[-1，1]之間；圖像分割算法中，定義在3×3大小的圖像窗口中計(jì)算對(duì)應(yīng)點(diǎn)的熵作為該點(diǎn)的鄰域單元熵，聚類數(shù)為6。實(shí)驗(yàn)結(jié)果如圖1（b）、（c）、（d），分別為FCM、TDFCM、PSO_TDFCM算法對(duì)原圖的分割效果圖；如圖2（b）、（c）、（d）分別為FCM、TDFCM、PSO_TDFCM算法對(duì)Lena加2%椒鹽噪聲圖的分割效果圖。

圖1 Lena原圖及分割效果圖

圖2 Lena噪聲圖及分割效果圖

從分割結(jié)果對(duì)比圖可以看出，TDFCM算法的抗噪能力明顯好于FCM算法，而PSO_TDFCM算法較TDFCM算法也有一定的改善。

表1給出了描述以上三種算法的圖像分割結(jié)果的定量指標(biāo)，其Time為圖像分割時(shí)間，Vpc為劃分系數(shù)，Vpe劃分熵；劃分系數(shù)越大，劃分越熵小，表明分割效果越好。從表1中可以看出，F(xiàn)CM算法時(shí)間最少，TDFCM算法由于是二維運(yùn)算分割時(shí)間比FCM算法長(zhǎng)，PSO_TDFCM算法先利用PSO算法獲得了最優(yōu)聚類中心，分割時(shí)間（不包括PSO算法運(yùn)行時(shí)間）比TDFCM算法短，但還是比FCM算法要長(zhǎng)；從劃分系數(shù)來(lái)看，PSO_TDFCM算法最大，其次是TDFCM算法，最小的是FCM算法；從劃分熵來(lái)看，PSO_TDFCM算法最小，其次是TDFCM算法，最大的是FCM算法。這表明PSO_TDFCM算法分割效果最佳，其次是TDFCM算法，F(xiàn)CM算法最差。

表1 Lena標(biāo)準(zhǔn)圖和2%椒鹽噪聲圖的FCM、TDFCM、PSO_TDFCM算法定量指標(biāo)比較

表2給出了Lena標(biāo)準(zhǔn)圖和噪聲圖中PSO_TDFCM和TDFCM算法分別與FCM算法相比，劃分系數(shù)和劃分熵的變化程度。PSO_TDFCM、TDFCM算法比FCM算法的劃分系數(shù)都有一定程度的增加，劃分熵都有一定程度的下降，尤其在噪聲圖像中PSO_TDFCM算法劃分系數(shù)的增加幅度要大于TDFCM算法的增加幅度，劃分熵的下降幅度也大于TDFCM算法的下降幅度。

表2 Lena標(biāo)準(zhǔn)圖和2%椒鹽噪聲圖TDFCM、PSO_TDFCM算法分別與FCM算法指標(biāo)變化幅度的比較（%）

表3給出了三種算法各自在Lena標(biāo)準(zhǔn)圖和噪聲圖間的變化程度。PSO_TDFCM算法分割時(shí)間的增加幅度最小，其次是TDFCM算法，最大的是FCM算法；對(duì)劃分系數(shù)的下降幅度和劃分熵的增加幅度，PSO_TDFCM算法都是最小，其次是TDFCM算法，最大的FCM算法。

綜合評(píng)價(jià)PSO_TDFCM算法的聚類效果比TDFCM和FCM算法好，取得了較滿意的分割效率，尤其是對(duì)噪聲圖像分割時(shí)表現(xiàn)出來(lái)了明顯的優(yōu)勢(shì)。

表3 三個(gè)算法在Lena標(biāo)準(zhǔn)圖和2%椒鹽噪聲圖間指標(biāo)變化幅度的比較（%）

6 結(jié)論

本文將粒子群算法與融入空間鄰域灰度熵、帶有距離約束項(xiàng)的模糊聚類圖像分割算法相結(jié)合，提出了一種新的算法。在距離度量中引入鄰域單元熵用二維距離代替?zhèn)鹘y(tǒng)的一維距離度量，具有良好的收斂性，分割更準(zhǔn)確；在目標(biāo)函數(shù)中加入約束項(xiàng)有效地解決了標(biāo)準(zhǔn)FCM對(duì)噪聲敏感的缺點(diǎn)；利用粒子群算法的全局尋優(yōu)能力，改善了標(biāo)準(zhǔn)FCM對(duì)初始聚類中心敏感，提高了分割速度與精度。實(shí)驗(yàn)結(jié)果表明，與其他算法相比，本文算法分割效果較理想，尤其對(duì)有噪聲圖像的分割表現(xiàn)出了明顯的優(yōu)勢(shì)，算法具有廣泛的實(shí)用價(jià)值。

[1]Cheng H D，Jiang X H，Sun Y，et al.Color image segmentation：advances and prospects[J].Pattern Recognition，2001，34：2259.

[2]Bezdek J C.Pattern recognition with fuzzy objective function algorithms[M].New York：Plenum Press，1981.

[3]王適，蔣璐璐，王寶成.改進(jìn)的模糊C均值聚類遙感圖像分割方法[J].計(jì)算機(jī)應(yīng)用，2010，30（S2）：54-57.

[4]張一行，王霞，方世明.基于空間信息的可能性模糊C均值聚類遙感圖像分割[J].計(jì)算機(jī)應(yīng)用，2011，31（11）：3004-3007.

[5]Soddu C.Recreating the city’s identity with a morphogenetic urban design[C]//Proceeding of the 17th International Conference on Making Cities Livable，F(xiàn)reibure-in-Bresfau，1995：5-9.

[6]劉弘，劉希玉.支持外觀造型創(chuàng)新設(shè)計(jì)的進(jìn)化計(jì)算方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18（1）：101-107.

[7]俞國(guó)燕，何真，鄭時(shí)雄.基于人機(jī)一體的混合智能創(chuàng)新設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用，2003，39（7）：43-45.

[8]王曉飛，郭敏.結(jié)合模糊C均值聚類與圖割的圖像分割方法[J].計(jì)算機(jī)應(yīng)用，2009，29（7）：1918-1920.

[9]劉金洋，郭茂祖，鄧超.基于雁群?jiǎn)⑹镜牧Ｗ尤簝?yōu)化算法[J].計(jì)算機(jī)科學(xué)，2006，33（11）：166-168.

[10]Kennedy J，Eberhart R C.Particle swarm optimization[C]// Proc of the IEEE International Conference on Neural Networks，1995：1942-1948.

[11]左浩，李雯.混沌粒子群與模糊聚類在圖像分割中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（2）：194-196.

LIU Huan1,XIAO Genfu2

1.Collgeg of Electronic and Information Engineering,Jinggangshan University,Ji’an,Jiangxi 343009,China
2.College of Machinery and Electrons,Jinggangshan University,Ji’an,Jiangxi 343009,China

In improved fuzzy clustering image segmentation method based on Particle Swarm Optimization（PSO_TDFCM）, the clustering centers searched by particle swarm are taken as image segmentation clustering initializations,which overcomes the sensitive to the clustering center initializations for Fuzzy C-Means（FCM）algorithm as well as improves the speed of FCM algorithm greatly.Meanwhile,on the one hand,the new idea taken into account the great correlation between the spatial site information of a pixel and it’s neighboring pixels,consequently,the neighboring penalized function is added in the objective function；on the other hand,it suggests to update the clustering centers at the two-dimension directions,from which the new objective function combines cell entropy.The results of comparative experiments demonstrate that this approach is an effective fuzzy clustering image segmentation algorithm,which can make a marked improvement in the speed of fuzzy clustering as well as insensitive to the initial clustering patters and robust to the noise.

particle swarm;Fuzzy C-Means clustering（FCM）;image segmentation;neighboring information;cell entropy

基于粒子群優(yōu)化的改進(jìn)模糊聚類圖像分割算法將微粒群搜索聚類中心作為圖像分割的聚類初值，克服了FCM分割算法對(duì)聚類中心初值敏感的缺點(diǎn)，大幅提高了圖像分割算法的計(jì)算速度。改進(jìn)的模糊聚類圖像分割算法，一方面考慮到像素的空間位置信息和相互鄰域之間像素有很大的相關(guān)性，在目標(biāo)函數(shù)中引入鄰域懲罰函數(shù)；另一方面提出聚類在二維方向上進(jìn)行更新的思想，建立了包含鄰域單元熵的新聚類目標(biāo)函數(shù)。實(shí)驗(yàn)結(jié)果表明，該方法可以使模糊聚類的速度得到明顯提高，對(duì)初始聚類中心不敏感，抗噪能力強(qiáng)，是一種有效的模糊聚類圖像分割方法。

粒子群；模糊C均值聚類；圖像分割；鄰域信息；單元熵

A

TP391.41

10.3778/j.issn.1002-8331.1208-0074

LIU Huan,XIAO Genfu.Improved fuzzy clustering image segmentation algorithm based on particle swarm optimization.Computer Engineering and Applications,2013,49（13）：152-155.

井岡山大學(xué)校級(jí)課題（No.JZ10011）。

劉歡（1981—），女，博士生，講師，主要研究領(lǐng)域?yàn)閳D形圖像處理，模式識(shí)別與智能系統(tǒng)；肖根福（1980—），男，博士生，講師，主要研究領(lǐng)域?yàn)橹悄芸刂?，?shù)值計(jì)算。E-mail：liuhuan816618@163.com

2012-08-06

2012-09-27

1002-8331（2013）13-0152-04

CNKI出版日期：2012-11-21http://www.cnki.net/kcms/detail/11.2127.TP.20121121.1100.014.html