1、SOFTWARE2022软 件第 43 卷 第 12 期2022 年Vol.43,No.12基金项目：金华高等研究院院设科研项目(Q202205)作者简介：韩煜（1996）,男,硕士研究生,助教,研究方向：不确定系统分析、优化算法；孟峻可（2001）,男,本科,研究方向：图像分割；刘丽娜（1985）,女,博士研究生,副教授,研究方向：数据挖掘。改进的 K-means 聚类图像分割算法设计与实现韩煜1 孟峻可2 刘丽娜2（1.金华高等研究院人工智能研究所，浙江金华 321013；.苏州大学电子信息学院，江苏苏州 215006）摘要：信息化时代,图像分割技术在医学、国土及交通等诸多领域得到广泛应用
2、。K-means 算法具有简单易实现的特点,是常用的图像分割算法,但它存在对初始值选取敏感等缺点。麻雀搜索算法是新提出一种群体智能算法,该算法在搜索进度、收敛速度和稳定性等方面性能优越。该文章利用麻雀搜索算法优化传统 K-means 算法的初始值,提出 SSK-means 算法。实验结果表明,对于给出的四组图像,SSK-means 算法分割结果均优于传统 K-means 算法的分割结果。关键词：图像分割；K-means 算法；麻雀搜索算法中图分类号：TP3文献标识码：ADOI：10.3969/j.issn.1003-6970.2022.12.004本文著录格式：韩煜,孟峻可,刘丽娜.改进的K-
3、means聚类图像分割算法设计与实现J.软件,2022,43(12):015-018+055Design and Implementation of Improved K-means Clustering Image Segmentation AlgorithmHAN Yu1,MENG Junke2,LIU Lina2(1.Department of Artificial Intelligence,Jinhua Advanced Research Institute,Jinhua Zhejiang 321013;2.School of Electronic and Information En
4、gineering,Soochow University,Suzhou Jiangsu 215006)【Abstract】：Intheinformationage,imagesegmentationhasbeenwidelyusedinmanyfields,suchasmedicine,landandtransportation.K-meansalgorithmissimpleandeasytoimplement.Itisacommonlyusedimagesegmentationalgorithm,butitalsohassomeshortcomings,suchassensitivityt
5、otheselectionofinitialvalues.Sparrowsearchalgorithmisanewswarmintelligencealgorithm,whichhasexcellentperformanceinsearchprogress,convergencespeedandstability.ThispaperusessparrowsearchalgorithmtooptimizetheinitialvalueoftraditionalK-meansalgorithm,andproposesSSK-meansalgorithm.Theexperimentalresults
6、showthatforthegivensiximages,thesegmentationresultsofSSK-meansalgorithmarebetterthanthoseoftraditionalK-meansalgorithm.【Key words】：imagesegmentation;K-meansalgorithm;sparrowsearchalgorithm基金项目论文0 引言随着计算机科学技术的不断发展,人类进入大数据时代。在各式各样的数据信息中,图像形式的信息占据了极大一部分1。然而,获取的图像信息往往只有部分内容是人们需要的,因此需要对原始图像进行处理,以提高工作的效率。
7、图像分割,是指把图像分为若干个特定的、具备特性的区域,从中提取出所需目标的技术和过程2。图像分割技术在现实生活中已经得到广泛应用。医生借助 CT 影像对患者进行诊断、判断病情3。通过分割拍摄到的遥感图像,可以分析地形地貌、能够辅助检测水土流失,为制定政策提供参考4。从图像中分割出车牌号,用于监管违反交通规则的车辆,追查肇事司机5。在信息化的时代,凡是涉及图像提取、测量的任务,均需要图像分割。可以预见到,图像分割技术势必会得到更广泛的应用,在人们生活中发挥越来越大的作用。因此,对于图像分割算法的研究具有十分重要的意义。聚类与图像分割具有重要的联系,K-means 聚类方法是基于划分的聚类算法,具
8、有简单易实现的特点6。但 K-means 算法存在对初始值选取非常敏感、需要事先设置聚类数目 k、不适用于数据量较大的对象和鲁棒性较差等问题。对此,诸多研究者提出来多种改进措施。16软 件第 43 卷 第 12 期SOFTWAREHrosik 等结合萤火虫算法,对初值选取进行优化,通过在医学图像上进行实验,成功实现了效果更好的分割7；Li 等提出结合动态粒子群理论,在分割质量和效率等方面优化了传统 K-means,且实现了较好的视觉效果8。KapoorS 等选择将灰狼优化算法和K-means 算法相结合,对传统灰狼优化算法进行适当修改以实现自动聚类,实现了卫星图像分割9；针对传统 K-mean
9、s 算法初始化以及局部最优的问题,KhrissiL 等结合正余弦算法,优化了传统方法初始值的选取,取得了预期的效果10。针对 K-means 算法对初值较为敏感的问题,该研究利用麻雀搜索算法的全局搜索能力,产生 K-means算法的初始中心,优化后的算法被称为 SSK-means 算法。仿真结果表明,SSK-means 算法在分割精度上有所提升。1 K-means 算法简介1.1 K-means 算法思想假设原始数据集12=,nXx xx具有 n 个样本,K-means 算法将数据集划分为 k 个类,不能存在空的类且各样本只有唯一归属。在每个类中各选择一个数据点作为初始聚类中心。根据距离划分各
10、个样本,把样本划分到最近的类中。接着重复之前的过程,更新聚类中心和样本到聚类中心点的距离,重新分配样本,直到聚类中心不再发生变化,输出聚类结果。1.2 算法流程以下是 K-means 算法具体流程：Step1：确定分组数量 k；Step2：随机选取 k 个点作为初始聚类中心 mi；Step3：按照公式(1)计算各样本 xi到聚类中心的欧氏距离：211iNkijiijJxm=(1)Step4：根据距离,把各样本划分到最近的聚类中；Step5：更新聚类中心 mi,如式（2）所示：11,1,2,iNiijjmx ikN=(2)其中 Ni是隶属于第 i 个聚类的样本数量。Step6：判断聚类中心是否发
11、生变化,若无变化,则算法终止。否则,转回 Step3。由此可见,K-means 算法的特点是每次迭代都需要重新判断各个样本是否被分配到正确的类中。如果分类结果不满足要求,就进行修正,在所有样本分类修正后,就认为各个样本被正确地划分到对应类中,再更新聚类中心,开始新一次的迭代。如果初始聚类中心选择不当,整个流程可能会相当冗长,会产生相当大的计算量,导致收敛时间长,效率低。2 SSK-means 算法简介2.1 麻雀搜索算法理论麻雀搜索算法(SparrowSearchAlgorithm,SSA)是受到麻雀的群体行为的启发而提出一种群体智能优化算法,该算法在搜索进度、收敛速度和稳定性等方面具有优越性
12、11。原理如下：麻雀觅食过程中,可以分成发现者和加入者,分别承担不同的责任。发现者的主要职责是找食物,并为其他个体指示方位；加入者跟随发现者来获得食物。所有麻雀都会侦查其他麻雀的活动,可能会因为其他麻雀的活动而随时改变自己的行为。模仿麻雀种群的这种活动方式,进行函数的最优化求解。发现者更新函数如式（3）所示：,21max,2exp,+|=|+|(4)式（4）中,tworstx为种群中的最差位置；1tpx+为当前发现者处于的最优位置；1()TTAAAA+=,A 为 1d 的矩阵,各个元素随机为 1 或-1。意识到危险的侦察者个体位置更新方式如式（5）所示：(),1,tttbesti jbesti
13、gttti ji jworstti jigiwxxxffxxxxKffff+|=|+=|+|(5)式（5）中：tbestx为当前全局最优位置；为步长控制参数；K 为随机数,取值范围为-1,1。fi、fg、fw分别表示当前个体适应度值、全局最优适应度值、全局最差适应度值；用于调节分母,防止分母为 0。具体步骤如下：Step1：初始化种群数量、迭代次数等参数；17韩煜孟峻可刘丽娜：改进的 K-means 聚类图像分割算法设计与实现Step2：计算适应度值,并排序；Step3：根据式(3)更新发现者位置；Step4：根据式(4)更新加入者位置；Step5：根据式(5)更新侦察者位置；Step6：重新
14、计算适应度值,更新所有个体的位置；Step7：判断是否满足条件,满足则退出。否则,重复执行 Step2-Step6。2.2 SSA 优化 K-means 算法流程利用 SSA 优化后 K-means 进行图像分割,首先利用 SSA 的全局搜索能力,产生 K-means 算法的初始中心；然后利用 K-means 算法进行图像分割,实现对传统方法的优化,将新算法命名为 SSK-means 算法。SSA 的适应度函数为 K-means 算法的最小损失函数,如式(6)所示。211iNkijiijfitxm=(6)具体流程如下：Step1：设置麻雀算法初始参数；把最小损失函数作为麻雀算法的适应度函数,计
15、算适应度值；Step2：产生聚类中心；Step3：根据欧氏距离,对像素进行聚类；Step4：将各类像素均值作为新的聚类中心；Step5：判断是否满足收敛条件,一般设置为聚类中心是否发生变化；若满足,输出结果；若不满足,返回 Step2；Step6：结束。SSK-means 算法流程图如图 1 所示。3 SSK-means 算法图像分割实验结果为了验证 SSK-means 在图像分割中的实际效果,利用 MATLAB 进行实验。选取四组图像进行测试,算法通用参数如下：最大迭代次数为 50、种群数量为 30、安全阈值 ST 为 0.6、意识到危险的麻雀数量占 20%。实验结果如下。3.1 主观分析总
16、体而言,传统 K-means 算法分割得到的结果略微粗糙,而 SSK-means 算法得到的结果更为清晰,在视觉效果上要优于传统算法。如图 2(a)、图 2(b)所示,将其进行对比,改进算法将蘑菇下方的物体分割地更为清晰。如图 3(a)、图 3(b)所示,传统算法无法描述远方的建筑物,改进算法则将其分割出来了。传统方法下,如图 4(a)所示中驼峰上的布匹花纹难以区分,图 4(b)中在一定程度上将它们区分开。如图 5(b)、图 5(c)所示,将其进行对比,传统方法分割得到的图像中,房子开始设置初始参数，计算适应度值；产生聚类中心对像素进行聚类更新聚类中心是否满足收敛条件结束是否图 1 SSK-means 算法流程图Fig.1 Flow chart of SSK-means algorithm图 2 图像 mushroom 及其分割结果Fig.2 Image mushroom and its segmentation results(a)K-means(a)K-means(b)SSK-means(b)SSK-means图 3 图像 cameraman 及其分割结果Fig.3 Image c