一种快速自动多目标图像分割算法

高华 邬春学

摘 要：針对进化多目标图像分割算法运行时间长且依赖人工挑选最优解的不足，提出一种快速自动多目标图像分割算法。首先使用自适应Mean-shift算法对图像进行预处理，将粗分割结果进行二次分割以提高运行速度;其次选择相互排斥的指标作为多目标的目标函数，并采用RM-MEDA框架对超像素颜色与纹理特征分别进行优化，同时对它们使用不同权值作为目标函数优化;最后由模糊模型从众多Pareto折中解集中自动选择满足实际分割要求的PS解。引入Mean-shift进行预分割，相对于标准的RM-MEDA，其运行速度提高近18%，由模糊模型推荐的Pareto解中，97%的情况符合分割要求。

关键词：图像分割;聚类分析;进化算法;Mean-shift;多目标

DOI：10. 11907/rjdk. 202166                                                                  开放科学（资源服务）标识码（OSID）：

中图分类号：TP317.4   文献标识码：A                文章编号：1672-7800（2020）011-0212-05

A Rapid Automatic Multi-objective Image Segmentation Algorithm

GAO Hua1，WU Chun-xue2

（1. Office of Educational Administration， University of Shanghai for Science and Technology;

2. School of Optical-Electrical and Computer Engineering， University of Shanghai for Science and Technology，

Shanghai 200093， China）

Abstract： The multi-objective image segmentation algorithm is confronted with some challenges such as long running speed and manual selection of the optimal solution. In this paper， a rapid automatic multi-objective segmentation algorithm （RAMOSA） is proposed to solve this problem. Firstly， the adaptive mean-shift algorithm is used to pre-segment the image， and the coarse segmentation results are re-segmented to improve the segmentation efficiency. Secondly， mutually exclusive indexes are selected as the multi-objective function， and RM-MEDA framework is used to optimize the color and texture features of super pixels respectively. Finally， the fuzzy model automatically selects the specific optimal solution that conforms to the current situation from many Pareto results. Multiple image materials are selected for image segmentation experiment， the experimental results show that RAMOSA algorithm has higher segmentation efficiency compared with general multi-target image segmentation. Mean-shift is introduced for pre-segmentation. Compared with the standard RM-MEDA， the operating speed is increased by 18%， and the accuracy of the results selected by the fuzzy model reached 70%.

Key Words：image segmentation; cluster analysis; evolutionary algorithms; mean-shift; multi-objective

0 引言

图像分割是图像模式识别和场景分析中重要的预处理环节。随着模式识别、计算机视觉、虚拟现实与仿真、卫星遥感图像等技术的发展，图像分割技术日益成熟，众多学者从数据处理方法、图像特征提取等方面，设计了多种代表性图像分割和处理算法。由于图像分割具有数据量大、图像信息维度多等特点，分割方法具有强烈的针对性，目前没有一种适用于所有图像的通用算法[1-3]。

相对于一般的单目标图像分割算法，多目标图像算法将多个特征空间作为算法多个目标函数，并且多个图像特征目标函数之间互斥，同时优化多个目标函数，通过对互斥多目标函数进行求解，可得到非唯一的最优解，称为Pareto最优解集。所以Pareto解集是多个互斥的特征空间最优分割结果集合，最终只需在众多Pareto集合中挑选满足实际分割要求的结果。进化多目标算法（Multi-objective Evolutionary Algorithms）优势独特，备受关注，目前研究比较成熟的算法主要有：NSGA-II[4]、SPEA2[5]、PEAS[6]、MOEA/D、IBEA[7]、HypE[8]等。根据不同的可提取进化的目标类型，将多目标图像分割算法分为3类：①将两种或者多种分割算法作为两个或多个目标;②将图像多个特征空间作为多个目标; ③将不同的距离度量函数作为多个目标。本文主要针对第二类算法展开研究。

