基于AHLO与K均值聚类的图像分割算法*

图像分割是指将图像中感兴趣的区域从复杂的背景中提取出来的一种图像处理技术.目前，图像分割的方法多种多样，如基于图像边缘的分割方法，基于阈值的分割方法，基于区域的分割方法等[1-6].基于K-均值聚类方法常用于图像分割，如Moftah等[7]利用K-均值算法对医疗CT图像进行分割取得了不错的效果；Jumb等[8]提出了K-均值与阈值分割法结合的图像分割法；徐黎明等[9]利用K-均值算法对杨梅采摘图像进行分割，取得了良好的效果.但是K-均值聚类的方法本身存在着受初始聚类中心影响、容易陷入局部最优的缺点[10-11].

针对K-均值算法的这些缺点，一些学者提出了改进算法.Tzortzis等[12]提出了一种改进K-均值算法，将权重引入聚类中，使得簇类方差变小，分类效果提高.一些学者也尝试将群智能算法与K-均值算法结合，提高K-均值算法的搜索性能.如Li和Younus等[13-14]将粒子群算法与K-均值算法结合，提高了K-均值算法的稳定性，并将其应用于图像分割及检索.

本文针对K-means存在受初始聚类中心影响大，容易陷入局部最优的缺点，将新型群智能算法自适应人类学习优化算法(AHLO)与K均值算法相结合，利用AHLO算法全局搜索能力强的特点，输出逼近全局最优聚类中心的初始聚类中心，再利用K-均值算法进行局部搜索.将本文算法应用到图像分割可提高K-均值算法分割图像的稳定性.

1 K-means算法

K-means算法常用于图像分割，传统的K-means算法基于欧式距离划分，优化目标函数E为样本点到所属簇类中心的距离平方和，即聚类误差平方和，优化目标函数表达式为

式中：xij为第i类第j个样本；Ni为第i类的样本个数；ci为第i类的聚类中心；k为聚类数目.K-means算法经过反复迭代，可计算新的聚类中心，即

当E最小时，迭代结束.对K-means聚类算法分析可知，聚类结果的好坏受初始聚类中心的影响比较大，如果初始聚类中心点在选取时包含相同的初始点，则会出现错误.

2 自适应人类学习优化算法

Wang等[15-17]于2015年提出一种全局优化算法，即自适应人类学习优化算法(adaptive human learning optimization，AHLO)，该算法是一种群智能算法，通过模拟人类的学习行为机制对问题进行寻优，其具有设置参数少，收敛速度快，全局寻优能力强，不易陷入局部最小值的优点.自适应人类学习优化算法包含三种学习算子，分别为随机学习算子、个体学习算子、社会学习算子.

自适应人类学习优化算法采用二进制编码，每个个体用一串二进制码表示.每个个体随机初始化为包含“0”和“1”的二进制码，该二进制码代表人类想要学习的知识.根据人类的学习过程，人类在刚开始学习知识，由于没有任何的先验知识，人类的初始学习过程一般是一种随机学习过程.随机学习算子可以表示为

式中，rand()为0～1之间的随机数.

当人类学习到一定程度时，人类具有一定的先验知识，此时人类的学习过程会根据以往的经验知识来避免错误，提高自身学习能力.用IKD(individual knowledge database)来表示人的知识库，其表达式为

虽然人类可以通过自己学习知识来解决问题，但是当问题比较复杂时，人类学习过程比较漫长，需要花较长时间才能解决问题.但是当很多人一起学习一起解决问题时，可以极大提高效率，很多人的学习经验就是社会知识库.社会知识库SKD(social knowledge database)的表达式为

个体整个学习过程包括随机学习算子、个体学习算子、社会学习算子，整个学习过程可表示为

式中：pr为随机学习的概率；pi-pr为个体学习的概率；1-pi为社会学习的概率.pi、pr这两个参数对于平衡三种算子的学习起着至关重要的作用，对算法性能的影响较大.根据不同问题调节pi、pr这两个参数值.为了提高搜索效率，减少参数设置的工作量，采用如下自适应策略，即

式中：prmin、pimin为pr、pi的最小值；prmax、pimax为pr、pi的最大值；Ite为当前迭代次数；Itemax为最大迭代次数.

3 自适应人类学习优化与K-means聚类算法

3.1 聚类策略与适应度函数

为了充分利用AHLO算法和K-means算法各自优势，首先利用AHLO算法进行全局搜索，此时AHLO算法可以很大程度上靠近全局解子空间，在AHLO算法达到收敛后，利用K-means算法进行局部搜索，达到聚类的目的.对于AHLO算法，每个粒子的适应度值利用聚类误差平方和计算.设有n个粒子，fi为第i个粒子的适应度值，fAvg为当前粒子适应度的平均值，其表达式为

