Graph Cut and Its Application in Computer Vision
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)題。
- 上一篇: 深度解析】Google第二代深度学习引擎
- 下一篇: iOS/OS X内存管理(一):基本概念