計(jì)算機(jī)視覺11-5[3].GraphCuts

1、2021/3/1712021/3/172引言圖論簡介圖割和最大流/最小割算法基于圖割的圖像分割算法2021/3/173圖像分割問題也可以被看作是關(guān)于圖像像素(或者體素)的一個(gè)聚類問題.基于圖的割就是將圖中的各個(gè)頂點(diǎn)分成或不相連的兩個(gè)子集.將圖像用圖的形式表示,就可以應(yīng)用圖論中的方法解決圖像分割問題.2021/3/174兩種類型的頂點(diǎn)兩種類型的邊Cut - Segmentation2021/3/175無向圖-Undirected GraphAn undirected graph is defined as a set of nodes (vertices V) and a set of undi

2、rected edges E that connect the nodes. Assigning each edge a weight , the graph becomes an undirected weighted graph.Eeew),(EVG 2021/3/176有向圖-Directed GraphA directed graph is defined as a set of nodes (vertices V) and a set of ordered set of vertices or directed edges E that connect the nodesFor an

3、 edge , u is called the tail of e, v is called the head of e. This edge is different from the edge ),(vue ),(EVG ),(uve 2021/3/177割集是一組邊的集合 , 使得邊兩端的頂點(diǎn)被分成兩個(gè)獨(dú)立的圖假如起始端為s,終止端為 t, 圖 的割集 cut cut (S, T) 是指將頂點(diǎn)集合V 分割成兩個(gè)新的頂點(diǎn)集合 S 和T = V S 的邊的集合, 滿足 和 EC ),(CEVG ),(EVG SsTt 2021/3/178流量網(wǎng)-flow networkflow networ

4、k 是指一個(gè)具有非負(fù)邊的有向圖圖G中的流- flowflow 是指滿足如下三個(gè)性質(zhì)的實(shí)值函數(shù): 邊滿足容量約束:For all 反對稱性For all 守恒性For all),(),(,vucvufVvu),(),(,uvfvufVvuVvvuftsVu0),(),(2021/3/179TheoremIn graph G, the maximum source-to-sink flow possible is equal to the capacity of the minimum cut in G.(L. R. Foulds, Graph Theory Applications, 1992

5、Springer-Verlag New York Inc., 247-248)2021/3/1710一些概念 對于一個(gè)流 f ,經(jīng)過割集cut (S, T) 的網(wǎng)絡(luò)流可被定義成一個(gè)函數(shù) f (S, T), 表示成所有由S到T的邊的和減去所有由T到S的邊的和。 割集cut (S, T ) 的容量是 c (S, T), 表示所有由S到T的邊的和。 最小割是指圖G的所有割集中容量最小的那個(gè)。2021/3/1711基于圖割的圖像分割基于圖割的圖像分割最大后驗(yàn)概率馬爾科夫隨機(jī)場最大后驗(yàn)概率馬爾科夫隨機(jī)場-MAP-MRF馬爾科夫隨機(jī)場馬爾科夫隨機(jī)場-MRF “貼標(biāo)簽貼標(biāo)簽”,將圖像建模轉(zhuǎn)化為標(biāo)注問題將圖像

6、建模轉(zhuǎn)化為標(biāo)注問題 給特定像素分配一個(gè)標(biāo)簽有分配代價(jià)給特定像素分配一個(gè)標(biāo)簽有分配代價(jià) 給臨近像素分配一對標(biāo)簽有分離代價(jià)給臨近像素分配一對標(biāo)簽有分離代價(jià) 找到總的分配代價(jià)和分離代價(jià)之和最小找到總的分配代價(jià)和分離代價(jià)之和最小貝葉斯框架貝葉斯框架 解決不確定性問題解決不確定性問題 最大后驗(yàn)概率最大后驗(yàn)概率 2021/3/1712一幅圖像并不是全圖各部分特征相同一幅圖像并不是全圖各部分特征相同, ,相同無信息相同無信息, ,不同不同才有信息才有信息, ,任一圖像特征為隨機(jī)的。且全場各部分間亦非任一圖像特征為隨機(jī)的。且全場各部分間亦非均勻（隨機(jī)的）不存在全圖統(tǒng)一的特征。均勻（隨機(jī)的）不存在全圖統(tǒng)一的特征

7、。圖像可作為二維隨機(jī)場中一個(gè)樣本來分析常是必要的。圖像可作為二維隨機(jī)場中一個(gè)樣本來分析常是必要的。在某些場合使用確定的表示來描述圖像有困難在某些場合使用確定的表示來描述圖像有困難, ,然而用平然而用平均特性能方便地描述均特性能方便地描述, ,如描述紋理結(jié)構(gòu)圖象可能很方便。如描述紋理結(jié)構(gòu)圖象可能很方便。圖像為實(shí)函數(shù)圖像為實(shí)函數(shù), ,只討論二維實(shí)隨機(jī)場。只討論二維實(shí)隨機(jī)場。二維隨機(jī)場二維隨機(jī)場: :僅一個(gè)時(shí)間變量函數(shù)僅一個(gè)時(shí)間變量函數(shù), ,一維隨機(jī)過程。圖象一維隨機(jī)過程。圖象為二維實(shí)隨機(jī)場。為二維實(shí)隨機(jī)場。圖像的隨機(jī)場形式圖像的隨機(jī)場形式2021/3/1713圖像建模的重要工具圖像建模的重要工具,

8、 ,應(yīng)用廣泛應(yīng)用廣泛 (J. Besag, 1974)(J. Besag, 1974)預(yù)備知識（標(biāo)注問題預(yù)備知識（標(biāo)注問題, ,labelinglabeling） 位位(site)(site)集合集合: : 標(biāo)志標(biāo)志(label)(label)集合集合, ,位上可能發(fā)生事件的集合位上可能發(fā)生事件的集合, ,可以是連續(xù)的可以是連續(xù)的, ,也可以是離散的也可以是離散的: :RXXLhlc,21ndlllL, ,mS, 2 , 12021/3/1714標(biāo)注標(biāo)注: :為位集合中每個(gè)位指定一個(gè)標(biāo)志的過程為位集合中每個(gè)位指定一個(gè)標(biāo)志的過程, ,位位集合到標(biāo)志集合的映射集合到標(biāo)志集合的映射: :LSf:mf

9、fff,212021/3/1715標(biāo)注標(biāo)注: :從如下從如下 空間中導(dǎo)出空間中導(dǎo)出 的過程的過程: :,21mLLLFmmLLLLF時(shí)，當(dāng)21在圖象領(lǐng)域在圖象領(lǐng)域, ,可將可將 理解為一幅圖象理解為一幅圖象, , 則是則是全部可允許圖像的集合全部可允許圖像的集合. . 標(biāo)注也被稱為著色標(biāo)注也被稱為著色(coloring,(coloring,數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃) )或配置或配置(configuration(configuration, ,隨機(jī)場隨機(jī)場) )fFFf 如果各個(gè)位為隨機(jī)變量如果各個(gè)位為隨機(jī)變量, ,則位集合則位集合 稱為隨機(jī)場稱為隨機(jī)場. .S2021/3/1716在隨機(jī)場中在隨機(jī)場中

10、, ,從從 導(dǎo)出導(dǎo)出 的過程就是的過程就是確定確定 出現(xiàn)的概率出現(xiàn)的概率. . 假設(shè)各個(gè)位的標(biāo)注是彼此無關(guān)的假設(shè)各個(gè)位的標(biāo)注是彼此無關(guān)的, ,則有則有 實(shí)際應(yīng)用時(shí)實(shí)際應(yīng)用時(shí), ,需要考慮上下文約束需要考慮上下文約束 (contextual constraints)(contextual constraints) MarkovMarkov隨機(jī)隨機(jī)場場 ifPfP)( iiifPffP)(, ,只需單獨(dú)考慮每個(gè)位只需單獨(dú)考慮每個(gè)位, ,問題簡單（理想）問題簡單（理想）Fff2021/3/1717當(dāng)且僅當(dāng)以下兩個(gè)條件滿足時(shí)當(dāng)且僅當(dāng)以下兩個(gè)條件滿足時(shí), ,隨機(jī)場為隨機(jī)場為MarkovMarkov隨機(jī)場

11、隨機(jī)場: : 0fP iNiiSiffPffP正性（正性（PositivityPositivity）MarkovMarkov性性(Markovianity)(Markovianity) 若若f fi i能夠獨(dú)立發(fā)生能夠獨(dú)立發(fā)生, ,那么那么f f就能夠發(fā)生就能夠發(fā)生 一個(gè)像素點(diǎn)的隨機(jī)概率只與它鄰域的像一個(gè)像素點(diǎn)的隨機(jī)概率只與它鄰域的像素有關(guān)素有關(guān)2021/3/1718鄰域系統(tǒng)的等級劃分鄰域系統(tǒng)的等級劃分舉例舉例: :根據(jù)矩陣中各位置與位置根據(jù)矩陣中各位置與位置i i的距離的距離, ,可以將鄰域系可以將鄰域系統(tǒng)表達(dá)為等級形式統(tǒng)表達(dá)為等級形式一個(gè)象素點(diǎn)和圖像中其他各象素點(diǎn)的相關(guān)性就可以通過條一個(gè)象

12、素點(diǎn)和圖像中其他各象素點(diǎn)的相關(guān)性就可以通過條件概率和鄰域系統(tǒng)來描述件概率和鄰域系統(tǒng)來描述2021/3/1719鄰域系統(tǒng)鄰域系統(tǒng)(neighboring system)(neighboring system) 鄰域集鄰域集 (neighbor set):(neighbor set):一階鄰域（四連通）一階鄰域（四連通）, ,二階鄰域（八連通）等二階鄰域（八連通）等 團(tuán)團(tuán)(cliques)(cliques): : 由鄰域關(guān)系限定的位子集由鄰域關(guān)系限定的位子集 單位團(tuán)單位團(tuán)(single-site) (single-site) , ,雙位團(tuán)雙位團(tuán)(pair-site) (pair-site) , ,

13、三三位團(tuán)位團(tuán)(triple-site)(triple-site)等等互為鄰居iiiiiiCiiCiC ,321團(tuán)是有序的團(tuán)是有序的: : iiii,2021/3/1720鄰域鄰域團(tuán)團(tuán) 團(tuán)具有尺寸團(tuán)具有尺寸, , 形狀和方向形狀和方向 2021/3/1721當(dāng)且僅當(dāng)隨機(jī)場的配置服從當(dāng)且僅當(dāng)隨機(jī)場的配置服從GibbsGibbs分布時(shí)分布時(shí), ,稱為稱為GibbsGibbs隨機(jī)場隨機(jī)場: : fUTezfP11規(guī)范化常量規(guī)范化常量, ,稱為劃分函數(shù)稱為劃分函數(shù)（partition functionpartition function） FffUTeZ1T: :溫度常量溫度常量, ,常取常取1 1 f

14、VfUCcc所有團(tuán)勢能之和所有團(tuán)勢能之和, ,稱為能量函稱為能量函數(shù)數(shù)(energy function)(energy function) fVc: :團(tuán)勢能團(tuán)勢能(clique potential)(clique potential)2021/3/1722物理意義物理意義 配置的能量越小配置的能量越小, ,其概率越大其概率越大均勻性均勻性 (homogeneity):(homogeneity): fVc與團(tuán)在隨機(jī)場中的位置無關(guān)與團(tuán)在隨機(jī)場中的位置無關(guān)iNiffP與位與位i i無關(guān)無關(guān) 各向同性各向同性(isotropic):(isotropic): fVc與團(tuán)的方向無關(guān)與團(tuán)的方向無關(guān) 在紋理

15、領(lǐng)域在紋理領(lǐng)域,Markov(Gibbs),Markov(Gibbs)隨機(jī)場具隨機(jī)場具 有均勻性有均勻性或者說或者說, ,2021/3/1723Hammersley-CliffordHammersley-Clifford定理定理 MarkovMarkov隨機(jī)場與隨機(jī)場與GibbsGibbs隨機(jī)場等價(jià)隨機(jī)場等價(jià)意義意義: : 既可以用局部成分的相互影響來建模既可以用局部成分的相互影響來建模, ,也可以也可以用全局能量來建模用全局能量來建模. .如何確定團(tuán)勢能的形式和參數(shù)是如何確定團(tuán)勢能的形式和參數(shù)是Markov(Gibbs)Markov(Gibbs)隨機(jī)場的主要工作隨機(jī)場的主要工作. .劃分函數(shù)

16、的計(jì)算復(fù)雜度很高劃分函數(shù)的計(jì)算復(fù)雜度很高, ,是一個(gè)難題是一個(gè)難題, ,實(shí)際多做一定簡化實(shí)際多做一定簡化. .2021/3/1724舉例舉例: :2021/3/1725MRF 的性質(zhì)的性質(zhì): Hammersley-Clifford Theorem:),|(Pr),|(PrpqpqpNqffpqff),(),(),(exp)(PrqpqpqpffVf 領(lǐng)域關(guān)系 (邊-n-links) 像素 (頂點(diǎn)-vertices)pf - 像素 p的類別),.,(1mfff - 配置-configuration2021/3/1726)Pr()|Pr(maxargffOffpqpqpqpppfffVfOgf),

