基于動態(tài)粒子群優(yōu)化與K-means聚類的圖像分割算法

李立軍 張曉光

摘 ?要： 為了解決K?means聚類算法圖像分割質(zhì)量過度依賴于初始聚類中心選取，且易于陷入局部最優(yōu)解等問題，提出一種基于動態(tài)粒子群優(yōu)化（DPSO）與K?means聚類的圖像分割算法（DPSOK）。通過動態(tài)調(diào)整慣性系數(shù)與學習因子來增強PSO算法的性能;然后計算粒子群適應度方差，找準切換至K?means算法時機;隨后，將DPSO輸出結(jié)果用來初始化K?means聚類中心，使其收斂至全局最優(yōu)解;最后，通過最小化目標函數(shù)的多次迭代，使K?means的聚類中心不斷更新，直到收斂。實驗結(jié)果表明，DPSOK能有效提高K?means的全局搜索能力，在圖像分割中它比K?means，PSO獲得了更好的分割效果，且與粒子群優(yōu)化和K?means算法相比， DPSOK算法具有更高的分割質(zhì)量與效率。

關(guān)鍵詞： 圖像分割; 動態(tài)粒子群優(yōu)化; K?means聚類; 適應度方差; 聚類算法; DPSOK

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

Abstract： An image segmentation algorithm based on dynamic particle swarm optimization and K?means clustering （DPSOK） is proposed to resolve the problems that the image segmentation quality of K?means clustering algorithm overly relies on the selection of initial clustering center， and it is easy for the algorithm to fall into the local optimal solution. The performance of the particle swarm optimization （PSO） algorithm is enhanced by dynamically adjusting the inertia coefficient and the learning factor. The variance of the particle swarm adaptability is calculated， and the timing of switching to the K?means algorithm is captured. The output results of dynamic particle swarm optimization （DPSO） are used to initialize the K?means clustering center and enable it to converge to the global optimal solution. The K?means clustering center is updated constantly until reaching convergence by means of multiple iterations of the minimized objective function. The experimental results show that the DPSOK can effectively improve the global search capability of K?means， obtain a better segmentation effect than K?means and the PSO in image segmentation， and has higher segmentation quality and efficiency in comparison with the particle swarm optimization and K?means algorithm.

Keywords： image segmentation; dynamic particle swarm optimization; K?means clustering; fitness variance; clustering algorithm; DPSOK

0 ?引 ?言

K?means原理簡單、計算速率高，已廣泛應用于圖像分割領(lǐng)域[1?3]。 但其也存在以下幾個缺點[4]：K?means必須在算法初始化時給出聚類數(shù)k值;K?means對初始聚類中心選取要求很高;K?means容易收斂到局部最優(yōu)解，將導致其錯過全局最優(yōu)解。

為了克服這些缺點，研究人員提出改進的K?means算法。如Chen提出基于層次的猶豫模糊K?means聚類算法[5]，穆瑞輝提出了一種基于粒子群優(yōu)化的模糊K?means目標分類算法 [6]，Siddiqui提出一種增強型移動K?means聚類算法 [7]。但是，這些改進的算法的復雜度較高。因此，需要更進一步的研究來解決K?means的問題。另外，也有部分學者利用PSO算法[8?10]實現(xiàn)圖像分割，但是PSO技術(shù)也存在著局部搜索能力較差、搜索精度不高并且容易陷入局部極值等缺點[9?10]。

因PSO具有強大的全局優(yōu)化能力，K?means具有優(yōu)異的局部搜索能力，所以有研究人員試圖將PSO與K?means結(jié)合起來以得到一個更好的混合算法。例如：班俊碩提出了基于PSO與K?means聚類的混合算法[11]，這種算法的主要思想是：所有粒子的初始化由K?means完成，聚類由PSO實現(xiàn)。近年來，研究人員將PSO與K?means聚類組合主要有以下三種主要方式：K?means+ PSO;K?means+ PSO + K?means;PSO + K?means。

