基于粒子群的改進模糊聚類圖像分割算法

劉歡，肖根福

1.井岡山大學 電子與信息工程學院，江西 吉安 343009 2.井岡山大學 機電學院，江西 吉安 343009

基于粒子群的改進模糊聚類圖像分割算法

劉歡1，肖根福2

1.井岡山大學 電子與信息工程學院，江西 吉安 343009 2.井岡山大學 機電學院，江西 吉安 343009

1 引言

圖像分割是圖像分析和模式識別需要解決的首要問題和基本問題，也是圖像處理和計算機視覺的經典難題之一，它決定了圖像的最終分析質量和模式識別的判別結果[1]。基于模糊理論的分割算法，特別是作為軟分類方法的模糊C均值（FCM）算法[2]可以較好地解決圖像信息的不確定性及多解性[3]，已經被成功地應用到圖像分割中。標準的FCM聚類算法沒有顧及像素的空間信息，對噪聲比較敏感；其次，FCM待聚類點的坐標值與目標函數都是離散量，迭代容易陷入局部極值，對初始值敏感，迭代過程中計算量太大，使聚類速度和性能都受到影響。為提高FCM算法的抗噪性能，近年來，許多研究提出了采用新的距離度量方法取代歐氏距離作為差異性的度量標準。文獻[4]提出了一種基于空間信息的可能性模糊C均值聚類算法，在一定程度上克服了FCM對噪聲的敏感性；文獻[5-7]把核聚類算法與FCM結合，用內核誘導距離來代替傳統FCM中采用的歐氏距離，從而把給定空間的非線性距離轉化為高維空間的線性距離；文獻[8]以FCM聚類中心建立網絡圖，通過網絡圖擴展移動求解能量函數最上值，實現圖像分割。這些算法依然存在對初始聚類中心數據較為敏感，運算速度慢等缺點。

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

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

2 TDFCM算法

2.1 TDFCM算法原理

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

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

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

2.2 TDFCM算法實現

算法實現的具體步驟為：

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

步驟2根據二維Xk=[xk，exk]T統計初始化聚類中心Mi=[mi，emi]T。

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

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

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

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

2.3 β參數的選取

β是正則化系數，其大小控制著后一項（鄰域信息）對前一項的相對影響。若β太小，則平滑效果不明顯，若β太大，則可能導致最后分割的錯誤。現給出一種β的選取辦法，先使用標準FCM算法對圖像進行分割，得到最佳的劃分矩陣U和目標函數JFCM值，再計算該劃分矩陣U對應的下述函數值，式中：NR表示鄰域的大小。

3 微粒群優化算法

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

其中，Vi為當代粒子移動速度；Vi-1為前一代粒子移動速度；r1、r2為介于[0，1]之間隨機數；c1、c2為學習因子，一般取2；xi為當代粒子位置；xi-1為前一代粒子位置；pb為個體最優位置，pg為全局最優位置；w為慣性因子。

搜索時，微粒的速度被最大速度vmax所限制。微粒的最大速度決定了解空間的搜索精度，對vmax進行動態調整可以使算法具有較好的自適應尋優效果。

4 PSO_TDFCM算法的策略和步驟

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

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

第一階段：

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

步驟2初始化微粒位置、速度、適應值。

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

步驟4.1對于每個微粒，將其當前適應值與其歷史最優位置適應值比較，若當前適應值較大，則更新歷史最優適應值，將當前位置作為歷史最優好位置；

步驟4.2當前所有粒子中最優位置的適應值與群歷史最優位置適應值比較，若當前所有粒子最優位置的適應值較大，則更新群歷史最優適應值，將當前所有粒子中最優位置作為群歷史最優好位置。

步驟5判斷循環條件是否成立，如果ε＞0.001則轉步驟3；否則步驟6。

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

第二階段：

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

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

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

步驟4判斷是否停止迭代計算，如果則轉步驟2；否則轉步驟5。

