图割是一类组合优化方法，用于解决计算机视觉和人工智能中出现的能量最小化问题。其核心思想是将标记或分割问题表示为图，其中节点对应像素或数据点，边编码成对关系。求解问题因此归结为在图中寻找最小割，该割将节点划分为不相交的集合，同时最小化代价函数。这种方法对于二元标记问题（如前景-背景分割）尤为有效，并可通过alpha-expansion等技术扩展到多标签问题。
图割的数学基础在于最大流最小割定理，该定理指出网络中从源点到汇点的最大流等于将它们分开的割的最小容量。在计算机视觉中，该定理通过构造一个带有两个特殊终端节点（源点和汇点）的图来利用，这两个节点代表两个标签。每个像素通过边连接到两个终端，边的容量反映将该像素分配给每个标签的一元代价。此外，相邻像素之间的边编码平滑惩罚，鼓励区域一致性。最小割随后产生一个最优标记，在数据保真度与空间正则性之间取得平衡。
历史发展
图割在计算机视觉中的使用在1990年代末和2000年代初获得 prominence，基于组合优化的早期工作。关键贡献来自Yuri Boykov和Vladimir Kolmogorov等研究者，他们引入了用于计算视觉问题中最小割的高效算法。他们2001年关于交互式图像分割的论文允许用户标记前景和背景区域，成为极具影响力的工作。大约同一时期，图割与马尔可夫随机场（MRF）之间的联系被形式化，表明许多具有成对项的能源函数可以使用基于图的方法精确或近似最小化。
计算机视觉中的应用
图割已应用于广泛的视觉任务。在图像分割中，它们用于将对象与背景分离，通常通过用户交互来引导过程。医学影像受益于图割在CT或MRI扫描中的器官描绘，其中该方法结合边界和区域信息的能力很有价值。立体匹配（从两幅图像估计深度）也使用图割来分配视差标签，同时强制平滑性。其他应用包括图像去噪（目标是从噪声观测中恢复干净图像）和多视图重建（图割帮助从多个相机视图融合3D表面）。
与能量最小化的关系
在人工智能中，图割是能量模型的一个具体实例，其中目标是找到最小化全局代价的配置。能量通常由一元项（衡量将标签分配给单个变量的代价）和成对项（衡量将标签分配给一对变量的代价）组成。图割方法通过将能量函数映射到图结构，利用最大流算法高效求解。这种关系使得图割成为解决计算机视觉中许多推理问题的强大工具，特别是在需要全局最优或近似最优解的场合。
局限性与扩展
图割受限于其对子模性（submodularity）的依赖以获得精确解。某些视觉任务中出现的非子模能量需要替代方法，如二次伪布尔优化或移动算法，这些方法可能不保证最优性。内存和时间复杂度也随图像尺寸增长，尽管GPU上的并行实现已缓解这一问题。扩展包括用于视频序列的动态图割（其中图被增量更新）和捕获更复杂交互的高阶势能。研究继续探索将图割与Reinforcement learning及其他AI范式集成，尽管核心技术仍是组合优化与感知交叉的经典示例。