基于改进粒子群优化算法和遗传变异的图像分割模型

梁 军，洪泽泓，余松森

（华南师范大学 软件学院，广东 佛山 528225）

0 引言

图像分割技术是图像处理中重要的环节，也是图像分析的预处理步骤之一。图像分割主要是根据原始图像的亮度、颜色或者图内纹路等信息将图片中不同的区域分开，以便根据具体需求去除不重要的部分和取出需要的部分，它被广泛应用于医药、农业、工业生产等各个领域［1］。目前，基于灰色图像的分割已十分成熟，但彩色图像的分割效率较低且精度不高，仍需进一步研究［2］。

聚类算法是图像分割的常用方法之一［3-4］。早期，Comaniciu 等［5-7］将Mean Shift 应用于图像平滑、分割和视频跟踪等领域，反复迭代计算当前点的偏移均值，最后经过多次移动直至满足条件；但Mean Shift 也存在很多缺点，比如分割效果时间复杂度较高、图像分块数量不可控。为了降低该算法的时间复杂度，Sheikh 等［8］提出了Medoid Shift 算法，它每次迭代会计算出新的中心点，而不是新的位置。后来，Vedaldi 等［9］对Medoid Shift 算法作出改进，使每个点移动到梯度增加的最近的点，称为Quick shift；但是Quick shift 算法并不是一种迭代的算法，因此不能有效控制聚类的数量以及大小。随着深度学习技术的发展，受到深度网络中Dropout技术的启发，张琦等［10］提出了稀疏聚类的方法，但是目前仍应用于像素点较少的图片数据集中。k均值（k-means）算法简单易用，但对聚类中心数量和其初始化位置有较大依赖。

粒子群优化（Particle Swarm Optimization，PSO）算法是Kennedy 等提出的一种的启发式算法，它具有良好的全局搜索能力［11］。将PSO 和k-means 聚类算法结合能很好地克服k-means 本身算法的局限性，例如：Chan 等［11］将PSO 算法与SOM（Self-Organizing Map）结合的混合算法对k-means 进行优化，选出最有价值的客户并针对有价值客户提出合理的营销策略；Wang 等［12］将PSO 算法结合k-means 应用于网络安全领域，对用户行为进行聚类分析和有效识别风险账户；He 等［13］将PSO 算法结合k-means 应用于矿产资源承载能力的评估；Ibrahim 等［14］使用聚类算法预测电力公司的用户行为，结合PSO 算法可达到更优的效果，使公司利润最大化；Tao 等［15］提出了一种基于适应度峰值聚类的动态多群粒子群算法和增强学习策略；Zhang 等［16］将PSO 算法与k-means 结合并 在YCbcr 颜色空间下对农产品进行语义分割。

PSO 算法结合k-means 应用于各领域都可达到较好的效果，但大部分算法忽视了PSO本身的局限性，即PSO算法容易陷入局部最优。结合不同的优化算法的优势可以实现对PSO算法本身的改进，例如高兵等［17］结合麻雀搜索算法的大范围搜索与PSO算法的快速收敛的特点提出网络入侵检测算法。本文不仅将PSO算法与k-means相结合应用到图像分割领域，还对PSO算法进行了一定改进，增加了遗传算法的变异机制，提高了算法性能和稳定性。本文提出了一种基于改进粒子群优化算法和遗传变异的图像分割模型PSOM-K（Particle Swarm Optimization Mutations-K-means），主要工作如下：

1）针对标准PSO 容易陷入局部最优的问题，对PSO 公式进行改进，增加随机邻居粒子位置对其自身位置的影响，提高其全局搜索能力。

2）将改进的PSO 与遗传变异（对每次优化后的位置按一定概率对其中一位进行变异）相结合，提高模型的泛化能力。

3）对红（Red，R）、绿（Green，G）、蓝（Blue，B）三通道的聚类中心的值（非位置）分别进行初始化且不需要确定它们聚类中心的具体位置（对于R 通道，像素点值与哪个聚类中心值接近，就属于哪一类，G 和B 通道类似）。

1 相关工作

1.1 标准PSO算法

