计算机视觉11 5[3].GraphCuts

1、Graph Cuts Approach to the Problems of Image Segmentation,引言 图论简介 图割和最大流/最小割算法 基于图割的图像分割算法,主要内容,图像分割问题也可以被看作是关于图像像素(或者体素)的一个聚类问题. 基于图的割就是将图中的各个顶点分成或不相连的两个子集. 将图像用图的形式表示,就可以应用图论中的方法解决图像分割问题.,引言,将图像转化为图,两种类型的顶点 两种类型的边 Cut - Segmentation,图论简介,无向图-Undirected Graph An undirected graph is defined as a set

2、 of nodes (vertices V) and a set of undirected edges E that connect the nodes. Assigning each edge a weight , the graph becomes an undirected weighted graph.,图论简介,有向图-Directed Graph A directed graph is defined as a set of nodes (vertices V) and a set of ordered set of vertices or directed edges E th

3、at connect the nodes For an edge , u is called the tail of e, v is called the head of e. This edge is different from the edge,割集是一组边的集合 , 使得边两端的顶点被分成两个独立的图 假如起始端为s,终止端为 t, 图 的割集 cut (S, T) 是指将顶点集合V 分割成两个新的顶点集合 S 和T = V S 的边的集合, 满足 和,图论简介,流量网-flow network 是指一个具有非负边的有向图 图G中的流- flow 是指满足如下三个性质的实值函数: 边满

4、足容量约束: For all 反对称性 For all 守恒性 For all,图割和最大流/最小割算法,Theorem In 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 Springer-Verlag New York Inc., 247-248),最大流与最小割定理,一些概念 对于一个流 f ，经过割集cut (S, T) 的网络流可被定义成一

5、个函数 f (S, T), 表示成所有由S到T的边的和减去所有由T到S的边的和。 割集cut (S, T ) 的容量是 c (S, T), 表示所有由S到T的边的和。 最小割是指图G的所有割集中容量最小的那个。,最大流与最小割问题,基于图割的图像分割,最大后验概率马尔科夫随机场-MAP-MRF,马尔科夫随机场-MRF,“贴标签”，将图像建模转化为标注问题 给特定像素分配一个标签有分配代价 给临近像素分配一对标签有分离代价 找到总的分配代价和分离代价之和最小,贝叶斯框架,解决不确定性问题 最大后验概率,一幅图像并不是全图各部分特征相同，相同无信息，不同才有信息，任一图像特征为随机的。且全场各部分

6、间亦非均匀（随机的）不存在全图统一的特征。 图像可作为二维随机场中一个样本来分析常是必要的。在某些场合使用确定的表示来描述图像有困难，然而用平均特性能方便地描述，如描述纹理结构图象可能很方便。图像为实函数，只讨论二维实随机场。 二维随机场：仅一个时间变量函数，一维随机过程。图象为二维实随机场。,图像的随机场形式,Markov随机场,图像建模的重要工具，应用广泛 (J. Besag, 1974) 预备知识（标注问题，labeling） 位(site)集合： 标志(label)集合，位上可能发生事件的集合，可以是连续的，也可以是离散的：,，,Markov随机场,标注：为位集合中每个位指定一个标志的

7、过程，位集合到标志集合的映射：,Markov随机场,标注：从如下 空间中导出 的过程：,在图象领域，可将 理解为一幅图象， 则是全部可允许图像的集合.,标注也被称为着色(coloring，数学规划)或配置(configuration，随机场),如果各个位为随机变量，则位集合 称为随机场.,Markov随机场,在随机场中，从 导出 的过程就是确定 出现的概率. 假设各个位的标注是彼此无关的，则有,实际应用时，需要考虑上下文约束 (contextual constraints) Markov随机场,，,只需单独考虑每个位，问题简单（理想）,Markov随机场,当且仅当以下两个条件满足时，随机场为M

8、arkov随机场：,正性（Positivity）,Markov性(Markovianity),若fi能够独立发生，那么f就能够发生 一个像素点的随机概率只与它邻域的像素有关,邻域系统的等级划分,举例:根据矩阵中各位置与位置i的距离，可以将邻域系统表达为等级形式,一个象素点和图像中其他各象素点的相关性就可以通过条件概率和邻域系统来描述,Gibbs随机场,邻域系统(neighboring system) 邻域集 (neighbor set)： 一阶邻域（四连通），二阶邻域（八连通）等 团(cliques)： 由邻域关系限定的位子集 单位团(single-site) ，双位团(pair-site)

