原文出處：
<a target="_blank" href="http://lincccc.blogspot.tw/2011/04/graph-cut-and-its-application-in.html">http://lincccc.blogspot.tw/2011/04/graph-cut-and-its-application-in.html</a>
現在好像需要代理才能通路了。。。
網絡流算法最初用于解決流網絡的優化問題，比如水管網絡、通信傳輸和城市的車流等。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)。
Max-Flow and Min-Cost Algorithms：
增廣路徑類算法有很多衍生，但大多具有以下特性：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)，如下圖所示。
提出一種雙向搜尋并重用搜尋樹的增廣路徑算法，雖然理論複雜度較高，但在實際應用中卻效率較高，是以很多需要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，但這在很大程度上限制了能量函數的定義。
Boykov[3]提出了兩種算法，能夠在多項式時間内逼近Muli-label問題的最優解，并給出了詳細證明和兩種算法的optimality property讨論。這是一篇值得細讀的文章。這兩種方法都是在尋找Local minima，最終使得圖中的任意一個像素改變其label都不能産生更好的解。在每一次疊代中，兩種方法分别進行 α-expansion 和 α-β-swap 形式的move
優化。α-expansion move 是指擴充 α-label 區域，使原本其他 label 的點屬于 α；α-β-swap move 則隻針對 α-label 和 β-label 區域，使其中的一些點的label從 α 變為 β 或相反。每一部疊代都是一次2-label的優化過程，形成以 α 和 非α 為滅點、以及以 α 和 β 為滅點的圖，尋找最優cut，重整label，不斷逼近最優解。α-expansion 要求平滑項滿足三邊定理，而 α-β-swap 可用于任意平滑項定義；但 α-expansion 有嚴格的optimality
property bound，總不會産生太壞的結果，是以被較多地使用。
Dynamic Graph Cut：
動态圖指一個圖序列，在時序上前後圖直接會保持平滑的過渡，是以，是否可以在前一張圖的residual graph基礎上修改變化了的像素點的能量以快速地求解？Dynamic graph cut并不尋求最優解，而是次優的快速的解。Kohli[12] 使用重新參數化圖（Graph Reparameterization）的方法修改動态變化的數值，并保持Capacity、Flow等基本限制，而後直接得到次優解。這種方法可以容忍少量邊的修改和少量任意節點拓撲的重構，但是和其他所有Dynamic
graph cut算法一樣，以少量、也就是輕微的時序變化為前提。主要應用于視訊相關的視覺方法，如Video segmentation。
Bibliography：
[1] L. Ford , D. Fulkerson. Flows in Networks. Princeton University Press, 1962.
[2] Andrew V. Goldberg, Robert E. Tarjan. A new approach to the maximum-flow problem. In Journal of the Association for Computing Machinery, 35(4):921–940, October 1988.
[3] Y. Boykov, V. Kolmogorov. An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision. In IEEE Transactions on Pattern Analysis and Machine
Intelligence (PAMI), volume 26, page 1124-1137, 2004.
[4] V. Kolmogorov, R. Zabih. What Energy Functions Can Be Minimized via Graph Cuts? In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), volume 26, no.2,
page 147-159, 2004.
[5] V. Kolmogorov, R. Zabih. Multi-camera Scene Reconstruction via Graph Cuts. In European Conference on Computer Vision (ECCV), May 2002 (best paper).
[6] Y. Boykov, O. Veksler and R. Zabih. Faster approximate energy minimization via graph cuts. In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), volume
23, no. 11, page 1-18, 2001.
[7] S. Roy, I. Cox. A maximum-flow formulation of the n-camera stereo correspondence problem. In International Conference on Computer Vision (ICCV), 1998.
[8] V. Vineet, P. J. Narayanan. CUDA Cuts: Fast Graph Cuts on the GPU. In: CVPR Workshop on Visual Computer Vision on GPUs, 2008.
[9] V. Kwatra, A. Schodl, I. Essa, G. Turk and A. Bobick. Graphcut Textures: Image and Video Synthesis Using Graph Cuts. In SIGGRAPH 2003, pp. 277-286.
[10] A. Blum, J. Lafferty, M.R. Rwebangira and R. Reddy. Semi-Supervised Learning Using Randomized Mincuts. In Proceedings of the 21st International Conference on Machine Learning
(ICML), Banff, Canada 2004.
[11] S. Z. Li, Markov Random Field Modeling in Computer Vision, Springer Verlag, 1995.
[12] P. Kohli and P. H. S. Torr. Dynamic graph cuts for efficient inference in markov random fields. IEEE Trans. Pattern Anal. Mach. Intell. (PAMI), 29(12):2079–2088, 2007.