步驟5根據圖像中各像素對類中心的隸屬度對圖像去模糊化，實現圖像分割。

5 實驗結果

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

圖1 Lena原圖及分割效果圖

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

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

表1給出了描述以上三種算法的圖像分割結果的定量指標，其Time為圖像分割時間，Vpc為劃分系數，Vpe劃分熵；劃分系數越大，劃分越熵小，表明分割效果越好。從表1中可以看出，FCM算法時間最少，TDFCM算法由于是二維運算分割時間比FCM算法長，PSO_TDFCM算法先利用PSO算法獲得了最優聚類中心，分割時間（不包括PSO算法運行時間）比TDFCM算法短，但還是比FCM算法要長；從劃分系數來看，PSO_TDFCM算法最大，其次是TDFCM算法，最小的是FCM算法；從劃分熵來看，PSO_TDFCM算法最小，其次是TDFCM算法，最大的是FCM算法。這表明PSO_TDFCM算法分割效果最佳，其次是TDFCM算法，FCM算法最差。

表1 Lena標準圖和2%椒鹽噪聲圖的FCM、TDFCM、PSO_TDFCM算法定量指標比較

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

表2 Lena標準圖和2%椒鹽噪聲圖TDFCM、PSO_TDFCM算法分別與FCM算法指標變化幅度的比較（%）

表3給出了三種算法各自在Lena標準圖和噪聲圖間的變化程度。PSO_TDFCM算法分割時間的增加幅度最小，其次是TDFCM算法，最大的是FCM算法；對劃分系數的下降幅度和劃分熵的增加幅度，PSO_TDFCM算法都是最小，其次是TDFCM算法，最大的FCM算法。

綜合評價PSO_TDFCM算法的聚類效果比TDFCM和FCM算法好，取得了較滿意的分割效率，尤其是對噪聲圖像分割時表現出來了明顯的優勢。

表3 三個算法在Lena標準圖和2%椒鹽噪聲圖間指標變化幅度的比較（%）

6 結論

本文將粒子群算法與融入空間鄰域灰度熵、帶有距離約束項的模糊聚類圖像分割算法相結合，提出了一種新的算法。在距離度量中引入鄰域單元熵用二維距離代替傳統的一維距離度量，具有良好的收斂性，分割更準確；在目標函數中加入約束項有效地解決了標準FCM對噪聲敏感的缺點；利用粒子群算法的全局尋優能力，改善了標準FCM對初始聚類中心敏感，提高了分割速度與精度。實驗結果表明，與其他算法相比，本文算法分割效果較理想，尤其對有噪聲圖像的分割表現出了明顯的優勢，算法具有廣泛的實用價值。

[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]王適，蔣璐璐，王寶成.改進的模糊C均值聚類遙感圖像分割方法[J].計算機應用，2010，30（S2）：54-57.

[4]張一行，王霞，方世明.基于空間信息的可能性模糊C均值聚類遙感圖像分割[J].計算機應用，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，Freibure-in-Bresfau，1995：5-9.

[6]劉弘，劉希玉.支持外觀造型創新設計的進化計算方法[J].計算機輔助設計與圖形學學報，2006，18（1）：101-107.

[7]俞國燕，何真，鄭時雄.基于人機一體的混合智能創新設計[J].計算機工程與應用，2003，39（7）：43-45.

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

[9]劉金洋，郭茂祖，鄧超.基于雁群啟示的粒子群優化算法[J].計算機科學，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]左浩，李雯.混沌粒子群與模糊聚類在圖像分割中的應用[J].計算機工程與應用，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

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

粒子群；模糊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.

井岡山大學校級課題（No.JZ10011）。

劉歡（1981—），女，博士生，講師，主要研究領域為圖形圖像處理，模式識別與智能系統；肖根福（1980—），男，博士生，講師，主要研究領域為智能控制，數值計算。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