La lecture en ligne est gratuite
Read Download

Share this publication

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