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

1、2021/8/2212021/8/222引言圖論簡介圖割和最大流/最小割算法基于圖割的圖像分割算法2021/8/223圖像分割問題也可以被看作是關(guān)于圖像像素(或者體素)的一個(gè)聚類問題.基于圖的割就是將圖中的各個(gè)頂點(diǎn)分成或不相連的兩個(gè)子集.將圖像用圖的形式表示,就可以應(yīng)用圖論中的方法解決圖像分割問題.2021/8/224兩種類型的頂點(diǎn)兩種類型的邊Cut - Segmentation2021/8/225無向圖-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/8/226有向圖-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/8/227割集是一組邊的集合 , 使得邊兩端的頂點(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/8/228流量網(wǎng)-flow networkflow networ

4、k 是指一個(gè)具有非負(fù)邊的有向圖圖G中的流- flowflow 是指滿足如下三個(gè)性質(zhì)的實(shí)值函數(shù): 邊滿足容量約束:For all 反對(duì)稱性For all 守恒性For all),(),(,vucvufVvu),(),(,uvfvufVvuVvvuftsVu0),(),(2021/8/229TheoremIn 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/8/2210一些概念 對(duì)于一個(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/8/2211基于圖割的圖像分割基于圖割的圖像分割最大后驗(yàn)概率馬爾科夫隨機(jī)場(chǎng)最大后驗(yàn)概率馬爾科夫隨機(jī)場(chǎng)-MAP-MRF馬爾科夫隨機(jī)場(chǎng)馬爾科夫隨機(jī)場(chǎng)-MRF “貼標(biāo)簽貼標(biāo)簽”，將圖像建模轉(zhuǎn)化為標(biāo)注問題，將圖

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

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

8、74)(J. Besag, 1974)預(yù)備知識(shí)（標(biāo)注問題，預(yù)備知識(shí)（標(biāo)注問題，labelinglabeling） 位位(site)(site)集合：集合： 標(biāo)志標(biāo)志(label)(label)集合，位上可能發(fā)生事件的集合，集合，位上可能發(fā)生事件的集合，可以是連續(xù)的，也可以是離散的：可以是連續(xù)的，也可以是離散的：RXXLhlc,21ndlllL，mS, 2 , 12021/8/2214標(biāo)注：標(biāo)注：為位集合中每個(gè)位指定一個(gè)標(biāo)志的過程，為位集合中每個(gè)位指定一個(gè)標(biāo)志的過程，位集合到標(biāo)志集合的映射：位集合到標(biāo)志集合的映射：LSf:mffff,212021/8/2215標(biāo)注：標(biāo)注：從如下從如下 空間中導(dǎo)出

9、空間中導(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ī)場(chǎng)，隨機(jī)場(chǎng)) )fFFf 如果各個(gè)位為隨機(jī)變量，則位集合如果各個(gè)位為隨機(jī)變量，則位集合 稱為隨機(jī)場(chǎng)稱為隨機(jī)場(chǎng). .S2021/8/2216在隨機(jī)場(chǎng)中，從在隨機(jī)場(chǎng)中，從 導(dǎo)出導(dǎo)出 的過程就的過程就是確定是確定 出現(xiàn)的概率出現(xiàn)的概率. . 假設(shè)

