图割优化是一种用于在图上定义的能量函数中寻找最小值的数学技术。它是计算机视觉和机器学习中的基础工具，许多问题可以被表述为为像素或数据点分配标签，同时平衡一元代价（为某个节点分配特定标签的代价）和成对代价（为相邻节点分配特定标签组合的代价）。该技术利用组合优化中的高效算法，尤其是最小割/最大流，来为某些类别的能量函数找到全局最优或近似最优的解决方案。
其核心思想是将能量最小化问题表示为图，其中节点代表变量（例如像素），边代表它们之间的相互作用。添加源点和汇点节点，并根据一元和成对代价设置边的容量。最小割，，即分离源点和汇点且总容量最小的边集合，，随后对应于最优标签分配。这种方法之所以特别强大，是因为最小割问题可以使用诸如推送-重标记方法或Boykov-Kolmogorov算法等算法在多项式时间内求解，这些算法对于图像处理中常见的网格结构图非常高效。
历史发展
图割优化的基础在于经典的极大流-极小割定理，该定理由莱斯特·福特和德尔伯特·富尔克森于1956年证明，随后发展了计算最大流的高效算法。这些思想在计算机视觉中的应用始于20世纪80年代末和90年代初，尤里·博伊科夫和奥尔加·韦克斯勒等研究者率先将图割用于图像分割和立体对应等问题。博伊科夫、韦克斯勒和拉明·扎比赫在2001年发表的一篇里程碑式论文中引入了α扩展和α-β交换算法，将图割扩展到具有非子模成对代价的多标签问题，使该技术得到广泛应用。
数学表述
图割优化通常处理如下形式的能量函数：E(L) = 对像素p求和 D_p(L_p) + 对像素对(p,q)求和 V_pq(L_p, L_q)，其中L是标签分配，D_p是一元数据项，V_pq是成对平滑项。对于二值标签问题（两个标签），如果成对项是子模的，即V(0,0) + V(1,1) <= V(0,1) + V(1,0)，则能量是可图表示的。在这种情况下，可以通过一次最小割计算找到精确的全局最小值。对于多标签问题，α扩展算法迭代地移动标签，每一步求解一个二值子问题，并保证解在全局最优的已知因子范围内。
在计算机视觉中的应用
图割优化在计算机视觉中作为主力工具已有二十多年。其主要应用包括：
- 图像分割：通过为每个像素分配标签来分离前景和背景，一元项基于颜色模型，成对项鼓励平滑边界。
- 立体匹配：从图像对计算视差图，能量惩罚对应点之间像素强度的差异。
- 图像恢复和去噪：通过最小化平衡数据保真度和平滑性的能量，从噪声观测中重建干净图像。
- 医学图像分析：在CT或MRI扫描中分割解剖结构，图割提供稳健且高效的解决方案。
与机器学习的关系
在机器学习中，图割优化出现在多个场景中。它用于结构化预测，其中输出是一组相互依赖的标签，例如使用条件随机场（CRF）进行语义分割。深度学习模型，特别是卷积神经网络，通常将图割作为后处理步骤来细化像素级预测。此外，图割已应用于机器学习中的问题，如聚类和特征选择，其中优化框架提供了一种原则性的方式来纳入成对关系。
算法与实现
已经开发了几种高效求解最小割问题的算法。Boykov-Kolmogorov算法于2004年提出，专门针对网格图设计，因其速度快和内存占用低而在计算机视觉中广泛使用。其他方法包括推送-重标记算法，该算法更通用，常用于大规模问题。实现可在OpenCV等库以及Boykov和Kolmogorov的Maxflow库等专门包中找到。近期研究还探索了GPU加速版本，以处理高分辨率图像的实时应用。
局限性与扩展
图割优化的主要局限性在于，它仅对子模二值能量保证全局最优性；对于更复杂的问题，它提供近似解。此外，对于非常大的图，内存和计算需求可能变得过高。为解决这些问题，研究者开发了扩展方法，如分层图割（在粗到细的网格上操作）和连续图割（处理非离散标签空间）。近期工作还探索了将图割与深度学习相结合，直接从数据中学习能量参数，从而在图像分割等任务上取得更好的性能。
参见
参考文献
- Boykov, Y., Veksler, O., & Zabih, R. (2001). Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence.
- Boykov, Y., & Kolmogorov, V. (2004). An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence.
- Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics.