一种基于超像素的快速聚类图像分割算法

许晓丽　赵明涛　高玲

摘要：本文提出一种基于超像素的快速聚类图像分割算法。该算法采用超像素分割策略，将多代表点近邻传播聚类算法应用于大规模图像数据的分割中，并与简单线性迭代聚类结合，实现快速图像分割。从结果看，提出的算法在进行大规模图像数据分割时，可以获得较好的分割效果，且分割效率较高。

关键词：超像素;快速聚类;图像分割

中图分类号： TP18        文献标识码：A

文章编号：1009-3044（2019）25-0235-02

Abstract： This paper proposes a fast clustering image segmentation algorithm based on superpixels. The proposed algorithm uses the superpixels segmentation strategy， and employs multi-exemplar affinity propagation clustering algorithm to large-scale image data segmentation. The proposed algorithm combines with a simple linear iterative clustering and obtains fast image segmentation effect. Experimental results illustrate that the proposed algorithm has superior performance and less computational costs compared for big data image segmentation.

Key words： superpixels; fast clustering; image segmentation

1 引言

图像分割是一种基本的计算机视觉技术，是图像预处理的关键步骤。在实际应用中，图像分割结果的好坏将直接影响到后续图像理解、识别和分类的精度。目前，超像素分割已成为一种重要图像预处理工具，深受国内外研究者的普遍关注。超像素利用像素间的相似性特征对像素点进行分组，用少量超像素描述图像总体特征，使图像后处理的复杂度降低，算法后续执行效率大幅提升。

简单线性迭代聚类（simple linear iterative clustering，SLIC）是一种超像素分割方法，SLIC基于颜色和距离相似性进行分割，生成形状规则且大小均匀的超像素。多代表点近邻传播（multi-exemplar affinity propagation，MEAP）聚类根据数据间相似度进行聚类，可以获得很好的聚类结果，但由于其具有很高的计算复杂度而难以用于大规模图像数据的快速分割。本文提出一种基于超像素的快速聚类图像分割算法—SLICMEAP算法，该算法采用超像素分割策略，将多代表点近邻传播（MEAP）聚类应用于大规模图像数据的分割中，并与简单线性迭代（SLIC）聚类结合，实现图像快速分割。从结果看，提出的算法在进行大规模图像数据分割时，可以获得较好的分割效果，且分割效率较高。

2 算法实现

2.1超像素图像的生成

SLIC算法是近年来流行的超像素分割算法，SLIC依据像素点空间距离和顏色相似特征进行局部迭代聚类。该算法首先初始化[K]个聚类中心，这些聚类中心在图像上均匀分布;然后遍历所有像素点，并将每一个像素点分配给与其距离最近的聚类中心，最后采用K-means聚类方法高效地生成超像素。SLIC有两种距离：空间距离和颜色距离。当遍历每个像素点时，分别计算该像素点和中心点的距离。距离计算包括以下几个公式。

其中，[ds]是空间距离，[dc]是颜色距离，[Ns]是类内最大空间距离，定义为[Ns=S=sqrt（N/K）]， 对每个聚类均适用。图像不同，聚类不同，则最大的颜色距离[Nc]也随之变化。

2.2 多代表点近邻传播聚类

多代表点近邻传播聚类模型定义了代表点和超代表点，遍历每个数据，将数据分配给最适合的代表点，每个代表点又分配给最适合的超代表点。在多代表点近邻传播（Multi-exemplar affinity propagation，MEAP）聚类中，设相似度矩阵为[[sij]N×N]，其含义是点[i]与潜在的代表点[j]之间的相似度。设链接矩阵为[[lij]N×N]，其含义是点[i]与其潜在的超代表点[j]之间的链接度。多代表点模型是寻找两个映射的过程，最大化[S1+S2]是该模型的目标，这里数据点与相应代表点间所有相似度之和是[S1]，代表点和相应超代表点间所有链接度之和是[S2]。

