Graph-cut-Graph-Cut---国立台湾大学-资讯工程学系

GraphCutDigitalVisualEffectsgYung-YuChuangwithslidesbyFredoDurand,RameshRaskarGraphcutGraphcut•InteractiveimagesegmentationusinggraphcutBilblfdbkd•Binarylabel:foregroundvs.background•Userlabelssomepixels–similartotrimap,usuallysparser•ExploitFFBp–StatisticsofknownFg&Bg–SmoothnessoflabelFFFFBBSmoothnessoflabel•TurnintodiscretegraphoptimizationGraphcut(mincut/maxflow)BFB–Graphcut(mincut/maxflow)Energyfunction•Labeling:onevalueperpixel,ForB•Energy(labeling)=data+smoothness•Energy(labeling)data+smoothness–Verygeneralsituation–WillbeminimizedOnelabeling•Data:foreachpixel–ProbabilitythatthiscolorbelongstoF(resp.B)g(ok,notbest)–SimilarinspirittoBayesianmatting•Smoothness(akaregularization):ihbiiliDataperneighboringpixelpair–Penaltyforhavingdifferentlabel–PenaltyisdownweightedifthetwoData–Penaltyisdownweightedifthetwopixelcolorsareverydifferent–SimilarinspirittobilateralfilterSmoothnessSmoothnessDataterm•A.k.aregionalterm(becauseintegratedoverfullregion)(becauseintegratedoverfullregion)•D(L)=i-logh[Li](Ci)()ig[i](i)•WhereiisapixelLiisthelabelati(ForB),Liisthelabelati(ForB),Ciisthepixelvalueh[Li]isthehistogramoftheobservedFgh[Li]isthehistogramoftheobservedFg(respBg)•Notetheminussign•NotetheminussignHardconstraints•TheuserhasprovidedsomelabelsThikddiild•Thequickanddirtywaytoincludeconstraintsintooptimizationistoreplacethedttbhltifttddatatermbyahugepenaltyifnotrespected.•D(L_i)=0ifrespected•D(L_i)=Kifnotrespected–e.g.K=-#pixelsgpSmoothnessterm•a.k.aboundaryterm,a.k.a.regularizationS(L)B(CC)(LL)•S(L)={j,i}inNB(Ci,Cj)(Li-Lj)•Wherei,jareneighbors–e.g.8-neighborhood(butIshow4forsimplicity)(LL)is0ifLL1otherwise•(Li-Lj)is0ifLi=Lj,1otherwise•B(Ci,Cj)ishighwhenCiandCjaresimilar,lowifthereisadiscontinuitybetweenthosetwopixelsthereisadiscontinuitybetweenthosetwopixels–e.g.exp(-||Ci-Cj||2/22)wherecanbeaconstant–wherecanbeaconstantorthelocalvariance•Notepositivesign•NotepositivesignOptimization•E(L)=D(L)+S(L)iblki•isablack-magicconstant•FindthelabelingthatminimizesE•Inthiscase,howmanypossibilities?–29(512)2(512)–Wecantrythemall!–Whataboutmegapixelimages?Whataboutmegapixelimages?Labelingasagraphproblem•Eachpixel=nodeAdddF&B•AddtwonodesF&B•Labeling:linkeachpixeltoeitherForBFDesiredresultBDataterm•PutoneedgebetweeneachpixelandF&GWihfdid•Weightofedge=minusdataterm–Don’tforgethugeweightforhardconstraints–CarefulwithsignFBSmoothnessterm•AddanedgebetweeneachneighborpairWihh•Weight=smoothnesstermFBMincut•EnergyoptimizationequivalenttomincutCddiFfB•Cut:removeedgestodisconnectFfromB•Minimum:minimizesumofcutedgeweightFcutBMincut=labeling•Inordertobeacut:FhiliththFGdhtbt–Foreachpixel,eithertheForGedgehastobecut•Inordertobeminimal–Onlyoneedgelabelperpixelcanbecut(otherwisecouldFcut(otherwisecouldbeadded)BEnergyminimizationviagraphcutsedgeweight),,(3dyxDd3d2d1LabelsedgeweightLabels(disparities)),(11ddVEnergyminimizationviagraphcutsddd3d1d2d1•GraphCost–Matchingcostbetweenimages–Neighborhoodmatchingterm–Goal:figureoutwhichlabelsareconnectedtogwhichpixelsEnergyminimizationviagraphcutsddd3d1d2d1•GraphCut–Deleteenoughedgessothat•eachpixelis(transitively)connectedtoexactlyonelabelnodelabelnode–Costofacut:sumofdeletededgeweightsFindingmincostcutequivalenttofindingglobal–FindingmincostcutequivalenttofindingglobalminimumofenergyfunctionComputingamultiwaycut•With2labels:classicalmin-cutproblem–Solvablebystandardflowalgorithms•polynomialtimeintheory,nearlylinearinpracticeMorethan2terminals:NPhard–Morethan2terminals:NP-hard[Dahlhausetal.,STOC‘92]•Efficientapproximationalgorithmsexist•Efficientapproximationalgorithmsexist–Withinafactorof2ofoptimal–ComputeslocalminimuminastrongsenseComputeslocalminimuminastrongsense•evenverylargemoveswillnotimprovetheenergy–YuriBoykov,OlgaVekslerandRaminZabih,FastApproximateEnergyMinimizationviaGraphCutsInternationalConferenceonComputerMinimizationviaGraphCuts,InternationalConferenceonComputerVision,September1999.MoveexamplesRed-blueswapmoveStartingpointGreenexpansionmoveTheswapmovealgorithm1.Startwithanarbitrarylabeling2.Cyclethrougheverylabelpair(A,B)insomeorderygyp(,)2.1FindthelowestElabelingwithinasingleAB-swap2.2GothereifEislowerthanthecurrentlabeling3.IfEdidnotdecreaseinthecycle,we’redoneOtherwise,gotostep2BBOiilhAABbhAOriginalgraphABsubgraph(runmin-cutonthisgraph)Theexpansionmovealgorithm1.Startwithanarbitrarylabeling2CyclethrougheverylabelAinsomeorder2.CyclethrougheverylabelAinsomeorder2.1FindthelowestElabelingwithinasingleA-expansion2.2GothereifitEislowerthanthecurrentlabelingg3.IfEdidnotdecreaseinthecycle,we’redoneOtherwise,gotostep2GrabCutGrabCutInteractieForegrondEtractionInteractieForegrondEtractionInteractiveForegroundExtractionInteractiveForegroundExtractionusingIteratedGraphCutsusingIteratedGraphCutsCarstenRotherCarstenRotherCarstenRotherCarstenRotherVladimirKolmogorovVladimirKolmogorovAndrewBlakeAndrewBlakeAndrewBlakeAndrewBlakeMicrosoftResearchCambridgeMicrosoftResearchCambridge--UKUKDemo•videoInteractiveDigitalPhotomontage•Combiningmultiplephotos•Combiningmultiplephotos•Findseamsusinggraphcu