分?jǐn)?shù)階粒子群的模糊聚類圖像分割算法研究

王文娜 馬瑜 姜雲(yún)騰 羅宇卓

摘 ?要： 針對模糊C?均值聚類算法易受初始聚類中心的影響而陷入局部極值的缺陷，提出基于分?jǐn)?shù)階粒子群的模糊聚類圖像分割算法。利用分?jǐn)?shù)階微積分容易跳出局部極值的固有優(yōu)勢，將其引入粒子群的速度、位置更新進(jìn)程，同時(shí)改進(jìn)分?jǐn)?shù)階階次的自適應(yīng)調(diào)整機(jī)制并引入步長控制因子。實(shí)驗(yàn)結(jié)果表明，該算法與傳統(tǒng)算法相比，具有更高的分割精度與更快的收斂速度。

關(guān)鍵詞： 模糊C?均值聚類; 初始聚類中心; 分?jǐn)?shù)階粒子群; 自適應(yīng)調(diào)整; 步長控制因子; 圖像分割

中圖分類號(hào)： TN911.73?34; TP391 ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2019）11?0059?05

Abstract： Since the fuzzy C?means clustering algorithm influenced by initial clustering center is easy to fall into local extremum， a fuzzy clustering image segmentation algorithm based on fractional particle swarm optimization is proposed. The inherent advantage of fractional calculus which is easy to jump out of local extremum is introduced into the velocity and position updating process of the traditional particle swarm. The fractional?order adaptive adjustment mechanism is improved， and the step?size control factor is introduced into the algorithm. The experimental results show that the proposed algorithm has higher segmentation accuracy and faster convergence rate than traditional algorithms.

Keywords： fuzzy C?means clustering; initial clustering center; fractional particle swarm; adaptive adjustment; step?size control factor; image segmentation

0 ?引 ?言

圖像分割是進(jìn)行圖像分析的重要基礎(chǔ)和關(guān)鍵步驟。模糊C?均值聚類（Fuzzy C?Means Algorithm，F(xiàn)CM）[1]由于其簡潔性、良好的處理圖像信息的多解性和不確定性，而受到了廣泛的應(yīng)用。但FCM算法易受初始聚類中心的影響，使其迭代尋優(yōu)過程容易陷入局部最優(yōu)。為了克服上述缺點(diǎn)，近年來不少學(xué)者做出了很多努力。文獻(xiàn)[2]提出增量核模糊聚類，通過優(yōu)化FCM的初始聚類中心，為每個(gè)數(shù)據(jù)塊提高聚類結(jié)果的質(zhì)量，但該算法并未提高FCM算法的穩(wěn)定性。文獻(xiàn)[3]利用改進(jìn)的遺傳算法優(yōu)化FCM，改善了FCM對初始聚類中心敏感的缺點(diǎn)，但分割效果與分割時(shí)間有待提高。文獻(xiàn)[4]提出利用帶約束的支持向量機(jī)優(yōu)化FCM，求解多目標(biāo)問題，提高了噪聲識(shí)別能力，但算法結(jié)果易受初始化質(zhì)心的影響，容易陷入局部最優(yōu)。

針對傳統(tǒng)FCM算法的缺陷，本文利用分?jǐn)?shù)階微積分優(yōu)化粒子群算法（Particle Swarm Optimization，PSO）[5]改進(jìn)分?jǐn)?shù)階階次的自適應(yīng)調(diào)整機(jī)制并引入步長控制因子，進(jìn)而優(yōu)化FCM算法，從而改善FCM算法對初始值較敏感而容易陷入局部極值的缺陷，提高算法的全局尋優(yōu)能力。

1 ?模糊C?均值聚類算法

FCM算法最早于1974年提出，利用其無監(jiān)督性及模糊性分割圖像，可以有效地解決圖像分割過程中的不確定性以及減少外部因素對圖像分割效果的影響。設(shè)[x=（x1，x2，…，xn）]為空間中樣本數(shù)為[n]的樣本子集，將其劃分為[s]個(gè)簇類， FCM的目標(biāo)函數(shù)一般形式如下：

2 ?全局自適應(yīng)的分?jǐn)?shù)階粒子群算法

2.1 ?傳統(tǒng)粒子群算法

假設(shè)在[E]維空間中，有粒子數(shù)為[N]的群體，[xi=（xi1，][xi2，…，xie）]表示第[i]個(gè)粒子在該向量空間中的位置，[vi=][（vi1，vi2，…，vie）]表示第[i]個(gè)粒子的速度，[pi=（pi1，pi2，…，pie）]表示第[i]個(gè)粒子的最優(yōu)位置，[pg=][（pg1，pg2，…，pge）]表示粒子群體的最優(yōu)位置。粒子的速度、位置更新公式如下：

