計算機視覺11-5[3].GraphCuts推薦課件

1、2021/8/2212021/8/222引言圖論簡介圖割和最大流/最小割算法基于圖割的圖像分割算法2021/8/223圖像分割問題也可以被看作是關(guān)于圖像像素(或者體素)的一個聚類問題.基于圖的割就是將圖中的各個頂點分成或不相連的兩個子集.將圖像用圖的形式表示,就可以應(yīng)用圖論中的方法解決圖像分割問題.2021/8/224兩種類型的頂點兩種類型的邊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割集是一組邊的集合 , 使得邊兩端的頂點被分成兩個獨立的圖假如起始端為s,終止端為 t, 圖 的割集 cut cut (S, T) 是指將頂點集合V 分割成兩個新的頂點集合 S 和T = V S 的邊的集合, 滿足 和 EC ),(CEVG ),(EVG SsTt 2021/8/228流量網(wǎng)-flow networkflow networ

4、k 是指一個具有非負邊的有向圖圖G中的流- flowflow 是指滿足如下三個性質(zhì)的實值函數(shù): 邊滿足容量約束:For all 反對稱性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一些概念 對于一個流 f ，經(jīng)過割集cut (S, T) 的網(wǎng)絡(luò)流可被定義成一個函數(shù) f (S, T), 表示成所有由S到T的邊的和減去所有由T到S的邊的和。 割集cut (S, T ) 的容量是 c (S, T), 表示所有由S到T的邊的和。 最小割是指圖G的所有割集中容量最小的那個。2021/8/2211基于圖割的圖像分割基于圖割的圖像分割最大后驗概率馬爾科夫隨機場最大后驗概率馬爾科夫隨機場-MAP-MRF馬爾科夫隨機場馬爾科夫隨機場-MRF “貼標簽貼標簽”，將圖像建模轉(zhuǎn)化為標注問題，將圖

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

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

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

9、空間中導(dǎo)出 的過程：的過程：,21mLLLFmmLLLLF時，當21在圖象領(lǐng)域，可將在圖象領(lǐng)域，可將 理解為一幅圖象，理解為一幅圖象， 則則是全部可允許圖像的集合是全部可允許圖像的集合. . 標注也被稱為著色標注也被稱為著色(coloring(coloring，數(shù)學(xué)規(guī)，數(shù)學(xué)規(guī)劃劃) )或配置或配置(configuration(configuration，隨機場，隨機場) )fFFf 如果各個位為隨機變量，則位集合如果各個位為隨機變量，則位集合 稱為隨機場稱為隨機場. .S2021/8/2216在隨機場中，從在隨機場中，從 導(dǎo)出導(dǎo)出 的過程就的過程就是確定是確定 出現(xiàn)的概率出現(xiàn)的概率. . 假設(shè)

10、各個位的標注是彼此無關(guān)的，則有假設(shè)各個位的標注是彼此無關(guān)的，則有 實際應(yīng)用時，需要考慮上下文約束實際應(yīng)用時，需要考慮上下文約束 (contextual constraints)(contextual constraints) MarkovMarkov隨機隨機場場 ifPfP)( iiifPffP)(，只需單獨考慮每個位，問題簡單（理想）只需單獨考慮每個位，問題簡單（理想）Fff2021/8/2217當且僅當以下兩個條件滿足時，隨機場當且僅當以下兩個條件滿足時，隨機場為為MarkovMarkov隨機場：隨機場： 0fP iNiiSiffPffP正性（正性（PositivityPositivity

11、）MarkovMarkov性性(Markovianity)(Markovianity)若若f fi i能夠獨立發(fā)生，那么能夠獨立發(fā)生，那么f f就能夠發(fā)生就能夠發(fā)生一個像素點的隨機概率只與它鄰域的像一個像素點的隨機概率只與它鄰域的像素有關(guān)素有關(guān)2021/8/2218鄰域系統(tǒng)的等級劃分鄰域系統(tǒng)的等級劃分舉例舉例: :根據(jù)矩陣中各位置與位置根據(jù)矩陣中各位置與位置i i的距離，可以將鄰域系的距離，可以將鄰域系統(tǒng)表達為等級形式統(tǒng)表達為等級形式一個象素點和圖像中其他各象素點的相關(guān)性就可以通過條一個象素點和圖像中其他各象素點的相關(guān)性就可以通過條件概率和鄰域系統(tǒng)來描述件概率和鄰域系統(tǒng)來描述2021/8/22

12、19鄰域系統(tǒng)鄰域系統(tǒng)(neighboring system)(neighboring system) 鄰域集鄰域集 (neighbor set)(neighbor set)：一階鄰域（四連通），二階鄰域（八連通）等一階鄰域（四連通），二階鄰域（八連通）等 團團(cliques)(cliques)： 由鄰域關(guān)系限定的位子集由鄰域關(guān)系限定的位子集 單位團單位團(single-site) (single-site) ，雙位團，雙位團(pair-site) (pair-site) ，三位團三位團(triple-site)(triple-site)等等互為鄰居iiiiiiCiiCiC ,321團是有序的

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

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

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

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

17、 noise)Prior (MRF model)Bayes rule2021/8/2227找到使得后驗概率能量函數(shù)最小的 :f),(),(),()|(ln)(qpqpqppppffVfOgfE數(shù)據(jù)項Data term(sensor noise)平滑項Smoothness term(MRF prior)2021/8/2228團勢能團勢能Clique potential)(),(,),(qpqpqpqpffuffV對于不連續(xù)性的懲罰項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,標簽的配置通過最小化能量函數(shù)標簽的配置通過最小化能量函數(shù) E( f )得到得到:constuqp,2021/8/2230p-vertices(pixels)Cost of n-link,2qpqpuCost of t-linkpplpKlOg)|(ln,0Terminals (可能的分割標簽)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團勢能團勢能|),(,),(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”