计算机视觉11-5[3].GraphCuts推荐课件

1、2021/8/2212021/8/222引言图论简介图割和最大流/最小割算法基于图割的图像分割算法2021/8/223图像分割问题也可以被看作是关于图像像素(或者体素)的一个聚类问题.基于图的割就是将图中的各个顶点分成或不相连的两个子集.将图像用图的形式表示,就可以应用图论中的方法解决图像分割问题.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流量网-flow networkflow networ

4、k 是指一个具有非负边的有向图图G中的流- flowflow 是指满足如下三个性质的实值函数: 边满足容量约束: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 ，经过割集cut (S, T) 的网络流可被定义成一个函数 f (S, T), 表示成所有由S到T的边的和减去所有由T到S的边的和。 割集cut (S, T ) 的容量是 c (S, T), 表示所有由S到T的边的和。 最小割是指图G的所有割集中容量最小的那个。2021/8/2211基于图割的图像分割基于图割的图像分割最大后验概率马尔科夫随机场最大后验概率马尔科夫随机场-MAP-MRF马尔科夫随机场马尔科夫随机场-MRF “贴标签贴标签”，将图像建模转化为标注问题，将图

6、像建模转化为标注问题 给特定像素分配一个标签有分配代价给特定像素分配一个标签有分配代价 给临近像素分配一对标签有分离代价给临近像素分配一对标签有分离代价 找到总的分配代价和分离代价之和最小找到总的分配代价和分离代价之和最小贝叶斯框架贝叶斯框架 解决不确定性问题解决不确定性问题 最大后验概率最大后验概率 2021/8/2212一幅图像并不是全图各部分特征相同，相同无信息，不一幅图像并不是全图各部分特征相同，相同无信息，不同才有信息，任一图像特征为随机的。且全场各部分间同才有信息，任一图像特征为随机的。且全场各部分间亦非均匀（随机的）不存在全图统一的特征。亦非均匀（随机的）不存在全图统一的特征。图

7、像可作为二维随机场中一个样本来分析常是必要的。图像可作为二维随机场中一个样本来分析常是必要的。在某些场合使用确定的表示来描述图像有困难，然而用在某些场合使用确定的表示来描述图像有困难，然而用平均特性能方便地描述，如描述纹理结构图象可能很方平均特性能方便地描述，如描述纹理结构图象可能很方便。图像为实函数，只讨论二维实随机场。便。图像为实函数，只讨论二维实随机场。二维随机场：仅一个时间变量函数，一维随机过程。图二维随机场：仅一个时间变量函数，一维随机过程。图象为二维实随机场。象为二维实随机场。2021/8/2213图像建模的重要工具，应用广泛图像建模的重要工具，应用广泛 (J. Besag, 19

8、74)(J. Besag, 1974)预备知识（标注问题，预备知识（标注问题，labelinglabeling） 位位(site)(site)集合：集合： 标志标志(label)(label)集合，位上可能发生事件的集合，集合，位上可能发生事件的集合，可以是连续的，也可以是离散的：可以是连续的，也可以是离散的：RXXLhlc,21ndlllL，mS, 2 , 12021/8/2214标注：标注：为位集合中每个位指定一个标志的过程，为位集合中每个位指定一个标志的过程，位集合到标志集合的映射：位集合到标志集合的映射：LSf:mffff,212021/8/2215标注：标注：从如下从如下 空间中导出

9、空间中导出 的过程：的过程：,21mLLLFmmLLLLF时，当21在图象领域，可将在图象领域，可将 理解为一幅图象，理解为一幅图象， 则则是全部可允许图像的集合是全部可允许图像的集合. . 标注也被称为着色标注也被称为着色(coloring(coloring，数学规，数学规划划) )或配置或配置(configuration(configuration，随机场，随机场) )fFFf 如果各个位为随机变量，则位集合如果各个位为随机变量，则位集合 称为随机场称为随机场. .S2021/8/2216在随机场中，从在随机场中，从 导出导出 的过程就的过程就是确定是确定 出现的概率出现的概率. . 假设

