分割与分组

发表于 2026-03-14 Waline：阅读次数：本文字数： 5.5k 阅读时长 ≈ 20 分钟

上一章讨论的边缘检测关注的是像素之间的不连续——哪里发生了变化。本章转向互补的问题：哪些像素属于同一组？这就是图像分割（Image Segmentation）——将图像的像素划分为若干有意义的区域。

Max Wertheimer 在 1923 年写道：「我站在窗前看到房子、树和天空。理论上我可以说有 327 种亮度和色彩。但我看到的是 327 吗？不，我看到的是天空、房子和树。」这正是分割要解决的问题：从像素级的「327 种亮度」中恢复出人类感知的「天空、房子和树」。

分组问题

自顶向下与自底向上

分割可以从两个方向进行。自顶向下（Top-down）方法利用对物体的先验知识——像素属于同一组是因为它们来自同一个物体。自底向上（Bottom-up）方法则纯粹基于视觉相似性——像素属于同一组是因为它们看起来相似（颜色、亮度、纹理等）。

本章主要讨论自底向上的方法。自底向上分割的困难在于：什么叫「有意义的区域」取决于具体应用。过分割（太多太碎的区域）和欠分割（把不同物体混在一起）之间没有普适的最优解。

分割的用途

分割不一定是最终目标，更常见的是作为中间步骤服务于其他任务：

提高效率：将像素聚合为超像素（Superpixel），后续处理以超像素而非单个像素为单位，计算量大幅减少
更好的特征：一个分割区域比固定大小的矩形窗口更能适应物体的形状
物体候选（Object Proposals）：生成一组可能包含物体的区域，作为检测器的输入
直接目标：交互式分割（如 GrabCut）中，分割本身就是用户想要的结果

格式塔理论

在提出算法之前，先看看人类视觉系统是如何做分组的。20 世纪初德国心理学家提出的格式塔理论（Gestalt Theory）给出了一系列直觉原则——「整体大于部分之和」，部分之间的关系能产生新的属性。

格式塔分组因素

邻近性（Proximity）：空间上接近的元素倾向于被分为一组
相似性（Similarity）：颜色、形状、大小相似的元素倾向于被分为一组
共同命运（Common Fate）：一起运动的元素被视为一组
连续性（Continuity）：沿平滑曲线排列的元素倾向于被分为一组
封闭性（Closure）：构成封闭形状的元素更容易被感知为一个整体
共同区域（Common Region）：位于同一封闭区域内的元素倾向于被分为一组
对称性（Symmetry）和平行性（Parallelism）：也促进分组

这些原则的一个经典演示是「隐藏」在斑点中的达尔马提亚犬——你的视觉系统能从看似随机的黑白斑点中自动「找到」狗的轮廓。这是邻近性、连续性和封闭性共同作用的结果。

格式塔原则提供了很好的直觉，但将它们翻译成精确的算法非常困难。例如「连续性」需要全局推理——一条被遮挡的曲线在遮挡物背后是否继续延伸，取决于整个场景的解读。

分割作为聚类

特征空间的选择

自底向上分割的核心思路是：将每个像素映射到一个特征空间（Feature Space）中的一个点，然后在特征空间中做聚类——特征接近的像素分为一组。

特征空间的选择决定了分割的行为：

亮度（1 维）：在亮度直方图中找聚类。但仅靠亮度聚类的区域不一定在空间上连通——两只黑色的眼睛可能被聚到同一类，即使它们在空间上相隔很远。

颜色（3 维 RGB 或 Lab）：在颜色空间中聚类。能区分不同颜色的区域，但颜色相同的不同物体（如两片树叶）仍会被混在一起。

