分數階粒子群的模糊聚類圖像分割算法研究

王文娜 馬瑜 姜雲騰 羅宇卓

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

關鍵詞： 模糊C?均值聚類; 初始聚類中心; 分數階粒子群; 自適應調整; 步長控制因子; 圖像分割

中圖分類號： TN911.73?34; TP391 ? ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ?文章編號： 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 ?引 ?言

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

針對傳統FCM算法的缺陷，本文利用分數階微積分優化粒子群算法（Particle Swarm Optimization，PSO）[5]改進分數階階次的自適應調整機制并引入步長控制因子，進而優化FCM算法，從而改善FCM算法對初始值較敏感而容易陷入局部極值的缺陷，提高算法的全局尋優能力。

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

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

2 ?全局自適應的分數階粒子群算法

2.1 ?傳統粒子群算法

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

式中：[c1]，[c2]為學習因子;[r1e]，[r2e]為區間[0，1]內的隨機數;[ω]為慣性權重因子;[pie]為個體極值;[pge]為全局極值。粒子的速度、位置通過式（3），式（4）不斷更新，使整個種群不斷逼近全局最優解。

2.2 ?全局自適應分數階粒子群算法

2.2.1 ?分數階粒子群算法

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

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

式中[a]表示分數階次。由式（8）可得，PSO算法中粒子的當前速度由歷史速度綜合決定，當前速度之前的第一次粒子速度對當前速度的影響最大，第二次、第三次的影響程度逐漸降低，且影響大小可由[a]調節。考慮到粒子前一次位置對當前位置的影響，引入影響因子[b]，對PSO算法位置公式進行更新，得：

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

從式（11）可以看出，粒子的當前位置由歷史位置綜合決定，充分利用已有經驗更新當前位置，有利于每個粒子的全局尋優，步長約束因子[1-b]可自適應地控制步長，根據紋理信息實現圖像的精細分割。

2.2.2 ?分數階次[a]自適應調整機制

對于分數階粒子群算法，如果只采用固定的分數階階次，難以達到理想的效果。因此本文采用全局自適應的方式動態調整分數階次，引入進化因子[ρ]：

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

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

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

3 ?分數階粒子群的模糊聚類圖像分割算法

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

1） 初始化聚類數目[s]，模糊加權指數[m]，粒子群種群規模[N]，最大迭代次數max_iter，最優解改變量閾值TE，慣性因子[ω=1]，學習因子[c1]，[c2]等參數。

2） 計算圖像的梯度均值與方差。即根據式（15）調整分數階次[a]與步長控制因子[1-b]。

3） 根據編碼規則隨機生成初始種群，每個粒子對應一組聚類中心。設置各粒子的[pie]為初始位置，[pge]為種群的初始最優位置。

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

5） 計算各粒子的適應度值。若該值大于[pie]對應的適應值，則更新該粒子的最優位置;若當前[pie]對應的適應度值大于[pge]，則用[pie]更新[pge]。

6） 若當前的迭代次數[i]達到max_iter，迭代或最優解改變量小于閾值TE，得到適應度值最大的粒子所對應的編碼串，進入步驟7）;否則返回步驟4）。

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

4 ?實驗結果與分析

4.1 ?分割結果

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

圖1 ?Lena圖像分割結果

圖2 ?Cameraman圖像分割結果

圖3 ?Hurricane Andrew圖像分割結果

4.2 ?分割精度

本文在評價算法分割精度時，采用的標準是統一度量標準參數，即參數[u]。該參數由Sahoo P K等人首次提出，并由Maitra等人首次用于圖像分割質量評價[11]。參數[u]的表達式如下：

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

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

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

4.3 ?收斂速度

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

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

表2 ?三種算法收斂迭代次數比較

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

5 ?結 ?語

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

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

參考文獻

[1] 文傳軍，詹永照，柯佳.廣義均衡模糊C均值聚類算法[J].系統工程理論與實踐，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] 魏晶茹.基于分數階粒子群的Otsu圖像分割算法研究[D].銀川：寧夏大學，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] 郭通，蘭巨龍，李玉峰，等.自適應的分數階達爾文粒子群優化算法[J].通信學報，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].江西理工大學學報，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.