基于模擬退火和粒子群改進的圖像分割FCM方法

陸振宇 夏志巍 盧亞敏 黃現云

摘 要： 針對模糊C均值聚類（FCM）算法在分割圖像時需要事先給出聚類數和容易陷入局部極小值的問題，提出一種新的FCM算法。首先，利用粒子群算法更新FCM的聚類中心，以加強算法的搜索能力，提高收斂速度；其次，根據模擬退火準則決定是否接受新的聚類中心，以得到當前迭代下的全局最優值；最后，設定有效性函數尋找圖像的最佳聚類數，使算法具有自適應判斷圖像類別個數的能力。實驗結果表明，該算法具有較好的全局收斂性，并且在未知聚類數的情況下能自適應尋找圖像的最佳分類個數。

關鍵詞： 自適應圖像分割； 模擬退火算法； 粒子群算法； 模糊C均值； 聚類中心； 全局最優

中圖分類號： TN911.73?34 文獻標識碼： A 文章編號： 1004?373X（2018）07?0036?05

Improved FCM method for image segmentation based on simulated

annealing and particle swarm optimization

LU Zhenyu1， 2， XIA Zhiwei1， LU Yamin1， HUANG Xianyun1

（1. School of Electronic & Information Engineering， Nanjing University of Information Science and Technology， Nanjing 210044， China；

2. Jiangsu Collaborative Innovation Center on Atmospheric Environment and Equipment， Nanjing 210044， China）

Abstract： Since the traditional fuzzy C?means （FCM） algorithm needs to give the clustering numbers in advance and is easy to fall into local minimum for image segmentation， a novel FCM algorithm based on simulated annealing algorithm and particle swarm optimization （PSO） is proposed. The PSO algorithm is applied to update the clustering center of FCM to enhance the search ability and convergence rate of the algorithm. And then the simulated annealing rule is used to decide whether to accept the new clustering center or not， so as to obtain the global optimal value of current iteration. The validity function is set to find the optimal clustering numbers of the image， and make the proposed algorithm have the ability to adaptively judge the numbers of an image category. The experiment results demonstrate that the algorithm has perfect global convergence， and is able to adaptively find the optimum catelory numbers of the image in the case of the unknown clustering numbers.

Keywords： adaptive image segmentation； simulated annealing algorithm； particle swarm optimization； fuzzy C?means； clustering center； global optimization

0 引 言

圖像分割是根據一定的準則把圖像分割成幾個互不重疊且各具特色的區域。目前圖像分割方法主要有：基于閾值的分割方法，如最大類間方差的自適應閾值分割[1]、基于粒子群優化的多級閾值分割[2]；基于邊緣檢測的分割方法，如拉普拉斯算子[3]、結構化森林[4]；基于區域生長和分裂合并的分割方法，如區域生長與神經網絡相結合的方法[5]、水平集與區域生長相結合的方法[6]；結合特定理論的分割方法，如基于分水嶺的標號法[7]、深度卷積神經網絡方法[8]。

聚類分割方法屬于區域分割方法，它是一種無監督的統計方法，在圖像分割領域應用非常廣泛。FCM分割方法具有程序實現簡單、不需要人為干預等方面的優勢，但傳統的FCM算法在求解目標函數時采用最速下降法，易使得迭代過程陷入局部最優解。此外，對圖像進行分割前必須預先給出圖像的聚類個數，可擴展性較差。

針對這些問題，許多學者提出了很多改進的方法。針對目標函數求解時易陷入局部極值的問題，文獻[9]提出粒子群與FCM融合（PSOFCM）的方法；文獻[10]提出捕食者?食餌者微粒群與FCM融合（PPPSOFCM）的方法。針對如何自適應判定圖像最優聚類數的問題，文獻[11]提出基于數據集模糊劃分模式的劃分系數來確定聚類數；文獻[12]提出基于緊密度和分離度這兩個指標的有效性函數[VXB]來確定最佳聚類數。