亮度 + 位置（3 维）：将像素坐标 $(x, y)$ 也纳入特征向量，这样即使两个区域颜色相同但空间上分开，也能被区分。举个具体的例子：一张熊猫照片中，两只眼睛的亮度几乎相同——仅用亮度聚类会把它们归为同一组。但如果加入位置信息，左眼和右眼在 $(x, y)$ 坐标上相距很远，特征空间中它们就被自然分开了。这同时编码了相似性和邻近性——正是格式塔原则中最基本的两个因素。

但仅靠亮度、颜色和位置还不够——当物体和背景的颜色相似时（如落叶中的鹿、波点裙与斑点背景），这些特征都无法区分它们。

纹理（高维）：用滤波器组对图像提取响应，通过 $k$ -means 聚类得到纹理子（Texton），再用 texton 直方图描述每个像素的局部纹理特征。具体来说：对图像应用一组滤波器（如 24 个不同尺度和方向的 Gabor 滤波器），每个像素得到一个 24 维的响应向量；对所有响应向量做 $k$ -means 聚类得到 $k$ 个 texton；然后在每个像素的邻域内统计各 texton 出现的频率作为纹理描述。

K-Means 聚类

$K$ -means 是最简单的聚类算法。它最小化所有点到其所属聚类中心的距离平方和：

$J = \sum_{i=1}^{K} \sum_{\bm{x} \in C_i} \|\bm{x} - \bm{c}_i\|^2$

但直接优化 $J$ 是 NP-hard 的（即使 $K = 2$ ），所以 $K$ -means 用一种贪心的交替策略：

分配（Assignment）：将每个数据点分配给距离最近的聚类中心
更新（Update）：重新计算每个聚类的中心为其成员的均值

这两步的交替对应一个「鸡生蛋」问题：如果知道中心，就能分配点；如果知道分配，就能算中心。 $K$ -means 从随机初始化的中心出发，交替执行直到收敛。

$K$ -means 总是收敛，但只收敛到局部最优——不同的初始化可能得到完全不同的结果。常用的策略是多次随机初始化，取目标函数最小的那次。

from sklearn.cluster import KMeans
import numpy as np

# 将图像展平为 (N, 特征维度) 的矩阵
pixels = img.reshape(-1, 3)  # RGB 3维
kmeans = KMeans(n_clusters=K, n_init=10).fit(pixels)
labels = kmeans.labels_.reshape(img.shape[:2])  # 恢复为 H×W

优点	缺点
简单快速	需要预设 $K$
保证收敛	对初始化敏感
	对异常值敏感
	只能检测球形聚类

高斯混合模型与 EM 算法

$K$ -means 将每个点硬分配给一个聚类，无法回答「这个点有多大概率属于聚类 $m$ 」。高斯混合模型（Gaussian Mixture Model, GMM）用概率的方式解决这个问题：假设数据由 $M$ 个高斯分布混合生成，每个高斯对应一个聚类。

$p(x_n \mid \bm{\mu}, \bm{\sigma}^2, \bm{\pi}) = \sum_m \pi_m \cdot \frac{1}{\sqrt{2\pi\sigma_m^2}} \exp\!\left(-\frac{(x_n - \mu_m)^2}{2\sigma_m^2}\right)$

其中 $\pi_m$ 是第 $m$ 个分量的混合权重（ $\sum_m \pi_m = 1$ ）， $\mu_m$ 和 $\sigma_m^2$ 分别是均值和方差。一个重要的理论性质是：只要分量数足够多，GMM 可以逼近任意概率密度函数——这使它成为通用的密度估计器。

GMM 的参数通过期望最大化（Expectation-Maximization, EM）算法估计。EM 本身是一个通用框架，适用于任何含隐变量的概率模型（不限于 GMM）。

EM 要最大化的是观测数据的对数似然：

$\hat{\theta} = \operatorname{argmax}_\theta \log \sum_{\bm{z}} p(\bm{x}, \bm{z} \mid \theta)$

