计算机视觉——九、图像分割
图像分割：无监督方法详解
图像分割是计算机视觉中的核心任务之一，目标是将图像划分为若干个具有语义或视觉一致性的区域。本讲聚焦于无监督图像分割，即无需人工标注的类别标签，仅利用图像自身的低层特征（如颜色、位置、纹理）将像素聚类成不同组。下面将系统介绍两类经典方法：基于k 均值的聚类分割和基于图割（Graph Cut）的分割算法。
一、基于 k 均值的图像分割
1.1 k 均值算法回顾
k 均值是一种迭代求解的聚类算法，将 n 个样本点划分到 k 个簇中，使得簇内样本点到簇中心的距离平方和最小。主要步骤：
初始化：随机选择 kk 个点作为初始簇中心。
分配：对每个样本，计算其到各个簇中心的距离，归入距离最近的簇。
更新：重新计算每个簇内所有样本的均值，作为新的簇中心。
重复：交替执行步骤2和3，直到簇中心不再变化或达到最大迭代次数。
1.2 以 RGB 值为特征对像素聚类
特征构建：将每个像素视为一个三维向量 (R,G,B)，取值范围通常为 0~255。
操作流程：
读入图像，获取所有像素的 RGB 值（例如，H×W的图像共有 N=H⋅W 个样本）。
设定 k 值（期望分割出的区域数），运行 k 均值算法。
将每个像素的最终簇标签映射为一个颜色（如该簇中心的 RGB 值），生成分割结果图。
示例：若 k=3，算法会将颜色相近的像素归为同一簇，比如天空的蓝色像素、草地的绿色像素、墙壁的白色像素各成一类。
1.3 纯 RGB 特征的问题与改进
问题：仅基于颜色，空间上不连续的像素可能因颜色相似而被划入同一簇，导致分割结果中出现大量离散的噪点或“椒盐效应”。例如，草地上的一片落叶（绿色调）可能被错误地并入草地簇，但实际它应该属于前景物体。
改进方法：在 RGB 特征中纳入像素点的空间坐标(x,y)，形成五维特征向量 (R,G,B,x,y)。此时：
颜色相似但距离较远的像素会被分到不同簇。
空间邻近性促使产生连通、紧凑的分割区域。
实现注意事项：RGB 值与坐标的取值范围差异很大（颜色 0~255，坐标可能达到数百或上千），需要先对每一维进行归一化（例如缩放到 [0,1] 区间），否则坐标的数值主导距离计算，削弱颜色的作用。
二、基于图切割的图像分割
图割方法将图像建模为一个带权无向图 G=(V,E,W)，通过切割图中某些边将顶点集划分为若干子集，每个子集对应一个分割区域。
2.1 图的构建
顶点：每个像素 p 对应图中的一个节点 vp。
边及权重：
相邻像素（4邻域或8邻域）之间连接一条边，权重 wpq 度量两个像素的相似性，常用高斯函数
其中 Ip,Iq 为颜色向量，Xp,Xq为坐标向量，σ,σx 为控制衰减的参数。
2.2 最小割（Min Cut）算法
定义：一个割 C 将顶点集 V 划分为 A 和 B（A∪B=V,A∩B=∅），割的代价为连接 A 与 B 之间所有边的权重之和：
最小割：寻找一个割，使得 Cut(A,B)Cut(A,B) 最小。可通过最大流算法（如 Ford-Fulkerson）高效求解。
问题：最小割倾向于产生孤立的小区域（因为只切少数几条大权重边，代价很小），无法获得全局语义上均衡的分割。
2.3 归一化割（Normalized Cut, Ncut）
为解决最小割的偏向性问题，Shi & Malik 提出了归一化割，不仅考虑被切边的权重，还考虑到每个子集内部的“连接强度”。
其中 assoc(A,V)=∑u∈A,v∈V表示子集 A 中所有顶点与全图所有顶点的边权之和（即 A 的“总连接度”）。分母越大，对该子集进行分割的惩罚越高，从而鼓励分割出的子集大小适中、内部紧密。
用二值向量表示分割：设 xx 是一个 n×1 的指示向量（n=∣V|），若顶点 vi 属于 A 则 xi=1，属于 B 则 xi=−1（或 0/1，具体形式依推导而定）。可以证明：
其中 W 是权重矩阵（Wij=wij），D 是对角矩阵，Dii=∑jWij（即顶点的度）。L=D−W称为图拉普拉斯矩阵。
求解：最小化 Ncut 等价于求解广义特征值问题：
因为 xx 中的元素被限制为二值（例如±1），这是一个 NP 难问题。实际求解时放松约束，允许 xx 取任意实数值。此时最小化瑞利熵
的解为第二小特征值 λ2λ2 对应的特征向量x2（最小特征值 λ1=0λ1=0 对应平凡解）。
从特征向量得到分割：
计算 x2，其每个分量对应一个顶点（像素）。
对 x2 中的值设定一个阈值（如 0 或中位数），大于阈值的顶点划分到 A，其余到 B。
得到两个子集后，可以递归地对每个子集继续应用 Ncut，直到达到所需的区域数量或满足停止条件。
三、总结与对比
| 方法 | 原理 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| k 均值 + 颜色 | 基于颜色向量的欧氏距离聚类 | 实现简单、速度快 | 忽略空间邻近性，易产生离散噪点 | 对区域连通性要求不高的颜色量化 |
| kk 均值 + 颜色+坐标 | 引入坐标信息，特征归一化 | 可得到空间上紧凑的区域 | 需调参（k 值、归一化尺度）；不适合形状复杂的目标 | 简单场景下的超像素预分割 |
| 最小割 | 图割最小化切割边权和 | 可精确求解 | 倾向分割出孤立小区域 | 几乎不单独使用，作为 Ncut 的基础 |
| 归一化割 (Ncut) | 归一化切割代价，平衡区域大小 | 全局最优性好，对噪声鲁棒 | 计算量大（特征分解）；对参数敏感（权重函数中的 σ） | 中等尺寸图像的多区域分割 |
选择建议：
快速原型、实时应用 → 使用带空间信息的 kk 均值。
追求高质量、非实时分割 → 优先考虑 Ncut 或其近似算法（如基于多尺度、超像素的 Ncut）。
理解这些基础算法后，可进一步学习现代深度学习方法（如 U-Net、Mask R-CNN），它们通常需要大量标注数据，但能在复杂场景中取得远优于无监督方法的性能。