計算機視覺學習第1頁/共43頁引言圖論簡介圖割和最大流/最小割算法基于圖割的圖像分割算法主要內容第2頁/共43頁圖像分割問題也可以被看作是關于圖像像素(或者體素)的一個聚類問題.基于圖的割就是將圖中的各個頂點分成或不相連的兩個子集.將圖像用圖的形式表示,就可以應用圖論中的方法解決圖像分割問題.引言第3頁/共43頁將圖像轉化為圖兩種類型的頂點兩種類型的邊Cut-Segmentation第4頁/共43頁圖論簡介無向圖-UndirectedGraph Anundirectedgraphisdefinedasasetofnodes(verticesV)andasetofundirectededgesEthatconnectthenodes. Assigningeachedgeaweight,thegraphbecomesanundirectedweightedgraph.第5頁/共43頁圖論簡介有向圖-DirectedGraph Adirectedgraphisdefinedasasetofnodes(verticesV)andasetoforderedsetofverticesordirectededgesEthatconnectthenodes Foranedge,uiscalledthetailofe,viscalledtheheadofe.Thisedgeisdifferentfromtheedge

第6頁/共43頁割集是一組邊的集合,使得邊兩端的頂點被分成兩個獨立的圖假如起始端為s,終止端為

t,圖的割集

cut(S,T)是指將頂點集合V

分割成兩個新的頂點集合

S

和T=V\S的邊的集合,滿足

和

圖論簡介第7頁/共43頁流量網-flownetwork

是指一個具有非負邊的有向圖圖G中的流-flow

是指滿足如下三個性質的實值函數:邊滿足容量約束: For

all反對稱性 Forall守恒性 Forall圖割和最大流/最小割算法第8頁/共43頁Theorem IngraphG,themaximumsource-to-sinkflowpossibleisequaltothecapacityoftheminimumcutinG.

(L.R.Foulds,GraphTheoryApplications,1992Springer-VerlagNewYorkInc.,247-248)最大流與最小割定理第9頁/共43頁一些概念對于一個流

f

，經過割集cut(S,T)的網絡流可被定義成一個函數

f(S,T),表示成所有由S到T的邊的和減去所有由T到S的邊的和。割集cut(S,T)的容量是

c(S,T),表示所有由S到T的邊的和。最小割是指圖G的所有割集中容量最小的那個。最大流與最小割問題第10頁/共43頁基于圖割的圖像分割最大后驗概率馬爾科夫隨機場-MAP-MRF馬爾科夫隨機場-MRF“貼標簽”，將圖像建模轉化為標注問題給特定像素分配一個標簽有分配代價給臨近像素分配一對標簽有分離代價找到總的分配代價和分離代價之和最小貝葉斯框架解決不確定性問題最大后驗概率第11頁/共43頁一幅圖像并不是全圖各部分特征相同，相同無信息，不同才有信息，任一圖像特征為隨機的。且全場各部分間亦非均勻（隨機的）不存在全圖統一的特征。圖像可作為二維隨機場中一個樣本來分析常是必要的。在某些場合使用確定的表示來描述圖像有困難，然而用平均特性能方便地描述，如描述紋理結構圖象可能很方便。圖像為實函數，只討論二維實隨機場。二維隨機場：僅一個時間變量函數，一維隨機過程。圖象為二維實隨機場。圖像的隨機場形式第12頁/共43頁Markov隨機場圖像建模的重要工具，應用廣泛．

(J.Besag,1974)預備知識（標注問題，labeling）位(site)集合：

標志(label)集合，位上可能發生事件的集合，可以是連續的，也可以是離散的：，第13頁/共43頁Markov隨機場標注：為位集合中每個位指定一個標志的過程，位集合到標志集合的映射：第14頁/共43頁Markov隨機場標注：從如下空間中導出的過程：在圖象領域，可將理解為一幅圖象，則是全部可允許圖像的集合.標注也被稱為著色(coloring，數學規劃)或配置(configuration，隨機場)如果各個位為隨機變量，則位集合稱為隨機場.第15頁/共43頁Markov隨機場在隨機場中，從導出的過程就是確定出現的概率.假設各個位的標注是彼此無關的，則有

實際應用時，需要考慮上下文約束

(contextualconstraints)Markov隨機場，只需單獨考慮每個位，問題簡單（理想）第16頁/共43頁Markov隨機場當且僅當以下兩個條件滿足時，隨機場為Markov隨機場：

正性（Positivity）Markov性(Markovianity)若fi能夠獨立發生，那么f就能夠發生一個像素點的隨機概率只與它鄰域的像素有關第17頁/共43頁鄰域系統的等級劃分舉例:根據矩陣中各位置與位置i的距離，可以將鄰域系統表達為等級形式一個象素點和圖像中其他各象素點的相關性就可以通過條件概率和鄰域系統來描述第18頁/共43頁Gibbs隨機場鄰域系統(neighboringsystem)