困难在于 $\log$ 里面有一个求和——对数和之和无法分解为各分量的独立优化。这里隐藏着一个关键的数学结构：将求和改写为期望的形式 $\log \sum_{\bm{z}} q(\bm{z}) \cdot \frac{p(\bm{x}, \bm{z} \mid \theta)}{q(\bm{z})}$ ，这是一个对数期望（log of expectation）。直接优化它很难，但 Jensen 不等式告诉我们：对凹函数 $f$ ， $f(\mathbb{E}[X]) \ge \mathbb{E}[f(X)]$ 。于是可以将「对数期望」松弛为「期望对数」——后者容易优化。

EM 正是利用这个下界交替进行两步：

E 步：固定参数 $\theta^{(t)}$ ，计算隐变量的后验分布 $p(\bm{z} \mid \bm{x}, \theta^{(t)})$ ，用它作为 $q(\bm{z})$ 来收紧下界。

M 步：固定 $q(\bm{z})$ ，最大化期望对数似然：

$\theta^{(t+1)} = \operatorname{argmax}_\theta \sum_{\bm{z}} \log\bigl(p(\bm{x}, \bm{z} \mid \theta)\bigr) \, p(\bm{z} \mid \bm{x}, \theta^{(t)})$

每一步都保证不降低对数似然，因此算法单调收敛。

具体到 GMM：

E 步：用当前参数估计每个数据点属于每个分量的后验概率（「责任」 $\alpha_{nm}$ ）。

M 步：用加权后的数据点更新每个分量的参数：

$\hat{\mu}_m = \frac{\sum_n \alpha_{nm} x_n}{\sum_n \alpha_{nm}}, \quad \hat{\sigma}_m^2 = \frac{\sum_n \alpha_{nm} (x_n - \hat{\mu}_m)^2}{\sum_n \alpha_{nm}}, \quad \hat{\pi}_m = \frac{\sum_n \alpha_{nm}}{N}$

EM 与 $K$ -means 的关系可以这样理解： $K$ -means 是 EM 的特殊情况——当所有高斯分量的方差相同且趋近于零时，软分配退化为硬分配。

GMM vs K-means

GMM 的优势在于：(1) 给出概率而非硬标签——边界处的像素有合理的不确定性；(2) 高斯分量可以有不同的方差和形状——能捕获椭圆形的聚类而非只有球形；(3) 作为生成模型，可以预测新数据点的概率；(4) 存储相对紧凑（只需保存每个分量的参数）。

代价也更多：(1) 和 $K$ -means 一样容易陷入局部最优——常用的实践是先跑几轮 $K$ -means 作为初始化；(2) 需要选择分量数（可用 AIC/BIC 等模型选择准则，或更灵活的 Dirichlet 过程混合模型）；(3) 高维时容易出现数值问题（协方差矩阵接近奇异）。

EM 的适用范围

EM 不仅仅用于 GMM。作为通用的隐变量优化框架，它适用于任何聚类问题、模型估计问题、缺失数据问题、异常值检测，以及各类分割任务（基于颜色、运动、前景/背景分离等）。

Mean-Shift 分割

核密度估计

$K$ -means 和 GMM 都对数据的分布做了参数假设（球形聚类或高斯混合）。均值漂移（Mean-Shift）则走了一条非参数路线：直接从数据中估计概率密度函数，然后找到密度的模（Mode，即局部极大值点），将收敛到同一个模的数据点归为一类。

密度估计使用核密度估计（Kernel Density Estimation, KDE）：在每个数据点处放一个核函数（如高斯核），将所有核函数叠加：

$\hat{f}(\bm{x}) = \frac{1}{nh^d} \sum_{i=1}^{n} K\!\left(\frac{\bm{x} - \bm{x}_i}{h}\right)$

其中 $h$ 是带宽（Bandwidth），控制核的宽度， $d$ 是数据的维度。带宽越大，密度估计越平滑，找到的模越少（大块分割）；带宽越小，保留的细节越多（碎片分割）——与高斯滤波中 $\sigma$ 的作用类似。