Mean-Shift算法核心内容是最优化理论中的梯度下降法（亦称牛顿法，最速下降法等）[9]，即沿着梯度下降方法寻找目标函数极值。在图像分割应用中，算法的解是最大相似度值的候选目标位置。Zhang 等[10]提出的 RM-MEDA 框架充分使用连续多目标优化的特性，即对m个目标函数的连续多目标优化问题。由 Karush-Kuhn-Tucker 条件可知，Pareto最优解集合PS（Pareto Set）在决策空間上的分布呈现分段连续的（m-1）维流形[11]。RM-MEDA 算法本质是通过建立多个线性（m-1）-维流形分布的概率模型，分段逼近整个非线性的 PS 流形，再分别对所有线性模型随机采样并生成子代种群。

基于文献[12]，本文针对Mean-shift算法运算量大、需要设定带宽等缺点，引入改进的Mean-shift算法，对图像进行降像素及自动带宽调节。通常以手工方法选取最佳Pareto解，本文引入模糊模型从众多Pareto折中解中找到符合当前情况的具体最佳解，对进化算法相应检验指标进行改进，使改进后的指标更加符合本文研究的图像分割实验。

1 快速自动多目标图像分割

1.1 算法框架

RAMOSA算法流程主要包括4个模块：第1模块是自适应Mean-shift预处理，后续再分割基于预分割的过度分割结果;第2模块是基于过度分割区域获取图像纹理及颜色两个特征;第3模块是使用多目标算法的求解，包括编码、进化算子、适应度函数设置和产生Pareto集;第4模块是自动选取较好的Pareto解，综合Pareto 解集与具体最优方案的求解方法。本文RAMOSA算法流程如图1 所示。

1.2 Mean-shift算法改进

本文基于MS过度分割的结果再进行分割。k（x）是核函数K（x）的剖面函数，且 k（x）是一个单调递减的凸函数，核函数K（x）、G（x）分别由K（x）=k（||x||2）、G（x）=g（||x||2）定义且g（x）=-k′（x），则基于核函数的Mean-shift算法具有收敛性。

本文核函数K（x）的剖面函数k（x）为：

k（x）=exp-x2 （1）

在一副n*n大小的彩色图像中，共有n*n个点x？i（i=1，2，…，n*n），使用RGB色彩空间表示像素点颜色值，可以形成1个五维空间——颜色联合特征空间R5（R，G，B，X，Y），图像中的每个像素点使用1个五维特征向量表示，即由颜色三维和位置二维表示。由于色彩信息与空间信息相互独立，K（x）可由公式（2）的两个k（x）的乘积表示。

Khshr（x）=Chs2hrpk（xshs2）k（xrhr2） （2）

其中，C是归一化常数，xs表示像素空间位置信息，xr表示像素三维色彩信息，hs为空间窗口区域半径，hr为颜色空间窗口半径。

Mean-shift滤波算法在处理较大图像时，面临计算量大且处理速度过慢等问题[13]。在实际运用中，算法运行效率是衡量算法的主要标准，为了提高Mean-shift算法运行效率、减少运行时间，对标准的Mean-shift滤波算法进行如下改进：

（1）从算法运行效率方面考虑，使用高斯金字塔分割算法降低图像分辨率，算法处理后得到低像素的预处理图像，使用Mean-shift算法对高斯金字塔分割算法处理的结果再进行滤波处理，最后对滤波后的图像恢复到初始分辨率[14]。

（2）使用Mean-shift对图像进行多次滤波处理，一般直接将x设置为收敛点对应的值，直接计算的数据运算量较大，滤波后的图像颜色不均匀，滤波后图像效果很难达到分割要求。因此，本文对赋值方法进行改进：在算法实现过程中采用归类思想对每个像素点设置1个标志位记录该像素点类别，当算法迭代达到结束条件时候，将所有梯度方向上没有设置标记值的像素点设置为同一类别号Ti（i=1，2，3，…，n），如果当前梯度方向已有被标记过的像素点，则将当前梯度方向所有未被标记的像素点类别号设置为已标记像素点的标记值。改进后Mean-shift滤波算法主要步骤为：①读入原始图像，降低图像的像素，保存降低分辨率后的图像信息;②遍历降分辨率图像，根据式（1）计算mh？（x）;③mh？（x）的值赋给x 即x=mh？（x）;④如果‖mh？（x）-x‖<ε，算法得到概率密度最大值的点即为算法收敛点，算法运算结束。若‖-x‖>ε，则重复执行步骤②和③，直到满足迭代停止条件，则将该梯度方向未标记的像素点记为同一类;⑤使用同一颜色表示同一标记的像素点;⑥将处理结束的图像还原到初始分辨率。

