图割与最大流算法及其在连续情况下的扩展

图割

在图像分割领域中,交互式分割方法被称为图割（Graph Cuts）。相较于其他较早发展的水平集、活动轮廓等分割技术,这些基于能量最小化的优化求解的方法虽然效果显著但无法保证全局最优性；而图割的优势在于能够获得全局最优解。

在离散域中，图像的分割可以通过使以下能量函数最小化得到：

（公式1）

其中D代表区域项能量,其用于计算将像素p分配至区域l_p（如分割目标或背景）所涉及的成本;而V代表平滑项能量,其则用于评估将相邻像素p与q分别分配至区域l_p与l_q所需付出的成本

该能量最小化的过程可通过最大流算法求解，并以图的形式展示如下：

该图由顶点集合V与边集合E构成，在该图中每个像素对应一个顶点。此外，在该图中还设置了源节点s与汇节点t。其中分为两类边：一类连接相邻像素形成en边界；另一类则将像素与源或汇相连形成et边界。为了将图像分割问题转化为对该