式中：[c1]，[c2]為學(xué)習(xí)因子;[r1e]，[r2e]為區(qū)間[0，1]內(nèi)的隨機(jī)數(shù);[ω]為慣性權(quán)重因子;[pie]為個(gè)體極值;[pge]為全局極值。粒子的速度、位置通過式（3），式（4）不斷更新，使整個(gè)種群不斷逼近全局最優(yōu)解。

2.2 ?全局自適應(yīng)分?jǐn)?shù)階粒子群算法

2.2.1 ?分?jǐn)?shù)階粒子群算法

PSO算法存在的一個(gè)缺陷是容易陷入局部最優(yōu)[6?8]， 本文將分?jǐn)?shù)階微積分引入PSO算法中，提出分?jǐn)?shù)階粒子群算法（IMFPSO）。由于分?jǐn)?shù)階微積分固有的優(yōu)勢，基于分?jǐn)?shù)階微積分的學(xué)習(xí)訓(xùn)練算法能夠很容易地跳出局部極值，使得PSO算法的粒子尋優(yōu)軌跡更適合全局最優(yōu)的情況。

假設(shè)一元信號(hào)[f（s）]為連續(xù)信號(hào)，[s]的持續(xù)時(shí)間為[[a，t]]，把[s]按[h=1]劃分為[n]份，則[n=（t-a）h=t-a]。當(dāng)[v>0]時(shí)，Grunwald?Letnikov定義（簡稱G?L定義）下[f（s）]的表達(dá)式為：

式中[a]表示分?jǐn)?shù)階次。由式（8）可得，PSO算法中粒子的當(dāng)前速度由歷史速度綜合決定，當(dāng)前速度之前的第一次粒子速度對當(dāng)前速度的影響最大，第二次、第三次的影響程度逐漸降低，且影響大小可由[a]調(diào)節(jié)?？紤]到粒子前一次位置對當(dāng)前位置的影響，引入影響因子[b]，對PSO算法位置公式進(jìn)行更新，得：

式（10）表明，對位置的加權(quán)相當(dāng)于對速度的約束，速度約束因子[1-b]可以控制當(dāng)前粒子速度的步長，防止粒子因步長過快而陷入局部極值，影響分割精度。為合理地控制步長，將[b]的大小設(shè)為[a]，即步長控制因子大小等于[1-a]。在紋理信息較豐富的部分或圖像邊緣，[1-b]較小，粒子移動(dòng)的步長變小，可以實(shí)現(xiàn)該部分較精細(xì)的分割。同粒子群速度的更新公式，將式（10）引入分?jǐn)?shù)階微積分，得PSO算法的位置更新公式：

從式（11）可以看出，粒子的當(dāng)前位置由歷史位置綜合決定，充分利用已有經(jīng)驗(yàn)更新當(dāng)前位置，有利于每個(gè)粒子的全局尋優(yōu)，步長約束因子[1-b]可自適應(yīng)地控制步長，根據(jù)紋理信息實(shí)現(xiàn)圖像的精細(xì)分割。

2.2.2 ?分?jǐn)?shù)階次[a]自適應(yīng)調(diào)整機(jī)制

對于分?jǐn)?shù)階粒子群算法，如果只采用固定的分?jǐn)?shù)階階次，難以達(dá)到理想的效果。因此本文采用全局自適應(yīng)的方式動(dòng)態(tài)調(diào)整分?jǐn)?shù)階次，引入進(jìn)化因子[ρ]：

式中：[k1]，[k2]為加權(quán)系數(shù)，且滿足[k1+k2=1];[κ]表示圖像的梯度;[ζ]表示方差。[κ]與[ζ]可以很好地反映圖像的紋理信息與紋理復(fù)雜程度，在圖像紋理信息豐富、紋理復(fù)雜的地方或邊緣部分，梯度與方差較大，在圖像分割過程中，取較大的分?jǐn)?shù)階次， 可保持分割圖像較好的紋理特性。梯度與方差的計(jì)算公式如下：

式中：[M（s，t）]為梯度幅值的均值，[M1]為[M（s，t）]的最大值，[M2]為[M（s，t）]的最小值。[Q（s，t）]為像素的局部方差。由此可知，[ρ]的取值范圍為[0，1]，而分?jǐn)?shù)階次在[0.5，0.8]范圍內(nèi)算法能夠獲得更快的收斂速度[9]，故構(gòu)造新的分?jǐn)?shù)階次動(dòng)態(tài)調(diào)整函數(shù)如下：

