Generalized Gradients: Priors on Minimization Flows

By
Published by

Niveau: Supérieur, Licence, Bac+2
Generalized Gradients: Priors on Minimization Flows G. Charpiat, P. Maurel, J.-P. Pons, R. Keriven, O. Faugeras Odyssee Lab? ENS/INRIA/ENPC Paris/Sophia-Antipolis/Champs-sur-Marne, France Abstract This paper tackles an important aspect of the variational problem underlying active contours: optimization by gradient flows. Classically, the definition of a gradient depends directly on the choice of an inner product structure. This consideration is largely absent from the active contours literature. Most authors, explicitely or implicitely, assume that the space of admissible deformations is ruled by the canonical L2 inner prod- uct. The classical gradient flows reported in the literature are relative to this particular choice. Here, we investigate the relevance of using (i) other inner products, yielding other gradient descents, and (ii) other minimizing flows not deriving from any inner product. In particular, we show how to induce different de- grees of spatial consistency into the minimizing flow, in order to decrease the probability of getting trapped into irrelevant local minima. We report numerical experiments indicating that the sensitivity of the active contours method to initial conditions, which seriously limits its applicability and efficiency, is alleviated by our application-specific spatially coherent minimizing flows. We show that the choice of the inner product can be seen as a prior on the deformation fields and we present an extension of the definition of the gradient toward more general priors.

  • inner product

  • active contour

  • traditional l2

  • exact minimization

  • contour

  • problem underlying active

  • gradient descent

  • l2 inner

  • tracking problem