基于以上兩個問題的綜合考慮，本文提出一種自適應的模擬退火粒子群FCM算法，該算法在已有的FCM聚類算法中融合了模擬退火、粒子群和有效性函數。首先在優化FCM目標函數時，利用粒子群算法更新FCM的聚類中心。其次，根據模擬退火的Metropolis準則繼續調整聚類中心，使得算法在每次迭代時都能達到全局最優。最后，引入有效性函數，通過計算圖像在不同類別數下的有效值，判定圖像的最佳聚類數，使得算法在未知類別數的情況下得到合理的分割結果，進一步提升算法的自適應性。利用改進的方法對仿真圖像和自然圖像進行實驗，實驗結果表明，本文算法不僅能夠達到全局最優，而且可以在未知聚類數的情況下自動尋找圖像的最佳分類個數。

1 FCM算法

FCM方法是將樣本空間[X={x1，x2，…，xn}]的樣本點分成[c]個類別， 其目標函數為：

式中：[U=（μij）n×c]是隸屬度矩陣；[μij]是樣本點[xi]隸屬于第[j] 類的值；[m（m>1）]是模糊指數；[V=（v1，v2，…，vc）]是聚類中心值的矩陣；[vj]表示第[j]個聚類中心；[d2ij（xi，vj）=xi-vj]是樣本點[xi]到聚類中心[vj]的歐氏距離。

該算法首先確定聚類數[c]和初始化隸屬度矩陣，然后通過式（2），式（3）反復更新聚類中心和隸屬度矩陣，當達到一定精度時，就得到各類的聚類中心和隸屬度。

該算法有以下缺點：對初始值敏感，很大程度上依賴初始聚類中心的選擇，當初始聚類中心嚴重偏離全局最優聚類中心時，用FCM很可能陷入局部極小值。且必須預先給定聚類數[c，]但對于大多數樣本往往不知道最佳聚類數。

2 PSOFCM算法

基于粒子群的模糊C均值聚類算法（PSOFCM）的圖像分割通過PSO算法優化FCM的聚類中心，在一定程度上避免了傳統的FCM對初始值敏感、容易陷入局部最優的缺點，同時圖像分割的效果也得到了提高，性能也比傳統的FCM方法更加穩定。

矩陣[Z=（Z1，Z2，…，ZN）T]是[N]個粒子的位置矩陣，其中[Zl=（zl1，zl2，…，zlc）]作為PSO中的一個粒子，表示一個聚類中心的集合。通過式（2）可以計算隸屬度矩陣[U，]將FCM算法的目標函數作為PSO的適應度函數：

式中：[vlj]是第[l]個粒子的速度在第[j]維上的分量；[Pl=（pl1，pl2，…，plc）]是第[l]個粒子的最佳位置；[Pg=][（pg1，pg2，…，pgc）]是全體粒子的最佳位置；[w]是慣性系數；[c1，c2]是學習因子，一般取2。

該算法通過式（5），式（6）改變每個粒子的位置即聚類中心的取值從而產生多種聚類結果，直到找到可接受的簇中心，即適應度函數達到終止條件或整個循環達到最大循環次數。此算法與FCM算法的最大區別在于不再使用梯度下降方法而是使用PSO來確定聚類中心。

PSOFCM算法主要通過粒子群的速度和位置公式來更新FCM算法中的聚類中心，該算法加強了FCM的全局搜索能力并提高了收斂速度，但仍然沒有有效解決FCM易陷入局部極值的問題和需要事先給定聚類數的缺點。

3 本文方法

首先在FCM算法中加入模擬退火粒子群算法，利用粒子群算法的速度公式更新FCM的聚類中心，并用模擬退火算法的Metropolis準則來判斷是否接受新的聚類中心。然后引入有效性函數，計算不同聚類數下的最優值所對應的有效值。最后根據有效值得到最佳的類別數和最優的分割結果。

3.1 改進的模擬退火粒子群與FCM的融合（SAPSOFCM）

N. Metropolis等人在1953年提出模擬退火算法，其思想是通過模擬高溫物體退火過程的方法來找到優化問題的全局最優或近似全局最優解。為了解決PSOFCM易陷入局部極值的缺點，在PSOFCM方法中引入模擬退火算法，即在每次迭代過程中，若粒子的適應度小于該粒子之前的適應度則接受新值，反之以概率[P（T）]來接受惡化解。

[P（T）=exp（-ΔfT）] （7）

式中：[T]為當前溫度；[Δf=fit（U，Z（k）l）-fit（U，Z（k-1）l）]，[k]為迭代次數。

這樣粒子的適應度會偶爾向增加的方向發展，有利于跳出局部極小區域。隨著假想溫度的降低，系統活動性降低，最終以概率1穩定在全局最優值。