粒子群算法是一种仿生算法，通过模拟飞鸟的行为寻找最优解。它的本质是通过算法将个体信息和社会信息联合起来，从而使无序的群体慢慢收敛于最优粒子周围。每个粒子的位置代表一种解决方案（即一种解）。在整个寻优的过程中，每个粒子会根据式（1）（2）来更新自己的速度和位置：

其中：i表示微粒i；j表示微粒的第j维；表示第代；c1和c2为加速常量，通常在（0，2）上取值；w为惯性权重因子；r1和r2为（0，1）上两个相互独立的随机函数。假设d表示解空间的维度，那么xi=(xi1，xi2，…，xid)为 第i个粒子的位置，vi=(vi1，vi2，…，vid)为第i个粒子飞行的速度，pi=(pi1，pi2，…，pid)为第i个粒子的个体历史最优位置，gi=(gi1，gi2，…，gid)为全局历史最优位置。

1.2 图像的聚类分割算法

假设需将一张灰色图像分割成k个部分。那么，任意一个像素点与第i个聚类中心Ci(1 ≤i≤k)之间的距离为：

其中t为像素点的值。

令Ti={ti1，ti2，…，timi}(1 ≤i≤k)表示图像第i个部分的像素点的集合，mi表示第i个部分的像素点的总数。那么，该像素点集合Ti的质心点值Xi为：

k-means 对灰色图像分割的算法如算法1。针对彩色图像，可分别对R、G、B 通道用算法1 完成分割，然后再合并成彩色图像。

算法1 灰色图像分割算法。

输入 一张灰色图像、图像分割数量k，迭代次数m和阈值σ；

输出 分成k个部分的灰色图像。

步骤1 随机设置k个像素点的值为聚类中心。

步骤2 按式（3）计算每个像素点与k个聚类中心的距离，并将每个点划分为与之最近的聚类中心点的类别。

步骤3 按式（4）更新聚类中心。

步骤4 当迭代次数小于m或前后聚类中心值的距离大于σ，循环步骤2～3；否则跳到步骤5。

步骤5 已确定k个聚类中心，按式（3）计算每个像素点和k个聚类中心的距离，并将该像素点的值变更为与之最近的聚类中心点的值。

步骤6 将这张灰色图像分割成k个部分。

1.3 图像分割评价指标及适应度函数

图像分割质量通常可通过均方误差（Mean-Square Error，MSE）、峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）、结构相似性（Structural Similarity Index Measure，SSIM）、特征相似性（Feature Similarity Index Measure，FSIM）和FSIMc（Feature Similarity Index Measure color）［18］进行评估。这些指标在图像分割、超分辨率以及图像去模糊等领域应用广泛。FSIM 是SSIM 较成功的变种，可用于对灰色和彩色图像分割质量的评估。FSIMc相较于FSIM，更有利于评价彩色图像，它对一张图片中的所有像素点赋予不同的重要性，如沿着图片中央物体边缘的像素点相较于其他背景像素点，肯定更能界定物体的结构。但采用FSIMc 指标的文献较少，大部分文献还是用PSNR 和FSIM 作为评价彩色图像的指标，因此本文只是将FSIMc 指标作为粒子群优化中的适应度函数，在图像分割的最终评价指标上仍采用PSNR和FSIM。

1.3.1 图像分割评价指标

1）PSNR指标。

其中：x、y分别表示原图及图像分割后的图片；M、N分别表示输入图片的横向和纵向长度。PSNR 的值越大，说明图像分割质量越好。

2）FSIM指标。

假设PC1(x)和PC2(x)分别表示原图与分割后的图片的相位一致性特征（详细公式见文献［18］）。PCm(x)=max{PC1(x)，PC2(x)}，取值在［0，1］。通过Sobel、Prewitt 和Scharr 算子结合，可以分别从横向和纵向计算图片的梯度特征Gx与Gy，并得到单幅图片的梯度特征为G=假设原图与分割后的图片的梯度特征为G1与G2，结合PC1(x)与PC2(x)可以计算出SL(x)。FSIM 的取值为［0，1］，FSIM 越接近1，表示图像分割的效果越好。FSIM 可将图片转为YIQ颜色空间，然后改成图像分割指标FSIMc。

3）FSIMc指标。