Mean-Shift 算法

找密度的模就是找 $\nabla \hat{f}(\bm{x}) = 0$ 的点——梯度上升法可以做到。对核密度估计求梯度后，可以证明梯度方向正比于一个均值漂移向量：

$\bm{m}(\bm{x}) = \frac{\sum_{i=1}^{n} \bm{x}_i \, g\!\left(\left\|\frac{\bm{x} - \bm{x}_i}{h}\right\|^2\right)}{\sum_{i=1}^{n} g\!\left(\left\|\frac{\bm{x} - \bm{x}_i}{h}\right\|^2\right)} - \bm{x}$

其中 $g(x) = -k'(x)$ 是核的导数。 $\bm{m}(\bm{x})$ 指向局部密度增大最快的方向——直觉上，它是以 $\bm{x}$ 为中心的窗口内所有点的加权平均位置减去当前位置。窗口不断朝着「人多的方向」移动，最终停在密度最高的地方。

Mean-Shift 聚类的完整流程：

选择核函数和带宽
对每个数据点，以该点为起点执行 mean-shift 迭代直到收敛到某个模
将收敛到同一个模（或距离足够近的模）的所有数据点归为一类

收敛到同一模的所有起始点构成该模的吸引域（Attraction Basin）——每个吸引域就是一个聚类。

用于图像分割

将 mean-shift 用于分割时，特征向量通常包含颜色和位置信息，分别用 $K_f$ （特征带宽）和 $K_s$ （空间带宽）控制两个维度的平滑程度。算法对每个像素执行 mean-shift 后，合并距离小于带宽的模。

优点	缺点
通用性好	需要选择带宽
区域数目和形状自动确定	不适合高维特征
对异常值鲁棒	计算量大
可用于追踪等其他任务

Mean-shift 的计算瓶颈在于：每次迭代都需要计算当前点与所有数据点的距离。对于图像分割，一张 $320 \times 240$ 的图像就有 76800 个数据点。常用的加速手段包括：

分箱估计（Binned Estimation）：将空间划分为网格，每个网格内的点用中心点和总质量代替
快速邻居搜索：用 k-d 树或近似最近邻加速窗口内的数据查找
并行更新：每次迭代同时更新所有窗口（而非逐个），加快收敛
自适应带宽：用 kNN 确定每个点的局部带宽，自动适应密度变化

归一化切割

前面介绍的 $K$ -means、GMM 和 mean-shift 都是在特征空间中对像素做聚类，隐含地假设聚类的形状（球形、椭圆形或通过密度定义）。但图像分割还有另一种完全不同的思路：把图像看成一张图，用图论的工具来划分。

图的视角

另一种分割思路是把图像看作图（Graph）：每个像素是一个节点，像素之间的相似度是边的权重。分割变成了图的划分问题——将图切成几块，使得切断的边的权重之和尽可能小（组间相似度低），同时组内的边权重尽可能大（组内相似度高）。

像素 $i$ 和 $j$ 之间的亲和度（Affinity）通常用高斯函数衡量：

$w_{ij} = \exp\!\left(-\frac{\|\bm{x}_i - \bm{x}_j\|^2}{2\sigma_d^2}\right)$

$\sigma$ 越大，越远的像素也有较高的亲和度（倾向于大块分割）； $\sigma$ 越小，只有紧挨着的像素才有显著亲和度（倾向于碎片分割）。

最小切割的问题

最直接的想法是找到最小切割（Minimum Cut）： $\text{cut}(A, B) = \sum_{p \in A, q \in B} w_{pq}$ 。但最小切割有一个严重缺陷——它倾向于把单个像素或很小的区域切出来（因为切掉一个孤立点只需要断开很少的边），而非做出有意义的均衡分割。

归一化切割

归一化切割（Normalized Cut, NCut）通过用每个子集的「体积」来归一化，解决了这个问题：