9、，三位团(triple-site)等,团是有序的:,Gibbs随机场,邻域 团 团具有尺寸, 形状和方向,Gibbs随机场,当且仅当随机场的配置服从Gibbs分布时，称为Gibbs随机场:,规范化常量，称为划分函数（partition function）,：温度常量，常取1,所有团势能之和，称为能量函数(energy function),：团势能(clique potential),Gibbs随机场,物理意义 配置的能量越小，其概率越大 均匀性 (homogeneity)：,与团在随机场中的位置无关,与位i无关,各向同性(isotropic)：,与团的方向无关,在纹理领域，Markov(Gib

10、bs)随机场具 有均匀性,或者说，,Gibbs随机场,Hammersley-Clifford定理 Markov随机场与Gibbs随机场等价 意义： 既可以用局部成分的相互影响来建模，也可以用全局能量来建模. 如何确定团势能的形式和参数是Markov(Gibbs)随机场的主要工作. 划分函数的计算复杂度很高，是一个难题，实际多做一定简化.,势能的物理意义为当前区域与其相邻域区域之间标记的关联程度。,举例:,基于MRF 框架的图像分割,MRF 的性质:,Hammersley-Clifford Theorem:,领域关系 (边-n-links),像素 (顶点-vertices),MRF配置的最大后验

11、概率估计,能量优化算法,找到使得后验概率能量函数最小的 :,广义波特模型-Generalized Potts model,团势能Clique potential,能量函数Energy function,统计学线索- 选择合适的,图像分割 : White Rectangle in front of the black background,利用图割算法实现能量最小化,p-vertices (pixels),Terminals (可能的分割标签),多向割集-multiway cut,vertices V = pixels + terminals,edges E = n-links + t-link

12、s,A multiway cut C yields some segmentation configuration,Remove a subset of edges C,C is a multiway cut if terminals are separated in G(C),主要结果 (generalized Potts model),Under some technical conditions on the multiway min-cut C on G gives_ that minimizes E( f ) - the posterior energy function for t

13、he generalized Potts model.,Multiway cut Problem: find minimum cost multiway cut C graph G,求解 multiway cut 问题,Case 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 approxim

14、ation algorithms that are optimal within a factor of 2,算法描述,Initialize at arbitrary multiway cut C,1. Choose a pair of terminals,2. Consider connected pixels,算法描述,Initialize at arbitrary multiway cut C,1. Choose a pair of terminals,2. Consider connected pixels,3. Reallocate pixels between two termin

15、als by running max-flow algorithm,算法描述,Initialize at arbitrary multiway cut C,1. Choose a pair of terminals,2. Consider connected pixels,3. Reallocate pixels between two terminals by running max-flow algorithm,4. New multiway cut C is obtained,Iterate until no pair of terminals improves the cost of

16、the cut,线性团势能模型,基于图割的能量最小化,a cut C yields some configuration,主要结果 (linear clique potential model),Under some technical conditions on the min-cut C on gives that minimizes - the posterior energy function for the linear clique potential model.,图像分割实例,图像分割实例,Yuri. Boykov and Marie-Pierre Jolly, “Intera

17、ctive Graph Cuts for Optimal Boundary & Regiion Segmentation of Objects in N-D Images”, In Proceeding of “International Conference on Computer Vision”, Volume I, 105-112, July 2001 Yuri. Boykov and Vladimir Kolmogorov, “An Experiment Comparison of Min-Cut / Max-Flow Algorithms for Energy Minimizatio

18、n in Vision”, IEEE Transactions on PAMI, 26 (9): 1124-1137, September 2004 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 2003 Vladimir Kolmogorov and Ramin Zabi

19、h, “What Energy Functions can be Minimized via Graph Cuts?”, IEEE Transactions on PAMI, 26 (2): 147-159, February 2004 Y. Boykov, O. Veksler, and R. Zabih, “Fast Approximate Energy Minimization via Graph Cuts,” IEEE Transactions on PAMI, 23 (11): 1222-1239, November 2004 Sudipta Sinha, “Graph Cut Al

20、gorithms in Vision, Graphics and Machine learning, An Integrated Paper”, UNC Chapel Hill, November 2004 Yuri Boykov and Olga Veksler, “Graph Cuts in Vision and Graphics: Theories and Applications”, Chapter 5 of The Handbook of Mathematical Models in Computer Vision, 79-96, Springer, 2005 Thomas Cormen, Charles Lei