先将图片由RGB 颜色空间转换成YIQ 颜色空间，然后利用Y 通道计算SL(x)与PCm(x)，计算方法与上述FSIM 方法相同。再根据YIQ 中的I、Q 通道，计算两幅图片的色度相似度SI(x)与SQ(x)，即得到SC(x)=SI(x) ·SQ(x)。FSIMc的取值也为［0，1］。

1.3.2 适应度函数

假设向量X、Y、Z分别代表R、G、B 三通道的k个聚类中心，即 ：X={x1，x2，…，xk}，Y={y1，y2，…，yk}、Z={z1，z2，…，zk}(0 ≤xi，yi，zi≤255，1 ≤i≤k)。定义每个粒子的位置为{x1，x2，…，xk，y1，y2，…，yk，z1，z2，…，zk}。

计算单个粒子的适应度函数值，如算法2 所示。

算法2 适应度函数值计算。

步骤1 对于R 通道的二维矩阵的任意一个像素点x′，计算x′与其聚类中心{x1，x2，…，xk}中哪一个类中心xi(1 ≤i≤k) 最近，则该像素点属于那一类并更新x′。即x′=

步骤2 对G、B 通道做和R 通道相类似的操作。

步骤3 利用式（8）计算粒子对应的FSIMc 值，即适应度函数值。

2 PSOM-K

2.1 改进的PSO算法

将标准PSO 算法用于k-means 图像分割领域易陷入局部最优且全局视野不够，因此本文对标准PSO 公式进行了改进，增加了当代随机邻居粒子位置对其自身的影响。通过增强粒子的社会性增加它的全局搜索解的能力。

更新后的公式为：

其中：sk=(sk1，sk2，…，skd)为当代随机邻居粒子k的位置，其余参数与式（1）（2）类似。

同时，每次更新完位置，将三通道的位置转换成二进制表示，三通道的位置各有0.05 的概率产生变异，将其中的一位变成相反的数字，防止陷入局部最优。

2.2 遗传变异操作

本文增加遗传变异操作的目的也是为了使模型不易陷入局部最优。在每次用式（9）（10）对粒子的位置更新后，然后以β的概率确定其是否变异。首先将每个粒子更新后的位置拆分成R、G、B 三通道的聚类中心。

针对R 通道，按β概率确定其聚类中心值{x1，x2，…，xk}是否变异。如变异，则先将所有k个值都转变为二进制。然后对每一个二进制数，随机选取一位进行变异，即0-1 变换（0 变为1 和1 变为0）。

对G 和B 通道做类似的操作。最后将R、G、B 三通道的聚类中心按1.3.2 节方式合成该粒子的位置。

2.3 PSOM-K

本文提出了一种基于改进粒子群优化算法和遗传变异的图像分割模型PSOM-K。PSOM-K 将改进PSO 和遗传变异操作相结合对聚类中心进行初始化，最后运用k-means 对图像分割。PSOM-K 的图像分割流程如算法3 所示。

算法3 图像分割模型PSOM-K。

输入 一张彩色图像、图像分割数量k，粒子数N，粒子群优化迭代数Num和变异概率β（一张彩色图像可看成R、G、B 三通道的合成，每个通道是一个二维矩阵，取值范围为0～255）；

输出 图像分割后的彩色图像。

步骤1 对N个粒子的位置（即N个解决方案）进行随机初始化，即对每个粒子代表的R、G、B 三通道的聚类中心进行随机初始化。

步骤2 根据算法2 计算N个粒子的适应度函数值（即FSIMc 值），更新粒子群的全局最优位置和每个粒子的历史最优位置。

步骤3 用改进的粒子群优化公式，即式（9）（10），对N个粒子的位置进行更新。

步骤4 根据第2.2 节，对每个粒子的位置进行遗传变异操作。

步骤5 当迭代次数不小于Num时，重复步骤2～4；否则跳到步骤6。

步骤6 根据第1.3.2 节，可将全局历史最优粒子的位置拆分成R、G、B 三个通道的聚类中心的初始值（每个通道k个聚类中心）。用算法1 的步骤2～6 分别对R、G、B 三通道的聚类中心进行更新。

步骤7 合并R、G、B 三通道，输出这张彩色图像的分割结果。

在PSOM-K 中，由于不同的彩色图像拥有不同的色彩分布，从R、G、B 三通道分别用PSO 对其聚类中心进行优化，得到较合理的聚类中心；同时，结合遗传算法的变异操作，提高模型的泛化性；另外，从R、G、B 三通道分别聚类，提升彩色图像分割的效果。