如Gao證明了PSO + K?means算法優(yōu)于其他兩種方法[12]。劉桂紅等使用PSO + K?means混合算法來改進全局優(yōu)化能力[13]，Shi將其應用于YCbCr彩色空間中的棉花圖像分割 [14]，Avanija使用它來恢復語義網(wǎng)中相關(guān)文檔等[15]，PSO + K?means算法得到了一些研究人員的肯定。為了便于表達，本文將文獻[13?15]中提到的這種混合聚類算法簡稱為PSOK（Particle Swarm Optimization and K?means）。然而，PSO本身存在一些缺點。一方面，很難找到合適的常數(shù)作為PSO的慣性系數(shù);另一方面，很難找到兩個合適的常數(shù)作為PSO的學習因子。不合適的學習因子可能導致粒子在局部極端過渡徘徊，使得最終結(jié)果難以收斂或過早收斂到局部最小值。將PSO和K?means進行組合，將會導致算法計算效率較低或數(shù)據(jù)表現(xiàn)不佳。所以，巧妙地結(jié)合PSO與K?means各自優(yōu)點，將其用于圖像分割領(lǐng)域，近年來已成為一個研究熱點。

受PSOK的啟發(fā)，本文提出的DPSOK（Dynamic Particle Swarm Optimization and K?means）算法是一種基于DPSO和K?means聚類的圖像分割算法。與PSOK不同，DPSOK采用動態(tài)慣性系數(shù)和學習因子來計算粒子速度，故其具有平衡優(yōu)化能力，可獲得令人滿意的分割效果。最后，測試了所提算法的分割性能。

3.3 ?定量分析

DPSOK相對于PSOK更好，究其原因在于有動態(tài)學習因子的DPSO明顯優(yōu)于PSO。為了證明該觀點，本文采用3種標準測試函數(shù)共同評估DPSO和PSO各自性能。測試結(jié)果見表1。

在表1中，Sphere是一個單峰函數(shù)。它在[（x1，x2，…，xn）=（0，0，…，0）]處只有一個最小值點。Griewank在[xi=±kπi（i=1，2，…，n;k=1，2，…，n）]處有很多局部最小值點。Schaffer的全局最小值在（0，0）處。因Schaffer在點（0，0）附近不穩(wěn)定，故Schaffer難以實現(xiàn)全局優(yōu)化。使用這3個標準測試函數(shù)對DPSO和PSO分別進行多次測試。使用這3種標準測試函數(shù)測試的迭代結(jié)果見圖4。其中圖4a）～圖4c）分別為Sphere，Griewank，Schaffer函數(shù)測試PSO和DPSO的迭代結(jié)果。

從圖4a）可以看出，在100次迭代過程中，兩種算法都能很快地接近最優(yōu)解，并且兩種算法之間的差異很小。主要原因在于Sphere是一個簡單的單峰函數(shù)，很容易尋找到極值。從圖4b）可知， DPSO與PSO雖均未收斂于全局最優(yōu)解，但很明顯DPSO相對于PSO更接近全局最優(yōu)解，而PSO收斂于局部最優(yōu)解。從圖4c）可知，兩種算法均可接近最優(yōu)解，但當收斂到全局最優(yōu)時，明顯DPSO比PSO更快?？梢?，DPSOK在圖像分割中實現(xiàn)了所期望的效果。

與K?means算法相比，DPSOK的分割圖像質(zhì)量得到了顯著提高，僅效率有些降低，是因為利用PSO算法在圖像分割初期的全局優(yōu)化能力來提升DPSOK的全局搜索能力。與PSOK相比，DPSOK的效率和分割質(zhì)量均得到了提升，原因是DPSOK使用動態(tài)慣性系數(shù)和動態(tài)學習因子，提高了其優(yōu)化能力。

4 ?結(jié) ?語

本文提出基于動態(tài)粒子群優(yōu)化與K?means聚類的混合算法，該算法通過使用動態(tài)慣性系數(shù)和動態(tài)學習因子來提升其優(yōu)化能力，可獲得優(yōu)異的圖像分割效果。實驗結(jié)果表明，DPSOK算法不僅保留了K?means快速收斂的優(yōu)點，而且還克服了其易于收斂到局部最優(yōu)解的缺點。與PSOK算法相比，DPSOK在圖像分割效率和質(zhì)量方面具有更大的優(yōu)勢。