SAPSOFCM方法步驟如下：

Step1：初始化參數，對初始溫度[T0、]溫度下降系數dec、群體規模[N、]學習因子[c1，c2、]慣性系數[w]等賦初值，粒子群的最大迭代次數為[kP，]模擬退火的最大迭代次數為[kS]。隨機產生[N]個初始位置，設[k=1，][i=1]。

Step2：根據式（4）求出各粒子的適應值，若當前粒子的適應度小于該粒子最佳位置的適應度，則用[Zl]替代[Pl；][Pg]取所有粒子中適應度最小的最佳位子。

Step3：根據式（5），式（6）更新粒子群的速度及位置，并根據Metropolis準則決定是否接受新值。

Step4：若[fit（U，P（k）g）-fit（U，P（k-1）g）<ε]或[k>kP，]則進入下一步。否則轉入Step2且[k=k+1]。

Step5：進行退火操作[T=dec?T]且令[k=0]。

Step6：若[i>kS，]則進入下一步；否則轉入Step2且[i=i+1]。

Step7：得到最小有效值對應的隸屬度矩陣，根據最大隸屬度原則得到分割圖像。

此方法在分割圖像時用粒子群算法的速度和位置公式改變聚類中心，并用模擬退火算法的Metropolis準則來判斷是否接受新的聚類中心，使得該方法能夠以一定的概率跳出局部極值，從而達到全局最優值。

3.2 自適應的SAPSOFCM方法

雖然SAPSOFCM算法解決了模糊C均值聚類易陷入局部極值的缺點，但仍然需要預先給出聚類數。人們在給出聚類數時，往往憑借經驗，有時并不能得到很好的分割結果。若在SAPSOFCM算法中引入有效性準則函數，則該算法能夠自適應地找到最佳聚類數。

首先確定聚類數[c]的范圍，因為圖像最少要分成兩類，最多分割成最大灰度值的根號，所以取[cmin=2，cmax=15。]然后在[c]取不同值的情況下調用SAPSOFCM方法分別對圖像進行聚類，求出不同聚類數條件下的聚類中心值及其對應的隸屬度矩陣。最后調用式（8）求出不同聚類數對應的有效值。最小有效值對應的聚類數即為最佳聚類數。

通過有效性準則函數確定最優聚類數，本文選取文獻[13]提出的[VWSJ]函數進行仿真實驗，其定義如下：

式中：[Pg=（Pgj）1×c]表示聚類中心向量；[Pgj]是第[j]個聚類中心；上標[S]表示樣本空間[X]的維度；[xpj]表示數據[xj]的第[p]維值；[σ（X）p]表示樣本集[X]的第[p]維數據方差，在本文中[X]是一維數據空間，即[S=1]。當[VWSJ（U，Pg，c）]達到最小值時，說明分類的效果最好。

3.3 方法步驟

綜上，本文方法的總體步驟如下：

4 實驗結果

本實驗的測試環境為CPU酷睿2.5 GHz，內存8 GB，用Matlab 2012a編程實現。在合成圖像和Berkeley大學數據庫中的圖像進行對比實驗，以驗證本文方法在圖像分割中的效果。

其中，初始參數設置為[c1=1.9，][c1=1.8，][w=0.7，][N=30，][T0=5 000，]dec=0.9。

圖1是對仿真圖像的實驗，以驗證本文方法能否找到最佳聚類數。圖1a）和圖1c）是待分割圖像，都包含5個區域，圖1a）中5個區域的灰度值有較明顯的差異，但圖1c）中上面2個區域和中間圓形區域的灰度值非常接近。使用本文方法對圖1a）和圖1c）進行分割，其結果如圖1b）和圖1d）所示。從結果中可以看出，本文方法能自動檢測出圖中的5個區域，能夠在未知聚類數的情況下自適應地得到最佳聚類數。

為驗證本文方法的效果，選擇經典的Camera和Berkeley大學圖像庫中一張自然圖像176039進行測試。分別用本文方法，PSOFCM和FCM方法對這些圖像分割3次。

圖2，圖3顯示了不同方法在各個圖像上的3次分割結果。其中第1行是原始待分割圖像，第2行～第4行分別是本文方法，PSOFCM方法以及FCM方法得到的3次分割結果。