17、(),(),()|(lnexpmaxarg)|(PrmaxargOfffObserved dataLikelihoodfunction(sensor noise)Prior (MRF model)Bayes rule2021/3/1727找到使得后驗(yàn)概率能量函數(shù)最小的 :f),(),(),()|(ln)(qpqpqppppffVfOgfE數(shù)據(jù)項(xiàng)Data term(sensor noise)平滑項(xiàng)Smoothness term(MRF prior)2021/3/1728團(tuán)勢能團(tuán)勢能Clique potential)(),(,),(qpqpqpqpffuffV對于不連續(xù)性的懲罰項(xiàng)Penalty f

18、or discontinuity at (p,q)能量函數(shù)能量函數(shù)Energy functionpqpqpqpppffufOgfE,)(2)|(ln)(2021/3/1729圖像分割圖像分割 : White Rectangle in front of the black background ,qpuconstuqp,標(biāo)簽的配置通過最小化能量函數(shù)標(biāo)簽的配置通過最小化能量函數(shù) E( f )得到得到:constuqp,2021/3/1730p-vertices(pixels)Cost of n-link,2qpqpuCost of t-linkpplpKlOg)|(ln,0Terminals (可

19、能的分割標(biāo)簽)2021/3/1731vertices V = pixels + terminalsedges E = n-links + t-links A multiway cut C yields some segmentation configuration CfRemove a subset of edges C C is a multiway cut if terminals are separated in G(C)Graph G = Graph G(C) = 2021/3/1732Under some technical conditions on the multiway mi

20、n-cut C on G gives_ that minimizes E( f ) - - the posterior energy function for the generalized Potts model.pKCf Multiway cut Problem: find minimum cost multiway cut C graph G2021/3/1733Case of two terminals: max-flow algorithm (Ford, Fulkerson 1964)polinomial time (almost linear in practice).NP-com

21、plete if the number of labels 2 (Dahlhaus et al., 1992)Efficient approximation algorithms that are optimal within a factor of 22021/3/1734 Initialize at arbitrary multiway cut C1. Choose a pair of terminals2. Consider connected pixels2021/3/1735 Initialize at arbitrary multiway cut C1. Choose a pair

22、 of terminals2. Consider connected pixels3. Reallocate pixels between two terminals by running max-flow algorithm2021/3/1736 Initialize at arbitrary multiway cut C1. Choose a pair of terminals2. Consider connected pixels3. Reallocate pixels between two terminals by running max-flow algorithm 4. New

23、multiway cut C is obtainedIterate until no pair of terminals improves the cost of the cut2021/3/1737團(tuán)勢能團(tuán)勢能|),(,),(qpqpqpqpffuffVPenalty for discontinuity at (p,q)Energy functionpqpqpqpppffufOgfE,|2)|(ln)(2021/3/1738Cost of n-link,2qpqpuCost of t-linkpplpKlOg)|(ln,p,q part of graphGa cut C yields som

24、econfigurationCfcut C2021/3/1739Under some technical conditions on the min-cut C on gives that minimizes - - the posterior energy function for the linear clique potential model.pKCfG)(fE2021/3/17402021/3/1741圖像分割實(shí)例圖像分割實(shí)例2021/3/17421.Yuri. Boykov and Marie-Pierre Jolly, “Interactive Graph Cuts for Op

25、timal Boundary & Regiion Segmentation of Objects in N-D Images”, In Proceeding of “International Conference on Computer Vision”, Volume I, 105-112, July 20012.Yuri. Boykov and Vladimir Kolmogorov, “An Experiment Comparison of Min-Cut / Max-Flow Algorithms for Energy Minimization in Vision”, IEEE

26、 Transactions on PAMI, 26 (9): 1124-1137, September 20043.Yuri. Boykov and Vladimir Kolmogorov, “Computing Geodesic and Minimal Surfaces via Graph Cuts”, In Proceeding of “International Conference on Computer Vision”, Volume II, 26-33, October 20034.Vladimir Kolmogorov and Ramin Zabih, “What Energy

27、Functions can be Minimized via Graph Cuts?”, IEEE Transactions on PAMI, 26 (2): 147-159, February 20045.Y. Boykov, O. Veksler, and R. Zabih, “Fast Approximate Energy Minimization via Graph Cuts,” IEEE Transactions on PAMI, 23 (11): 1222-1239, November 20046.Sudipta Sinha, “Graph Cut Algorithms in Vision, Graphics and Machine learning, An Integrated Paper”, UN