3 实验与结果分析

本文使用Matlab R2019b作为开发工具。实验参数设置如下：粒子数N=10，粒子群优化迭代数Num=10，加速常量c1=0.1，c2=0.8，c3=0.1，变异概率β=0.05，聚类中心数量k∈｛4，6，8，10｝。本文取3次实验的平均值作为评估结果。

3.1 数据集

本文选用伯克利大学分割数据集（BSDS500）［19］中的21张图像做实验，其中一部分选择的图像是为了与相关文献作对比，其他的图像是随机抽取的。这21 张图像如图1 所示。

图1 伯克利大学分割数据集的图像（481×321或321×481）Fig.1 Images（481×321 or 321×481）from Berkeley segmentation dataset

3.2 性能比较

针对不同的应用，图像分割可分为粗粒度图像分割和细粒度图像分割。本文拟对聚类中心数量k进行有差别的设置，使得算法能适用于不同的图像分割级别。本文拟划分k≤10（粗粒度）和k≥40（细粒度）这两个类别作测试。

3.2.1 粗粒度图像分割对比

令聚类中心数量k=4、6、8、10，本文将PSOM-K 与CEFO（Chaotic Electromagnetic Field Optimization）［20］和WOA-DE（Whale Optimization Algorithm-Differential Evolution）［21］等算法对比性能。因此，本文选用了文献［20］和［21］中的6 张图像在图像分割指标PSNR和FSIM上进行对比，结果如表1所示。

图像分割指标PSNR 和FSIM 越大越好，从表1 可以看出，与CEFO［20］和WOA-DE［21］相比，本文PSOM-K 模型在这6张图片上的图像分割指标PSNR 和FSIM 上都能达到最好效果。例如：当k=4 时，相对于CEFO［20］，PSOM-K 在图1（e）（g）（h）上FSIM 分别提高了9.97%、12.69%、7.70%；相较于WOA-DE［21］，PSOM-K 在图1（j）（k）（l）上FSIM 分别提高了15.57%、5.05%、19.02%。当k=10 时，相对于CEFO［20］，PSOM-K 在图1（e）（g）（h）上PSNR 分别提高了29.92%、30.43%、30.77%；相较于 WOA-DE［21］，PSOM-K 在图1（j）（k）（l）上PSNR 分别提高了0.87%、14.93% 和14.62%。在k=4 的时候FSIM指标与CEFO［20］相比提 升 了7.7%～12.69%，与WOA-DE［21］相比提升了5.05%～19.02%。因此，本文PSOM-K 模型用将改进PSO 和遗传变异结合后的策略应用于k-means 的聚类中心位置的初始化是非常有效的。

图2 展示了部分图像在CEFO 和PSOM-K 上的分割效果。从主观感受对图2 进行评价：采用CEFO 的整体图像亮度偏暗，颜色稍微失衡，整体的色彩倾向灰度，如：图2（d）在较低阈值的时候，可以看出颜色明显偏离原图；图2（b）的其他图片也有着肉眼可见的偏蓝色调。PSOM-K 产生的分割效果更加接近真实图片，而且在图片的细节展示中更加细腻，本文模型相较于CEFO 更加符合真实情况。

3.2.2 细粒度图像分割对比

令聚类中心数量k=40、50、60、70，将PSOM-K 与和HWOA（Hybrid Whale Optimization Algorithm）［22］对比性能。表2 表明，相较于HWOA［22］，PSOM-K 在FSIM 指标上稍有下降，但在PSNR 指标上有很明显的提升。例如：在图（s）上，当k=40 时，PSOM-K 相对于HWOA，FSIM下降了0.11%，但PSNR 提升了8.41%；在其他情况，与细粒度分割算法HWOA相比，在k=40 时，PSOM-K 在FSIM 指标最多下降0.45%，但PSNR 指标提升7.59%～13.58%。由于PSNR 指标主要从图片噪声方面评价图片质量，而FSIM 指标对图片的评价，更多集中于图像的特征相似性。PSOM-K 在PSNR 指标上提升较多，说明本文模型对于噪声的处理更有优势；PSOM-K 在FSIM 指标上略有下降，说明本文模型因为对于整体噪声优化而忽视了一些局部特征。

