Morphological Component Analysis

MorphologicalComponentAnalysisJ.-L.Starcka,c,Y.Mouddena,J.Bobina,M.Eladb,andD.L.DonohocaDAPNIA/SEDI-SAP,Serviced’Astrophysique,CEA/Saclay,91191GifsurYvette,FrancebComputerScienceDepartment,StanfordUniversity,Stanford,CA,94305,USAcStatisticDepartment,StanfordUniversity,Stanford,CA,94305,USAABSTRACTTheMorphologicalComponentAnalysis(MCA)isaanewmethodwhichallowsustoseparatefeaturescontainedinanimagewhenthesefeaturespresentdifferentmorphologicalaspects.WeshowthatMCAcanbeveryusefulfordecomposingimagesintotextureandpiecewisesmooth(cartoon)partsorforinpaintingapplications.WeextendMCAtoamultichannelMCA(MMCA)foranalyzingmultispectraldataandpresentarangeofexampleswhichillustratestheresults.Keywords:BasisPursuitDenoising,TotalVariation,SparseRepresentations,PiecewiseSmooth,Texture,Wavelet,LocalDCT,Ridgelet,Curvelet,ICA,BlindSourceSeparation.1.INTRODUCTIONThetaskofdecomposingsignalsintotheirbuildingatomsisofgreatinterestformanyapplications.Insuchproblemsatypicalassumptionismadethatthegivensignalisalinearmixtureofseveralsourcesignalsofmorecoherentorigin.Theseproblemshavedrawnalotofresearchattentioninlastyears.IndependentComponentAnalysis(ICA)andsparsitymethodsaretypicallyusedfortheseparationofsignalmixtureswithvaryingdegreesofsuccess.Aclassicalexampleisthecocktailpartyproblemwhereasoundsignalcontainingseveralconcurrentspeakersistobedecomposedintotheseparatespeakers.Inimageprocessing,aparallelsituationisencounteredforexampleincasesofphotographscontainingtransparentlayers.AdictionaryDbeingdefinedasacollectionofwaveforms(ϕγ)γ∈Γ,thegeneralprincipleconsistsinrepre-sentingasignalsasa“sparse”linearcombinationofasmallnumberofbasiselementsϕγsuchthat:s=Xγaγϕγ(1)orasanapproximatedecompositions=mXi=1aγiϕγi+R(m).(2)Givensandthedictionaryatoms,animportantquestionistheatom-decompositionproblem,whereweseektherepresentationcoefficientsalphai.Whilethisisgenerallyahardtask(combinatorialcomplexity),pursuitmethodstoapproximatethedesiredcoefficientsareavailable.TheMatchingPursuit1,2method(MP)usesagreedyalgorithmwhichadaptivelyrefinesthesignalapproxi-mationwithaniterativeprocedure:•Sets0=0andR0=0.•Findtheelementαkϕγkwhichbestcorrelateswiththeresidual.Furtherauthorinformation:[e-mail]•UpdatesandR:sk+1=sk+αkϕγkRk+1=s−sk+1.(3)Inthecaseofnonorthogonaldictionaries,ithasbeenshown3thatMPmayspendmostofthetimecorrectingmistakesmadeinthefirstfewterms,andthereforeissuboptimalintermsofsparsity.TheBasisPursuitmethod3(BP)isaglobalprocedurewhichsynthesizesanapproximation˜stosbymini-mizingafunctionalofthetypeks−˜sk2`2+λ·kαk`1subjectto˜s=Φα.(4)Amongallpossiblesolutions,thechosenonehastheminimuml1norm.Thischoiceofl1normisveryimportant.Anl2norm,asusedinthemethodofframes,4doesnotpreservesparsity.3Inmanycases,BPorMPsynthesisalgorithmsarecomputationallyveryexpensive.Wepresentinthispaperanalternativetotheseapproaches,theMCAmethod(MorphologicalComponentAnalysis)whichcanbeseenasakindofBasisPursuitmethodinwhichi)ourdictionaryisaconcatenationofsub-dictionarieswhichisassociatedtoatransformationwithfastforwardandadjointimplementations,andii)anykindofconstraintcanbeeasilyimposedonthereconstructedcomponents.Section2presentstheMCAapproach.Section3andsection4showrespectivelyhowMCAcanbeusedfortextureseparationandinpainting.TwoextensionstomultichannelMCAareproposedinsections5and6.2.IMAGEDECOMPOSITIONUSINGTHEMCAAPPROACH2.1.ModelAssumptionAssumethatthedatasisalinearcombinationofKparts,s=PKk=1sk,whereeachskrepresentsadifferenttypeofsignaltobedecomposed.Ourmodelassumesthefollowingtoholdtrue:1.Foreverypossiblesignalsk,thereexistsadictionary(whichcanbeovercomplete),Φk∈MN×Lk(wheretypicallyLAN)suchthatsolvingαoptk=Argminαkαk0subjectto:sA=ΦAα(5)leadstoaverysparsesolution(i.e.kαoptkk0isverysmall).Thedefinitionintheaboveequationisessentiallytheovercompletetransformofsk,yieldingarepresentationαk.2.Foreverypossiblesignalsl,solvingfork6=lαoptl=Argminαkαk0subjectto:sl=Φkα(6)leadstoaverynon-sparsesolution.ThisrequirementsuggeststhatthedictionaryΦkisdistinguishingbetweenthedifferenttypesofsignalstobeseparated.Thus,thedictionariesΦkplayaroleofdiscriminantsbetweenthedifferentcontenttypes.Finally,weconsideronlydictionariesΦkwhichhaveafasttransformationTk(αk=Tksk)andreconstructionRk(sk=Rkαk).2.2.TheMCAconceptForanarbitrarysignalscontainingKlayersasalinearcombination,weproposetoseekthesparsestofallrepresentationsovertheaugmenteddictionarycontainingallΦk.Thusweneedtosolve{αopt1,...,αoptK}=Argmin{α1,...,αK}KXk=1kαkk0(7)subjectto:s=KXk=1Φkαk.Thisoptimizationtaskislikelytoleadtoasuccessfulseparationofthesignalcontent,basedontheassump-tionsmadeearlieraboutΦkbeingveryefficientinrepresentingonephenomenonandbeinghighlynon-effectiveinrepresentingtheothersignaltypes.Whilesensiblefromthepointofviewofthedesiredsolution,theproblemformulatedinEquation(7)isnon-convexandhardtosolve.Itscomplexitygrowsexponentiallywiththenumberofcolumnsintheoveralldictionary.TheBasisPursuit(BP)method3suggeststhereplacementofthe`0-normwithan`1-norm,thusleadingtoasolvableoptimizationproblem(LinearProgramming)oftheform{αopt1