GraphCut

小象实战讲义 · 基于深度学习的计算机视觉

在图像分割领域，我们已学习了基于阈值、边缘和区域的方法。本节将介绍一种基于图论的经典分割算法——GraphCut。它将图像分割问题巧妙地转化为图论中的最小割问题，通过定义能量函数并求解其最小值，实现前景与背景的分离。这种方法在深度学习兴起前，曾是交互式分割的重要工具，其思想对后续算法仍有深远影响。

💡 核心导读

• 图论映射：将图像像素映射为带权无向图的顶点，像素间的相似度作为边的权重。
• 能量最小化：分割问题转化为求解能量函数的最小值，能量函数由区域项和边界项构成。
• 交互式分割：算法需要用户提供少量前景和背景的“种子点”作为先验知识。
• 最小割求解：通过求解图的最小割，将图划分为前景和背景两个子集，完成分割。

从图像到图：问题的转化

GraphCut 是一种基于图论的图像分割方法。其核心思想是将图像分割问题转化为一个图论中的最小割问题。

首先，将待分割的图像映射为一个带权重的无向图 G = (V, E)。其中：

• 顶点 (V)：图中的每个节点对应图像中的一个像素。
• 边 (E)：图中连接顶点的边分为两类：
  1. 邻域边：连接相邻的像素顶点（例如，采用4邻域或8邻域连接）。每条边上的权重 w(p, q) 代表了相邻像素 p 和 q 之间的非负相似度。相似度可以根据像素的灰度、颜色或纹理特征来计算，越相似则权重越大。
  2. 终端边：除了像素顶点，图中还有两个特殊的终端顶点，分别代表前景（Source, S） 和背景（Sink, T）。每个像素顶点 p 都分别与 S 和 T 相连，形成两条边。

这样，一张图像就被构造成了一个包含两类顶点和两类边的复杂网络。

所谓“割”，是指一个边的集合 C，如果将这些边从图中移除，会导致整个图被分割成两个互不连通的子集：一个包含 S，另一个包含 T。一个“割”的代价是这个集合中所有边权重之和。GraphCut 的目标就是找到所有可能的割中，代价最小的那个，即“最小割”。根据最大流最小割定理，最小割问题可以通过最大流算法高效求解。

找到最小割后，与 S 相连的像素被标记为前景，与 T 相连的像素被标记为背景，从而完成分割。下图直观展示了这一映射与分割过程：

图像像素平面：        对应的图结构：
┌───┬───┬───┐        S (前景源点)
│ p │ q │   │         ↑  ↑  ↑ ...
├───┼───┼───┤        │  │  │
│   │   │   │        p──q── ... (邻域边)
└───┴───┴───┘        ↓  ↓  ↓ ...
                      T (背景汇点)

一个可能的“割”（虚线）：
S ----////---- p ---- q ---- ... (割断了S-p和p-q边)
        C
T ------------ p ---- q ---- ... (p与T仍相连)
割断后，p与S断开，与T相连 => p被分为背景。

能量函数的定义

如何将我们对“好的分割”的期望，用数学语言描述并融入到最小割的框架中呢？GraphCut 使用了一个基于能量最小化的模型。一个好的分割对应一个能量较低的状态。

能量函数 E(A) 由两部分组成：

$$E(A) = \lambda \cdot R(A) + B(A)$$

其中 A 代表一种分割方案（即每个像素的标签分配），λ 是一个平衡两项权重的系数。

区域项 R(A)：数据拟合惩罚

区域项 R(A) 衡量的是单个像素被赋予某个标签（前景或背景）的代价。它的思想是：一个像素的颜色如果更接近已知的前景颜色分布，那么它被分为前景的代价就应该小；反之，被分为背景的代价就大。

设 p 为某个像素，lp 为其标签（0 代表背景，1 代表前景）。区域项通常定义为：

$$R(A) = \sum_{p \in P} R_p(l_p)$$

$$R_p(1) = -\ln \Pr(I_p | \text{前景模型})$$ $$R_p(0) = -\ln \Pr(I_p | \text{背景模型})$$

这里 I_p 是像素 p 的颜色值。Pr(I_p | model) 表示该颜色值属于某个颜色模型的概率。概率越高，负对数就越小，惩罚也就越小。因此，算法会倾向于将像素分配给其颜色概率更高的那个类别。

在实际的交互式分割中，前景和背景的颜色模型（例如，颜色直方图或高斯混合模型）是由用户提供的“种子点”来初始化的。

边界项 B(A)：分割边界平滑惩罚

边界项 B(A) 衡量的是相邻像素之间标签不一致的代价。它的目标是鼓励分割边界沿着图像中颜色、纹理等特征变化剧烈的地方通过，从而使分割结果在视觉上更平滑、更合理。

边界项通常定义为：

$$B(A) = \sum_{\lbrace p, q\rbrace \in N} B_{\lbrace p, q\rbrace } \cdot \delta(l_p \neq l_q)$$

$$\delta(l_p \neq l_q) = \begin{cases} 1 & \text{if } l_p \neq l_q \\ 0 & \text{if } l_p = l_q \end{cases}$$

