实验四、基于grabcut交互式图像分割graphcut

GraphCutGraphcutGraphcutInteractiveimagesegmentationusinggraphcutBinarylabel:foregroundvs.backgroundUserlabelssomepixelssimilartotrimap,usuallysparserExploitStatisticsofknownFg&BgSmoothnessoflabelTurnintodiscretegraphoptimizationGraphcut(mincut/maxflow)FBFFFFBBBEnergyfunctionLabeling:onevalueperpixel,ForBEnergy(labeling)=data+smoothnessVerygeneralsituationWillbeminimizedData:foreachpixelProbabilitythatthiscolorbelongstoF(resp.B)SimilarinspirittoBayesianmattingSmoothness(akaregularization):

perneighboringpixelpairPenaltyforhavingdifferentlabelPenaltyisdownweightedifthetwo

pixelcolorsareverydifferentSimilarinspirittobilateralfilterOnelabeling

(ok,notbest)DataSmoothnessDatatermA.k.aregionalterm

(becauseintegratedoverfullregion)D(L)=i-logh[Li](Ci)Whereiisapixel

Liisthelabelati(ForB),

Ciisthepixelvalue

h[Li]isthehistogramoftheobservedFg

(respBg)NotetheminussignHardconstraintsTheuserhasprovidedsomelabelsThequickanddirtywaytoinclude

constraintsintooptimizationistoreplacethedatatermbyahugepenaltyifnotrespected.D(L_i)=0ifrespectedD(L_i)=Kifnotrespectede.g.K=-#pixelsSmoothnessterma.k.aboundaryterm,a.k.a.regularizationS(L)={j,i}inNB(Ci,Cj)(Li-Lj)Wherei,jareneighborse.g.8-neighborhood

(butIshow4forsimplicity)

(Li-Lj)is0ifLi=Lj,1otherwiseB(Ci,Cj)ishighwhenCiandCjaresimilar,lowifthereisadiscontinuitybetweenthosetwopixelse.g.exp(-||Ci-Cj||2/22)wherecanbeaconstant

orthelocalvarianceNotepositivesignOptimizationE(L)=D(L)+S(L)

isablack-magicconstantFindthelabelingthatminimizesEInthiscase,howmanypossibilities?29(512)Wecantrythemall!Whataboutmegapixelimages?LabelingasagraphproblemEachpixel=nodeAddtwonodesF&BLabeling:linkeachpixeltoeitherForBDesiredresultDatatermPutoneedgebetweeneachpixelandF&GWeightofedge=minusdatatermDon’tforgethugeweightforhardconstraintsCarefulwithsignSmoothnesstermAddanedgebetweeneachneighborpairWeight=smoothnesstermMincutEnergyoptimizationequivalenttomincutCut:removeedgestodisconnectFfromBMinimum:minimizesumofcutedgeweightcutMincut<=>labelingInordertobeacut:Foreachpixel,eithertheForGedgehastobecutInordertobeminimalOnlyoneedgelabel

perpixelcanbecut

(otherwisecould

beadded)cutEnergyminimizationviagraphcutsLabels(disparities)d1d2d3edgeweightedgeweightGraphCostMatchingcostbetweenimagesNeighborhoodmatchingtermGoal:figureoutwhichlabelsareconnectedtowhichpixelsd1d2d3EnergyminimizationviagraphcutsEnergyminimizationviagraphcutsd1d2d3GraphCutDeleteenoughedgessothateachpixelis(transitively)connectedtoexactlyonelabelnodeCostofacut:sumofdeletededgeweightsFindingmincostcutequivalenttofindingglobalminimumofenergyfunctionComputingamultiwaycutWith2labels:classicalmin-cutproblemSolvablebystandardflowalgorithmspolynomialtimeintheory,nearlylinearinpracticeMorethan2terminals:NP-hard[Dahlhausetal.,STOC‘92]EfficientapproximationalgorithmsexistWithinafactorof2ofoptimalComputeslocalminimuminastrongsenseevenverylargemoveswillnotimprovetheenergyYuriBoykov,OlgaVekslerandRaminZabih,FastApproximateEnergyMinimizationviaGraphCuts,InternationalConferenceonComputerVision,September1999.MoveexamplesStartingpointRed-blueswapmoveGreenexpansionmoveTheswapmovealgorithm1.Startwithanarbitrarylabeling2.Cyclethrougheverylabelpair(A,B)insomeorder2.1FindthelowestElabelingwithinasingleAB-swap2.2GothereifEislowerthanthecurrentlabeling3.IfEdidnotdecreaseinthecycle,we’redoneOtherwise,gotostep2OriginalgraphABABsubgraph(runmin-cutonthisgraph)BATheexpansionmovealgorithm1.Startwithanarbitrarylabeling2.CyclethrougheverylabelAinsomeorder2.1FindthelowestElabelingwithinasingleA-expansion2.2GothereifitEislowerthanthecurrentlabeling3.IfEdidnotdecreaseinthecycle,we’redoneOtherwise,gotostep2GrabCut

InteractiveForegroundExtraction

usingIteratedGraphCuts

CarstenRother

VladimirKolmogorov

AndrewBlake

MicrosoftResearchCambridge-UKDemovideoInteractiveDigitalPhotomontageAseemAgarwala,MiraDontcheva,ManeeshAgrawala,StevenDrucker,AlexColburn,BrianCurless,DavidSalesin,MichaelCohen,“InteractiveDigitalPhotomontage”,SIGGRAPH2004CombiningmultiplephotosFindseamsusinggraphcutsCombinegradientsandintegrateactualphotomontage