表2 细粒度图像分割的FSIM和PSNR对比Tab.2 Comparison of FSIM and PSNR of fine-grained image segmentation

3.3 消融实验

为了测试PSOM-K 中改进策略的有效性，首先将标准粒子群优化（Standard PSO）算法与k-means 的结合称为“SPSO-K”，只增加邻居粒子的改进PSO 算法与k-means 算法结合称为“PSON-K”，然后对比k-means、SPSO-K、PSON-K 和PSOM-K 在指标FSIM 和PSNR 上的性能表现，如表3 所示。

表3 不同聚类中心数量的FSIM和PSNRTab.3 FSIM and PSNR for different numbers of cluster centers

表3 显示出：使用标准PSO 算法对k-means 聚类中心的位置初始化（即SPSO-K）可以提高k-means 算法的性能，使用随机邻居粒子的PSON-K 可以提高SPSO-K 算法的性能，验证的改进步骤的有效性；并且在增加了随机邻居粒子的基础上增加遗传变异机制的PSOM-K 能进一步提高PSON-K 算法的性能。在粒子群算法中，增加随机邻居粒子对自身位置的影响，提高了粒子的全局搜索能力，有利于寻找全局最优解；而遗传算法的变异机制提高了PSOM-K 的泛化能力，在模型中加入随机变异，相当于增加了模型的噪声扰动，训练出来的模型更稳定。

本文每个实验做3 次，3 次实验的标准差可反映算法的稳定性。表3 展示了5 张图片图1（a）（b）（f）（c）（i）在FSIM和PSNR 指标上的标准差的平均值（k等于4、6、8、10 的标准差的平均值）。表4 表明了PSOM-K 模型在5 张图片上的FSIM 值的标准差都比SPSO-K 与PSON-K 小；在PSNR 值的标准差上，除了图片（f），其余都比SPSO-K 小。再对5 张图片的标准差进一步平均，在FSIM 和PSNR 指标上，PSOM-K 的平均标准差分别为0.003 095 和0.146 069，而SPSO-K 的平均标准差分别为0.008 56 和0.308 604，PSON-K 的平均标准差分别为0.004 440 和0.223 173。PSOM-K 模型的平均标准差更小，说明PSOM-K 相对于SPSO-K 和PSON-K 更稳定，进一步表明了随机邻居位置影响和遗传变异这两种改进策略的有效性。

表4 SPSO-K、PSON-K和PSOM-K在FSIM和PSNR上的标准差比较Tab.4 Standard deviation comparison of SPSO-K，PSON-K and PSOM-K in FSIM and PSNR

将SPSO-K、PSON-K 和PSOM-K 算法在图1（a）上（k=4）进行图像预分割的参数收敛测试，通过互不干扰的100次迭代寻优结果如图3 所示。可以看出：基于标准PSO 的SPSO-K 算法收敛速度较快，但是很快便陷入局部最优；而只增加了随机邻居粒子的PSON-K 增加了全局搜索能力，获得了较好的效果，但是对于陷入局部的问题仍然没有解决；而增加了遗传变异机制的PSOM-K算法则提升了算法的泛化能力，可以使算法通过不断迭代获得更好的效果。

图3 图像预分割优化效果Fig.3 Image pre-segmentation optimization effect

4 结语

针对k-means 算法聚类中心位置对其性能有较大影响的问题，本文提出了PSOM-K 模型对粒子群算法进行了改进，并结合了遗传算法的变异操作，同时采用了FSIMc 作为适应度函数，最后应用RGB 颜色空间的三通道独立聚类的方式对彩色图像进行分割。在伯克利分割数据集上的实验结果表明：随机邻居位置影响、遗传变异及三通道独立聚类这三种策略提高了k-means 算法的分割性能及其稳定性。因为PSOM-K 应用了复杂度较高的聚类中心位置的初始化方法，所以它的运行时间相对于k-means 较长。PSOM-K 模型可被应用于图像预处理、图像压缩等方面。在未来的工作中，可尝试将这三种改进策略应用于不同的算法（例如Hierarchical clusting、Bayesian clustering、evolution-based clusting 等）来提高图像分割的效果。