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

陸振宇 夏志巍 盧亞敏 黃現(xiàn)云

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

關(guān)鍵詞： 自適應(yīng)圖像分割； 模擬退火算法； 粒子群算法； 模糊C均值； 聚類中心； 全局最優(yōu)

中圖分類號(hào)： TN911.73?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

圖像分割是根據(jù)一定的準(zhǔn)則把圖像分割成幾個(gè)互不重疊且各具特色的區(qū)域。目前圖像分割方法主要有：基于閾值的分割方法，如最大類間方差的自適應(yīng)閾值分割[1]、基于粒子群優(yōu)化的多級(jí)閾值分割[2]；基于邊緣檢測(cè)的分割方法，如拉普拉斯算子[3]、結(jié)構(gòu)化森林[4]；基于區(qū)域生長(zhǎng)和分裂合并的分割方法，如區(qū)域生長(zhǎng)與神經(jīng)網(wǎng)絡(luò)相結(jié)合的方法[5]、水平集與區(qū)域生長(zhǎng)相結(jié)合的方法[6]；結(jié)合特定理論的分割方法，如基于分水嶺的標(biāo)號(hào)法[7]、深度卷積神經(jīng)網(wǎng)絡(luò)方法[8]。

聚類分割方法屬于區(qū)域分割方法，它是一種無監(jiān)督的統(tǒng)計(jì)方法，在圖像分割領(lǐng)域應(yīng)用非常廣泛。FCM分割方法具有程序?qū)崿F(xiàn)簡(jiǎn)單、不需要人為干預(yù)等方面的優(yōu)勢(shì)，但傳統(tǒng)的FCM算法在求解目標(biāo)函數(shù)時(shí)采用最速下降法，易使得迭代過程陷入局部最優(yōu)解。此外，對(duì)圖像進(jìn)行分割前必須預(yù)先給出圖像的聚類個(gè)數(shù)，可擴(kuò)展性較差。

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

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

1 FCM算法

FCM方法是將樣本空間[X={x1，x2，…，xn}]的樣本點(diǎn)分成[c]個(gè)類別， 其目標(biāo)函數(shù)為：

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

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

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

2 PSOFCM算法

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

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

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

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

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

3 本文方法

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

3.1 改進(jìn)的模擬退火粒子群與FCM的融合（SAPSOFCM）

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

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

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

這樣粒子的適應(yīng)度會(huì)偶爾向增加的方向發(fā)展，有利于跳出局部極小區(qū)域。隨著假想溫度的降低，系統(tǒng)活動(dòng)性降低，最終以概率1穩(wěn)定在全局最優(yōu)值。

SAPSOFCM方法步驟如下：

Step1：初始化參數(shù)，對(duì)初始溫度[T0、]溫度下降系數(shù)dec、群體規(guī)模[N、]學(xué)習(xí)因子[c1，c2、]慣性系數(shù)[w]等賦初值，粒子群的最大迭代次數(shù)為[kP，]模擬退火的最大迭代次數(shù)為[kS]。隨機(jī)產(chǎn)生[N]個(gè)初始位置，設(shè)[k=1，][i=1]。

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

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

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

Step5：進(jìn)行退火操作[T=dec?T]且令[k=0]。

Step6：若[i>kS，]則進(jìn)入下一步；否則轉(zhuǎn)入Step2且[i=i+1]。

Step7：得到最小有效值對(duì)應(yīng)的隸屬度矩陣，根據(jù)最大隸屬度原則得到分割圖像。

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

3.2 自適應(yīng)的SAPSOFCM方法

雖然SAPSOFCM算法解決了模糊C均值聚類易陷入局部極值的缺點(diǎn)，但仍然需要預(yù)先給出聚類數(shù)。人們?cè)诮o出聚類數(shù)時(shí)，往往憑借經(jīng)驗(yàn)，有時(shí)并不能得到很好的分割結(jié)果。若在SAPSOFCM算法中引入有效性準(zhǔn)則函數(shù)，則該算法能夠自適應(yīng)地找到最佳聚類數(shù)。

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

通過有效性準(zhǔn)則函數(shù)確定最優(yōu)聚類數(shù)，本文選取文獻(xiàn)[13]提出的[VWSJ]函數(shù)進(jìn)行仿真實(shí)驗(yàn)，其定義如下：

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

3.3 方法步驟

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

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

本實(shí)驗(yàn)的測(cè)試環(huán)境為CPU酷睿2.5 GHz，內(nèi)存8 GB，用Matlab 2012a編程實(shí)現(xiàn)。在合成圖像和Berkeley大學(xué)數(shù)據(jù)庫中的圖像進(jìn)行對(duì)比實(shí)驗(yàn)，以驗(yàn)證本文方法在圖像分割中的效果。

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

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

為驗(yàn)證本文方法的效果，選擇經(jīng)典的Camera和Berkeley大學(xué)圖像庫中一張自然圖像176039進(jìn)行測(cè)試。分別用本文方法，PSOFCM和FCM方法對(duì)這些圖像分割3次。

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

從圖中可以看出，由PSOFCM方法和FCM方法得到的3個(gè)分割結(jié)果差異較大，且大部分分割結(jié)果不符合實(shí)際需求。而本文方法所得的分割結(jié)果符合人類視覺系統(tǒng)的特點(diǎn)，且3次分割結(jié)果非常接近。這些結(jié)果表明本文方法的分割結(jié)果非常穩(wěn)定。

表1給出了不同方法在各個(gè)圖像上運(yùn)行3次所得的目標(biāo)函數(shù)值，其中最優(yōu)值用粗體標(biāo)出。從表中可以看出，由本文方法所得的分割結(jié)果所對(duì)應(yīng)的目標(biāo)函數(shù)值最小，且3次都能達(dá)到最小。

5 結(jié) 論

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

參考文獻(xiàn)

[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].計(jì)算機(jī)工程與應(yīng)用，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].武漢理工大學(xué)學(xué)報(bào)，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.