粒子适应度的方差反应了AHLO算法的收敛度，其表达式为

在AHLO算法迭代过程中，粒子适应度值会趋于平稳，这时方差会稳定在一个确定的区域.所以当方差趋于确定区域时，可认为AHLO算法已经趋于最优解附近，此时利用K-means算法进行局部寻优.

3.2 算法流程

本文算法流程如图1所示，具体步骤如下：1)初始化，设定人类学习种群数量和知识范围；2)计算适应度值，保存个体知识库和社会学习知识库；3)进行随机学习、个体学习、社会学习；4)根据适应度值更新个体学习知识库和社会学习知识库；5)计算平均适应度值和适应度方差；6)判断适应度方差值是否大于阈值，如果没有则重复步骤2)～5)过程；7)将AHLO算法的输出作为K-means算法的初始聚类中心；8)计算聚类误差平方和；9)更新聚类中心；10)判断是否达到迭代次数，如果没有则重复步骤8)、9)；11)输出聚类中心.

4 实验仿真与分析

实验采用CPU为Intel(R) Core 2 CPU@2.30 GHz，内存为4 GB的计算机，操作系统为Windows 7，编译软件为Matlab 2014a.

4.1 AHLO-Kmeans算法性能测试

本文利用UCI标准数据集中的Iris、Balance-scale、Glass数据对算法性能进行测试，其数据参数如表1所示.AHLO-Kmeans算法参数设定为：种群规模为30，最大迭代次数为100，编码长度为8位.粒子群算法参数设定为：种群规模为30，c1=2.1，c2=2.0，最大迭代次数为100.Iris中聚类数目k=3，Balance-scale中聚类数目k=3；Glass中聚类数目k=6.Kmeans、PSO-Kmeans，AHLO-Kmeans对数据集聚类的结果如表2所示.

从表2中可以看出，Kmeans算法由于受初始聚类中心的影响，聚类的标准差较大，稳定性较差.PSO-Kmeans算法利用PSO算法改善了初始聚类中心的选择，改善了Kmeans均值算法的稳定性，但是相比AHLO-Kmeans算法，PSO-Kmeans算法的标准差仍然比本文算法的标准差大，这是因为AHLO算法相比PSO算法，全局寻优能力更强，更加逼近聚类中心，而PSO算法有时会陷入局部最优，全局搜索能力相对较差.

4.2 图像分割

4.2.1 灰度图像分割

本文利用Lena、camera、baboon、lake这四幅经典灰度图像测试本文算法的聚类效果，分别对图像进行聚类个数为k=2，k=5，k=7，k=9的聚类分割，AHLO-Kmeans算法的分割效果如图2所示.从左往右依次为原始图，聚类个数为2、5、7、9的图像分割结果.为了衡量Kmeans算法、PSO-Kmeans算法、AHLO-Kmeans算法对图像分割的好坏，用这3种算法对上述4幅经典图像进行分割，实验次数为20次，利用得到的平均峰值信噪比(PSNR)作为评价标准衡量各算法的好坏.实验结果数据如表3所示.

从图2的分割图可以看出，AHLO-Kmeans算法的分割效果较好，边缘清晰，各部分灰度区域分割比较均匀.从表3中的数据可以看出，在聚类个数比较少时，如k=2时，三种算法分割得到的PSNR值基本相同，但是随着聚类个数的增加，Kmeans算法受初始聚类中心影响比较大，Kmeans算法分割得到的PSNR值最小，PSO-Kmeans对初始聚类中心的选择有一定的改善，分割得到的PSNR值次之，而AHLO-Kmeans算法分割得到的PSNR值最大，表明本文算法对Kmeans算法初始聚类中心选择改进效果最好，具有更好的聚类效果.

4.2.2 彩色图像分割

K-means算法常应用于农业图像的分割中，本文利用AHLO-Kmeans算法对杨梅图像、荔枝图像、苹果图像、草莓图像进行分割，其中聚类个数为3，验证本文算法的实用性.首先将图像由RGB空间转换到Lab空间，然后对a、b分量进行聚类分割，分割效果如图3所示，其中，第一列为原始图像，第二列为分割图像，第三列为提取的水果图像.

从图3的分割图像可以看出，AHLO-Kmeans算法对于彩色图像的分割效果比较好，能够有效地分割出杨梅、荔枝、苹果、草莓，分割轮廓也比较均匀，具有较强的实用性.

5 结论

图像分割技术被广泛应用于机器视觉和计算机视觉领域.本文提出了一种结合自适应人类学习优化与K均值算法的聚类算法.该算法在初始化K均值聚类中心之前，利用自适应人类学习优化算法的全局搜索能力，快速逼近全局最优聚类中心，然后将自适应人类学习优化算法输出的聚类中心作为K均值算法的初始聚类中心进行迭代寻优.将本文算法与传统K均值算法、PSO-Kmeans算法进行对比发现，本文算法稳定性更好，聚类标准差更低，聚类效果更佳.将本文算法应用于灰度图像与彩色图像的分割，获得的PSNR值更高，具有较强的实用价值.

