1、152 信息：技术与应用信息记录材料 2022年12月 第23卷第12期 0 引言K-means 作为一种经典的基于划分的聚类算法，它具有操作简单、效率高、局部搜索性能好等优势1。但是传统的K-means算法也存在很多的问题：（1）K值需要预先确定，但在实际中 K 值的选定是非常困难的；（2）K-means 算法中相似度是以欧氏距离来度量的，因此远离群点的存在对算法结果影响较大2。针对这些问题，文献3采用灰度梯度最大熵法从图像中提取特征，再用 K-means 对图像进行分类，达到了很好的图像分割效果；文献4利用遗传算法寻得 K 值，该算法在降低迭代次数的同时提高了准确率。在分析已有的 K-me
2、ans 改进算法的基础上，使用 LBP算子提取图像的纹理特征，再使用遗传算法和 K-means 算法结合的方法对图像进行聚类。将本文算法与 FCM 和经典 K-means 算法进行对比实验。实验结果表明，改进后的K-means 算法的聚类效果优于经典 K-means 算法。1 LBP特征提取局部二值模式5（local binary pattern,LBP）是一种图像纹理提取算法。本文通过 LBP 算子实现图像特征提取的步骤如下：（1）细分区域；（2）将每个区域中心点的灰度值作为阈值，并与周围的 8 个像素进行比较。若周围像素值较大，则被标记为1；否则为 0；（3）计算每个区域的直方图，并进行归
3、一化处理。（4）将步骤（3）得到的所有直方图连接成为一个特征向量，即整幅图的LBP纹理特征向量。LBP值计算如式（1）所示。10(,)()2ppccpcLBP x yS ii=（1）其中，(x,)ccy表示 3*3 邻域的中心元素；ci表示中心像素值，pi表示邻域像素值，()pcS ii是符号函数，即：1,()0,pcpcpciiS iiii|=（2）2 遗传算法遗传算法（genetic algorithm，GA）是一种模仿大自然进化规律（适者生存，不适者淘汰）的算法。该算法的构成要素包括编码、初始化种群、遗传算子（如交叉、变异）、选择策略和停止策略6。首先根据实际问题选择合适的编码方式，并根
4、据问题规模确定种群的规模。然后根据问题设计对应的适应度函数，并设定终止条件。若满足终止条件，则输出结果；否则进行选择、交叉、变异运算。上述流程如图 1 所示。图 1 遗传算法流程图基于 LBP 算子和 GA-K-means 的图像分割算法 王甜甜1，3，史卫亚2，3（1 河南工业大学信息科学与工程技术学院 河南 郑州 450001）（2 河南工业大学人工智能与大数据学院 河南 郑州 450001）（3 河南工业大学粮食信息处理与控制教育部重点实验室 河南 郑州 450001）【摘要】K-means 聚类算法具有简单、快速等优点。但是由于聚类中心的选择严重影响聚类结果，因此在应用中受到限制。遗传
5、算法的全局寻优能力弥补了 K-means 算法的缺陷。首先采用了局部二值模式（LBP）算子来描述图像局部纹理特征，然后将 K-means 算法的局部搜索能力与遗传算法的全局寻优搜索能力相结合。将该算法在猫、狗、海豚等图像中进行实验，实验结果表明本文算法像素精确度达到 95%，取得了较好的分割效果。【关键词】遗传算法；局部二值模式；K-means 算法；图像聚类；聚类中心【中图分类号】TP39 【文献标识码】A 【文章编号】1009-5624（2022）12-0152-03DOI:10.16009/13-1295/tq.2022.12.076 153信息：技术与应用信息记录材料 2022年12月
6、 第23卷第12期 在遗传算法的每个循环中，选择、交叉和变异算子在寻优过程中最为重要：（1）选择：选择是将种群中的某些个体挑选出来用于繁衍下一代种群的新个体。（2）交叉：两个配对的染色体以设定的交叉概率对个体进行交叉操作，其目的是通过交换二者的部分基因，不断产生新的个体；（3）变异：变异是允许每位个体以一个很小的概率改变自身。3 基于遗传算法的k-means 聚类3.1 算法步骤本文算法的基本步骤如下：（1）为了方便后续步骤，将实验所用的图像统一尺寸为 440*300，生成样本集。（2）使用 LBP 算法对样本集进行特征提取。（3）使用遗传算法找到最优的 K 值。（4）利用（3）中的 K 值，
7、使用遗传算法中的初始化找到最优初始聚类中心。（5）使用（3）（4）中的 K 值和初始聚类中心，对数据集进行聚类操作。（6）聚类结束。3.2 实现步骤本文采用基于聚类中心的浮点数编码7，将类别中心点编码为染色体。类内的距离 8 如式（3）所示。2()11inkijiICSijDISxm=（3）其中，k代表类别的个数；im代表第i类的样本均值；()ijx代表第i类的第j个样本；in代表第i类的样本个数。类间的距离如式（4）所示。1()()TiikICDimmmDISm=（4）其中，m代表全部样本的均值向量。适应度函数定义如式（5）所示。平均类内距离越小，类间距离越大，聚类效果越好，适应度函数值越大
8、9。ICDICSDISFDIS=（5）本文采用轮盘赌法10，使个体被选中的概率取决于其对应的适应度的大小，适应度值越大，其参与后代繁殖的概率就越高。4 实验结果本文算法的实验环境为：Windows10 操作系统、Python 语言，系统的硬件环境为 Inter(R)Core(TM)i5-7200U CPU 处理器。本文使用了像素准确率（pixel accuracy，PA）对图像聚类效果进行评估，PA 用来计算被正确分类的像素个数和总像素数之间的比例，其计算公式如式（6）所示。000kiiikkijijppPA=（6）其中，k代表类别总数，ijp代表真实像素类别为i的像素被预测为类别j的总数量；
9、iip代表真实像素为i的像素被预测为类别i的总数量。4.1 特征提取本文首先对图像的尺寸、颜色归一化；然后采用 LBP算法进行特征提取，实验结果如图 2 所示。（a）原图（b）LBP 提取的特征图图 2 特征提取图4.2 实验结果及分析本实验将遗传算子的交叉概率为0.3，变异概率为0.2，迭代次数为 50。由遗传算法的适应度函数定义可知，适应函数值越大，聚类效果越好。在分割 3 幅图像时，迭代次数对应的适应度函数如图 3 所示。从图中可以看出，收敛代数均在 30 40 之间。图 3 遗传算法的收敛曲线不同算法的分割结果如图 4 所示，K-means 对图像边缘的分割性能较差，无法精准识别动物图
10、片的边缘信息；FCM 能够识别边缘信息，但是在细节分割方面效果较差；遗传算法和 K-means 结合能进一步完善对细节的分割性能，但是在纹理复杂的图像中表现不如本文算法。方框中圈出的区域为本文算法优于其他算法的区域。比较可得，本文算法在边缘划分和小区域目标的划分中占有优势。154 信息：技术与应用信息记录材料 2022年12月 第23卷第12期 图 4 不同算法分割实验对比从 PA 的定义可以看出，PA 值越大，图像聚类的效果越好。分析表 1 可得，在分割时间上，本文算法稍长于K-means 算法和 FCM 算法，但是优于没有引入 LBP 算法的GA-K-means 算法。从 PA 的值可得，
11、客观评价指标与主观分析结果一致，表明本文分割结果更接近于基准分割。表 1 分割效果评估算法狗猫海豚PA/%分割时间s PA/%分割时间sPA/%分割时间s经典 K-means0.738.70.8611.40.806.6FCM0.899.10.8910.30.918.4遗传算法+K-means0.929.70.9115.70.9710.6 本文算法 0.9510.50.9213.60.93 9.55 结语本文针对经典 K-means 方法中存在的问题，提出了优化方案。本文的改进在于首先用 LBP 算子对图像进行特征提取，然后再使用改进的 K-means 算法对图像进行分割。仿真实验表明，本文算法
12、优于经典的 K-means 方法和 GA-K-means 算法，但是在运行速度上稍逊于经典的 K-means算法。【参考文献】1LIKAS A,VLASSIS N,J VERBEEK J.The global k-means clustering algorithm J.Pattern Recognit,2003,36(2):451-461.2 樊一康，刘建伟.支持差分隐私保护及离群点消除的并行K-means 算法 J.计算机应用研究，2019，36(6):1776-1781，1787.3SHAN P F.Image segmentation method based on K-mean al
13、gorithm J.J Image Video Proc,2018:81.4 冯永亮，李浩.基于遗传算法的 K-means 聚类改进研究 J.计算机与数字工程，2020，48(8):1831-1834，1839.5 姚立平，潘中良.基于改进的 HOG 和 LBP 算法的人脸识别方法研究 J.光电子技术，2020，40(2):114-118，124.6 谢娟英，王艳娥.最小方差优化初始聚类中心的 K-means 算法 J.计算机工程，2014，40(8):205-211，223.7 孙红艳.用遗传算法优化初始聚类中心的 K-means 算法研究 J.电声技术，2019，43(11):32-33，
14、47.8 卜秋瑾，段隆振，段文影.结合遗传 k 均值改进的密度峰值聚类算法 J.计算机工程与设计，2020，41(4):1012-1016.9 黄松，邱建林.改进的遗传 k-means 算法及其应用 J.计算机工程与设计，2020，41(6):1617-1623.10 梁宇宏，张欣.对遗传算法的轮盘赌选择方式的改进 J.信息技术，2009，33(12):127-129.基金项目：国家自然科学基金(62006071)；河南省科技攻关项目(212102210149)。作者简介：王甜甜（1997），女，河南驻马店，硕士，研究方向：图像分割。【参考文献】1 蒋明炜.北京机械工业自动化研究所：深化 AI
15、 赋能加快新一代信息技术与制造业融合发展 N.中国电子报，2021-05-14.2 熊亚蒙.基于 TensorFlow 的移动终端图像识别方法 J.无线互联科技，2018，15(21):111-112，130.3 史尊魁.共同危险行为与高空抛物之区分 J.武汉大学学报(哲学社会科学版)，2010，63(4):540-544.4 王成，鲁智勇.高空抛物侵权行为探究 J.法学评论，2007，25(2):141-150.5 王国荣，张伟光，杨旭，等.基于图像识别的人体目标检测传感器模块设计 J.哈尔滨师范大学自然科学学报，2020，36(5):53-60.6 李晨.城市居住环境下住户高空抛物行为调查
16、 J.城市问题，2007(11):57-61，66.7ZIVKOVIC Z.Efficient adaptive density estimation per image pixel for the task of background subtractionJ.Pattern Recognit Lett,2006,27(7):773-780.8 刘仲民，何胜皎，胡文瑾，等.基于背景减除法的视频序列运动目标检测 J.计算机应用，2017，37(6):5.9 贺国庆，闫骞，吴潼，等.监控视频关键帧提取过程中帧差参数的研究 J.科技视界，2020(36):36-38.项目基金：2021 年广西壮族自治区级大学生创新创业训练计划项目(桂教高教202146 号 S202111546091，S202111546095)；广西高校中青年教师基础能力提升项目（桂科教研20211 号 2021KY0853）。作者简介：谭超友（2000），男，广西，本科，研究方向：大数据方向。（上接第 151 页）