$$B_{\lbrace p, q\rbrace } \propto \exp \left( -\frac{(I_p - I_q)^2}{2\sigma^2} \right) \cdot \frac{1}{\text{dist}(p, q)}$$

其中：

• N 是所有相邻像素对的集合。
• δ(·) 是指示函数，仅当相邻像素 p 和 q 被赋予不同标签时，惩罚项才被激活。
• B_{p,q} 是惩罚强度，它取决于像素 p 和 q 的相似度。
  • (I_p - I_q)^2：像素间的颜色差异。差异越小（越相似），exp 值越大，惩罚强度 B 越大。这意味着分割边界穿过了颜色均匀的区域，这是不希望的，因此要施以重罚。
  • dist(p, q)：像素间的空间距离（通常为1）。距离越近，惩罚强度越大。
  • σ 是一个常数，用于控制颜色差异的敏感度。

边界项的直观理解：如果两个相邻像素颜色非常接近，我们期望它们属于同一物体（前景或背景），因此给它们分配不同标签的代价很高。如果它们颜色差异很大，那它们很可能处于物体的边缘，此时分配不同标签的代价就很小。

权重的计算与算法流程

综合以上，我们可以总结出图中各类边的权重赋值规则。设 K 为一个极大的数（如所有边权重之和加1），代表“绝对不可切断”。

基于上述权重构建好图之后，GraphCut 的标准算法流程如下：

1. 用户交互：用户在图像上标记少量绝对属于前景和背景的种子点。
2. 模型初始化：根据种子点的颜色，建立前景和背景的颜色概率模型（如直方图）。
3. 建图：根据当前颜色模型和上述规则，为图中所有边计算权重。
4. 求解最小割：在构建的图上运行最大流/最小割算法（如Boykov-Kolmogorov算法）。
5. 分配标签：根据最小割的结果，将所有与 S 连通的像素标记为前景，其余标记为背景。
6. （可选）迭代优化：在更高级的变体（如GrabCut）中，会用新的分割结果更新颜色模型，然后回到步骤3迭代优化，直到能量函数收敛。

下面，我们用一个极度简化的数值例子来演示权重的计算思想。假设我们有一张2x2的灰度图像，用户指定了左上角为前景(S)，右下角为背景(T)。

import numpy as np

# 定义一个极大的数 K
K = 1e6

# 假设的2x2图像灰度值
image = np.array([[100, 120],
                  [110, 50]], dtype=np.float32)

# 用户交互：种子点 (行, 列)
foreground_seed = (0, 0)  # 左上角，值100
background_seed = (1, 1)  # 右下角，值50

# 简化计算：区域项 R(p) 用灰度值到种子点灰度差的负指数模拟概率
# 前景模型“中心”假设为100，背景模型“中心”假设为50
def simple_likelihood(pixel_val, model_center):
    # 简化：相似度与差值的负指数成正比
    diff = abs(pixel_val - model_center)
    return np.exp(-diff / 20.0)  # 20是随意选的尺度参数

# 计算每个像素属于前景(F)和背景(B)的“概率”（未归一化）
prob_fg = np.zeros_like(image)
prob_bg = np.zeros_like(image)
for i in range(image.shape[0]):
    for j in range(image.shape[1]):
        prob_fg[i, j] = simple_likelihood(image[i, j], 100) # 前景中心100
        prob_bg[i, j] = simple_likelihood(image[i, j], 50)  # 背景中心50

print("像素灰度矩阵:")
print(image)
print("\n像素属于前景的‘似然’值 (基于种子点(100)):")
print(prob_fg)
print("\n像素属于背景的‘似然’值 (基于种子点(50)):")
print(prob_bg)

# 计算区域项惩罚 R(p) = -ln(probability)，避免log(0)，加小常数
epsilon = 1e-10
R_fg = -np.log(prob_fg + epsilon)  # Rp(1)
R_bg = -np.log(prob_bg + epsilon)  # Rp(0)

print("\n区域项惩罚 R_fg (标签为前景的代价):")
print(R_fg)
print("\n区域项惩罚 R_bg (标签为背景的代价):")
print(R_bg)

# 设定平衡参数 λ
lambda_val = 1.0

# 根据规则计算权重（仅示意几个关键边）
print("\n--- 关键边权重计算示意 ---")
# 1. 种子点相关的终端边
print(f"边 [前景种子(0,0) -> S]: w = {K} (极大，不可割)")
print(f"边 [前景种子(0,0) -> T]: w = {0} (应割断)")
print(f"边 [背景种子(1,1) -> S]: w = {0} (应割断)")
print(f"边 [背景种子(1,1) -> T]: w = {K} (极大，不可割)")

# 2. 未知点 (0,1) 的终端边
p = (0, 1)
R_fg_val = R_fg[p]
R_bg_val = R_bg[p]
print(f"\n未知像素 (0,1) 灰度={image[p]}:")
print(f"  边 [p -> S]: w = λ * R_bg(p) = {lambda_val} * {R_bg_val:.4f} = {lambda_val * R_bg_val:.4f}")
print(f"  边 [p -> T]: w = λ * R_fg(p) = {lambda_val} * {R_fg_val:.4f} = {lambda_val * R_fg_val:.4f}")
if R_fg_val < R_bg_val:
    print(f"  分析：R_fg({R_fg_val:.4f}) < R_bg({R_bg_val:.4f})，说明该像素更可能属于前景。")
    print(f"        因此边[p->T]权重({lambda_val * R_fg_val:.4f})较小，在最小割中更可能被切断，从而使p连接S（前景）。")
