SCI论文（www.lunwensci.com）
摘 要：信息化时代,图像分割技术在医学、国土及交通等诸多领域得到广泛应用。K-means 算法具有简单易实现的特 点,是常用的图像分割算法,但它存在对初始值选取敏感等缺点。麻雀搜索算法是新提出一种群体智能算法,该算法在搜索进 度、收敛速度和稳定性等方面性能优越。该文章利用麻雀搜索算法优化传统 K-means 算法的初始值,提出 SSK-means 算法。 实验结果表明,对于给出的四组图像,SSK-means 算法分割结果均优于传统 K-means 算法的分割结果。
关键词： 图像分割,K-means算法,麻雀搜索算法
Design and Implementation of Improved K-means Clustering Image Segmentation Algorithm
HAN Yu1. MENG Junke2. LIU Lina2
(1.Department of Artificial Intelligence,Jinhua Advanced Research Institute, Jinhua Zhejiang 321013;
2.School of Electronic and Information Engineering, Soochow University, Suzhou Jiangsu 215006)
【Abstract】： In the information age, image segmentation has been widely used in many fields, such as medicine, land and transportation . K-means algorithm is simple and easy to implement . It is a commonly used image segmentation algorithm, but it also has some shortcomings, such as sensitivity to the selection of initial values. Sparrow search algorithm is a new swarm intelligence algorithm, which has excellent performance in search progress, convergence speed and stability. This paper uses sparrow search algorithm to optimize the initial value of traditional K-means algorithm, and proposes SSK-means algorithm. The experimental results show that for the given six images, the segmentation results of SSK-means algorithm are better than those of traditional K-means algorithm.
【Key words】： image segmentation;K-means algorithm;sparrow search algorithm
引言
随着计算机科学技术的不断发展,人类进入大数据 时代。在各式各样的数据信息中,图像形式的信息占据 了极大一部分 [1]。然而,获取的图像信息往往只有部分 内容是人们需要的,因此需要对原始图像进行处理,以 提高工作的效率。
图像分割,是指把图像分为若干个特定的、具备 特性的区域,从中提取出所需目标的技术和过程 [2]。图 像分割技术在现实生活中已经得到广泛应用。医生借 助 CT 影像对患者进行诊断、判断病情 [3]。通过分割拍 摄到的遥感图像,可以分析地形地貌、能够辅助检测水土流失,为制定政策提供参考 [4]。从图像中分割出车牌 号,用于监管违反交通规则的车辆,追查肇事司机 [5]。
在信息化的时代,凡是涉及图像提取、测量的任务, 均需要图像分割。可以预见到,图像分割技术势必会得 到更广泛的应用,在人们生活中发挥越来越大的作用。 因此,对于图像分割算法的研究具有十分重要的意义。
聚类与图像分割具有重要的联系, K-means 聚类方 法是基于划分的聚类算法,具有简单易实现的特点 [6]。 但 K-means 算法存在对初始值选取非常敏感、需要事 先设置聚类数目 k、不适用于数据量较大的对象和鲁棒 性较差等问题。对此,诸多研究者提出来多种改进措施。
Hrosik 等结合萤火虫算法,对初值选取进行优 化,通过在医学图像上进行实验,成功实现了效果更 好的分割 [7];Li 等提出结合动态粒子群理论,在分割 质量和效率等方面优化了传统 K-means,且实现了较 好的视觉效果 [8]。Kapoor S 等选择将灰狼优化算法和 K-means 算法相结合,对传统灰狼优化算法进行适当 修改以实现自动聚类,实现了卫星图像分割 [9];针对传 统 K-means 算法初始化以及局部最优的问题,Khrissi L 等结合正余弦算法,优化了传统方法初始值的选取,取得了预期的效果 [10]
针对 K-means 算法对初值较为敏感的问题,该研 究利用麻雀搜索算法的全局搜索能力,产生 K-means 算法的初始中心,优化后的算法被称为 SSK-means 算 法。仿真结果表明, SSK-means 算法在分割精度上有 所提升。
1 K-means 算法简介
1.1 K-means 算法思想
假设原始数据集 X={x1 , x2 , …, xn , } 具有 n 个样本, K-means 算法将数据集划分为 k 个类,不能存在空的 类且各样本只有唯一归属。在每个类中各选择一个数据 点作为初始聚类中心。根据距离划分各个样本,把样本 划分到最近的类中。接着重复之前的过程,更新聚类中 心和样本到聚类中心点的距离,重新分配样本,直到聚 类中心不再发生变化,输出聚类结果。
1.2 算法流程
以下是 K-means 算法具体流程：
Step1：确定分组数量 k;
Step2： 随机选取 k 个点作为初始聚类中心 mi;
Step3： 按照公式 (1) 计算各样本 xi 到聚类中心的 欧氏距离：
Step4：根据距离,把各样本划分到最近的聚类中;
Step5：更新聚类中心 mi ,如式(2)所示：
其中 Ni 是隶属于第 i 个聚类的样本数量。
Step6： 判断聚类中心是否发生变化,若无变化, 则算法终止。否则,转回 Step3.
由此可见, K-means 算法的特点是每次迭代都需 要重新判断各个样本是否被分配到正确的类中。如果分 类结果不满足要求,就进行修正,在所有样本分类修正 后,就认为各个样本被正确地划分到对应类中,再更新聚类中心,开始新一次的迭代。如果初始聚类中心选择 不当,整个流程可能会相当冗长,会产生相当大的计算 量,导致收敛时间长,效率低。
2 SSK-means 算法简介
2.1 麻雀搜索算法理论
麻雀搜索算法 (Sparrow Search Algorithm, SSA) 是受到麻雀的群体行为的启发而提出一种群体智能优化 算法,该算法在搜索进度、收敛速度和稳定性等方面具 有优越性 [11]。原理如下：
麻雀觅食过程中, 可以分成发现者和加入者, 分别 承担不同的责任。发现者的主要职责是找食物,并为其 他个体指示方位;加入者跟随发现者来获得食物。所有 麻雀都会侦查其他麻雀的活动,可能会因为其他麻雀的 活动而随时改变自己的行为。
模仿麻雀种群的这种活动方式,进行函数的最优化 求解。
发现者更新函数如式(3)所示：
式(3) 中, t 为迭代次数; xi(t),j 代表第 t 代第 i 个的 个体在第j 维位置;itermax为最大迭代次数;α 为随机数, 取值范围为 (0.1];Q 为服从标准正态分布的随机数;L
为 1×d 的矩阵,矩阵中元素均为 1;ST 为安全值,取 值范围为 [0.5.1];R2 为预警值,取值范围为 [0.1]。
加入者更新函数如式(4)所示：
式(4) 中, xtworst 为种群中的最差位置; xtp+1 为当前发现者处于的最优位置; A+ = AT (AAT )− 1 , A 为 1×d 的 矩阵,各个元素随机为 1 或 -1.
意识到危险的侦察者个体位置更新方式如式(5)所示：
式(5) 中： xb(t)est 为当前全局最优位置;β 为步长控 制参数;K 为随机数,取值范围为 [-1.1]。fi、fg、fw 分别表示当前个体适应度值、全局最优适应度值、全局最 差适应度值;ε 用于调节分母,防止分母为 0.
具体步骤如下：
Step1：初始化种群数量、迭代次数等参数;
Step2：计算适应度值,并排序;
Step3：根据式 (3) 更新发现者位置;
Step4：根据式 (4) 更新加入者位置;
Step5：根据式 (5) 更新侦察者位置;
Step6：重新计算适应度值,更新所有个体的位置;
Step7： 判断是否满足条件,满足则退出。否则, 重复执行 Step2-Step6.
2.2 SSA 优化 K-means 算法流程
利用 SSA 优化后 K-means 进行图像分割,首先利 用 SSA 的全局搜索能力,产生 K-means 算法的初始中 心;然后利用 K-means 算法进行图像分割,实现对传 统方法的优化,将新算法命名为 SSK-means 算法。
SSA 的适应度函数为 K-means 算法的最小损失函 数,如式 (6) 所示。
具体流程如下：
Step1： 设置麻雀算法初始参数; 把最小损失函数 作为麻雀算法的适应度函数,计算适应度值;
Step2：产生聚类中心;
Step3：根据欧氏距离,对像素进行聚类 ; Step4：将各类像素均值作为新的聚类中心;
Step5： 判断是否满足收敛条件, 一般设置为聚类 中心是否发生变化;若满足,输出结果;若不满足,返 回 Step2;
Step6：结束。
SSK-means 算法流程图如图 1 所示。
3 SSK-means 算法图像分割实验结果
为了验证 SSK-means 在图像分割中的实际效果, 利用 MATLAB 进行实验。选取四组图像进行测试,算 法通用参数如下：最大迭代次数为 50、种群数量为 30、 安全阈值 ST 为 0.6、意识到危险的麻雀数量占 20%。 实验结果如下。
3.1 主观分析
总体而言,传统 K-means 算法分割得到的结果略微 粗糙,而 SSK-means 算法得到的结果更为清晰,在视 觉效果上要优于传统算法。如图 2(a)、图 2(b) 所示,将 其进行对比,改进算法将蘑菇下方的物体分割地更为清 晰。如图 3(a)、图 3(b) 所示,传统算法无法描述远方 的建筑物,改进算法则将其分割出来了。传统方法下, 如图 4(a) 所示中驼峰上的布匹花纹难以区分,图 4(b) 中在一定程度上将它们区分开。如图 5(b)、图 5(c) 所 示,将其进行对比,传统方法分割得到的图像中,房子的轮廓、草地上骑手的影子较为模糊;改进后的算法能 够较为清晰地刻画上述事物。
3.2 客观分析
为了能定量评估优化算法的图像分割的性能,选取 了两种常见的图像分割度量指标峰值信噪比 (Peak Signal to Noise Ratio, PSNR) 和结构相似性指数 (StructuralSimilarity Index,比较。
PSNR 以 dB 为单位测量,如公式 (7) 所示：
其中 L 是最大强度值, MSE 是均方误差,如公式 (8)
所示：
PSNR 值越大,代表分割效果越好。
SSIM 度量描述了两个图像之间的相似性,计算方 法如公式 (9) 所示：
其中µu 和µ小 表示原始图像和分割图像的平均值, σu小 是两图像的协方差,而σ小(2)和σu(2)分别是图像 小 和 u 的 方差。变量 p1 和 p2 用于避免出现零除。最终计算结果 如表 1 所示。
从表 1 可知, 不管是 PSNR 还是 SSIM,SSK-means 算法图像分割在性能上都得到了一定的提升, 实现了更为 优良的分割效果。特别是 cameraman 图像上, PSNR 从 18.7501 增加至 21.3629. 约提高 14%;在 pyramid 图像 上,SSIM 从 0.7678 增加至 0.8286. 约提高 8%。实验结 果表明,改进后算法进行图像分割要优于传统方法,在 性能上有一定的提高。
4 结语
该研究针对 K-means 算法对初值选取较为敏感的 问题,利用麻雀搜索算法优化 K-means 算法,提出SSK-means 算法。经过仿真测试,发现改进后的算法在 分割精度有所提升,实现了对传统 K-means 算法的改进。
接下来,可进一步研究图像数据较大及存在噪声的 情况下,如何继续改进 K-means 算法,以实现更好的 分割效果及更高地运行效率。
参考文献
[1] 杨兵,刘晓芳 .基于模糊隶属度函数的脑图像分割方法[J].计 算机应用与软件,2022.39(4):254-262.
[2] 张文飞,韩建海,郭冰菁,等.改进的分水岭算法在粘连图像分 割中的应用[J].计算机应用与软件,2021.38(6):243-248.
[3] 任侠,胡玉平 .卷积神经网络结合可变模型的MRI图像自动 分割方法[J].计算机应用与软件,2020.37(1):230-236+283.
[4] 张斌,张晓静,赵丙辰,等 .一种改进的DenseASPP网络在遥 感图像分割中的应用[J].计算机应用与软件,2021.38(7):46-52. [5] 顾恭 .一种基于MSER及CNN的车牌文字定位新方法[J].计 算机应用与软件,2021.38(8):206-213+279.
[6] 郭超凡,王旭明,石晨宇,等 .基于改进K-means算法的玉米叶片图像分割[J]. 中北大学学报(自然科学版),2021.42(6):524- 529.
[7] HROSIK R C,TUBA E,DOLICANIN E,et al.Brain Image Segmentation Based on Firefly Algorithm Combined with K-means Clustering[J].Studies in Informatics and Control,2019.28:167-176.
[8] LI H,HE H,WEN Y. Dynamic Par ticle Swarm Optimization and K-means Clustering Algorithm for Image Segmentation[J].Optik,2015.126(24):4817-4822.
[9] KAPOOR S,ZEYA I,SINGHAL C,et al .A Grey Wolf Optimizer Based Automatic Clustering Algorithm for Satellite Image Segmentation[J].Procedia Computer Science, 2017.115:415-422.
[10] KHRISSI L,EL AKKAD N,SATORI H,et al.Clustering Method and Sine Cosine Algorithm for Image Segmentation[J]. Evolutionary Intelligence,2021:1-14.
[11] 薛建凯 .一种新型的群智能优化技术的研究与应用 —麻 雀搜索算法[D].上海:东华大学,2020.
关注SCI论文创作发表，寻求SCI论文修改润色、SCI论文代发表等服务支撑，请锁定SCI论文网！
文章出自SCI论文网转载请注明出处：https://www.lunwensci.com/jisuanjilunwen/53435.html