鄰域集(neighborset)：一階鄰域（四連通），二階鄰域（八連通）等

團(cliques)：

由鄰域關系限定的位子集單位團(single-site)，雙位團(pair-site)，三位團(triple-site)等團是有序的:第19頁/共43頁Gibbs隨機場鄰域團團具有尺寸,

形狀和方向

第20頁/共43頁Gibbs隨機場當且僅當隨機場的配置服從Gibbs分布時，稱為Gibbs隨機場:

規范化常量，稱為劃分函數（partitionfunction）：溫度常量，常取1所有團勢能之和，稱為能量函數(energyfunction)：團勢能(cliquepotential)第21頁/共43頁Gibbs隨機場物理意義配置的能量越小，其概率越大均勻性(homogeneity)：

與團在隨機場中的位置無關與位i無關各向同性(isotropic)：與團的方向無關

在紋理領域，Markov(Gibbs)隨機場具有均勻性或者說，第22頁/共43頁Gibbs隨機場Hammersley-Clifford定理

Markov隨機場與Gibbs隨機場等價意義：

既可以用局部成分的相互影響來建模，也可以用全局能量來建模.如何確定團勢能的形式和參數是Markov(Gibbs)隨機場的主要工作.劃分函數的計算復雜度很高，是一個難題，實際多做一定簡化.第23頁/共43頁勢能的物理意義為當前區域與其相鄰域區域之間標記的關聯程度。舉例:第24頁/共43頁基于MRF框架的圖像分割MRF的性質:Hammersley-CliffordTheorem:領域關系(邊-n-links)像素(頂點-vertices)

-像素p的類別-配置-configuration第25頁/共43頁MRF配置的最大后驗概率估計ObserveddataLikelihoodfunction(sensornoise)Prior(MRFmodel)Bayesrule第26頁/共43頁能量優化算法找到使得后驗概率能量函數最小的:數據項Dataterm(sensornoise)平滑項Smoothnessterm(MRFprior)第27頁/共43頁廣義波特模型-GeneralizedPottsmodel團勢能Cliquepotential對于不連續性的懲罰項Penaltyfordiscontinuityat(p,q)能量函數Energyfunction第28頁/共43頁統計學線索-選擇合適的圖像分割

:WhiteRectangleinfrontoftheblackbackground標簽的配置通過最小化能量函數E(f)得到:第29頁/共43頁利用圖割算法實現能量最小化p-vertices(pixels)Costofn-linkCostoft-linkTerminals(可能的分割標簽)第30頁/共43頁多向割集-multiwaycut

vertices

V=pixels+terminalsedgesE=n-links+t-links

AmultiwaycutC

yieldssomesegmentationconfiguration

Removeasubsetofedges

C

C

isamultiwaycutifterminalsareseparatedin

G(C)GraphG=<V,E>GraphG(C)=<V,E-C>第31頁/共43頁主要結果

(generalizedPottsmodel)Undersometechnicalconditionsonthemultiwaymin-cutConGgives___

thatminimizesE(f)-theposteriorenergyfunctionforthegeneralizedPottsmodel.

MultiwaycutProblem:findminimumcost multiwaycutCgraphG第32頁/共43頁求解multiwaycut問題Caseoftwoterminals:max-flowalgorithm(Ford,Fulkerson1964)polinomialtime(almostlinearinpractice).NP-completeifthenumberoflabels>2(Dahlhaus

etal.,1992)Efficientapproximationalgorithmsthatareoptimalwithinafactorof2第33頁/共43頁算法描述

InitializeatarbitrarymultiwaycutC1.Chooseapairofterminals2.Considerconnectedpixels第34頁/共43頁算法描述

InitializeatarbitrarymultiwaycutC1.Chooseapairofterminals2.Considerconnectedpixels3.Reallocatepixelsbetweentwoterminalsbyrunningmax-flowalgorithm第35頁/共43頁算法描述

InitializeatarbitrarymultiwaycutC1.Chooseapairofterminals2.Considerconnectedpixels3.Reallocatepixelsbetweentwoterminalsbyrunningmax-flowalgorithm

4.NewmultiwaycutC’

isobtainedIterateuntilnopairofterminalsimprovesthecostofthecut第36頁/共43頁線性團勢能模型團勢能Penaltyfordiscontinuityat(p,q)Energyfunction第37頁/共43頁基于圖割的能量最小化Costofn-linkCostoft-link{p,q}partofgraphacutCyieldssomeconfigurationcutC第38頁/共43頁主要結果

(linearcliquepotentialmodel)Undersometechnicalconditionsonthemin-cutCongivesthatminimizes-theposteriorenergyfunctionforthelinearcliquepotentialmodel.第39頁/共43頁圖像分割實例第40頁/共43頁圖像分割實例第41頁/共43頁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”,