$\text{NCut}(A, B) = \frac{\text{cut}(A, B)}{\text{vol}(A)} + \frac{\text{cut}(A, B)}{\text{vol}(B)}$

其中 $\text{vol}(A) = \sum_{i \in A} d_i$ ， $d_i = \sum_j w_{ij}$ 是节点 $i$ 的度。

直觉上，除以 $\text{vol}(A)$ 惩罚了「从大块上切下一小片」的行为——小块的 volume 小，除完后 NCut 值变大。可以证明 NCut 在 $\text{vol}(A) = \text{vol}(B)$ 时最小，因此它鼓励均衡的切割。

精确求解 NCut 是 NP-hard 的。松弛为连续优化后，问题转化为一个广义特征值问题：

$(\bm{D} - \bm{W})\bm{y} = \lambda \bm{D}\bm{y}$

其中 $\bm{W}$ 是亲和度矩阵， $\bm{D}$ 是度矩阵。取第二小特征值对应的特征向量（Fiedler 向量），对其做阈值化即可将图二分。递归地对子图重复这个过程，可以得到多个分割区域。

NCut 的局限

NCut 生成的区域比较规整，但需要预设区域数目，且存储和计算开销大（需要构建和分解大型亲和度矩阵）。它也有倾向于生成大小相近区域的偏置。

过分割与超像素

到此为止，我们讨论的方法（ $K$ -means、GMM、mean-shift、NCut）都试图找到「正确」的分割。但在实践中，完美的分割往往不可能也不必要——更实用的策略是先把图像切成大量小区域（每个区域保证落在某个物体内部），然后让后续的高层算法来决定哪些区域属于同一个物体。这种过分割（Oversegmentation）产生的小区域就是超像素（Superpixel）。

分水岭算法

分水岭（Watershed）算法借用了地形学的隐喻：把梯度图看作地形表面（梯度大 = 高山，梯度小 = 低谷），从所有局部最小值处开始「灌水」。随着水位上升，不同最小值的水域逐渐扩张；两个水域相遇的地方就是分水岭——即分割边界。

实际实现用优先队列：

将所有局部最小值作为种子区域
将种子的邻居按梯度值加入优先队列
取出队首像素，若其已标记的邻居标签一致则赋予该标签，并将其未标记邻居入队
重复直到队列为空——剩余的未标记像素即为边界

直接在梯度图上做分水岭通常会过度碎片化——每个微小的噪声凹坑都会产生一个区域。解决方法是先用高斯或中值滤波器平滑梯度图，减少虚假的局部最小值。

分水岭算法非常快——对一张 $512 \times 512$ 的图像通常不到 1 秒，因为优先队列保证了每个像素只被处理一次。但它的质量完全取决于输入的「地形表面」：如果用原始梯度图，结果往往过于碎碎片；如果用 Pb 边界检测器（不做非极大值抑制）的输出作为表面，效果会好得多。

分水岭也可以和上一章的 Pb 边界检测器结合：用 Pb 的输出作为「地形表面」，效果远好于原始梯度。这种 Pb + 分水岭的层次化分割（OWT-UCM）是传统方法中的最佳方案之一。

Felzenszwalb-Huttenlocher 方法

这是一种基于图的贪心合并方法。核心思想是：如果两个区域之间的最小边权重小于两个区域各自内部的最大边权重，就合并它们。形式化地：

$\text{Merge}(C_1, C_2) = \begin{cases} \text{True} & \text{if } \text{dif}(C_1, C_2) < \text{in}(C_1, C_2) \\ \text{False} & \text{otherwise} \end{cases}$

其中 $\text{dif}(C_1, C_2) = \min_{v_i \in C_1, v_j \in C_2, (v_i, v_j) \in E} w(v_i, v_j)$ 是连接两个分量的最小权重边， $\text{in}(C_1, C_2) = \min_{C \in \{C_1, C_2\}} \bigl[\max_{v_i, v_j \in C} w(v_i, v_j) + k/|C|\bigr]$ 是两个分量中内部最大权重边加上阈值的较小者。