[1]贺振东，王耀南，刘洁，等.基于背景差分的高铁钢轨表面缺陷图像分割 [J].仪器仪表学报，2016，37(3)：640-649.

(HE Zhen-dong，WANG Yao-nan，LIU Jie，et al.Background differencing-based high-speed rail surface defect image segmentation [J].Chinese Journal of Scientific Instrument，2016，37(3)：640-649.)

[2]马英辉，吴一全.基于二维Renyi交叉熵的刀具磨损图像分割 [J].电子测量与仪器学报，2016，30(12)：1869-1876.

(MA Ying-hui，WU Yi-quan.Image segmentation for tool wear based on 2D Renyi cross entropy [J].Journal of Electronic Measurement and Instrument，2016，30(12)：1869-1876.)

[3]夏平，刘小妹，雷帮军，等.基于复小波域树结构化MRF模型的声纳图像分割 [J].仪器仪表学报，2016，37(4)：895-903.

(XIA Ping，LIU Xiao-mei，LEI Bang-jun，et al.Sonar image segmentation based on tree-structured MRF model in complex-wavelet domain [J].Chinese Journal of Scientific Instrument，2016，37(4)：895-903.)

[4]刘琼，史诺，申妙芳.基于区间二型模糊集的农田障碍物分割方法 [J].国外电子测量技术，2016，35(4)：81-84.

(LIU Qiong，SHI Nuo，SHEN Miao-fang.Farmland obstacle image segmentation based on interval type Ⅱ fuzzy set [J].Foreign Electronic Measurement Technology，2016，35(4)：81-84.)

[5]王云烨，李勃，董蓉，等.基于透射率空间与色彩纹理相关性的图像分割 [J].电子测量技术，2015，38(1)：41-46.

(WANG Yun-ye，LI Bo，DONG Rong，et al.An transmittance space and color-texture correlation based graph theoretic image segmentation method [J].Electronic Measurement Technology，2015，38(1)：41-46.)

[6]刘琼，史诺.基于Lab和YUV颜色空间的农田图像分割方法 [J].国外电子测量技术，2015，34(4)：39-41.

(LIU Qiong，SHI Nuo.Farmland image segmentation based on Lab and YUV color spaces [J].Foreign Electronic Measurement Technology，2015，34(4)：39-41.)

[7]Moftah H M，Azar A T，Al-Shammari E T，et al.Adaptive K-means clustering algorithm for MR breast image segmentation [J].Neural Computing and Applications，2014，24(7/8)：1917-1928.

[8]Jumb V，Sohani M，Shrivas A.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.

[9]徐黎明，吕继东.基于同态滤波和K均值聚类算法的杨梅图像分割 [J].农业工程学报，2015，31(14)：202-208.

(XU Li-ming，LÜ Ji-dong.Bayberry image segmentation based on homomorphic filtering and K-means clustering algorithm [J].Transactions of the Chinese Society of Agricultural Engineering，2015，31(14)：202-208.)

[10]Dhanachandra N，Manglem K，Chanu Y J.Image segmentation using K-means clustering algorithm and subtractive clustering algorithm [J].Procedia Computer Science，2015，54：764-771.

[11]Velmurugan T.Performance based analysis between K-means and fuzzy C-means clustering algorithms for connection oriented telecommunication data [J].Applied Soft Computing，2014，19：134-146.

[12]Tzortzis G，Likas A.The minmax K-means clustering algorithm [J].Pattern Recognition，2014，47(7)：2505-2516.

[13]Li H，He H，Wen Y.Dynamic particle swarm optimization and K-means clustering algorithm for image segmentation [J].Optik-International Journal for Light and Electron Optics，2015，126(24)：4817-4822.

[14]Younus Z S，Mohamad D，Saba T，et al.Content-based image retrieval using PSO and K-means clustering algorithm [J].Arabian Journal of Geosciences，2015，8(8)：6211-6224.

[15]Wang L，Ni H Q，Yang R，et al.A simple human learning optimization algorithm [C]//International Conference on Life System Modeling and Simulation and International Conference on Intelligent Computing for Sustainable Energy and Environment.Shanghai，China，2014：56-65.

[16]Wang L，Yang R，Ni H，et al.A human learning optimization algorithm and its application to multi-dimensional knapsack problems [J].Applied Soft Computing，2015，34：736-743.

[17]Wang L，Ni H，Yang R，et al.An adaptive simplified human learning optimization algorithm [J].Information Sciences，2015，320：126-139.