[ρ]越大，[a]越大，即在梯度值與局部方差較大處，取得較大的分?jǐn)?shù)階次，反之取較小的分?jǐn)?shù)階次，故可以較好地保持圖像的紋理特性，提高圖像的分割精度。

3 ?分?jǐn)?shù)階粒子群的模糊聚類圖像分割算法

FCM在進(jìn)行圖像分割時(shí)，算法性能過分依賴于初始聚類中心而容易陷入局部最優(yōu)解，致使分割精度降低。因此本文采用分?jǐn)?shù)階粒子群算法優(yōu)化FCM的初始聚類中心，提出分?jǐn)?shù)階粒子群的模糊聚類圖像分割算法（IMFPSO?FCM）。利用FPSO強(qiáng)大的全局搜索能力，彌補(bǔ)FCM的不足。算法步驟如下：

1） 初始化聚類數(shù)目[s]，模糊加權(quán)指數(shù)[m]，粒子群種群規(guī)模[N]，最大迭代次數(shù)max_iter，最優(yōu)解改變量閾值TE，慣性因子[ω=1]，學(xué)習(xí)因子[c1]，[c2]等參數(shù)。

2） 計(jì)算圖像的梯度均值與方差。即根據(jù)式（15）調(diào)整分?jǐn)?shù)階次[a]與步長控制因子[1-b]。

3） 根據(jù)編碼規(guī)則隨機(jī)生成初始種群，每個(gè)粒子對應(yīng)一組聚類中心。設(shè)置各粒子的[pie]為初始位置，[pge]為種群的初始最優(yōu)位置。

4） 根據(jù)式（8）更新各粒子的速度，根據(jù)式（11）不斷更新粒子的位置。

5） 計(jì)算各粒子的適應(yīng)度值。若該值大于[pie]對應(yīng)的適應(yīng)值，則更新該粒子的最優(yōu)位置;若當(dāng)前[pie]對應(yīng)的適應(yīng)度值大于[pge]，則用[pie]更新[pge]。

6） 若當(dāng)前的迭代次數(shù)[i]達(dá)到max_iter，迭代或最優(yōu)解改變量小于閾值TE，得到適應(yīng)度值最大的粒子所對應(yīng)的編碼串，進(jìn)入步驟7）;否則返回步驟4）。

7） 根據(jù)步驟6）返回的編碼串得到FCM逼近全局最優(yōu)的初始聚類中心。執(zhí)行FCM，得到圖像的最佳分割閾值。

4 ?實(shí)驗(yàn)結(jié)果與分析

4.1 ?分割結(jié)果

為驗(yàn)證本文算法的有效性，分割灰度圖像的準(zhǔn)確性以及算法的收斂速度，實(shí)驗(yàn)分別利用Lena圖像、Cameraman圖像與Hurricane Andrew圖像進(jìn)行處理。實(shí)驗(yàn)前，對原圖像加椒鹽噪聲，并利用中值濾波進(jìn)行去噪處理，得到一幅去噪后仍含有噪聲的模糊圖像，分別用PSO?FCM、文獻(xiàn)[10]中的IMPSO?FCM算法與本文IMFPSO?FCM算法進(jìn)行處理，得到的分割結(jié)果如圖1～圖3所示。

圖1 ?Lena圖像分割結(jié)果

圖2 ?Cameraman圖像分割結(jié)果

圖3 ?Hurricane Andrew圖像分割結(jié)果

4.2 ?分割精度

本文在評(píng)價(jià)算法分割精度時(shí)，采用的標(biāo)準(zhǔn)是統(tǒng)一度量標(biāo)準(zhǔn)參數(shù)，即參數(shù)[u]。該參數(shù)由Sahoo P K等人首次提出，并由Maitra等人首次用于圖像分割質(zhì)量評(píng)價(jià)[11]。參數(shù)[u]的表達(dá)式如下：

式中：[Mj]表示第[j]個(gè)分割區(qū)域;[xmax]，[xmin]分別為像素的最大值與最小值;[hj]表示第[j]個(gè)區(qū)域中像素的平均灰度值。Sahoo等人指出，[u]值越大分割質(zhì)量越好，分割精度越高;反之，分割質(zhì)量越差，分割精度越低。

分割圖像[u]值表如表1所示。從表1可以看出，在閾值圖像分割時(shí)，IMFPSO?FCM的度量標(biāo)準(zhǔn)[u]值最大，可以分別取到0.980 5，0.992 4，0.985 9，算法分割性能最好，可見本文算法的分割精度優(yōu)于其他算法。

表1 ?分割圖像[u]值表

4.3 ?收斂速度