参数 $k$ 控制分割的粗细： $k$ 越大，越容易合并，倾向于更大的区域；但 $k$ 并不直接设定区域的最小尺寸。

优点	缺点
能处理细长区域（不像 NCut 偏向均衡）	有时会生成形状奇怪的区域
速度快	偶尔会犯很大的错误（把不同物体合并）
容易控制分割粗细
同一结果中可包含大小不同的区域

SLIC 超像素

SLIC（Simple Linear Iterative Clustering）是目前最常用的超像素方法之一。它本质上是在 5 维空间（ $L^*a^*b^*$ 颜色 + $xy$ 位置）上的局部 $K$ -means：

在图像上均匀放置 $K$ 个初始聚类中心，间距 $S = \sqrt{N/K}$
将每个中心移到其 $3 \times 3$ 邻域内梯度最小的位置（避开边缘）
对每个像素，仅与 $2S$ 范围内的中心比较（而非所有中心），分配给最近的中心
重新计算聚类中心
迭代直到收敛

SLIC 的速度很快（ $320 \times 240$ 图像约 $\pu{0.36s}$ ），生成的超像素形状规整且贴合边界。

多重分割

没有一种分割方法能给出唯一「正确」的结果——不同的参数、不同的方法会产生不同的分割。与其执着于一种分割，不如生成多重分割（Multiple Segmentations）。

策略包括：

层次化分割：从过分割开始，逐步合并区域形成层次结构。最具代表性的是 Pb + 分水岭的层次化方案（OWT-UCM）：先用 Pb 边界检测器得到软边界图，在其上做定向分水岭变换得到初始过分割，然后按边界强度从弱到强逐步合并相邻区域。最终得到一张超度量轮廓图（Ultrametric Contour Map），对其在任意阈值处切一刀就得到一种分割粒度——阈值低则精细，阈值高则粗糙。在 BSDS 基准上，gPb-owt-ucm 取得了 $F = 0.73$ 的成绩，是传统方法中的最佳
变化参数：用不同的 $K$ （ $K$ -means）、 $\sigma$ （归一化切割）或带宽（mean-shift）运行多次
区域候选：从种子超像素出发，尝试分割出包含它的物体（Selective Search 将 Felzenszwalb-Huttenlocher 的结果作为起点，通过凝聚聚类逐步合并，生成多尺度的物体候选框）

方法对比

flowchart TD
    subgraph 基于聚类
        KM["K-Means<br/>简单快速<br/>需预设 K"]
        GMM["GMM + EM<br/>概率模型<br/>软分配"]
        MS["Mean-Shift<br/>非参数<br/>自动确定 K"]
    end
    subgraph 基于图
        NC["归一化切割<br/>谱方法<br/>均衡分割"]
    end
    subgraph 过分割
        WS["分水岭<br/>快速<br/>层次化"]
        FH["FH 方法<br/>贪心合并<br/>自适应大小"]
        SL["SLIC<br/>均匀规整<br/>最常用"]
    end

    KM --> GMM
    GMM -.-> MS
    NC
    WS --> FH --> SL

    classDef cluster fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef graph fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px
    classDef overseg fill:#fff3e0,stroke:#ef6c00,stroke-width:2px

    class KM,GMM,MS cluster
    class NC graph
    class WS,FH,SL overseg

方法	适用场景	关键参数
K-Means	简单快速的初步分割	$K$
GMM + EM	需要概率解释的分割	分量数 $M$
Mean-Shift	通用分割、追踪	带宽 $h$
归一化切割	需要规整区域的过分割	区域数、 $\sigma$
分水岭	超像素、层次化分割	预平滑程度
SLIC	高效超像素	超像素数 $K$