從圖中可以看出，由PSOFCM方法和FCM方法得到的3個分割結果差異較大，且大部分分割結果不符合實際需求。而本文方法所得的分割結果符合人類視覺系統的特點，且3次分割結果非常接近。這些結果表明本文方法的分割結果非常穩定。

表1給出了不同方法在各個圖像上運行3次所得的目標函數值，其中最優值用粗體標出。從表中可以看出，由本文方法所得的分割結果所對應的目標函數值最小，且3次都能達到最小。

5 結 論

鑒于FCM方法進行圖像分割時有對初始值敏感易陷入局部極值且需要事先給出聚類數的缺陷，本文提出了基于模擬退火粒子群算法的自適應FCM方法。首先使用粒子群算法的速度公式和位置公式來更新聚類中心，加強算法的全局搜索能力，提高收斂速度；然后以模擬退火準則來判斷是否為新的聚類中心，使得該方法能夠以一定的概率接受惡化解，從而跳出局部極值的陷阱達到全局最優解；最后通過有效性準則函數來計算不同聚類數下的有效值，最小有效值所對應的聚類數則為最佳聚類數。通過合成圖像的實驗結果表明，本文方法能夠在未知聚類數的情況下自適應地尋找最佳聚類數；對自然圖像的分割結果表明，本文方法能夠達到全局最優并且具有很好的穩定性。該方法具有一定的實用價值。

參考文獻

[1] JUMB Vijay， SOHANI Mandar， SHRIVAS Avinash. Color image segmentation using k?means clustering and Otsu′s adaptive thresholding [J]. International journal of innovative technology and exploring engineering， 2014， 3（9）： 72?76.

[2] LIU Yi， MU Caihong， KOU Weidong， et al. Modified particle swarm optimization?based multilevel thresholding for image segmentation [J]. Methodologies and application， 2015， 19（5）： 1311?1327.

[3] KUMAR Kalyan， SASMITA Jena， SAROJANANDA Mishra. Edge detection of satellite images： a comparative study [J]. International journal of innovative science， engineering & technology， 2015， 2（3）： 75?79.

[4] DOLLAR P， ZITNICK C L. Fast edge detection using structured forests [J]. IEEE transactions on pattern analysis and machine intelligence， 2015， 37（8）： 1558?1570.

[5] ROUHI Rahimeh， JAFARI Mehdi， KASAEI Shohreh， et al. Benign and malignant breast tumors classification based on region growing and CNN segmentation [J]. Expert systems with applications， 2015（42）： 990?1002.

[6] ZHAO Yuqian， WANG Xiaohong， WANG Xiaofang， et al. Re?tinal vessels segmentation based on level set and region growing [J]. Pattern recognition， 2014， 47（7）： 2437?2446.

[7] ZHANG Xiaodong， JIA Fucang， LUO Suhuai， et al. A marker?based watershed method for X?ray image segmentation [J]. Computer methods and programs in biomedicine， 2014， 113（3）： 894?903.

[8] ZHANG Wenlu， LI Rongjian， DENG Houtao， et al. Deep convolutional neural networks for multi?modality isointense infant brain image segmentation [J]. Neuro image， 2015， 108： 214?224.

[9] 陳曦，李春月，李峰，等.基于PSO的模糊C?均值聚類算法的圖像分割[J].計算機工程與應用，2008，44（18）：181?182.

CHEN Xi， LI Chunyue， LI Feng， et a1. Image segmentation based on PSO and fuzzy C?means clustering algorithm [J]. Computer engineering and applications， 2008， 44（18）： 181?182.

[10] 周鮮成，申群太.基于空間鄰域信息的模糊聚類圖像分割[J].武漢理工大學學報，2009，31（1）：102?105.

ZHOU Xiancheng， SHEN Quntai. Fuzzy C?means clustering algorithm based on spatial information for image segmentation [J]. Journal of Wuhan University of Technology， 2009， 31（1）： 102?105.

[11] BEZDEK J C. Pattern recognition with objection function algorithms [M]. New York： Plenum Press， 1981.

[12] XIE X L， BENI G. A validity measure for fuzzy clustering [J]. IEEE transactions on pattern analysis & machine intelligence， 1991， 13（8）： 841? 847.

[13] SUN H J， WANG S G， JIANG Q S. FCM?based model selection algorithms for determing the number of cluster [J]. Pattern recognition， 2004， 37（10）： 2027?2037.