1.3 检验指标改进

选择合适的聚类算法目标函数是本文算法成功的关键，本文选择的两个目标函数具有矩阵关系，因此使用RM-MEDA算法同时优化两个目标函数[15-16]。

1.3.1 聚类算法设计

本文算法采用聚类的内部紧凑函数Com第一个目标函数与类的中心点值进行计算，第一个目标函数类聚类的内部紧凑函数如公式（3）所示。

Com（k）=i=1kxj∈ci||xj-xvi|| （3）

K 为类的数量，需算法提前设定。类的数量k 和Com（k）函数之间是单调递减关系，k 数值增大使Com（k）结果变小。聚类算法为了得到最佳的聚类数目，同时需要将类与类之间的差异性考虑在目标函数之中。本文使用类的中心点值进行计算，类与类之间差异性函数如公式（4）所示。

Sep（k）=mini≠j？？？||xvi-xvj||？ （4）

本文根据在聚类内部紧凑函数及类与类差异性之间寻找平衡点的原则[17]，设计基于距离矩阵的有效性指标DXB，如公式（5）所示。聚类内部紧凑函数与类与类之间差的异性函数的比值为：

DXB=Com（k）/Sep（k） （5）

DXB 有以下优点：①Com（k）、Sep（k）与k是单调递减的关系，当k值变大，Sep（k）与Com（k）的函数值变小，一个成功的聚类应该是当Sep（k）的函数可以取到较大值，Com（k）函数可以取到较小值，最佳聚类数指其折中值;②DXB是参照距离矩阵定义的聚类有效性检验指标，使用类代表点作为类中心点，同时引入不同的相似性指标到目标函数中 ;③RAMOSA通过使用实数值编解码的方式得到算法类代表点，一般优化算法需要遍历类内所有点，本文算法可缩短搜索类代表点的时间。

1.3.2 多目标组合

本文使用Com 与DXB两个目标函数，采用RM-MEDA多目标框架同时进行优化。具体描述为：

F1=Com（k）F2=DXB（k） （3）

1.4 進化算子

Zhang 等[11]提出的 RM-MEDA 算法框架充分利用了连续多目标优化的特点，处理对于m个目标函数的连续多目标问题。由 Karush-Kuhn-Tucker 条件可知，Pareto最优解集合PS（Pareto Set）在决策空间上的分布呈分段连续的（m-1）维流形[18-19]。RM-MEDA 算法本质是通过建立多个线性（m-1）维流形分布的概率模型，分段逼近整个非线性的 PS 流形，再分别对所有线性模型随机采样并生成子代种群。

算法主要流程为：

算法名称：RM-MEDA算法

步骤1：初始化参数。t为算法运行的代数，pop（t）={x1，x2，…，xn}为t代大小为N的种群，Fx1，Fx2，…，Fxn，令t=0，初始化pop（0），pop（0）的个体随机得到，计算器函数适应值。

步骤2：判断停止条件。达到停止条件，算法计算终止同时返回pop（t）的PS目标函数向量和种群。

步骤3：模型建立。建立相应的分布概率模型计算pop（t）。

步骤4：繁殖子代。生成新的种群从而得到新的解集Q，使用已经建立的模型，同时得到Q目标函数值。

步骤5：选择N个来自从Q∪pop（t）中的个体作为下一代pop（t+1）…，…{f（x1），…，f（xi）}。

1.5 基于模糊模型识别的最优解确定