10、各個(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ī)場(chǎng)場(chǎng) ifPfP)( iiifPffP)(，只需單獨(dú)考慮每個(gè)位，問題簡單（理想）只需單獨(dú)考慮每個(gè)位，問題簡單（理想）Fff2021/8/2217當(dāng)且僅當(dāng)以下兩個(gè)條件滿足時(shí)，隨機(jī)場(chǎng)當(dāng)且僅當(dāng)以下兩個(gè)條件滿足時(shí)，隨機(jī)場(chǎng)為為MarkovMarkov隨機(jī)場(chǎng)：隨機(jī)場(chǎng)： 0fP iNiiSiffPffP正性（正性（PositivityPositivity

11、）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/8/2218鄰域系統(tǒng)的等級(jí)劃分鄰域系統(tǒng)的等級(jí)劃分舉例舉例: :根據(jù)矩陣中各位置與位置根據(jù)矩陣中各位置與位置i i的距離，可以將鄰域系的距離，可以將鄰域系統(tǒng)表達(dá)為等級(jí)形式統(tǒng)表達(dá)為等級(jí)形式一個(gè)象素點(diǎn)和圖像中其他各象素點(diǎn)的相關(guān)性就可以通過條一個(gè)象素點(diǎn)和圖像中其他各象素點(diǎn)的相關(guān)性就可以通過條件概率和鄰域系統(tǒng)來描述件概率和鄰域系統(tǒng)來描述2021/8/22

12、19鄰域系統(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) ，三位團(tuán)三位團(tuán)(triple-site)(triple-site)等等互為鄰居iiiiiiCiiCiC ,321團(tuán)是有序的

13、團(tuán)是有序的: : iiii,2021/8/2220鄰域鄰域團(tuán)團(tuán) 團(tuán)具有尺寸團(tuán)具有尺寸, , 形狀和方向形狀和方向 2021/8/2221當(dāng)且僅當(dāng)隨機(jī)場(chǎng)的配置服從當(dāng)且僅當(dāng)隨機(jī)場(chǎng)的配置服從GibbsGibbs分布時(shí)，稱為分布時(shí)，稱為GibbsGibbs隨機(jī)場(chǎng)隨機(jī)場(chǎng): : fUTezfP11規(guī)范化常量，稱為劃分函數(shù)規(guī)范化常量，稱為劃分函數(shù)（partition functionpartition function） FffUTeZ1T：溫度常量，常?。簻囟瘸Ａ?，常取1 1 fVfUCcc所有團(tuán)勢(shì)能之和，稱為能量函所有團(tuán)勢(shì)能之和，稱為能量函數(shù)數(shù)(energy function)(energy funct

14、ion) fVc：團(tuán)勢(shì)能：團(tuán)勢(shì)能(clique potential)(clique potential)2021/8/2222物理意義物理意義 配置的能量越小，其概率越大配置的能量越小，其概率越大均勻性均勻性 (homogeneity)(homogeneity)： fVc與團(tuán)在隨機(jī)場(chǎng)中的位置無關(guān)與團(tuán)在隨機(jī)場(chǎng)中的位置無關(guān)iNiffP與位與位i i無關(guān)無關(guān) 各向同性各向同性(isotropic)(isotropic)： fVc與團(tuán)的方向無關(guān)與團(tuán)的方向無關(guān) 在紋理領(lǐng)域，在紋理領(lǐng)域，Markov(Gibbs)Markov(Gibbs)隨機(jī)場(chǎng)具隨機(jī)場(chǎng)具 有均勻性有均勻性或者說，或者說，2021/8/22

15、23Hammersley-CliffordHammersley-Clifford定理定理 MarkovMarkov隨機(jī)場(chǎng)與隨機(jī)場(chǎng)與GibbsGibbs隨機(jī)場(chǎng)等價(jià)隨機(jī)場(chǎng)等價(jià)意義：意義： 既可以用局部成分的相互影響來建模，也可既可以用局部成分的相互影響來建模，也可以用全局能量來建模以用全局能量來建模. .如何確定團(tuán)勢(shì)能的形式和參數(shù)是如何確定團(tuán)勢(shì)能的形式和參數(shù)是Markov(Gibbs)Markov(Gibbs)隨機(jī)場(chǎng)的主要工作隨機(jī)場(chǎng)的主要工作. .劃分函數(shù)的計(jì)算復(fù)雜度很高，是一個(gè)難劃分函數(shù)的計(jì)算復(fù)雜度很高，是一個(gè)難題，實(shí)際多做一定簡化題，實(shí)際多做一定簡化. .2021/8/2224舉例舉例: :2

16、021/8/2225MRF 的性質(zhì)的性質(zhì): Hammersley-Clifford Theorem:),|(Pr),|(PrpqpqpNqffpqff),(),(),(exp)(PrqpqpqpffVf 領(lǐng)域關(guān)系 (邊-n-links) 像素 (頂點(diǎn)-vertices)pf - 像素 p的類別),.,(1mfff - 配置-configuration2021/8/2226)Pr()|Pr(maxargffOffpqpqpqpppfffVfOgf),(),(),()|(lnexpmaxarg)|(PrmaxargOfffObserved dataLikelihoodfunction(sensor

17、 noise)Prior (MRF model)Bayes rule2021/8/2227找到使得后驗(yàn)概率能量函數(shù)最小的 :f),(),(),()|(ln)(qpqpqppppffVfOgfE數(shù)據(jù)項(xiàng)Data term(sensor noise)平滑項(xiàng)Smoothness term(MRF prior)2021/8/2228團(tuán)勢(shì)能團(tuán)勢(shì)能Clique potential)(),(,),(qpqpqpqpffuffV對(duì)于不連續(xù)性的懲罰項(xiàng)Penalty for discontinuity at (p,q)能量函數(shù)能量函數(shù)Energy functionpqpqpqpppffufOgfE,)(2)|(ln

18、)(2021/8/2229圖像分割圖像分割 : White Rectangle in front of the black background ,qpuconstuqp,標(biāo)簽的配置通過最小化能量函數(shù)標(biāo)簽的配置通過最小化能量函數(shù) E( f )得到得到:constuqp,2021/8/2230p-vertices(pixels)Cost of n-link,2qpqpuCost of t-linkpplpKlOg)|(ln,0Terminals (可能的分割標(biāo)簽)2021/8/2231vertices V = pixels + terminalsedges E = n-links + t-lin

19、ks 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/8/2232Under some technical conditions on the multiway min-cut C on G gives_ that minimizes E( f ) - - the posterior energy functio

20、n for the generalized Potts model.pKCf Multiway cut Problem: find minimum cost multiway cut C graph G2021/8/2233Case of two terminals: max-flow algorithm (Ford, Fulkerson 1964)polinomial time (almost linear in practice).NP-complete if the number of labels 2 (Dahlhaus et al., 1992)Efficient approxima

21、tion algorithms that are optimal within a factor of 22021/8/2234 Initialize at arbitrary multiway cut C1. Choose a pair of terminals2. Consider connected pixels2021/8/2235 Initialize at arbitrary multiway cut C1. Choose a pair of terminals2. Consider connected pixels3. Reallocate pixels between two

22、terminals by running max-flow algorithm2021/8/2236 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 multiway cut C is obtainedIterate until no pair of terminals improves the

23、cost of the cut2021/8/2237團(tuán)勢(shì)能團(tuán)勢(shì)能|),(,),(qpqpqpqpffuffVPenalty for discontinuity at (p,q)Energy functionpqpqpqpppffufOgfE,|2)|(ln)(2021/8/2238Cost of n-link,2qpqpuCost of t-linkpplpKlOg)|(ln,p,q part of graphGa cut C yields someconfigurationCfcut C2021/8/2239Under some technical conditions on the min

24、-cut C on gives that minimizes - - the posterior energy function for the linear clique potential model.pKCfG)(fE2021/8/22402021/8/22412021/8/2242Yuri. Boykov and Marie-Pierre Jolly, “Interactive Graph Cuts for Optimal Boundary & Regiion Segmentation of Objects in N-D Images”, In Proceeding of “I

25、nternational Conference on Computer Vision”, Volume I, 105-112, July 2001Yuri. Boykov and Vladimir Kolmogorov, “An Experiment Comparison of Min-Cut / Max-Flow Algorithms for Energy Minimization in Vision”, IEEE Transactions on PAMI, 26 (9): 1124-1137, September 2004Yuri. Boykov and Vladimir Kolmogor

26、ov, “Computing Geodesic and Minimal Surfaces via Graph Cuts”, In Proceeding of “International Conference on Computer Vision”, Volume II, 26-33, October 2003Vladimir Kolmogorov and Ramin Zabih, “What Energy Functions can be Minimized via Graph Cuts?”, IEEE Transactions on PAMI, 26 (2): 147-159, February 2004Y. Boykov, O. Veksler, and R. Zabih, “Fast Approximate Energy Minimization via Graph Cuts,” IEEE Transactions on PAMI, 23 (11): 1222-1239, November 2004Sudipta Sinha, “Graph Cut Algorithms in Vision, Graphics and Machine learning, An Integrated Paper”