2.3 相似度矩阵的构建

多代表点近邻传播聚类根据数据点间的相似度进行聚类，由相似度形成相似度矩阵，求解相似度矩阵时，对于图像我们需定义其特征空间。本文图像特征选取颜色信息，在彩色图像中，每点的颜色用三维向量表示。本文提出的算法中，设输入图像经SLIC预分割后得到[N]个超像素区域[Ri（i=1，2，…，N）]，每个超像素的颜色向量为[ZRi=（z1i，z2i，z3i）]，其中[z1i，z2i，z3i]分别是第[i]个超像素区域内所有像素颜色均值。定义超像素间的相似度为[sij=-||ZRi-ZRj||2]，取负的欧氏距离作为相似度，即距离越小，相似度越大。在图像分割时，定义本文算法的链接度矩阵[[lij]N×N]为[lij=sijN]。 根据定义的超像素相似度矩阵和链接度矩阵，本文算法求解最优的类分配矩阵[C]采用目标函数最大化，并进一步采用最大和置信传播算法求这个最优问题。

2.4 算法实现步骤

本文提出的SLICMEAP算法实现图像分割的步骤如下。

（1） 应用SLIC算法对原图像进行预分割，得到超像素图像。该步骤中对SLIC算法参数进行合理设置，得到超像素区域大概在几百左右。

（2）计算每个超像素颜色均值，并求得超像素间颜色均值的负的欧氏距离作为超像素的相似度，构建相似度矩阵和链接度矩阵，即[[sij]N×N]和[[lij]N×N];

（3）MEAP算法消息初始化及其参数设置：最大迭代次数[tmax=1000]，连续迭代直到聚类中心不发生改变的次数[tconv=100]，[λ=0.9];

（4）根据[[sij]N×N]、[[lij]N×N]及消息传递公式，完成消息的迭代更新，采用最大和信念传播最大化目标函数直到收敛，得到最优的聚类标签;

（5）根据最终输出的聚类标签和图像像素点的映射关系，得到图像分割结果。

3仿真结果与分析

本实验实现环境为MATLAB2014b，选择Berkeley大学的标准彩色图像库的多幅图像进行仿真实验，图像大小为481×321。图1是本文SLICMEAP算法，SLICDBSCAN方法及人工分割结果在分割效果上的对比。原始图像首先经SLIC预分割得到超像素图像，如图1（b）所示。预分割后的超像素个数基本在几百左右，远小于图像像素点的个数，这样图像细节信息有效保留的同时，很好地降低了后续聚类处理的数据规模，分割效率大幅提升。后处理算法分别采用DBSCAN和MEAP获得的分割结果如图1（c）（d）所示，人工分割结果如图（e）所示，可以看出本文算法分割效果更优。从算法运行时间看，SLIC预处理时间相对较长，大约10s， DBSCAN和MEAP两种算法后续处理时间很短，约0.2s。因此，可以知道，算法中SLIC预处理过程消耗大部分时间，到二次聚类时，数据规模大幅度减小，总耗时很少。

4 结论

本文提出一种基于超像素的快速聚類图像分割算法，选择Berkeley大学的标准彩色图像库的多幅图像进行仿真实验，实验结果表明该方法获得了较好的分割效果，且分割效率较高。

参考文献：

[1] R. Achanta， A. Shaji， K. Smith， et al. SLIC superpixels compared to state-of-the-art superpixel methods[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（11）： 2274-2282.

[2] C. D. Wang， J. H. Lai， C. Y. Suen， et al. Multi-exemplar affinity propagation[J]. IEEE transactions on Pattern Analysis and MachineIntelligence， 2013， 35（9）： 2223-2237.

[3] 刘汉强，赵静.基于半监督的超像素谱聚类彩色图像分割算法[J].计算机工程与应用， 2018， 54（14）： 186-190.

【通联编辑：唐一东】