為驗(yàn)證本文算法的收斂速度優(yōu)于其他算法，以Lena圖像為例給出聚類中心收斂情況圖，如圖4所示。3幅圖像的聚類中心隨迭代次數(shù)的收斂情況見表2。

圖4 ?Lena圖像聚類中心收斂情況對比圖

表2 ?三種算法收斂迭代次數(shù)比較

綜合圖4與表2可以看出，本文算法分別在約25次，20次，30次迭代時(shí)，聚類中心達(dá)到最優(yōu)，收斂速度最快;IMPSO?FCM雖然分割精度有所提高，但算法的收斂速度較PSO?FCM變慢。可見，本文算法在確保分割精度的同時(shí)，具有較快的收斂速度。

5 ?結(jié) ?語

在聚類過程中FCM算法容易受到初始聚類中心的影響而陷入局部極值，導(dǎo)致分割結(jié)果不精確。本文提出的IMFPSO?FCM算法，通過在粒子群算法中引入步長控制因子，并與分?jǐn)?shù)階微積分結(jié)合，根據(jù)圖像的像素信息，構(gòu)造新的分?jǐn)?shù)階階次函數(shù)，實(shí)現(xiàn)[a]的全局自適應(yīng)調(diào)整，以此對FCM算法的初始聚類中心進(jìn)行優(yōu)化，提高FCM算法的全局尋優(yōu)能力，避免FCM算法易受初始聚類中心的影響而陷入極值。通過實(shí)驗(yàn)證明，本文算法IMFPSO?FCM與PSO?FCM，IMPSO?FCM相比，能保證較好的分割精度，且收斂速度加快。但本文算法僅僅局限在對灰度圖像的分割，將算法應(yīng)用到彩色圖像與三維圖像是下一步的研究方向。

注：本文通訊作者為馬瑜。

參考文獻(xiàn)

[1] 文傳軍，詹永照，柯佳.廣義均衡模糊C均值聚類算法[J].系統(tǒng)工程理論與實(shí)踐，2012，32（12）：2751?2755.

WEN Chuanjun， ZHAN Yongzhao， KE Jia. Generalized equilibrium fuzzy C?means clustering algorithm [J]. System enginee?ring theory and practice， 2012， 32（12）： 2751?2755.

[2] JIAO R， LIU S， WEN W， et al. Incremental kernel fuzzy C?means with optimizing cluster center initialization and delivery [J]. Kybernetes， 2016， 45（8）： 1273?1291.

[3] DING Y， FU X. Kernel?based fuzzy C?means clustering algorithm based on genetic algorithm [J]. Neurocomputing， 2016， 188： 233?238.

[4] SABZEKAR M， NAGHIBZADEH M. Fuzzy C?means improvement using relaxed constraints support vector machines [J]. Applied soft computing Journal， 2013， 13（2）： 881?890.

[5] 魏晶茹.基于分?jǐn)?shù)階粒子群的Otsu圖像分割算法研究[D].銀川：寧夏大學(xué)，2017.

WEI Jingru. Otsu image segmentation algorithm based on fractional order particle swarm optimization [D]. Yinchuan： Ningxia University， 2017.

[6] YANG Q， TIAN J， SI W. An improved particle swarm optimization based on difference equation analysis [J]. Journal of difference equations & applications， 2016， 181（6）： 1?18.

[7] WANG H， SUN H， LI C， et al. Diversity enhanced particle swarm optimization with neighborhood search [J]. Information sciences， 2013（2）： 119?135.

[8] CHENG R， JIN Y. A social learning particle swarm optimization algorithm for scalable optimization [J]. Information sciences， 2015（6）： 43?60.

[9] 郭通，蘭巨龍，李玉峰，等.自適應(yīng)的分?jǐn)?shù)階達(dá)爾文粒子群優(yōu)化算法[J].通信學(xué)報(bào)，2014，35（4）：130?140.

GUO Tong， LAN Julong， LI Yufeng， et al. Adaptive fractional Darwinian particle swarm optimization algorithm [J]. Journal of communications， 2014， 35（4）： 130?140.

[10] MAITRA M， CHATTERJEE A. A hybrid cooperative?comprehensive learning based PSO algorithm for image segmentation using multilevel thresholding [M]. Pergamon： Pergamon Press Inc.， 2008.

[11] 劉建生，喬尚平，匡奕群.基于差分粒子群和模糊聚類的彩色圖像分割算法[J].江西理工大學(xué)學(xué)報(bào)，2013（5）：66?71.

LIU Jiansheng， QIAO Shangping， KUANG Yiqun. Color image segmentation algorithm based on difference particle swarm optimization and fuzzy clustering [J]. Journal of Jiangxi University of Science and Technology， 2013（5）： 66?71.