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

引言图论简介图割和最大流/最小割算法基于图割的图像分割算法图像分割问题也可以被看作是关于图像像素(或者体素)的一个聚类问题.基于图的割就是将图中的各个顶点分成或不相连的两个子集.将图像用图的形式表示,就可以应用图论中的方法解决图像分割问题.两种类型的顶点两种类型的边Cut-Segmentation无向图-UndirectedGraphAnundirectedgraphisdefinedasasetofnodes(verticesV)andasetofundirectededgesEthatconnectthenodes.Assigningeachedgeaweight,thegraphbecomesanundirectedweightedgraph.122322st2Eeew),(EVG有向图-DirectedGraphAdirectedgraphisdefinedasasetofnodes(verticesV)andasetoforderedsetofverticesordirectededgesEthatconnectthenodesForanedge,uiscalledthetailofe,viscalledtheheadofe.Thisedgeisdifferentfromtheedge122322st31222222),(vue),(EVG),('uve割集是一组边的集合,使得边两端的顶点被分成两个独立的图假如起始端为s,终止端为t,图的割集cut(S,T)是指将顶点集合V分割成两个新的顶点集合S和T=V\S的边的集合,满足和EC)\,('CEVG),(EVGSsTt流量网-flownetwork是指一个具有非负边的有向图图G中的流-flow是指满足如下三个性质的实值函数:◦边满足容量约束:Forall◦反对称性Forall◦守恒性Forall),(),(,,vucvufVvu),(),(,,uvfvufVvuVvvuftsVu0),(}),,{\(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•“贴标签”，将图像建模转化为标注问题•给特定像素分配一个标签有分配代价•给临近像素分配一对标签有分离代价•找到总的分配代价和分离代价之和最小贝叶斯框架•解决不确定性问题•最大后验概率一幅图像并不是全图各部分特征相同，相同无信息，不同才有信息，任一图像特征为随机的。且全场各部分间亦非均匀（随机的）不存在全图统一的特征。图像可作为二维随机场中一个样本来分析常是必要的。在某些场合使用确定的表示来描述图像有困难，然而用平均特性能方便地描述，如描述纹理结构图象可能很方便。图像为实函数，只讨论二维实随机场。二维随机场：仅一个时间变量函数，一维随机过程。图象为二维实随机场。图像的随机场形式图像建模的重要工具，应用广泛．(J.Besag,1974)预备知识（标注问题，labeling）位(site)集合：标志(label)集合，位上可能发生事件的集合，可以是连续的，也可以是离散的：RXXLhlc],[],,,[21ndlllL，mS,,2,1标注：为位集合中每个位指定一个标志的过程，位集合到标志集合的映射：LSf:mffff,,,21标注：从如下空间中导出的过程：,21mLLLFmmLLLLF时，当21在图象领域，可将理解为一幅图象，则是全部可允许图像的集合.•标注也被称为着色(coloring，数学规划)或配置(configuration，随机场)fFFf•如果各个位为随机变量，则位集合称为随机场.S在随机场中，从导出的过程就是确定出现的概率.假设各个位的标注是彼此无关的，则有•实际应用时，需要考虑上下文约束(contextualconstraints)Markov随机场ifPfP)(iiifPffP)(，只需单独考虑每个位，问题简单（理想）Fff当且仅当以下两个条件满足时，随机场为Markov随机场：0fPiNiiSiffPffP正性（Positivity）Markov性(Markovianity)•若fi能够独立发生，那么f就能够发生•一个像素点的随机概率只与它邻域的像素有关邻域系统的等级划分举例:根据矩阵中各位置与位置i的距离，可以将邻域系统表达为等级形式一个象素点和图像中其他各象素点的相关性就可以通过条件概率和邻域系统来描述邻域系统(neighboringsystem)邻域集(neighborset)：一阶邻域（四连通），二阶邻域（八连通）等团(cliques)：由邻域关系限定的位子集单位团(single-site)，双位团(pair-site)，三位团(triple-site)等互为邻居iiiiiiCiiCiC,,,,,,,,321团是有序的:iiii,,邻域团团具有尺寸,形状和方向当且仅当随机场的配置服从Gibbs分布时，称为Gibbs随机场:fUTezfP11规范化常量，称为划分函数（partitionfunction）FffUTeZ1T：温度常量，常取1fVfUCcc所有团势能之和，称为能量函数(energyfunction)fVc：团势能(cliquepotential)物理意义配置的能量越小，其概率越大均匀性(homogeneity)：fVc与团在随机场中的位置无关iNiffP与位i无关•各向同性(isotropic)：fVc与团的方向无关•在纹理领域，Markov(Gibbs)随机场具有均匀性或者说，Hammersley-Clifford定理Markov随机场与Gibbs随机场等价意义：既可以用局部成分的相互影响来建模，也可以用全局能量来建模.如何确定团势能的形式和参数是Markov(Gibbs)随机场的主要工作.划分函数的计算复杂度很高，是一个难题，实际多做一定简化.举例:MRF的性质:Hammersley-CliffordTheorem:),|(Pr),|(PrpqpqpNqffpqff),(),(),(exp~)(PrqpqpqpffVf•领域关系(边-n-links)•像素(顶点-vertices)pf-像素p的类别),...,(1mfff-配置-configuration)Pr()|Pr(maxargˆffOffpqpqpqpppfffVfOgf),(),(),()|(lnexpmaxargˆ)|(PrmaxargˆOfffObserveddataLikelihoodfunction(sensornoise)Prior(MRFmodel)Bayesrule找到使得后验概率能量函数最小的:f),(),(),()|(ln)(qpqpqppppffVfOgfE数据项Dataterm(sensornoise)平滑项Smoothnessterm(MRFprior)团势能Cliquepotential)(),(},{),(qpqpqpqpffuffV对于不连续性的惩罚项Penaltyfordiscontinuityat(p,q)能量函数EnergyfunctionpqpqpqpppffufOgfE},{},{)(2)|(ln)(图像分割:WhiteRectangleinfrontoftheblackbackground},{qpuconstuqp},{标签的配置通过最小化能量函数E(f)得到:constuqp},{p-vertices(pixels)Costofn-link},{},{2qpqpuCostoft-linkpplpKlOg)|(ln},{0Terminals(可能的分割标签)verticesV=pixels+terminalsedgesE=n-links+t-links•AmultiwaycutCyieldssomesegmentationconfigurationCfRemoveasubsetofedgesC•CisamultiwaycutifterminalsareseparatedinG(C)GraphG=V,EGraphG(C)=V,E-CUndersometechnicalconditionsonthemultiwaymin-cutConGgives___thatminimizesE(f)-theposteriorenergyfunctionforthegeneralizedPottsmodel.pKCf•MultiwaycutProblem:findminimumcostmultiwaycutCgraphGCaseoftwoterminals:◦max-flowalgorithm(Ford,Fulkerson1964)◦polinomialtime(almostlinearinpractice).NP-completeifthenumberoflabels2◦(Dahlhausetal.,1992)Efficientapproximationalgorithmsthatareoptimalwithinafactorof2InitializeatarbitrarymultiwaycutC1.Chooseapairofterminals2.ConsiderconnectedpixelsInitializeatarbitrarymultiwaycutC1.Chooseapairofterminals2.Considerconnectedpixels3.Reallocatepixelsbetweentwoterminalsbyrunningmax-flowalgorithmInitializeatarbitrarymultiwaycutC1.Chooseapairofterminals2.Considerconnectedpixels3.Reallocatepixelsbetweentwoterminalsbyrunningmax-flowalgorithm4.NewmultiwaycutC’isobtainedIterateuntilnopairofterminalsimprovesthecostofthecut团势能||),(},{),(qpqpqpqpffuffVPenaltyfordiscontinuityat(p,q)EnergyfunctionpqpqpqpppffufOgfE},{},{||2)|(ln)(ˆCostofn-link},{},{2qpqpuCostoft-linkpplpKlOg)|(ln},{{p,q}partofgraphGˆacutCyieldssomeconfigurationCfcutCUndersometechnicalconditionsonthemin-cutCongivesthatminimizes-theposteriorenergyfunctionforthelinearcl