基于动态粒子群优化与K-means聚类的图像分割算法

李立军 张晓光

摘  要： 为了解决K?means聚类算法图像分割质量过度依赖于初始聚类中心选取，且易于陷入局部最优解等问题，提出一种基于动态粒子群优化（DPSO）与K?means聚类的图像分割算法（DPSOK）。通过动态调整惯性系数与学习因子来增强PSO算法的性能;然后计算粒子群适应度方差，找准切换至K?means算法时机;随后，将DPSO输出结果用来初始化K?means聚类中心，使其收敛至全局最优解;最后，通过最小化目标函数的多次迭代，使K?means的聚类中心不断更新，直到收敛。实验结果表明，DPSOK能有效提高K?means的全局搜索能力，在图像分割中它比K?means，PSO获得了更好的分割效果，且与粒子群优化和K?means算法相比， DPSOK算法具有更高的分割质量与效率。

关键词： 图像分割; 动态粒子群优化; 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原理简单、计算速率高，已广泛应用于图像分割领域[1?3]。 但其也存在以下几个缺点[4]：K?means必须在算法初始化时给出聚类数k值;K?means对初始聚类中心选取要求很高;K?means容易收敛到局部最优解，将导致其错过全局最优解。

为了克服这些缺点，研究人员提出改进的K?means算法。如Chen提出基于层次的犹豫模糊K?means聚类算法[5]，穆瑞辉提出了一种基于粒子群优化的模糊K?means目标分类算法 [6]，Siddiqui提出一种增强型移动K?means聚类算法 [7]。但是，这些改进的算法的复杂度较高。因此，需要更进一步的研究来解决K?means的问题。另外，也有部分学者利用PSO算法[8?10]实现图像分割，但是PSO技术也存在着局部搜索能力较差、搜索精度不高并且容易陷入局部极值等缺点[9?10]。

因PSO具有强大的全局优化能力，K?means具有优异的局部搜索能力，所以有研究人员试图将PSO与K?means结合起来以得到一个更好的混合算法。例如：班俊硕提出了基于PSO与K?means聚类的混合算法[11]，这种算法的主要思想是：所有粒子的初始化由K?means完成，聚类由PSO实现。近年来，研究人员将PSO与K?means聚类组合主要有以下三种主要方式：K?means+ PSO;K?means+ PSO + K?means;PSO + K?means。

如Gao证明了PSO + K?means算法优于其他两种方法[12]。刘桂红等使用PSO + K?means混合算法来改进全局优化能力[13]，Shi将其应用于YCbCr彩色空间中的棉花图像分割 [14]，Avanija使用它来恢复语义网中相关文档等[15]，PSO + K?means算法得到了一些研究人员的肯定。为了便于表达，本文将文献[13?15]中提到的这种混合聚类算法简称为PSOK（Particle Swarm Optimization and K?means）。然而，PSO本身存在一些缺点。一方面，很难找到合适的常数作为PSO的惯性系数;另一方面，很难找到两个合适的常数作为PSO的学习因子。不合适的学习因子可能导致粒子在局部极端过渡徘徊，使得最终结果难以收敛或过早收敛到局部最小值。将PSO和K?means进行组合，将会导致算法计算效率较低或数据表现不佳。所以，巧妙地结合PSO与K?means各自优点，将其用于图像分割领域，近年来已成为一个研究热点。

受PSOK的启发，本文提出的DPSOK（Dynamic Particle Swarm Optimization and K?means）算法是一种基于DPSO和K?means聚类的图像分割算法。与PSOK不同，DPSOK采用动态惯性系数和学习因子来计算粒子速度，故其具有平衡优化能力，可获得令人满意的分割效果。最后，测试了所提算法的分割性能。

3.3  定量分析

DPSOK相对于PSOK更好，究其原因在于有动态学习因子的DPSO明显优于PSO。为了证明该观点，本文采用3种标准测试函数共同评估DPSO和PSO各自性能。测试结果见表1。

在表1中，Sphere是一个单峰函数。它在[（x1，x2，…，xn）=（0，0，…，0）]处只有一个最小值点。Griewank在[xi=±kπi（i=1，2，…，n;k=1，2，…，n）]处有很多局部最小值点。Schaffer的全局最小值在（0，0）处。因Schaffer在点（0，0）附近不稳定，故Schaffer难以实现全局优化。使用这3个标准测试函数对DPSO和PSO分别进行多次测试。使用这3种标准测试函数测试的迭代结果见图4。其中图4a）～图4c）分别为Sphere，Griewank，Schaffer函数测试PSO和DPSO的迭代结果。

从图4a）可以看出，在100次迭代过程中，两种算法都能很快地接近最优解，并且两种算法之间的差异很小。主要原因在于Sphere是一个简单的单峰函数，很容易寻找到极值。从图4b）可知， DPSO与PSO虽均未收敛于全局最优解，但很明显DPSO相对于PSO更接近全局最优解，而PSO收敛于局部最优解。从图4c）可知，两种算法均可接近最优解，但当收敛到全局最优时，明显DPSO比PSO更快。可见，DPSOK在图像分割中实现了所期望的效果。

与K?means算法相比，DPSOK的分割图像质量得到了显著提高，仅效率有些降低，是因为利用PSO算法在图像分割初期的全局优化能力来提升DPSOK的全局搜索能力。与PSOK相比，DPSOK的效率和分割质量均得到了提升，原因是DPSOK使用动态惯性系数和动态学习因子，提高了其优化能力。

4  结  语

本文提出基于动态粒子群优化与K?means聚类的混合算法，该算法通过使用动态惯性系数和动态学习因子来提升其优化能力，可获得优异的图像分割效果。实验结果表明，DPSOK算法不仅保留了K?means快速收敛的优点，而且还克服了其易于收敛到局部最优解的缺点。与PSOK算法相比，DPSOK在图像分割效率和质量方面具有更大的优势。

參考文献

[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] 穆瑞輝，苗国义.基于粒子群优化的模糊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] 刘桂红，赵亮，孙劲光，等.一种改进粒子群优化算法的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.