參考文獻

[1] 吉長東，李相澤，敖國政.基于全局K?means算法的超像素分割方法[J].沈陽大學學報（自然科學版），2017，29（3）：212?216.

JI Changdong， LI Xiangze， AO Guozheng. Superpixel segmentation method based on global K?means [J]. Journal of Shenyang University （Natural science）， 2017， 29（3）： 212?216.

[2] 伍育紅.聚類算法綜述[J].計算機科學，2015，42（z1）：491?499.

WU Yuhong. General overview on clustering algorithms [J]. Computer science， 2015， 42（S1）： 491?499.

[3] MEDEIROS R S， SCHARCANSKI J， WONG A. Image segmentation via multi?scale stochastic regional texture appearance models [J]. Computer vision and image understanding， 2016， 142（C）： 23?36.

[4] FENG Yuncong， ZHAO Haiying， LI Xiongfei.， et al A multi?scale 3D Otsu thresholding algorithm for medical image segmentation [J]. Digital signal processing， 2016， 60： 186?199.

[5] CHEN Na， XU Zeshui， XIA Meimei. Hierarchical hesitant fuzzy K?means clustering algorithm [J]. Applied mathematics： a journal of Chinese universities， 2014， 29 （1）： 1?17.

[6] 穆瑞輝，苗國義.基于粒子群優(yōu)化的模糊K?means目標分類算法[J].計算機測量與控制，2013，21（5）：1266?1268.

MU Ruihui， MIAO Guoyi. Algorithm for goal classification based on particle swarm optimization and fuzzy K?means [J]. Computer measurement & control， 2013， 21（5）： 1266?1268.

[7] SIDDIQUI F U， ISA N A M. Enhanced moving K?means （EMKM） algorithm for image segmentation [J]. IEEE transactions on consumer electronics， 2015， 57（2）： 833?841.

[8] 黃山，李眾，李飛，等.基于改進粒子群和自適應濾波的快速模糊聚類圖像分割[J].計算機測量與控制，2016，24（4）：171?173.

HUANG Shan， LI Zhong， LI Fei， et al. Image segmentation of fast fuzzy clustering based on improved particle swarm optimization and adaptive filtering [J]. Computer measurement & control， 2016， 24（4）： 171?173.

[9] DENG M H， LI Z C， ZHU S P. The agriculture vision image segmentation algorithm based on improved quantum?behaved particle swarm optimization [J]. Applied mechanics & materials， 2015， 713?715： 1947?1950.

[10] GAO H， PUN C M， KWONG S. An efficient image segmentation method based on a hybrid particle swarm algorithm with learning strategy [J]. Information sciences， 2016， 369： 500?521.

[11] 班俊碩，賴惠成，林憲峰，等.改進PSO與K均值聚類膚色分割的人臉檢測算法[J].激光雜志，2017，38（2）：82?86.

BAN Junshuo， LAI Huicheng， LIN Xianfeng， et al. Human face detection algorithm for skin color segmentation using improved PSO and K?means clustering [J]. Laser journal， 2017， 38（2）： 82?86.

[12] GAO S， YANG J Y. Swarm intelligence algorithm and applications [M]. Beijing： China Water & Power Press， 2006.

[13] 劉桂紅，趙亮，孫勁光，等.一種改進粒子群優(yōu)化算法的Otsu圖像閾值分割方法[J].計算機科學，2016，43（3）：309?312.

LIU Guihong， ZHAO Liang， SUN Jinguang， et al. Ostu image threshold segmentation method based on improved particle swarm optimization [J]. Computer science， 2016， 43（3）： 309?312.

[14] SHI Hao， LAI Huicheng， QIN Xizhong. Image segmentation algorithm of cotton based on PSO and K?means hybrid clustering [J]. Computer engineering & applications， 2013， 49（21）： 226?229.

[15] AVANIJA J， RAMAR K. A hybrid approach using PSO and K?means for semantic clustering of web documents [J]. Journal of web engineering， 2013， 12（3/4）： 249?264.