else:
    print(f"  分析：R_bg({R_bg_val:.4f}) < R_fg({R_fg_val:.4f})，说明该像素更可能属于背景。")
    print(f"        因此边[p->S]权重({lambda_val * R_bg_val:.4f})较小，在最小割中更可能被切断，从而使p连接T（背景）。")

# 3. 邻域边权重 B{p,q} 计算示意 (以(0,0)和(0,1)为例)
p_val = image[0,0]
q_val = image[0,1]
color_diff = abs(p_val - q_val)
sigma = 30.0  # 假设参数
B_pq = np.exp(- (color_diff ** 2) / (2 * sigma ** 2))
print(f"\n邻域边 [(0,0)-{p_val} <-> (0,1)-{q_val}]:")
print(f"  颜色差 = {color_diff}")
print(f"  边界项权重 B = exp(-({color_diff}^2)/(2*{sigma}^2)) = {B_pq:.4f}")
print(f"  意义：若两像素最终标签不同，割断此边将付出 {B_pq:.4f} 的代价。")

像素灰度矩阵:
[[100. 120.]
 [110.  50.]]

像素属于前景的‘似然’值 (基于种子点(100)):
[[1.         0.36787942]
 [0.60653067 0.08208501]]

像素属于背景的‘似然’值 (基于种子点(50)):
[[0.08208501 0.03019738]
 [0.04978707 1.        ]]

区域项惩罚 R_fg (标签为前景的代价):
[[-0.   1. ]
 [ 0.5  2.5]]

区域项惩罚 R_bg (标签为背景的代价):
[[ 2.5  3.5]
 [ 3.  -0. ]]

--- 关键边权重计算示意 ---
边 [前景种子(0,0) -> S]: w = 1000000.0 (极大，不可割)
边 [前景种子(0,0) -> T]: w = 0 (应割断)
边 [背景种子(1,1) -> S]: w = 0 (应割断)
边 [背景种子(1,1) -> T]: w = 1000000.0 (极大，不可割)

未知像素 (0,1) 灰度=120.0:
  边 [p -> S]: w = λ * R_bg(p) = 1.0 * 3.5000 = 3.5000
  边 [p -> T]: w = λ * R_fg(p) = 1.0 * 1.0000 = 1.0000
  分析：R_fg(1.0000) < R_bg(3.5000)，说明该像素更可能属于前景。
        因此边[p->T]权重(1.0000)较小，在最小割中更可能被切断，从而使p连接S（前景）。

邻域边 [(0,0)-100.0 <-> (0,1)-120.0]:
  颜色差 = 20.0
  边界项权重 B = exp(-(20.0^2)/(2*30.0^2)) = 0.8007
  意义：若两像素最终标签不同，割断此边将付出 0.8007 的代价。

通过这个例子可以看到，权重的计算如何将我们对颜色相似性、用户交互先验的期望编码到图结构中，最终的最小割求解过程就是在所有可能的“分割方案”中，找到总权重代价最小的那一个。

📝 动手练一练

1. 概念辨析：GraphCut 能量函数中的“区域项”和“边界项”分别主要影响分割结果的哪些方面？如果一幅图像的前景和背景颜色区分非常明显，但各自内部纹理复杂，你认为应该调高 λ 来侧重区域项，还是调低 λ 来侧重边界项？为什么？

2. 权重计算：假设在构建图时，对于用户明确标记为背景的种子像素 p，它连接到源点 S（前景）的边权重被设置为 0，而连接到汇点 T（背景）的边权重被设置为一个极大的数 K。请从最小割的角度解释，为什么这样设置能保证该像素在最终分割结果中一定被标记为背景？

本章小结

本节我们深入探讨了基于图论的经典分割算法——GraphCut。它将图像分割转化为图的最小割问题，通过精心设计的能量函数（区域项与边界项）来形式化我们对“好分割”的定义，并利用用户提供的少量交互信息作为先验，最终通过最大流/最小割算法求得全局能量最优的分割结果。

GraphCut 及其改进算法 GrabCut 在深度学习普及之前，是交互式图像分割领域的标杆。其核心的“能量最小化”思想和将视觉问题转化为图优化问题的思路，至今仍在许多计算机视觉任务中有所体现。

📋 行动清单

• 理解映射关系：能够清晰复述如何将一幅图像及其像素关系映射为带权无向图，并说明两类顶点和两类边的作用。
• 掌握能量函数：能够写出 GraphCut 的能量函数公式，并解释区域项和边界项每一项的物理意义及计算方法。
• 分析权重设置：给定一个简单的图像和用户交互示例，能够推导出图中关键边（种子点终端边、未知点终端边、邻域边）的权重设置逻辑。

—— 小象教研组