多目标图像分割在算法获得Pareto 最优解集后，通常需经人工在众多PS解集中挑选出分割效果好的结果[20-21]。本文采用模糊模型识别算法自动推荐最优分割结果，具体实现步骤为：

（1）求出各非劣解的隶属度向量。各粒子目标隶属度公式为：

Ai，k=fk，max-fi，kfk，max-fk，min （7）

其中，Ai，k与f i，k分别表示第i 个粒子的第k 个目标隶属度值与实际结果;fk，max与fk，min分别为第k 个目标函数的最大值与最小值。

（2）先根据实际情况对各目标的重要程度进行排序，再结合模糊语气算子，将最重要的目标与其它目标进行二元对比，得到非归一化的隶属度指标目标向量[α1，α2 ，α3]。

（3）求各粒子隶属度向量 [Ai1， Ai2， Ai2]（i=1，2，…，n）与目标权重向量 [α1，α2 ，α3]的贴近度 σ（A i，α），其公式为：

δ（Ai，α）=2（Ai，α）（Ai，Ai）+（α，α）（i=1，2...n）  （8）

其中，

（Ai，α）=Ai，1α1+ Ai，2α2+Ai，3α3 （9）

（4）寻找与 [α1，α2 ，α3]最为贴近的隶属度向量，其对应分割结果即为最优分割结果。

2 实验分析

本文算法实验参数设置为：种群个数为50，最大迭代代数是100。Mean-shift带宽为（7，7，50），图像颜色特征与纹理特征权重初始值分别为0.9、0.1。

本文选取的测试图像使用标准的RM_MEDA算法与本文RAMOSA算法按照加权的颜色和纹理图像特征进行分割的结果如图2所示。第一列是标准RM_MEDA算法分割结果，第二列是本文RAMOSA算法分割结果。

选用标准的RM_MEDA算法与本文算法对图2（a）-（f）进行图像分割实验，试验时间如表1所示，将表1数据以折线图的方式呈现，如图3所示。由图3可以看出：①两条线趋势较为一致，说明本文算法与标准RM_MEDA算法在多目标图像分割上有效;②标准RM_MEDA算法的折线在本文算法的上面，说明本文算法在分割效率上优于标本RM_MEDA算法，运行速度提高近18%;③第3张照片算法运行时间比其它图像时间更长，说明图像分割时间长短与图像像素大小具有正相关关系。

本文RAMOSA对图2（a）-（f）图像进行分割的Pareto集合结果如图4所示，RAMOSA算法并没有收敛成单一解，而是产生了一组Pareto折中解，但是很多Pareto折中解存在重复，为了方便展示效果，去除重复的解和一些明显错误的解，只突出分割结果比较好的折中解。由实验结果产生大量Pareto解集，说明本文选定的两个Com和DXB目标函数是相互排斥的，本文选取的目标函数是合适的。

图4中矩形点为各图像较好的Pareto解，通过观察可发现当两个互斥的目标函数值较为接近时得到的Pareto解通常符合实际分割要求。实心点为模糊模型推荐的第一个最优解，椭圆点是为模糊模型推荐的第二个解。实验结果表明， 模糊模型推荐的较好的Pareto解中，97%的情况符合分割要求。

3 结语

本文基于RM_MEDA框架引入自适应Mean_shift与模糊模型算法， 提出了一种自动快速多目标图像分割算法RAMOSA。由于进化多目标图像分割算法存在运行速度缓慢及依赖人工挑选最优解等缺点，首先引入自适应Mean-Shift算法，对图像进行预处理，提取预分割纹理及颜色特征，通过设置不同的权重生成新特征;其次选择相互排斥的类内紧凑度Com与DXB作为目标函数，RM-MEDA算法对两个目标函数同时进行优化;最后模糊模型能够在Pareto折中解集中推荐符合實际分割要求的解。由于引入了Mean-shift进行预分割，运行速度相对于标准RM-MEDA提高近18%，97%由模糊模型推荐的Pareto解符合分割要求。

