基于PSO-KMeans快速图像分割算法模型的应用

陈兴志　王代文　刘乃瑶　乐文涛　黄飞翔

摘  要：图像分割是图像识别和计算机视觉至关重要的预处理。文章结合PSO算法搜索全局最优及KMeans算法对选取初始聚类中心的缺陷，使用PSO算法搜索并寻找全局最优，将搜寻值回代到KMeans聚类算法中对图像进行分割。结果表明，基于PSO-KMeans快速图像分割算法模型具有更高的精确度和有效性。PSO算法对KMeans算法的优化作用明显，有效对图片数据进行了分割，进一步优化了KMeans算法对图像分割的时间，提高了算法收敛的速度。

关键词：PSO算法;KMeans算法;PSO-KMeans快速算法;收敛速度;图像分割

中图分类号：TP391.4        文献标识码：A 文章编号：2096-4706（2020）05-0079-04

Application of Fast Image Segmentation Algorithm Model

Based on PSO-KMeans

CHEN Xingzhi，WANG Daiwen，LIU Naiyao，LE Wentao，HUANG Feixiang

（School of Science，Southwest University of Science and Technology，Mianyang  621010，China）

Abstract：Image segmentation is an important preprocessing of image recognition and computer vision. In this paper，PSO algorithm is used to search the global optimum and KMeans algorithm is used to select the initial cluster center. PSO algorithm is used to search and find the global optimum，and the search value is replaced by KMeans clustering algorithm to segment the image. The results show that the fast image segmentation algorithm model based on PSO-KMeans has higher accuracy and effectiveness. PSO algorithm plays an important role in the optimization of KMeans algorithm，effectively segmenting the image data，further optimizing the time of image segmentation of KMeans algorithm，and improving the convergence speed of the algorithm.

Keywords：PSO algorithm;KMeans algorithm;PSO-KMeans fast algorithm;convergence speed;image segmentation

0  引  言

圖像分割是图像识别和计算机视觉至关重要的预处理，在国内外有着众多相关图像分割算法研究，但是目前仍未有一种能够适用于绝大多数图像通用的分割算法，当前国内外对于图像分割相关研究最常用的是聚类算法中的K均值算法，K均值算法需要先选择K个初始类均值，之后将每个像素归入均值离它最近的类，再重新计算出新的类均值，此后迭代执行前面步骤，直到新类与旧类均值之差小于某一阈值。

本文研究内容是西南科技大学大学生创业项目，目的是找到一种能够适用于多数图像的分割算法，该研究以PSO算法与K-Means算法为基础，通过粒子群算法的方式，实现对复杂多线性多维度数据空间的有效计算，进而达到对图像进行分割的目的，此类算法能够应用于多数图像的分割，极大缩短了图像分割速度[1]。

1  基于PSO-KMeans快速图像分割算法模型的建立

1.1  粒子群算法（PSO）

算法原理：

假设在D维的目标搜索空间中，有N个粒子组成一个群落，其中第i个粒子表示为：

Xi=（Xi1，Xi2，…，XiD），i=1，2，…，N

第i个粒子的速度记为：

Vi=（Vi1，Vi2，…ViD），i=1，2，…，N

第i个粒子搜索到的最优位置称为个体极值，记为：

Pbest=（Pi1，Pi2，…，PiD），i=1，2，…N

整个粒子群迄今为止搜索到的最优位置为全局极值，记为：

gbest=（Pg1，Pg2，…，PgD）

在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和位置：

，

其中，C1和C2和为学习因子，也称加速常数，W为惯性因子，rand1和rand2为[0，1]范围内均匀随机数。

1.2  K-means聚类算法

1.2.1  算法思想

K-Means聚类算法是以K为参数，将N个对象分为K个簇，使簇内有较高的相似度，簇间的相似度较低。相似度通常使用欧式距离表示。

1.2.2  欧氏距离

设数据集：

X={Xm|m=1，2，3，…，total}，其中，X中的样本用d个描述属性的A1，A2，…，Ad来表示，并且d个描述属性都是连续性属性。

数据样本Xi=（Xi1，Xi2，…，Xid），Xj=（Xj1，Xj2， …，Xjd），其中Xi1，Xi2，…，Xid和Xj1，Xj2，…，Xjd分别是样本Xi和Xj对应d个描述属性A1，A2，…，Ad的具体取值。

样本Xi和Xj之间的欧氏距离d（xi，xj）为：

d（xi，xj）=[2]。

1.3  基于PSO-KMeans快速图像分割算法模型

1.3.1  算法原理

设在D维的像素矩阵搜索空间中，有N个像素矩阵元素组成一个群落，其中第i个像素矩阵元素表示为D维的向量：

Xi=（Xi1，Xi2，…，XiD），i=1，2，…，N

第i个像素矩阵元素的“飞行”速度也是D维的向量，记为：

