Graph Cut and Its Application in Computer Vision

网络流算法最初用于解决流网络的优化问题，比如水管网络、通信传输和城市的车流等。Graph cut作为其中一类最常见的算法，用于求解流网络的最小割，即寻找一个总容量最小的边集合，去掉这个集合中的所有边将阻断这个网络。图像和视频也能被视作网络（或者MRF），以像素作为节点，具体应用定义相邻像素间边的能量值（容量）。因此从九十年代末开始，Graph cut渐渐被引入计算机视觉、图像处理和机器学习领域，用于优化分类、分割和合成等问题。

The Max-Flow and Min-Cost Problem： 
定义图（或者流网络）G = (V, E)，可以为有向图或无向图。图中所有的边 e(u, v) ∈ E 附有一个非负的容量 c(u, v) ≥ 0，即该边所能承受的最大流量。图中通常定义两个特殊的节点，源点 s 和终点 t；存在拥有多个端点的图，对其的Max-flow求解为NP问题，需要转化为双端点问题求解次优解。定义满足以下条件的 f : VXV → R 为图 G 上的流：
   ●  Capacity Constrain，对于所有 u, v ∈ V，f(u, v) ≤ c(u, v)
   ●  Skew Symmetry，对于所有 u, v ∈ V，f(u, v) = ﹣f(u, v)
   ●  Flow Conservation，对于所有 u ∈ V﹣{s, t} 和 v ∈ V，∑ f(u, v) = 0
从 s 出发的所有流量的总和就是整个图的总流量。如下图所示，图的当前总流量为19，没有达到最大值。
 
Cut（割）将整个图的所有节点分为两个不相交的集合 S 和 T，比如s ∈ S，t ∈ T。割的容量定义为：
     c(S, T) = ∑_x∈S ∑_y∈T c(x, y)。
Min-cut（最小割）就是图的所有割中容量最小的一个。算法上要直接找Min-cut是十分困难的，根据最大流最小割定理，即图的最大流量等于图的最小割容量，通常要将问题转化为与之等价的Max-flow问题（理论推导点我）。

Max-Flow and Min-Cost Algorithms：
Max-flow问题的求解有两类经典的算法，增广路径[1] 和Push-relabel [2]。增广路径类算法遵循循序渐进的原则，不断在图上查找从 s 到 t 的可用路径，从0开始慢慢地提升图的总流量至最大；而Push-relabel类算法则从局部出发，总是尽可能地向图中输送更多的流量，在不断重复的Push和Relabel操作中达到节点间的平衡，是水流的一种拟态。Push-relabel类算法具有较高的并行性，适用于GPU加速，大体流程点我。
增广路径类算法有很多衍生，但大多具有以下特性：1）维护残余容量网络；2）通过寻找Augmenting path逼近最大流。Augmenting path具有形式：s, e1, v1, e2, v2, … , ek, t，其中没有重复的节点、没有饱和的前向边和空流量的后向边。对残余网络的定义有很多形式，这里我们定义边的残余容量（Redsidual capacity，RC）当其为前向边时等于 c(i, j) – f(i, j)，当其为后向边时等于 f(i, j)，如下图所示。
 
Augmenting path的残余容量为其每条边残余容量的最小值，如上图路径的残余容量为1。Ford-Fulkerson算法不断在残余网络中查询Augmenting path，比如使用广度或深度优先搜索，直到再也找不到任何路径。例子点我。Boykov[3] 提出一种双向搜索并重用搜索树的增广路径算法，虽然理论复杂度较高，但在实际应用中却效率较高，因此很多需要Graph cut的应用都采用Boykov提供的源代码。

Applications in Computer Vision：
计算机视觉中很多问题，都可以归结为量化方程的优化问题。比如图像分割的问题，定义每一个像素属于前景或背景的可能性度量，那整个问题就变成了如何让整个可能性量化方程取值最大的问题。当然有时，我们还需要定义平滑项，用于约束相邻像素的属性变化。这就形成了在视觉中最为常见的一类能量优化方程：
      E(f) = Esmooth(f) + Edata(f)
1维图还可用动态规划方法求解，但2维以上由于其几何级的复杂度增长，则大多使用Graph cut。典型的应用有Segmentation、Stereo matching、Image Restoration、Motion estimation等。根据不同的应用有不同的图构、相邻约束和能量函数。Kolmogorov[4] 研究了什么样的能量方程能用Graph cut优化，并提出了三元及以下能量函数自动转换成图的方法。

Multi-label Graph Cut：
根据应用的需要，有时定义的图构是多个label的，也就是有多个灭点，如下图所示。这种图的Min-cut是Multi-way的，求解过程是一个NP问题（Boykov[3]在他的论文中有详细证明）。比如Stereo matching中的disparity、Image Restoration中的intensity等，其本质都是一个Multi-label的优化问题。虽然有些方法可以将其人为地转变为2-label，但这在很大程度上限制了能量函数的定义。