【图像处理笔记】图像分割之聚类和超像素 - 湾仔码农

大多数分割算法都基于图像灰度值的两个基本性质之一：不连续性和相似性。第一类方法根据灰度的突变（如边缘）将图像分割为多个区域：首先寻找边缘线段，然后将这些线段连接为边界的方法来识别区域。第二类方法根据一组预定义的准则把一幅图像分割为多个区域。本节讨论两种相关的区域分割方法:(1)在数据中寻找聚类的经典方法，它与亮度和颜色等变量有关;(2)用聚类从图像中提取“超像素”的现代方法。

1 使用k均值聚类的区域分割

1.1 原理

聚类方法的思想是将样本集合按照其特征的相似性划分为若干类别，使同一类别样本的特征具有较高的相似性，不同类别样本的特征具有较大的差异性。令{z1, z2, z3 ..., zn}是样本集合，在图像分割中，样本向量z的每个分量表示一个数值像素属性。例如，分割只基于灰度尺度时，z是一个表示像素灰度的标量。分割的如果是RGB彩色图像，z通常是一个三维向量，这个三维向量的每个分量是RGB三通道的灰度值。k均值聚类的目的就是将样本集合划分为k个满足如下最优准则的不相交的聚类集合C={C1, C2, ..., Ck}：

式中，mi是集合Ci中样本的均值向量（或质心），||z-mi||项是Ci中的一个样本到均值mi的欧式距离。换言之，这个公式说，我们感兴趣的是找到集合C={C1, C2, ..., Ck}，集合中的每个点到该集合的均值的距离之和是最小的。

基于聚类的区域分割，就是基于图像的灰度、颜色、纹理、形状等特征，用聚类算法把图像分成若干类别或区域，使每个点到聚类中心的均值最小。k 均值（k-means）是一种无监督聚类算法。基于 k 均值聚类算法的区域分割，算法步骤为：

（1）初始化算法：规定一组初始均值

（2）将样本分配给聚类：对所有的像素点，计算像素到每个聚类中心的距离，将像素分类到距离最小的一个聚类中；

（3）更新聚类中心：根据分类结果计算出新的聚类中心；

（4）完备性验证：计算当前步骤和前几步中平均向量之间的差的欧几里得范数。计算残差E，即k个范数之和。若E≤T，其中T是一个规定的非负阈值，则停止。否则，返回步骤2。

1.2 cv::kmeans函数

OpenCV提供了函数cv::kmeans来实现 k-means 聚类算法。函数cv::kmeans不仅可以基于灰度、颜色对图像进行区域分割，也可以基于样本的其它特征如纹理、形状进行聚类。

double cv::kmeans(InputArray data,  //用于聚类的数据，类型为 CV_32F
                  int K, //设定的聚类数量
                  InputOutputArray bestLabels,  //输出整数数组，用于存储每个样本的聚类类别索引
                  TermCriteria criteria,  //算法终止条件：即最大迭代次数或所需精度
                  int attempts,  //用于指定使用不同初始标记执行算法的次数
                  int flags,  //初始化聚类中心的方法：0=随机初始化 1=kmeans++方法初始化 2=第一次用用户指定的标签初始化，后面attempts-1都用随机或版随机的初始化
                  OutputArray centers = noArray()  //聚类中心的输出矩阵，每个聚类中心占一行
                  )

示例 图像分割之k均值聚类

1.3 cv::kmeans源码

当图片非常大时，对图像进行简单的计算操作，耗时就会变得非常大，常用的加速方法如OpenMp,TBB,OpenCL和CUDA。使用cuda时，图片在cpu和gpu之间的传输时间就达到上百ms，不适合本来就是ms级的计算。在kmeans源码中使用parallel_for_并行计算各个样本到聚类中心的距离。这边写一个简单的例子，了解下parallel_for_的用法。

示例 利用并行计算加速图片旋转

源码位于opencv路径下sources\modules\core\src\kmeans.cpp中，首先是初始化算法：规定一组初始center，一种是随机产生，另一种是用kmeans++初始化。kmeans++初始化聚类中心是以概率的形式逐个选择聚类中心，并在选择聚类中心时，给距离较远的点更高的权重，即更容易被选择为聚类中心。假设有5个点，随机选择其中一个点为中心，计算其他点到该点的距离的平方分别为10，20，5，15。则选下一个聚类中心时它们的权值为0.2,0.4,0.1和0.3。用代码写就是，距离平方和50，在【0,50】间随机生成一个数，用这个数挨个减去10，再减去20...直到结果小于0，下一个聚类中心就是该点。

计算距离

更新标签

kmeans

2 使用超像素的区域分割

超像素图像分割基于依赖于图像的颜色信息及空间关系信息，将图像分割为远超于目标个数、远小于像素数量的超像素块，达到尽可能保留图像中所有目标的边缘信息的目的，从而更好的辅助后续视觉任务（如目标检测、目标跟踪、语义分割等）。

超像素是由一系列位置相邻，颜色、亮度、纹理等特征相似的像素点组成的小区域，我们将其视为具有代表性的大“像素”，称为超像素。超像素技术通过像素的组合得到少量（相对于像素数量）具有感知意义的超像素区域，代替大量原始像素表达图像特征，可以极大地降低图像处理的复杂度、减小计算量。超像素分割的结果是覆盖整个图像的子区域的集合，或从图像中提取的轮廓线的集合。 超像素的数量越少，丧失的细节特征越多，但仍然能基本保留主要区域之间的边界及图像的基本拓扑。

常用的超像素分割方法有：简单线性迭代聚类（Simple Linear Iterative Clustering，SLIC）、能量驱动采样（Super-pixels Extracted via Energy-Driven Sampling，SEEDS）和线性谱聚类（Linear Spectral Clustering，LSC）。SLIC超像素算法是对上节讨论的k均值算法的一种改进，通常使用（但不限于）包含三个颜色分量和两个空间坐标的五维向量。

OpenCV 在 ximgproc 模块提供了ximgproc.createSuperpixelSLIC函数实现SLIC算法。需要编译opencv_contrib模块，可以参考VS2019编译Opencv4.6.0GPU版本，记得勾选ximgproc。

示例 SLIC超像素区域分割

1. 冈萨雷斯《数字图像处理（第四版）》Chapter 10（所有图片可在链接中下载）

2. 【youcans 的 OpenCV 例程200篇】171.SLIC 超像素区域分割

3. 当我们在谈论kmeans（3）