Vi=（Vi1，Vi2，…，ViD），i=1，2，…N

第i个像素矩阵元素迄今为止搜索到的最优位置称为个体极值，记为：

Pbest=（Pi1，Pi2，…，PiD），i=1，2，…，N

整个像素矩阵群迄今为止搜索到的最优位置为全局极值，记为：

gbest=（Pg1，Pg2，…，PgD）

在找到这两个最优值时，像素矩阵元素根据如下的公式来更新自己的速度和位置：

通过PSO算法将N个对象分为K个簇，并将其通过迄今为止搜索得到的最优值回代到K-Means算法中作为初始聚类分割中心和初始分割类K，K-Means算法是以K为参数对图像进行分割，使簇内相似度较高，簇间较低。相似度用欧式距离表示。

PSO-KMeans快速图像分割模型算法原理：开始导入原始图像，图像灰度化处理，获取图像像素矩阵，初始化每个像素矩阵元素的速度和位置，计算每个像素矩阵元素的适应值，求出像素矩阵每个元素的个体最优，求解出整个像素矩阵的全局最优质，根据方程对元素粒子的速度进行优化，根据方程对元素粒子的位置进行优化，不满足条件则重新优化粒子速度与位置，满足相关条件则输出分割中心和分割个数K，分配各个数据到距离最近的分割中心，重新计算各个分割中心，不收敛则重新分配距离最近的分割中心，收敛则输出分割结果。

2  模型检验

通过PSO算法、K-Means算法、PSO-KMeans算法，分别对图像进行分割，检验基于PSO-KMeans快速图像分割算法模型的有效性和精准性。得到K-Means算法模型和PSO-KMeans快速分割算法模型的分割参数对比，如表1所示。

三种算法模型的运行时间（单位：ms），K-Means（58），PSO（91），PSO-KMeans（33）。

将K-Means算法模型和PSO-KMeans快速分割算法模型的迭代次数与目标函数值收敛关系进行比较，如图1所示。

由图中和分割结果数据来看，PSO-KMeans快速分割算法模型能够有效地对原始“lena.jpg”图像进行分割，分割的时间有较大的提升。K-Means算法运行耗时58 ms，PSO-KMeans算法运行耗时33 s。且算法实现了更快的收敛，K-Means算法收敛迭代7次，而PSO-KMeans算法收敛只迭代2次。

3  PSO-KMeans快速分割算法模型图像分割应用

针对图像分割应用可参考原始未分割图像“Jobs.jpg”，如图2所示，将基于PSO-KMeans快速分割算法模型图像分割方法应用到该图像的分割上，得到结果如图3所示。K-Means聚类算法模型无法对图像进行准确的分割。

进一步检验本文所建立的基于PSO-KMeans快速分割算法模型的有效性和精准性。

通过对比两种算法模型所能分割的图像像素矩阵大小，256×256图像两者算法都可运行，574×450图像K-Means不可运行，PSO-KMeans可运行。

得到基于PSO-KMeans快速分割算法模型的迭代次数与目标函数值收敛对比，如表2所示。

整理基于PSO-KMeans快速分割算法模型的迭代次数与目标函数值收敛关系，如图4所示。

由图4、表1、表2可知，PSO-KMeans快速分割算法模型能够有效地对原始“Jobs.jpg”图像进行分割，可以分割像素矩阵更大的图像，并且算法收敛到最优只迭代4次。

4  结  论

本文利用建立的基于PSO-KMeans图像分割组合算法模型对图片进行分割处理，并对其进行了结果分析，总结如下：通过检验数据和收敛比较图可知，基于PSO-KMeans图像分割组合算法模型的分割效果明显，算法模型的收敛速度快、收敛次数小，算法模型的运行时间也更快;由图像分割应用，基于PSO-KMeans图像分割组合算法模型精准地实现了对图像的分割。可以分割像素矩阵更大的图像，并且只经过了4次迭代目标函数就收敛到了最优;基于PSO-KMeans快速分割算法模型解决了K-Means聚类算法具有初值选取不稳定、需要提前给出K值等缺点。分割的图像大小也更大，并且分割的效果和分割速度更快。

参考文献：

[1] 孙越泓.基于粒子群优化算法的图像分割研究 [D].南京：南京理工大学，2010.

[2] 楚晓丽.K-Means聚类算法和人工鱼群算法应用于图像分割技术 [J].计算机系统应用，2013，22（4）：92-94+103.

作者简介：陈兴志（1997.11-），男，汉族，云南昆明人，

本科，研究方向：应用数学;王代文（1999.05-），男，汉族，四川綿阳人，本科，研究方向：应用数学;刘乃瑶（1998.08-），女，汉族，吉林长春人，本科，研究方向：计算数学;乐文涛（1998.12-），男，汉族，四川南充人，本科，研究方向：计算数学;黄飞翔（1998.09-），男，彝族，云南昆明人，本科，研究方向：应用数学。