10、各个位的标注是彼此无关的，则有假设各个位的标注是彼此无关的，则有 实际应用时，需要考虑上下文约束实际应用时，需要考虑上下文约束 (contextual constraints)(contextual constraints) MarkovMarkov随机随机场场 ifPfP)( iiifPffP)(，只需单独考虑每个位，问题简单（理想）只需单独考虑每个位，问题简单（理想）Fff2021/8/2217当且仅当以下两个条件满足时，随机场当且仅当以下两个条件满足时，随机场为为MarkovMarkov随机场：随机场： 0fP iNiiSiffPffP正性（正性（PositivityPositivity

11、）MarkovMarkov性性(Markovianity)(Markovianity)若若f fi i能够独立发生，那么能够独立发生，那么f f就能够发生就能够发生一个像素点的随机概率只与它邻域的像一个像素点的随机概率只与它邻域的像素有关素有关2021/8/2218邻域系统的等级划分邻域系统的等级划分举例举例: :根据矩阵中各位置与位置根据矩阵中各位置与位置i i的距离，可以将邻域系的距离，可以将邻域系统表达为等级形式统表达为等级形式一个象素点和图像中其他各象素点的相关性就可以通过条一个象素点和图像中其他各象素点的相关性就可以通过条件概率和邻域系统来描述件概率和邻域系统来描述2021/8/22

12、19邻域系统邻域系统(neighboring system)(neighboring system) 邻域集邻域集 (neighbor set)(neighbor set)：一阶邻域（四连通），二阶邻域（八连通）等一阶邻域（四连通），二阶邻域（八连通）等 团团(cliques)(cliques)： 由邻域关系限定的位子集由邻域关系限定的位子集 单位团单位团(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规范化常量，称为划分函数规范化常量，称为划分函数（partition functionpartition function） FffUTeZ1T：温度常量，常取：温度常量，常取1 1 fVfUCcc所有团势能之和，称为能量函所有团势能之和，称为能量函数数(energy function)(energy funct

14、ion) fVc：团势能：团势能(clique potential)(clique potential)2021/8/2222物理意义物理意义 配置的能量越小，其概率越大配置的能量越小，其概率越大均匀性均匀性 (homogeneity)(homogeneity)： fVc与团在随机场中的位置无关与团在随机场中的位置无关iNiffP与位与位i i无关无关 各向同性各向同性(isotropic)(isotropic)： fVc与团的方向无关与团的方向无关 在纹理领域，在纹理领域，Markov(Gibbs)Markov(Gibbs)随机场具随机场具 有均匀性有均匀性或者说，或者说，2021/8/22

15、23Hammersley-CliffordHammersley-Clifford定理定理 MarkovMarkov随机场与随机场与GibbsGibbs随机场等价随机场等价意义：意义： 既可以用局部成分的相互影响来建模，也可既可以用局部成分的相互影响来建模，也可以用全局能量来建模以用全局能量来建模. .如何确定团势能的形式和参数是如何确定团势能的形式和参数是Markov(Gibbs)Markov(Gibbs)随机场的主要工作随机场的主要工作. .划分函数的计算复杂度很高，是一个难划分函数的计算复杂度很高，是一个难题，实际多做一定简化题，实际多做一定简化. .2021/8/2224举例举例: :2

16、021/8/2225MRF 的性质的性质: Hammersley-Clifford Theorem:),|(Pr),|(PrpqpqpNqffpqff),(),(),(exp)(PrqpqpqpffVf 领域关系 (边-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找到使得后验概率能量函数最小的 :f),(),(),()|(ln)(qpqpqppppffVfOgfE数据项Data term(sensor noise)平滑项Smoothness term(MRF prior)2021/8/2228团势能团势能Clique potential)(),(,),(qpqpqpqpffuffV对于不连续性的惩罚项Penalty for discontinuity at (p,q)能量函数能量函数Energy functionpqpqpqpppffufOgfE,)(2)|(ln

18、)(2021/8/2229图像分割图像分割 : White Rectangle in front of the black background ,qpuconstuqp,标签的配置通过最小化能量函数标签的配置通过最小化能量函数 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”