但同时对于低像素图像，本文算法效率没有标准的RM-MEDA算法处理速度快，模糊模型自动挑选的结果不唯一（有2个）。如何减少模糊模型推荐结果数量、提高低像素图像处理效率是下一步研究内容。

参考文献：

[1] 何志明.  图像分割综述[J].  山东工业技术，2016（22）：226.

[2] BALI A，SINGH S N. A review on the strategies and techniques of image segmentation[C]. Fifth International Conference on Advanced Computing & Communication Technologies， 2015：113-120.

[3] 刘丛，陈倩倩，陈应霞. 多距离聚类有效性指标研究[J]. 小型微型计算机系统，2019，40（10）：2209-2214.

[4] LONG J， ZHENG Z， GAO X， et al. A hybrid multi-objective evolutionary algorithm based on NSGA-II for practical scheduling with release times in steel plants[J].  Journal of the Operational Research Society， 2016， 67（9）：1184–1199.

[5] YU F， LI Y，WEI B， et al. Interactive differential evolution for user-oriented image retrieval system[J].  Soft Computing，2016，20（2）：1-15.

[6] EFSA. Reasoned opinion on the modification of the existing maximum residue levels （MRLs） for boscalid in beans and peas with pods[J].  EFSA Journal， 2016， 13（3）：1-19.

[7] BIOLOGíA I D. Quararibea yunckeri sessiliflora Standl. Miranda ex W.S. Alverson - IBUNAM： MEXU： TUXsn01463[D].  Mexico City：Unibio Colecciones Biológicas， 2016.

[8] KAMENOVA K，CAULFIELD T. Stem cell hype： media portrayal of therapy translation.[J].  Science Translational Medicine， 2015， 7（278）：278-281.

[9] 李振宇，胡涵. 基于组合排序的约束多目标优化算法[J]. 计算机技术与发展，2019，29（11）：32-36.

[10] ZHANG Q， ZHOU A， JIN Y. RM-MEDA： a regularity model-based multiobjective estimation of distribution algorithm[J].  IEEE Transactions on Evolutionary Computation， 2008， 12（1）：41-63.

[11] ZHANG H， ZHOU A， SONG S， et al. A Self-organizing multiobjective evolutionary algorithm[J].  IEEE Transactions on Evolutionary Computation， 2016， 20（5）：792？- 806.

[12] 刘丛， 邬春学.  进化多目标距离矩阵聚类研究[J].  小型微型计算机系统， 2016， 37（6）：1298-1302.

[13] 付丽梅.  使用彩色直方图均衡法改进的Mean Shift行人跟踪算法[J].  软件工程， 2019， 22（2）：17-19.

[14] 鸿源， 胡改玲， 姜凌奇，等.  Mean Shift算法在目标跟踪领域的应用研究[J].  计算机科学与应用， 2020， 10（7）：1391-1399.

[15] 杜冠军， 佟国香.  一种新的混合演化多目标优化算法[J].  软件， 2019， 40（2）：12-16.

[16] 严加展，陈华，李阳. 改进的模糊C-均值聚类有效性指标[J].  计算机工程与应用，2020， 56（9）：156-161.

[17] 刘丛， 万秀华，彭敦陆. 基于多目标进化算法的多距离聚类研究[J]. 计算机应用研究， 2019， 36（1）：94-98.

[18] 韦占江，梁宇. 快速HAC聚类算法的改进及应用于无监督语音分割[J]. 计算机科学与应用， 2020， 10（8）：1464-1470.

[19] 王慧君. 基于规则模型学习的多目标分布估计算法研究[D].  西安：西安理工大学，2019.

[20] 宋昊泽， 吴小俊.  图像多尺度密集网络去模糊模型[J].  激光与光电子学进展， 2019， 56（21）：1-10.

[21] 孙涛， 李东升.  基于非凸的全变分和低秩混合正则化的图像去模糊模型和算法[J].  计算机学报， 2020， 43（4）：643-652.

（责任编辑：江 艳）