基于图割（Graph Cut）的图像分割算法

题目描述
图像分割是计算机视觉中的基础任务，旨在将图像划分为多个有意义的区域。基于图割的图像分割算法将图像建模为一个图结构，通过最小化一个能量函数来实现分割，从而将像素分配为“前景”或“背景”。这种方法特别适合交互式分割（用户提供少量标记），例如在Photoshop等工具中提取物体。核心思想是将分割问题转化为图上的最小割问题，利用最大流最小割定理求解。

解题过程

1. 图的构建：

   • 将图像中的每个像素视为图的一个节点。
   • 添加两个特殊节点：源点（Source，代表前景）和汇点（Sink，代表背景）。
   • 图的边分为两类：
     • t-链路（终端链路）：连接每个像素节点与源点/汇点，权重反映像素属于前景或背景的概率（基于颜色、纹理或用户输入）。
     • n-链路（邻域链路）：连接相邻像素节点（如4邻域或8邻域），权重反映像素间的相似性，相似度越高则边权重越大，切割代价越高（鼓励相似像素归属同一区域）。

2. 能量函数定义：

   • 目标是最小化能量函数 \(E(A) = \lambda R(A) + B(A)\)，其中：
     • \(A\) 是分割结果（每个像素的标签）。
     • \(R(A)\) 是区域项，衡量像素与前景/背景模型的匹配程度（通过t-链路权重实现）。
     • \(B(A)\) 是边界项，惩罚相邻像素标签不一致的情况（通过n-链路权重实现）。
     • \(\lambda\) 是平衡两项的超参数。

3. 最小割求解：

   • 使用最大流算法（如Ford-Fulkerson或Push-Relabel）在图上计算最小割。
   • 最小割将图分为两部分：与源点相连的像素归为前景，与汇点相连的归为背景。

4. 迭代优化（可选）：

   • 若分割结果不理想，可更新前景/背景模型（例如用当前结果重新估计颜色分布），重新构建图并迭代求解，直到收敛。

关键点：图割通过结合局部边界平滑性约束和全局区域一致性，实现鲁棒分割。其优势在于能保证找到能量函数的全局最优解（对于子模能量函数）。