Published : Tuesday, June 19, 2012
Reading/s : 12
Origin : di.ens.fr
Number of pages: 28
See more See less
GeneralizedGradients:PriorsonMinimizationFlowsG.Charpiat,P.Maurel,J.-P.Pons,R.Keriven,O.FaugerasOdysseeLabENS/INRIA/ENPCParis/Sophia-Antipolis/Champs-sur-Marne,FranceAbstractThispapertacklesanimportantaspectofthevariationalproblemunderlyingactivecontours:optimizationbygradientflows.Classically,thedefinitionofagradientdependsdirectlyonthechoiceofaninnerproductstructure.Thisconsiderationislargelyabsentfromtheactivecontoursliterature.Mostauthors,explicitelyorimplicitely,assumethatthespaceofadmissibledeformationsisruledbythecanonicalL2innerprod-uct.Theclassicalgradientflowsreportedintheliteraturearerelativetothisparticularchoice.Here,weinvestigatetherelevanceofusing(i)otherinnerproducts,yieldingothergradientdescents,and(ii)otherminimizingflowsnotderivingfromanyinnerproduct.Inparticular,weshowhowtoinducedifferentde-greesofspatialconsistencyintotheminimizingflow,inordertodecreasetheprobabilityofgettingtrappedintoirrelevantlocalminima.Wereportnumericalexperimentsindicatingthatthesensitivityoftheactivecontoursmethodtoinitialconditions,whichseriouslylimitsitsapplicabilityandefficiency,isalleviatedbyourapplication-specificspatiallycoherentminimizingflows.Weshowthatthechoiceoftheinnerproductcanbeseenasaprioronthedeformationfieldsandwepresentanextensionofthedefinitionofthegradienttowardmoregeneralpriors.1.IntroductionManyproblemsincomputervisioncanadvantageouslybecastinavariationalform,i.e.asaminimizationofanenergyfunctional.Inthispaper,wefocusonvariationalmethodsdedicatedtotherecoveryofcontours.Inthiscase,theproblemamountstofindingacontourwhichcorrespondstoaglobalminimumoftheenergy.Unfortunately,inmostcases,theexactminimizationoftheenergyfunctionaliscomputationallyunfeasibleduetothehugenumberofunknowns.Thegraphcutsmethodisapowerfulenergyminimizationmethodwhichallowstofindaglobalminimumorastronglocalminimumofanenergy.Inthelastfewyears,thismethodhasbeensuccessfullyappliedtoseveralproblemsincomputervision,includingstereovision[17]andimagesegmentation[5].However,ithasaseverelimitation:itcannotbeappliedtoanarbitraryenergyfunction[18],and,whenapplicable,iscomputationallyexpensive.Hence,inmostcases,asuboptimalstrategymustbeadopted.Acommonminimizationprocedurecon-sistsinevolvinganinitialcontour,positionedbytheuser,inthedirectionofsteepestdescentoftheenergy.Thisapproach,knownintheliteratureasactivecontoursordeformablemodels,waspioneeredbyKass.etGuillaume.Charpiat@di.ens.fr,Pierre.Maurel@di.ens.fr,Jean-Philippe.Pons@sophia.inria.fr,Renaud.Keriven@certis.enpc.fr,Olivier.Faugeras@sophia.inria.fr1
al.in[16]forthepurposeofimagesegmentation.Since,ithasbeenappliedinmanydomainsofcomputervisionandimageanalysis(imagesegmentation[6],surfacereconstruction[35,11],stereoreconstruction[12,15,13],etc.).However,duetothehighlynon-convexnatureofmostenergyfunctionals,agradientdescentflowisverylikelytobetrappedinalocalminimum.Also,thislocalminimumdependsonthepositionoftheinitialcontour.Ifthelatterisfarfromtheexpectedfinalconfiguration,theevolutionmaybetrappedinacompletelyirrelevantstate.Thissensitivitytoinitialconditionsseriouslylimitstheapplicabilityandefficiencyoftheactivecontoursmethod.Wedetailinsection2thegeneralgradientdescentprocesssoastoemphasizethecrucialroleoftheinnerproduct.Afteranabstractstudyinsection3onhowtohandleinnerproductsandminimizingflows,wepropose,insection4,variousinnerproductsandshowhowtheyinducedifferentdegreesofspatialcoherenceintheminimizingflowwithnumericalexamplesofshapewarpinginsection5.Insection6,arewritingoftheusualdefinitionofthegradientshowshowthechoiceofaninnerproductcanbeseenasawaytointroduceaprioronthedeformationfields,andthisleadsustoanaturalextensionofthenotionofgradienttomoregeneralpriors.2.MinimizationandinnerproductInthefollowingweconsiderashapeΓ,seenasamanifoldofdimensionkembeddedinRn,forexampleaplanarcurveorasurfaceinthespaceR3.WedenotebyE(Γ)theenergyfunctionaltobeminimized.Inordertodenethegradientoftheenergyfunctional,therststepistocomputeitsGaˆteauxderivativesδE,v)inalldirections,i.e.foralladmissiblevelocityfieldsvdefinedontheshapeΓwithvaluesinRn.Thedeformationspace,setofallthesefieldsv,canbeseenasthetangentspaceofΓ,considereditselfasapointinthemanifoldofalladmissibleshapes.defE(Γ+v)E(Γ)δE,v)=lim0.(1)Then,wewouldliketopickthegradientasthedirectionofsteepestdescentoftheenergy.However,itisnotyetpossibleatthisstage:tobeabletoassessthesteepnessoftheenergy,thedeformationspaceneedsadditionalstructure,namelyaninnerproductintroducingthegeometricalnotionsofanglesandlengths.Thisconsiderationislargelyabsentfromtheactivecontoursliterature:mostauthors,explicitelyorimplicitely,assumethatthedeformationspaceisruledbythecanonicalL2innerproductonΓ,whichis,fortwodefor-mationfieldsuandv:Z1hu|viL2=|Γ|u(x)v(x)dΓ(x),ΓwheredΓ(x)standsfortheareaelementofthecontoursothattheintegraloverΓisintrinsicanddoesnotdependontheparametrization.Here,forsakeofgenerality,wemodelthespaceofadmissibledeformationsasaninnerproductspace(F,h|iF).IfthereexistsadeformationfielduFsuchthatvF,δE,v)=hu|viF,thenuisunique,wecallitthegradientofErelativetotheinnerproducth|iF,andwedenotebyu=rFE(Γ).TheexistenceofuisrelatedtothesmoothnessofE,ormoreexactlytothecontinuityofδE,v)withrespecttov(Rieszrepresentationtheorem,see[27]formoredetails).2
Clearly,eachchoiceofinnerproductyieldsitsowngradient.Thisisoftenneglectedandmostauthorsimproperlyrefertothegradientoftheenergy.Thus,theclassicalgradientflowsreportedintheliterature(meancurvatureflow,geodesicactivecontours[6,14,29],multi-view3Dreconstruction[12,15,13])arerelativetotheL2innerproduct.ThegradientdescentmethodconsistsindeforminganinitialcontourΓ0intheoppositedirectionofthegradient.(Γ(0)=Γ0dΓ=−rE(Γ)(2)FtdTheproblemoftheexistenceandtheuniquenessofthisminimizingflowisoutofthescopeofthisarticle.Indeed,itishighlydependentonthepropertiesofeachparticularenergyfunctional.Ifthisevolutionexists,itdecreasestheenergy:dE(Γ)=−krFE(Γ)k2F0.tdThestandardchoiceforFistheHilbertspaceofsquareintegrablevelocityfieldsL2,Rn)equippedwithitscanonicalinnerproduct.Veryfewauthorsintheactivecontoursareahaveconsideredusingotherinnerproducts,whereasthisisanestablishedtechniqueinimageregistration[31].Veryrecently,inthecontextofshaperepresentationandanalysis,[19,32]haveshownthatslightlymodifyingtheL2innerproductallowstobuildwell-behavedmetricsinthespaceofcurves;theparticularcaseoftheH1innerproducthasbeensimultaneouslyandindependentlyinvestigatedbyus[8]andbySundaramoorthietal..]03[Thevariationsonthegradientdescenttheme,asin[4],willstillbeapplicabletothenewgradientswepropose,sincethesemethodsareinfactnotspecifictotheparticularL2gradient.Minimizingflowsnotderivingfromanyinnerproduct,thatistosayevolutionsthatdecreasetheenergy,withoutanygradientinterpretation,havealsobeenoverlookedsofar.Notethatanyevolutionfulfillingthecondition dE(Γ)dΓdt=rFE(Γ) dt0(3)Fisacandidatetosolvetheminimizationproblem.Thisidea,proposedin[29],isappliedbythesameauthorstothealignmentofcurveinimagesin[23]:acomplicatedterminthegradientissafelyneglectedaftercheckingthattheevolutionstilldecreasestheenergy.Thespiritofourworkisdifferent.Wedonotfocuseitheronaspecificinnerproductoronaparticularenergyfunctional.Weratherexploregeneralprocedurestobuildsomenewinnerproductsandtocomputetheassociatedgradients.Wealsoaddressthedesignofnon-gradientminimizingflows.Ourmotivationisalsodifferent.Ourprimaryconcerninthisworkisthesensitivityoftheactivecontoursmethodtoinitialconditions.Thereareessentiallytwowaysofdealingwiththisproblem:positioningtheinitialcontourveryclosetotheexpectedfinalconfiguration,orusingamultiresolutioncoarse-to-finestrategy,inotherwordsrunningtheoptimizationonaseriesofsmoothedandsubsampledcontoursandinputdata.Inthispaper,wepioneerathirdwaytotackletheproblemofunwantedlocalminima:thecarefuldesignoftheminimizingflow.Wedonotmodifytheenergy,hencethereliefoftheenergylandscapeandinparticularthe“number”oflocalminimaremainsunchanged.Butbyusinganevolutionthatfavorscertaintypesofdirections,weexpecttodecreasetheprobabilityoffallingintounwantedenergybasins.Typically,inmanyapplications,spatiallycoherentmotionsaretobepreferredovererraticevolutions.Forexample,inthetrackingproblem,theobjectofinterestislikelytohavesimilarshapesinconsecutive3
frames.Soifweinitializethecontourwiththeresultofthepreviousframe,itmakessensetoencouragethemotionswhichpreserveitsoverallappearance.Thisway,itmaybeeasiertododgeunexpectedlocallow-energyconfigurations.AtraditionalL2gradientdescentdefinitelydoesnothavethisdesirablepropertysincetheL2innerproductcompletelydisregardsthespatialcoherenceofthevelocityfield.3.NewInnerProductsandNewFlowsInthissection,wesupposethatthespaceFofalladmissibledeformationsoftheshapeΓisinitiallyequippedwiththeinnerproducth|iF,forexampleinthestandardcasewewouldhaveF=L2,andwestudyhowtobuildnewinnerproductsornewminimizingflowsfromthegivenone.3.1.DesigningnewinnerproductsDefinition1.ForanysymmetricpositivedefinitelinearoperatorL:FF,anewinnerproductcanbedefinedbyhu|viL=hLu|viF.(4)Here,forsimplicity,weassumethatthedomainandtherangeofLareequaltoF.AsimilarstudyispossibleiftheyarestrictlysmallerthanF,undercertainconditions,usingtheFriedrichsextensionofL(see[1]fordetails).Butthesetechnicaldetailsareoutofthescopeofthispaper.Thefollowingobservationiscentraltoourwork:Proposition2.IfrFE(Γ)existsandifLisalsoinvertible,thenrLE(Γ)alsoexistsandwehaverLE(Γ)=L1(rFE(Γ)).(5)Proof.Indeed:vF,δE,v)=h rFE(Γ)|viF =LL1rFE(Γ)|vF= L1rFE(Γ)|v L.TheaboveprocedureisofgreatpracticalinterestbecauseitallowstoupgradeanyexistingL2gradientflow.However,itisnotcompletelygeneralinthesensethanallinnerproductscannotbeexpressedinthis.mrofNevertheless,ifFisaseparableHilbertspace(i.e.completewithrespecttothenormkkF),theRieszrepresentationtheoremtellsusthatanyinnerproducth|iLsuchthatC>0,uF,kukL<CkukFcanbewrittenintheformofequation(4).Thissuggeststhatourprocedureaccountsforawiderangeofinnerproducts.4
3.2.DesigningnewminimizingflowsInthissubsection,wefollowtheinverseapproach.Insteadofworkingwiththeinnerproduct,weapplyalinearoperatorL:FFtothegradient,andwestudythepropertiesoftheresultingflow:Γddt=LrFE(Γ).(6)Thisnaturallysetsupahierarchyamongdifferenttypesofoperators:ifLispositive,theenergyisnon-increasingalongtheflow(6).Indeed,dE(Γ)=−hrFE(Γ)|LrFE(Γ)iF60.tdifLispositivedefinite,theenergystrictlydecreasesalongtheflow(6)untilacriticalpointoftheoriginalgradientflow(2)isreached.ifLissymmetricpositivedefiniteandinvertible,theflow(6)coincideswithagradientdescentrelativetotheinnerproducth|iL1,asdefinedinequation(4).ThethirdcaseiscontainedinSubsection3.1.AusefulexampleofthesecondcaseisgiveninSubsection.3.43.3.AddinganorthogonaltermTherateofdecreaseoftheenergywhenfollowingthedirectionofdescentddtΓisgivenby:dE(Γ) dΓ dt=rFE(Γ) dt60.FInparticular,fortheusualevolutionddtΓ=−rFE(Γ),wehave:)Γ(Ed=−krFE(Γ)k2FtdIfwedenotebyvanyvectorfielddefinedonΓsuchashrFE(Γ)|viF=0,thenaddingsuchavectorfieldvtotheusualgradientdescenttermwillnotchangetheamountofdecreasedenergy:dE(Γ)=hrFE(Γ)|−rFE(Γ)+viF=−krFE(Γ)k2Ftdsowecanchoosethefieldvwhichwewouldliketoaddtotheinitialgradient.Ratherthanchoosingv=0asusual,wecouldforexamplechooseone,notedvˆ,thatminimizesaregularizingcriterionR(−rFE(Γ)+v):vˆ=argminR(−rFE(Γ)+v)(7)v⊥rFE(Γ)Infactthisremarkstillstandswhenthechoiceofthedirectionofdescentisnotthegradientitself.IfwedenotebyutheinitiallyproposeddeformationfieldddtΓ,thenaddingavectorfieldwhichisorthogonaltothe5
gradientrFE(Γ)willnotchangetheamountofdecreasedenergyatthisstepofthegradientdescent(butwillchangetheevolution):)Γ(Ed=hrFE(Γ)|−u+viF=hrFE(Γ)|−uiFtdNotethatthenotionofbeingorthogonaltothegradientisindependentfromthechoseninnerproduct.Indeed,ifFandGaretwodifferentinnerproducts,rFEandrGEtheassociatedgradients,andFandGtheassociatednotionsoforthogonality,wehave:hrFE(Γ)|viF=δE,v)=hrGE(Γ)|viGso,consequently:hrFE(Γ)|viF=0⇐⇒hrGE(Γ)|viG=0rFE(Γ)Fv⇐⇒rGE(Γ)Gv.4.SomeSpatiallyCoherentMinimizingFlowsThistheoreticalstudyhasbroughtusthetoolsweneedtobetterapprehendminimizingflowsandbuildnewones.Wenowproposesomeminimizingflowsyieldingdifferentdegreesofspatialcoherence.Weinsistonthefactthatthisspatialcoherencehasnothingtodowithaneventualregularitytermintheenergyfunctional.Wedonotmodifytheenergy,sotheregularityconstraintonthecontourremainsunchanged.Wemodifythetrajectoryoftheminimizingflow,byfavoringspatiallycoherentmotions,butthisdoesnotconditiontheregularityofthefinalcontour.Inthefollowing,wesometimesusedifferentialgeometry.Wereferthereaderto[10]forthebasicnotions.4.1.MotiondecompositionAsimpleandusefulprocedure,todesignnewinnerproductsyieldingspatiallycoherentflows,istode-composethedeformationspaceintoasumofseveralmutuallyorthogonallinearsubspaces,andtoapplydifferentpenaltyfactorstothedifferenttypesofmotions.Typically,thesubspacesarechosenaccordingtoanapplication-specifichierarchyofthemotions.Forexample,rigid/non-rigid,affine/non-affine,etc.Wesupposethatsuchanorthogonal(withrespecttoh|iF)decompositionofthedeformationspaceFintoNclosedlinearsubspacesisavailable:F=F1F2⊥∙∙∙⊥FN.Thenanewinnerproductisderivedfromh|iFbyapplyingtheprocedureofSubsection3.1withNML=λiIdFi,1=iwherei,λi>0.Thelowerisλi,theshorteristhenormofthevelocityfieldsofsubspaceFi,andthestrongerwillbethistypeofmotioninthenewgradientflow.6
Obviously,Lissymmetricpositivedefiniteandinvertible.IfrFEexists,sodoesrLEandN1XrLE=λΠFi(rFE),(8)i1=iwhereΠFidenotestheorthogonalprojectionontheithsubspaceFi.Ofcourse,ifallλiareequalto1,rLEcoincideswithrFE.Weapplythisgeneralconstructiontotwousefulcases.Inthefirstcase,wedecomposethevelocityfieldintoatranslation,aninstantaneousrotation,arescalingmotionandanon-rigidresidual.Inthesecondcase,weisolatetheinstantaneousaffinemotion.RRInthefollowing,wedenotebyG=ΓxdΓ(x)/ΓdΓ(x)thecenterofmassoftheshape.4.1.1Translation,rotationandscalingInthisparagraph,wefocusonthetwo-dimensionalandthree-dimensionalcases.Theexpressionsbelowareforthe3Dcase,butcaneasilybeadaptedto2D.WedenotebyT,RandSthesubspacesofthetranslations,theinstantaneousrotationsaroundthecentroid,andthescalingmotionscenteredonthecentroid,respectively,definedontheshapeΓ: T=v:xΓ7→t|tR3,R=v:x7→(xG)ω|ωR3 ,S={v:x7→s(xG)|sR}.ThesesubspacesaremutuallyorthogonalfortheL2innerproduct.WesupposethattheyareincludedinthespaceofadmissibledeformationsF,andthatthelatterisruledbytheL2innerproduct.WedenotebyNtheorthogonalcomplementofthesesubspaces:F=TRSN.TheorthogonalprojectionofavelocityfielduononeofthesesubspacescanbefoundbyminimizingkuvkFwithrespecttovintheconsideredsubspace.Asanexample,wedetailthecomputationofRu).AsforeachelementvofRthereexistsanωsuchthatv(x)=(xG)ωforallx,weminimizethequantityku(∙−G)ωkL2withrespecttoω.ZZωku(y)(yG)ωk2dΓ(y)=u(y)(yG)ω(yG)dΓ(y)ΓΓZZZ=u(y)(yG)dΓ(y)+kyGk2dΓ(y)ω(yG)(yG)TdΓ(y)ωΓΓΓAsthisquantityiszerofortheωuwhichminimizesku(∙−G)ωkL2,wehave:ZZ1Zωu=kyGk2dΓ(y)Id(yG)(yG)TdΓ(y)u(y)(yG)dΓ(y)ΓΓΓToguaranteethatthelinearapplicationbetweenbracketsisinvertible,weproveitisasymmetricpositivedefinitematrixM.Wehaveindeedforanyx:Z2xTMx=kxk2kyGk2x(yG)dΓ(y)Γ7
Asforanyxandzwehave(xz)6kxkkzk,withequalityonlyifthetwovectorsarecollinear,andasxcannotbecollinearwithallyGforyinΓ,weobtainxTMx>0foranyx,soMispositivedefiniteandconsequentlyinvertible.NotethatifwehadnottakenforutheL2gradientbutthegradientforanotherinnerproductF,wewouldhavetoensurethesubspacesareorthogonalforthatinnerproductF,andcomputenewprojectionsbyminimizingkuvkF.WeapplythemethodwedetailedforthesubspaceRtotheothersubspacesTandS,andobtain:Z1Tu)(x)=u:=u(y)dΓ(y),|Γ|ΓRu)(x)=(RxG)ωu,Su)(x)=ΓRu(y)(yG)dΓ(y)(xG),ΓkyGk2dΓ(y)Nu)(x)=u(x)TRS)(u)(x).Inthetwo-dimensionalcase,theexpressionsoftheprojectionsarethesame,andtheexpressionofωucanbesimplifiedin:Rω=Γ(RyG)u(y)dΓ(y).uΓkyGk2dΓ(y)ThenewgradientisdeducedfromtheL2gradientbyequation(5)withL1=Id+1T+1R+1S.λTλRλSTheweightsλT,λRandλSareadaptedtotheuser’sneedsineachparticularapplication.Forexample:Boostrigid+scalingmotions:λTRS1,Boostrigidmotions:λTR1,λS=1,Boosttranslations:λT1,λR=λS=1.4.1.2AfnemotionWecanapplythissameideatothesubspaceAofinstantaneousaffinemotions:A=v:xΓ7→Ax+b|ARn×n,bRn .TheL2orthogonalprojectiononthissubspacewrites:Au)(x)=Ax+b,erehwZZ1A=u(y)(yG)TdΓ(y)(yG)(yG)TdΓ(y),ΓΓb=uAG.8
4.2.TheSobolevH1gradientflowWeconsiderthecanonicalinnerproductoftheSobolevspaceH1,Rn)ofsquareintegrablevelocityfieldswithsquareintegrablederivatives,definedontheshapeΓwithvaluesinRn.Fortwosuchfieldsuandvitsexpressionis:ZZ11hu|viH1=|Γ|u(x)v(x)dΓ(x)+|Γ|l2Dxu(x)Dxv(x)dΓ(x),ΓΓwhereDxdenotestheintrinsicderivativesonthecontourandlisacharacteristiclengthforthederivationwhichactsasaweightbetweenthetwointegrals.Thesecondtermofthisexpressionintroducesanotionofspatialcoherence:notonlythelengthofthevelocityfield,butalsoitsvariationsalongthecontourarepenalized.Indeed,Dxu(x)standsforthematrixofthederivativeofthevectorfielduatthepointxonthemanifoldΓandconsequentlyexpresseshowmuchthefielduvariesatpPointx.Inthetwo-dimensionalcase,Dxu(x)issimplyavector.Inthegeneralcase,Dxu(x)Dxv(x)=i,j(Dxu(x))i,j(Dxv(x))i,jistheusualinnerproductbetweenmatrices.BydefinitionofthegradientsofE(Γ),andthenthankstoanintegrationbypartsonthemanifoldΓ,we:evahv,hrL2E(Γ)|viL2=δE,v)=hrH1E(Γ)|viH12=h rH1E|viL2+lhD x rH1E|DxviL2=rH1El2ΔrH1E vL2ThustheH1innerproductisrelatedtotheL2innerproductasproposedinSubsection3.1throughthelinearoperatorL(u)=ul2Δu,whereΔdenotestheintrinsicLaplacianoperatoronthecontour,oftencalledtheLaplace-Beltramioperator.Asaconsequence,theH1gradientcanbeobtainedfromtheL2gradientbysolvinganintrinsicheatequationwithadataattachmentterm:l2Δu=u−rL2E.(9)Interestingly,thesolutionofequation(9)coincideswithZZ22argminku(x)−rL2E(Γ)(x)kdΓ(x)+l2kDxu(x)kdΓ(x)(10)uΓΓIntuitively,theH1gradientisasmoothedversionoftheL2gradientandcanbeobtainedbyaprocesssimilartotheimagerestorationprocessonamanifoldΓ,aproblemfamiliartotheimageprocessingcom-munity.Thefactorl2actsasaparameterbalancingtheinfluencesofthedatatermandtheregularizingterm.Actually,smoothingagradientusingthisparticularinnerproductisastandard”trick”,well-knowninnumericalanalysis.Aswementionedpreviously,thisideahasbeenintroducedincomputervisionsimul-taneouslybyus[8]andbySundaramoorthietal.[30].However,themainpointremainsthat,introducingthissmoothingviaamodificationofthegradientratherthandirectlyfromequation(10),warrantsthatthegradientdescentwilldecreasetheenergy.Inthetwo-dimensionalcase,theshapeisacurvewhichcanbeparametrizedbyitsarclengthσ,sothatanyfieldudefinedonΓcanbeseenasanapplicationfrom[0,|Γ|]toR2,where|Γ|isthelengthofthecurve.TheexplicitsolutionoftheequationΔu=uvisthenknownandgivenby:ZσZσu(σ)=1eσ/lAeτ/lv(τ)+eσ/lB+eτ/lv(τ)(11)l2009
e|Γ|/lIτ/lwithA=e|Γ|/l1ev(τ)ΓI1l/τandB=e|Γ|/l1ev(τ)dτ.ΓOfcourse,thechoiceoftheinitialpointonΓinordertodefineitsparametrizationbythearclengthdoesnotinterferewiththeresultingsolutionconsideredasanapplicationfromΓintoR2.Ingreaterdimensions,wecanobtaininpracticetheH1gradient,solutionofequation(9),fromaniterativeminimizationinducedby(10).Sincetheworkintroducedin[3],implementingaPDEonasurfaceisaffordableintheimplicitframeworkwiththelevelsetmethod[9,22].4.3.IntrinsicGaussiansmoothingWeapplytheprocedureofSubsection3.2todesignausefulminimizingflow:itisasmoothedversionoftheL2gradientflow.Hence,tosomeextent,itresemblestheH1gradientflowofSubsection4.2.However,here,weapplyanadhocproceduretotheL2gradientwithoutresortingtoaninnerproduct.WedefinealinearintrinsicsmoothingoperatorwhichmaybeseenasthecounterpartonthecontourofGaussiansmoothinginRn1,byconsideringthesolutionu˜oftheintrinsicheatequationonΓwithinitialconditionu:(˜u(.,0)=u∂u˜,(12)∂τ=Δ˜uwhereΔdenotestheLaplace-Beltramioperator.WethendenotebyLτuitssolutionu˜(.,τ)attimeτ0.Ontheonehand,Lτissymmetricpositive.Inparticular,aflow(6)basedonthisoperatordecreasestheenergy.Thelargerisτ,thesmootheristheflow.Lτissymmetric:hL0(u)|viL2=hu|L0(v)iL2=hu|viL2,∂τhLτ(u)|viL2=∂τhu|Lτ(v)iL2=−hDxu|DxviL2Lτispositive: hLτ(u)|uiL2=Lτ/2Lτ/2(u)|uL2= Lτ/2(u) L20Butontheotherhand,theinversionofLτforτ>0isanill-posedanti-diffusiveprocess.Soagradientinterpretationisnotavailable.5.NumericalExperimentsWithTheNewInnerProductsTheapproachpresentedinthispapercanbeappliedtovirtuallyanyactivecontourevolution.Inthissection,wehavechosensomeparticularapplicationstodemonstratetheinterestofourcontribution.Moreover,thecontentofthispaperisnotspecifictoaparticularimplementationofthecontourevolution.Inourexperiments,wehaveusedthelevelsetframework[9,22,28,20,21],motivatedbyitsnumericalstabilityanditsabilitytohandletopologicalchangesautomatically.TheimplicitframeworkalsooffersanelegantformulationoftheLaplace-Beltramioperator[2]andoftheaverageofaquantityalongthecontour.]52[01
Figure1:ShapewarpingwiththeL2gradientdescent(top)andwithamodifiedgradientdescentfavoringrigidplusscalingmotions(bottom):λT=λR=λS=0.025.Theadditionalcomputationalcostofourapproachdependsonthetypeofminimizingflowweconsider.Theextratimeisbarelynoticeablefortherigidplusscalingandaffineflowsofparagraphs4.1.1and4.1.2.Thelatteronlyrequiretocomputeahandfulofintegralsonthecontour.ThesmoothminimizingflowsofSubsections4.2and4.3aremoredemanding.In2D,theimplicitdiffusionequations(9)and(12)areequivalenttosomeconvolutionswithrespecttothecurvilinearcoordinateonΓ.In3Dandmore,theymustbesolvedwithsomeiterativemethods,foreachtimestep.5.1.ShapewarpingWeillustrateourapproachintheproblemofshapewarping.Inthiscontext,theenergyfunctionaltobeminimizedisameasureofdissimilaritybetweentheevolvingcontourandatargetcontour.Thestudyofshapemetricsisstillanactiveresearcharea[34,33,7,32],andtherearemanycandidatesforthedissimilaritymeasure.Inthispaper,weuseadifferentiableapproximationofthewell-knownHausdorffdistance,asproposedin[7],towarpthecontoursoftwodifferenthands.Figure1comparestheevolutionofthecontourwhenusingtheL2gradientdescent(toprow)andamodifiedgradientdescentfavoringrigidplusscalingmotions(bottomrow)asinparagraph4.1.1.Bothevolutionsachieveaperfectwarping.However,despitethesimilarityofthetwoinputshapes,theL2gradientflowgoesthroughsomestatesofcompletelydifferentappearances.Thetrajectoryfollowedbythisflowlooksparticularlyinefficientandunnatural,becausethenotionoflengthcontainedintheL2innerproductisveryfarfromourintuition.Incontrast,thebehaviorofourgradientflowisnaturalandvisuallypleasing.Somemoviesoftheseevolutionsareavailableinouradditionalsubmissiondata.InFigure2,weshowathree-dimensionalwarpingexamplefromateddybeartoHayaoMiyazaki’scharacterTotoro.WeuseheretheW1,2-normofthedistancefunctionsasproposedin[7].Despiteaninitialrigidregistration,theL2gradientdescentisunabletogivesatisfyingresults.Amodifiedgradientdescentfavoringrigidplusscalingmotionsleadstobetterresults.Thissuggeststhatourapproachcaninferrelevantcorrespondencesbetweenthetwocontours,asabyproductofthewarpingprocess.Thispoint-to-pointmatchingisobtainedbytrackingthepointsalongtheevolution.ItdoesnotmakemuchsensewithaL2gradientflow,becausethelatteryieldsastrictlynormalvelocityfield.Butwhenusingourapproach,thevelocityfieldhasameaningfultangentialpart.Maintaining11
Be the first to leave a comment!!

12/1000 maximum characters.