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

GraphCutsApproachtotheProblemsofImageSegmentation,引言图论简介图割和最大流/最小割算法基于图割的图像分割算法,主要内容,图像分割问题也可以被看作是关于图像像素(或者体素)的一个聚类问题.基于图的割就是将图中的各个顶点分成或不相连的两个子集.将图像用图的形式表示,就可以应用图论中的方法解决图像分割问题.,引言,将图像转化为图,两种类型的顶点两种类型的边Cut-Segmentation,图论简介,无向图-UndirectedGraphAnundirectedgraphisdefinedasasetofnodes(verticesV)andasetofundirectededgesEthatconnectthenodes.Assigningeachedgeaweight,thegraphbecomesanundirectedweightedgraph.,图论简介,有向图-DirectedGraphAdirectedgraphisdefinedasasetofnodes(verticesV)andasetoforderedsetofverticesordirectededgesEthatconnectthenodesForanedge,uiscalledthetailofe,viscalledtheheadofe.Thisedgeisdifferentfromtheedge,割集是一组边的集合,使得边两端的顶点被分成两个独立的图假如起始端为s,终止端为t,图的割集cut(S,T)是指将顶点集合V分割成两个新的顶点集合S和T=VS的边的集合,满足和,图论简介,流量网-flownetwork是指一个具有非负边的有向图图G中的流-flow是指满足如下三个性质的实值函数:边满足容量约束:Forall反对称性Forall守恒性Forall,图割和最大流/最小割算法,TheoremIngraphG,themaximumsource-to-sinkflowpossibleisequaltothecapacityoftheminimumcutinG.(L.R.Foulds,GraphTheoryApplications,1992Springer-VerlagNewYorkInc.,247-248),最大流与最小割定理,一些概念对于一个流f，经过割集cut(S,T)的网络流可被定义成一个函数f(S,T),表示成所有由S到T的边的和减去所有由T到S的边的和。割集cut(S,T)的容量是c(S,T),表示所有由S到T的边的和。最小割是指图G的所有割集中容量最小的那个。,最大流与最小割问题,基于图割的图像分割,最大后验概率马尔科夫随机场-MAP-MRF,马尔科夫随机场-MRF,“贴标签”，将图像建模转化为标注问题给特定像素分配一个标签有分配代价给临近像素分配一对标签有分离代价找到总的分配代价和分离代价之和最小,贝叶斯框架,解决不确定性问题最大后验概率,一幅图像并不是全图各部分特征相同，相同无信息，不同才有信息，任一图像特征为随机的。且全场各部分间亦非均匀（随机的）不存在全图统一的特征。图像可作为二维随机场中一个样本来分析常是必要的。在某些场合使用确定的表示来描述图像有困难，然而用平均特性能方便地描述，如描述纹理结构图象可能很方便。图像为实函数，只讨论二维实随机场。二维随机场：仅一个时间变量函数，一维随机过程。图象为二维实随机场。,图像的随机场形式,Markov随机场,图像建模的重要工具，应用广泛(J.Besag,1974)预备知识（标注问题，labeling）位(site)集合：标志(label)集合，位上可能发生事件的集合，可以是连续的，也可以是离散的：,，,Markov随机场,标注：为位集合中每个位指定一个标志的过程，位集合到标志集合的映射：,Markov随机场,标注：从如下空间中导出的过程：,在图象领域，可将理解为一幅图象，则是全部可允许图像的集合.,标注也被称为着色(coloring，数学规划)或配置(configuration，随机场),如果各个位为随机变量，则位集合称为随机场.,Markov随机场,在随机场中，从导出的过程就是确定出现的概率.假设各个位的标注是彼此无关的，则有,实际应用时，需要考虑上下文约束(contextualconstraints)Markov随机场,，,只需单独考虑每个位，问题简单（理想）,Markov随机场,当且仅当以下两个条件满足时，随机场为Markov随机场：,正性（Positivity）,Markov性(Markovianity),若fi能够独立发生，那么f就能够发生一个像素点的随机概率只与它邻域的像素有关,邻域系统的等级划分,举例:根据矩阵中各位置与位置i的距离，可以将邻域系统表达为等级形式,一个象素点和图像中其他各象素点的相关性就可以通过条件概率和邻域系统来描述,Gibbs随机场,邻域系统(neighboringsystem)邻域集(neighborset)：一阶邻域（四连通），二阶邻域（八连通）等团(cliques)：由邻域关系限定的位子集单位团(single-site)，双位团(pair-site)，三位团(triple-site)等,团是有序的:,Gibbs随机场,邻域团团具有尺寸,形状和方向,Gibbs随机场,当且仅当随机场的配置服从Gibbs分布时，称为Gibbs随机场:,规范化常量，称为划分函数（partitionfunction）,：温度常量，常取1,所有团势能之和，称为能量函数(energyfunction),：团势能(cliquepotential),Gibbs随机场,物理意义配置的能量越小，其概率越大均匀性(homogeneity)：,与团在随机场中的位置无关,与位i无关,各向同性(isotropic)：,与团的方向无关,在纹理领域，Markov(Gibbs)随机场具有均匀性,或者说，,Gibbs随机场,Hammersley-Clifford定理Markov随机场与Gibbs随机场等价意义：既可以用局部成分的相互影响来建模，也可以用全局能量来建模.如何确定团势能的形式和参数是Markov(Gibbs)随机场的主要工作.划分函数的计算复杂度很高，是一个难题，实际多做一定简化.,势能的物理意义为当前区域与其相邻域区域之间标记的关联程度。,举例:,基于MRF框架的图像分割,MRF的性质:,Hammersley-CliffordTheorem:,领域关系(边-n-links),像素(顶点-vertices),MRF配置的最大后验概率估计,能量优化算法,找到使得后验概率能量函数最小的:,广义波特模型-GeneralizedPottsmodel,团势能Cliquepotential,能量函数Energyfunction,统计学线索-选择合适的,图像分割:WhiteRectangleinfrontoftheblackbackground,利用图割算法实现能量最小化,p-vertices(pixels),Terminals(可能的分割标签),多向割集-multiwaycut,verticesV=pixels+terminals,edgesE=n-links+t-links,AmultiwaycutCyieldssomesegmentationconfiguration,RemoveasubsetofedgesC,CisamultiwaycutifterminalsareseparatedinG(C),主要结果(generalizedPottsmodel),Undersometechnicalconditionsonthemultiwaymin-cutConGgives_thatminimizesE(f)-theposteriorenergyfunctionforthegeneralizedPottsmodel.,MultiwaycutProblem:findminimumcostmultiwaycutCgraphG,求解multiwaycut问题,Caseoftwoterminals:max-flowalgorithm(Ford,Fulkerson1964)polinomialtime(almostlinearinpractice).NP-completeifthenumberoflabels2(Dahlhausetal.,1992)Efficientapproximationalgorithmsthatareoptimalwithinafactorof2,算法描述,InitializeatarbitrarymultiwaycutC,1.Chooseapairofterminals,2.Considerconnectedpixels,算法描述,InitializeatarbitrarymultiwaycutC,1.Chooseapairofterminals,2.Considerconnectedpixels,3.Reallocatepixelsbetweentwoterminalsbyrunningmax-flowalgorithm,算法描述,InitializeatarbitrarymultiwaycutC,1.Chooseapairofterminals,2.Considerconnectedpixels,3.Reallocatepixelsbetweentwoterminalsbyrunningmax-flowalgorithm,4.NewmultiwaycutCisobtained,Iterateuntilnopairofterminalsimprovesthecostofthecut,线性团势能模型,基于图割的能量最小化,acutCyieldssomeconfiguration,主要结果(linearcliquepotentialmodel),Undersometechnicalconditionsonthemin-cutCongivesthatminimizes-theposteriorenergyfunctionforthelinearcliquepotentialmodel.,图像分割实例,图像分割实例,Yuri.BoykovandMarie-PierreJolly,“InteractiveGraphCutsforOptimalBoundary&RegiionSegmentationofObjectsinN-DImages”,InProceedingof“InternationalConferenceonComputerVision”,VolumeI,105-112,July2001Yuri.BoykovandVladimirKolmogorov,“AnExperimentComparisonofMin-Cut/Max-FlowAlgorithmsforEnergyMinimizationinVision”,IEEETransactionsonPAMI,26(9):1124-1137,September2004Yuri.BoykovandVladimirKolmogorov,“ComputingGeodesicandMinimalSurfacesviaGraphCuts”,InProceedingof“InternationalConferenceonComputerVision”,VolumeII,26-33,October2003VladimirKolmogorovandRaminZabih,“WhatEnergyFunctionscanbeMinimizedviaGraphCuts?”,IEEETransactionsonPAMI,26(2):147-159,February2004Y.Boykov,O.Veksler,andR.Zabih,“FastApproximateEnergyMinimizationviaGraphCuts,”IEEETransactionsonPAMI,23(11):1222-1239,November2004SudiptaSinha,“GraphCutAlgorithmsinVision,GraphicsandMachinelearning,AnIntegratedPaper”,UNCChapelHill,November2004YuriBoykovandOlgaVeksler,“GraphCutsinVisionandGraphics:TheoriesandApplications”,Chapter5ofTheHandbookofMathematicalModelsinComputerVision,79-96,Springer,2005ThomasCormen,CharlesLeiserson,RonaldRivestandCliffordStein,“MaximumFlow”,Chapter26ofIntroductiontoalgorithms,secondedition,643-698,McGraw-Hill,2005L.R.Floulds,“AnIntroductiontoTransportationNetworks”,Section12.5.3ofGraphTheoryApplications,246-256,Springer,1992L.FordandD.Fulkerson,FlowsinNetworks,Princ