Matching Pursuit-Based Shape Representation and Re

MatchingPursuit-BasedShapeRepresentationandRecognitionUsingScale-SpaceFranc¸oisMendels,PierreVandergheynst,Jean-PhilippeThiranEcolePolytechniqueFederaledeLausanne,InstitutdeTraitementdesSignauxITS,STI,1015Lausanne,SwitzerlandReceived21May2005;accepted15December2006ABSTRACT:Inthispaper,weproposeananalyticallow-levelrepre-sentationofimages,obtainedbyadecompositionprocess,namelythematchingpursuit(MP)algorithm,asanewwayofdescribingobjectsthroughageneralcontinuousdescriptionusinganaffineinvariantdictionaryofbasisfunction(BFs).Thisdescriptionisusedtorecognizemultipleobjectsinimages.Inthelearningphase,atem-plateobjectisdecomposed,andtheextractedsubsetofBFs,calledmeta-atom,givesthedescriptionoftheobject.Thisdescriptionisthennaturallyextendedintothelinearscale-spaceusingthedefini-tionofourBFs,andthusprovidingamoregeneralrepresentationoftheobject.Weusethisenhanceddescriptionasapredefineddiction-aryoftheobjecttoconductanMP-basedshaperecognitiontaskintothelinearscale-space.Theintroductionofthescale-spaceapproachimprovestherobustnessofourmethod:weavoidlocalminimaissuesencounteredwhenminimizinganonconvexenergyfunction.Weshowresultsforthedetectionofcomplexsyntheticshapes,aswellasrealworld(aerialandmedical)images.VVC2007WileyPeriodicals,Inc.IntJImagingSystTechnol,16,162–180,2006;PublishedonlineinWileyInterScience().DOI10.1002/ima.20078Keywords:matchingpursuit;scale-spaceshaperepresentation;shaperecognition;sparserepresentationI.INTRODUCTIONShapemodelingandrecognitionisoneofthebasicoperationsinimageanalysis,andrepresentsagreatdealofinterest.Thesemeth-odsareusedinmanyapplicationsfields,suchasfacerecognition,retrievalofimagesindatabases(content-basedimageretrieval(CBIR)),satelliteimageanalysis,ormedicalimaging.Relevantregions,extractedfromaprevioussegmentationpro-cess,havetobecoded/representedinsomeway,sothatafurtheranalysisoftheirshapeispossible.Numerousmethodshavebeenpresented,butallofthemarelinkedbythesameneed:theshapehastobecodedinsomewaytobedescribedefficiently.Stynersum-marizesitas‘‘Ashapedescriptionissaidtobeefficientifshapesaredescribedbyconcisesetsofparametersorfeatures’’(StynerandGerig,2000).Moreover,thisdescriptionhastobeunique:wewanttogetthesamedescriptorfromthesameobjectasabasistoperformacorrectshaperecognitiontask.Thesedescriptionshavetobeinbothcasesinvarianttotranslation,rotation,andscale,asthesetrans-formationsdonotchangetheirintrinsicshapecharacterization.Theshaperecognitionprocessisthenrealized,basedontheirdescrip-tion,usuallyinaone-to-onecorrespondenceframework.Manyauthorshavepresenteddifferentwaystoproduceaso-calledshapedescriptororshaperepresentation,dependingonwhethertheygivequantitativeorqualitativemeasures(Pavlidis,1980;Loncaric,1998).ThereaderisreferredtotheworksbyPavli-dis(1980),Mehtreetal.(1997),Loncaric(1998),VeltkampandHagedoorn(1999),Kindratenko(2003),SafarandShahabi(2003),andZhangandLu(2004)forfurtherreferencesonclassicalmethods.Differentclassificationsofthesemethodswereproposedaccord-ingtogeneraldescriptioncriteria.Amongall,Pavlidis(1980)hasproposedthreedifferentclassificationsfortheshapeanalysismeth-ods(Pavlidis,1980):thefirstonedistinguishesbetweenboundary-based(local)andregion-based(global)methods.Thesecondonetakesintoaccounttheresultoftheanalysisasnumericalornot,bringingrespectivelyscalartransformorspatialtransformdomaintechniques.Thethirdonereliesontheinformationpreservingprop-ertyornot,ofeachmethods.Inthiswork,weareinterestedinmethodsrelatedtospatialsparserepresentationmodels,withbothlocalandglobalfeatures.Manyoftheseshapedescriptiontechniquescanbeseenasdecompositionmethodsintofundamentalelements/parts:manytermshavebeenusedtonamethem,suchasshapeprimitives(Sha-piro,1980),atoms(Pavlidis,1980),geons(Biederman,1985;Ull-man,1989),codons(HoffmanandRichards,1983),etc.,dependingofthefeaturesconsideredineachcase.Weusehereshapeprimi-tivesasageneralnamingconventionforalltheseterms.Thisexpressionisnormallydedicatedtoastructuralmodelofshape(see,e.g.,Shapiro,1980).Shapiro(1980)definedthemasfollows:Theprimitivesarethesimplepartsandintrusionsoftheshapewhichcanbederivedthroughthegraph-theoreticclusteringprocedure.Nevertheless,thisgenerictermofshapeprimitivescanbeinter-pretedinotherways:letuslookatthechaincodemethod(Freeman,1974),consistinginassigningadirectiontoeachCorrespondenceto:Dr.Franc¸oisMendels;e-mail:[e-mail]'2007WileyPeriodicals,Inc.segmentcomposingadigitizedcontour,oritsversionwithcriticalpoints(e.g.Freeman,1978).Wecanextendtheshapeprimitivesconceptandconsiderinthiscasethedirectionvectorsadjointtotheshapevariationinorientationastheshapeprimitives.Ofcourse,shapedecompositiontechniques,suchasFourierdescriptors(Arbteretal.,1990;Kauppinenetal.,1995),iconicrep-resentation(RaoandBallard,1995a,b;Ben-Arieetal.,1996a,b),medialshapedescriptors(SymmetricAxisTransform(SAT)(Blum,1967;BlumandNagel,1978),andSphericalHarmonicsfunctions(SPHARM(StynerandGerig,2000;Brechbu¨hleretal.,1995;Gerigetal.,2001)),leadnaturallytothisvisionofshapeprimitives,aseachofthemusessimpleelementstodesc