基于Boykov算法的图割Graph Cut图像分割系统

资 源 简 介

本项目完整实现并优化了由Yuri Boykov和Vladimir Kolmogorov提出的经典Graph Cut（图割）算法。该算法是计算机视觉领域的里程碑作品，通过将图像分割问题建模为能量函数最小化问题，并利用图论中的最小割/最大流理论进行求解。 核心功能包括将二维或三维图像像素映射为图论中的节点，构建包含n-links（邻接边）和t-links（终端边）的复杂网络。其中n-links捕捉像素间的空间相干性信息，确保分割边缘的平滑度；t-links则结合用户提供的种子点信息或预定义的概率分布，反映像素

详 情 说 明

基于Boykov-Kolmogorov算法的Graph Cut图像分割系统

项目介绍

本项目是一个基于MATLAB环境实现的图像分割工具，核心采用经典的Boykov-Kolmogorov（BK）最大流/最小割算法。该算法将图像分割任务转化为图论中的能量最小化问题，通过构建包含源点（Source）和汇点（Sink）的网络图，寻找消耗能量最低的路径，从而实现精准的前景与背景分离。该实现方案在保证分割质量的同时，特别强调了交互式操作以及算法核心逻辑的直观展现。

功能特性

• 交互式种子点标注：支持用户通过鼠标实时在图像上标记前景（OBJ）和背景（BKG）种子点，作为分割的约束条件。
• 高效率图构建：利用MATLAB稀疏矩阵技术高效存储大规模像素节点及其邻接关系，显著降低内存占用。
• BK算法核心实现：完整包含了Boykov-Kolmogorov算法的三大关键阶段：生长阶段（Growth）、增广阶段（Augmentation）和收留阶段（Adoption）。
• 自定义能量参数：提供平滑项系数（Lambda）和灰度敏感度（Sigma）调节，适应不同对比度和纹理特征的图像。
• 能量验证机制：算法运行后自动计算数据项能量与平滑项能量的总和，并与最大流结果进行比对，确保数学逻辑的一致性。
• 多维结果展示：直观对比原始图像、二值化掩码以及最终提取出的前景目标。

系统要求

• 软件环境：MATLAB R2016b 或更高版本。
• 硬件建议：由于需要构建大规模稀疏矩阵，建议配备 8GB 以上内存以处理高分辨率图像。
• 依赖工具箱：主要基于MATLAB基础函数开发，不强制要求额外的图像处理工具箱。

实现逻辑说明

该系统通过以下流程完成图像分割：

1. 数据初始化与交互：读取彩色或灰色图像并归一化。通过交互界面获取用户定义的种子像素坐标，这些坐标将作为图论中的绝对约束。
2. T-links（终端边）权重计算：利用高斯分布模型对前景和背景种子点的灰度特性进行建模。计算每个像素归属于前景或背景的负对数似然概率，作为像素连接到源点（S）和汇点（T）的边容量。
3. N-links（邻接边）权重计算：基于像素间的空间距离和灰度差异计算邻域边的权重。差异越小的像素间权重越高，从而鼓励在平坦区域进行平滑分割，在梯度较大处产生边界。
4. 图结构组合：将数百万个像素节点、n-links 及 t-links 合并为一个巨大的权重矩阵。
5. BK最大流求解：

* 生长阶段：从源点和汇点分别生长搜索树，直至两棵树相遇发现增广路径。 * 增广阶段：在发现的路径上推送最大可能流量，更新残余图容量。 * 收留阶段：处理因容量枯竭而产生的孤儿节点，重新维护树的结构。

1. 结果转换：根据最终搜索树的状态，将所有与源点相连的节点标记为前景，其余标记为背景。

关键算法细节

1. 非对称图构建 系统在内部构建了一个包含 $N+2$ 个节点的图（$N$ 为像素总数）。通过稀疏阵列技术，仅存储非零权重的边，极大地提高了在大规模网络中搜索路径的速度。

2. 能量函数模型 分割目标的能量函数由两部分组成：

• 数据项（Data Term）：反映像素与已知种子点模型的匹配程度。
• 平滑项（Smoothness Term）：利用 $exp(-Delta I^2 / (2sigma^2))$ 公式，根据相邻像素的灰度差动态调整惩罚值，实现边缘对齐。

3. Boykov-Kolmogorov 搜索策略 不同于传统的每次重新构建搜索树的增广路径算法（如Edmonds-Karp），本项目采用的BK策略允许搜索树在增广后继续存在。虽然在代码逻辑中由于MATLAB环境的脚本特性对收留阶段做了结构化简化，但依然保留了算法核心的“生长-增广-维护”循环逻辑，确保能求得全局最优解。

使用方法

1. 启动程序后，系统会弹出文件选择对话框，请选择需要分割的图片文件（支持jpg, png, bmp等）。
2. 在弹出的交互窗口中：

* 使用鼠标左键在目标物内部点击或拖动，标记为前景点（蓝色点）。 * 使用鼠标右键在目标物外部点击或拖动，标记为背景点（红色点）。 * 标注完成后，按下Enter键开始计算。

1. 等待控制台输出计算进度，算法完成后将自动弹出分割结果对比图。
2. 结果图中包含：标注图、二值掩码图、以及剔除背景后的纯前景图。