Graph Cut and Its Application in Computer Vision

?

原文出處：

http://lincccc.blogspot.tw/2011/04/graph-cut-and-its-application-in.html

?

?

網(wǎng)絡(luò)流算法最初用于解決流網(wǎng)絡(luò)的優(yōu)化問(wèn)題，比如水管網(wǎng)絡(luò)、通信傳輸和城市的車(chē)流等。Graph cut作為其中一類(lèi)最常見(jiàn)的算法，用于求解流網(wǎng)絡(luò)的最小割，即尋找一個(gè)總?cè)萘孔钚〉倪吋?#xff0c;去掉這個(gè)集合中的所有邊將阻斷這個(gè)網(wǎng)絡(luò)。圖像和視頻也能被視作網(wǎng)絡(luò)（或者M(jìn)RF），以像素作為節(jié)點(diǎn)，具體應(yīng)用定義相鄰像素間邊的能量值（容量）。因此從九十年代末開(kāi)始，Graph cut漸漸被引入計(jì)算機(jī)視覺(jué)、圖像處理和機(jī)器學(xué)習(xí)領(lǐng)域，用于優(yōu)化分類(lèi)、分割和合成等問(wèn)題。

The Max-Flow and Min-Cost Problem：?
定義圖（或者流網(wǎng)絡(luò)）G = (V, E)，可以為有向圖或無(wú)向圖。圖中所有的邊?e(u, v) ∈ E?附有一個(gè)非負(fù)的容量?c(u, v) ≥ 0，即該邊所能承受的最大流量。圖中通常定義兩個(gè)特殊的節(jié)點(diǎn)，源點(diǎn)?s?和終點(diǎn)?t；存在擁有多個(gè)端點(diǎn)的圖，對(duì)其的Max-flow求解為NP問(wèn)題，需要轉(zhuǎn)化為雙端點(diǎn)問(wèn)題求解次優(yōu)解。定義滿足以下條件的?f : VXV → R?為圖?G?上的流：
?? ●? Capacity Constrain，對(duì)于所有?u, v ∈ V，f(u, v) ≤ c(u, v)
?? ●? Skew Symmetry，對(duì)于所有?u, v ∈ V，f(u, v) = ﹣f(u, v)
?? ●? Flow Conservation，對(duì)于所有?u ∈ V﹣{s, t}?和?v ∈ V，∑ f(u, v) = 0
從?s?出發(fā)的所有流量的總和就是整個(gè)圖的總流量。如下圖所示，圖的當(dāng)前總流量為19，沒(méi)有達(dá)到最大值。
?
Cut（割）將整個(gè)圖的所有節(jié)點(diǎn)分為兩個(gè)不相交的集合?S?和?T，比如s ∈ S，t ∈ T。割的容量定義為：
?????c(S, T) = ∑_x∈S?∑_y∈T?c(x, y)。
Min-cut（最小割）就是圖的所有割中容量最小的一個(gè)。算法上要直接找Min-cut是十分困難的，根據(jù)最大流最小割定理，即圖的最大流量等于圖的最小割容量，通常要將問(wèn)題轉(zhuǎn)化為與之等價(jià)的Max-flow問(wèn)題（理論推導(dǎo)點(diǎn)我）。

Max-Flow and Min-Cost Algorithms：
Max-flow問(wèn)題的求解有兩類(lèi)經(jīng)典的算法，增廣路徑[1] 和Push-relabel [2]。增廣路徑類(lèi)算法遵循循序漸進(jìn)的原則，不斷在圖上查找從?s?到?t?的可用路徑，從0開(kāi)始慢慢地提升圖的總流量至最大；而Push-relabel類(lèi)算法則從局部出發(fā)，總是盡可能地向圖中輸送更多的流量，在不斷重復(fù)的Push和Relabel操作中達(dá)到節(jié)點(diǎn)間的平衡，是水流的一種擬態(tài)。Push-relabel類(lèi)算法具有較高的并行性，適用于GPU加速，大體流程點(diǎn)我。
增廣路徑類(lèi)算法有很多衍生，但大多具有以下特性：1）維護(hù)殘余容量網(wǎng)絡(luò)；2）通過(guò)尋找Augmenting path逼近最大流。Augmenting path具有形式：s, e1, v1, e2, v2, … , ek, t，其中沒(méi)有重復(fù)的節(jié)點(diǎn)、沒(méi)有飽和的前向邊和空流量的后向邊。對(duì)殘余網(wǎng)絡(luò)的定義有很多形式，這里我們定義邊的殘余容量（Redsidual capacity，RC）當(dāng)其為前向邊時(shí)等于?c(i, j) – f(i, j)，當(dāng)其為后向邊時(shí)等于?f(i, j)，如下圖所示。
?
Augmenting path的殘余容量為其每條邊殘余容量的最小值，如上圖路徑的殘余容量為1。Ford-Fulkerson算法不斷在殘余網(wǎng)絡(luò)中查詢Augmenting path，比如使用廣度或深度優(yōu)先搜索，直到再也找不到任何路徑。例子點(diǎn)我。Boykov[3] 提出一種雙向搜索并重用搜索樹(shù)的增廣路徑算法，雖然理論復(fù)雜度較高，但在實(shí)際應(yīng)用中卻效率較高，因此很多需要Graph cut的應(yīng)用都采用Boykov提供的源代碼。

Applications in Computer Vision：
計(jì)算機(jī)視覺(jué)中很多問(wèn)題，都可以歸結(jié)為量化方程的優(yōu)化問(wèn)題。比如圖像分割的問(wèn)題，定義每一個(gè)像素屬于前景或背景的可能性度量，那整個(gè)問(wèn)題就變成了如何讓整個(gè)可能性量化方程取值最大的問(wèn)題。當(dāng)然有時(shí)，我們還需要定義平滑項(xiàng)，用于約束相鄰像素的屬性變化。這就形成了在視覺(jué)中最為常見(jiàn)的一類(lèi)能量?jī)?yōu)化方程：
????? E(f) = Esmooth(f) + Edata(f)
1維圖還可用動(dòng)態(tài)規(guī)劃方法求解，但2維以上由于其幾何級(jí)的復(fù)雜度增長(zhǎng)，則大多使用Graph cut。典型的應(yīng)用有Segmentation、Stereo matching、Image Restoration、Motion estimation等。根據(jù)不同的應(yīng)用有不同的圖構(gòu)、相鄰約束和能量函數(shù)。Kolmogorov[4] 研究了什么樣的能量方程能用Graph cut優(yōu)化，并提出了三元及以下能量函數(shù)自動(dòng)轉(zhuǎn)換成圖的方法。

Multi-label Graph Cut：
根據(jù)應(yīng)用的需要，有時(shí)定義的圖構(gòu)是多個(gè)label的，也就是有多個(gè)滅點(diǎn)，如下圖所示。這種圖的Min-cut是Multi-way的，求解過(guò)程是一個(gè)NP問(wèn)題（Boykov[3]在他的論文中有詳細(xì)證明）。比如Stereo matching中的disparity、Image Restoration中的intensity等，其本質(zhì)都是一個(gè)Multi-label的優(yōu)化問(wèn)題。雖然有些方法可以將其人為地轉(zhuǎn)變?yōu)?-label，但這在很大程度上限制了能量函數(shù)的定義。

?

?

Boykov[3]提出了兩種算法，能夠在多項(xiàng)式時(shí)間內(nèi)逼近Muli-label問(wèn)題的最優(yōu)解，并給出了詳細(xì)證明和兩種算法的optimality property討論。這是一篇值得細(xì)讀的文章。這兩種方法都是在尋找Local minima，最終使得圖中的任意一個(gè)像素改變其label都不能產(chǎn)生更好的解。在每一次迭代中，兩種方法分別進(jìn)行?α-expansion?和?α-β-swap?形式的move 優(yōu)化。α-expansion move?是指擴(kuò)展?α-label?區(qū)域，使原本其他 label 的點(diǎn)屬于?α；α-β-swap move?則只針對(duì)?α-label?和?β-label?區(qū)域，使其中的一些點(diǎn)的label從?α?變?yōu)?β?或相反。每一部迭代都是一次2-label的優(yōu)化過(guò)程，形成以?α?和?非α?為滅點(diǎn)、以及以?α?和?β?為滅點(diǎn)的圖，尋找最優(yōu)cut，重整label，不斷逼近最優(yōu)解。α-expansion?要求平滑項(xiàng)滿足三邊定理，而?α-β-swap?可用于任意平滑項(xiàng)定義；但?α-expansion?有嚴(yán)格的optimality property bound，總不會(huì)產(chǎn)生太壞的結(jié)果，因此被較多地使用。

Dynamic Graph Cut：
動(dòng)態(tài)圖指一個(gè)圖序列，在時(shí)序上前后圖直接會(huì)保持平滑的過(guò)渡，因此，是否可以在前一張圖的residual graph基礎(chǔ)上修改變化了的像素點(diǎn)的能量以快速地求解？Dynamic graph cut并不尋求最優(yōu)解，而是次優(yōu)的快速的解。Kohli[12] 使用重新參數(shù)化圖（Graph Reparameterization）的方法修改動(dòng)態(tài)變化的數(shù)值，并保持Capacity、Flow等基本約束，而后直接得到次優(yōu)解。這種方法可以容忍少量邊的修改和少量任意節(jié)點(diǎn)拓?fù)涞闹貥?gòu)，但是和其他所有Dynamic graph cut算法一樣，以少量、也就是輕微的時(shí)序變化為前提。主要應(yīng)用于視頻相關(guān)的視覺(jué)方法，如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.

總結(jié)

以上是生活随笔為你收集整理的Graph Cut and Its Application in Computer Vision的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。