Simultaneous Structure and Texture Image Inpainting

mio,,,niversityPompeuFabra,UniversityofMinnesota,UCLAguille@tractAnalgorithmforthesimultaneousfilling-inoftextureandstricideaistofirstdecomposetheimageintothesumoftwofunctionswithdifferentba-siccharacteristics,andthenreconstructeachoneofthesefunctionsseparatelywithstructureandtexturefifirstfunctionusedinthedecompositionisofboundedvariation,representingtheunderlyingimagestruc-ture,ionofmissinginformationintheboundedvariationimageisreconstructedusingimagein-paintingalgorithms,whilethesameregioninthetextureimageisfielcontributionofthispaperistheninthecombinationofthesethreepreviouslydevelopedcom-ponents,imagedecompositionwithinpaintingandtexturesynthesis,whichpermitsthesimultaneoususeoffilds:Inpainting,filling-in,structure,texture,texturesynthesis,boundedvariation,imagedecomposition.1IntroductionThefilling-inofmissinginformationisaveryimportanttopicinimageprocessing,wi,recover-inglostblocks),,removalofobjects),,scratchremoval).Thebasicideabehindthealgorithmsthathavebeenproposedintheliteratureistofiformationcanbeau-tomaticallydetectedasin[4,8],orhintedbytheuserasinmoreclassicaltexturefillingtechniques[7,12,27].Thealgorithmsreportedintheliteraturebestperformforpuretexture,[8,12,27],orpurestructure,[2,3,4](seealsoearlyworkin[23],whichshowstheuseoftheBurt-Adelsonpyramidforthereconstructionofsmoothregions).1ThismeansthatforordinaryimagessuchastheoneinFig-ure1,[25],itwasshownhowtoautomaticallyswitchbetweenthepuretextureandpurestructurefidonebyanalyzingtheareasurroundingtheregiontobefilled-in(inspiredby[15]),andostimageareasarenotpuretextureorpurestructure,thisap-proachprovidesjustafirstattemptinthedirectionofsimul-taneoustextureandstructurefilling-in(attemptwhichwasfoundsufficientfortheparticularapplicationoftransmis-sionandcodingpresentedinthepaper).Itisthegoalofthispapertoadvanceinthisdirectionandproposeanewtech-niquethatwillperformbothtexturesynthesisandstructureinpaintinginallregionstobefiicideaofouralgorithmispresentedinFigure3,g-inalimage(firstrow,left)isfirstdecomposedintothesumoftwoimages,onecapturingthebasicimagestructureandonecapturingthetexture(andrandomnoise),llowstherecentworkbyVeseandOsherreportedin[28].ThefirstimageisinpaintedfollowingtheworkbyBertalmio-Sapiro-Caselles-Ballesterdescribedin[4],whilethesecondoneisfilled-inwithatexturesynthesisalgorithmfollowingtheworkbyEfrosandLeungin[8],reconstructedimagesarethenaddedbacktogethertoobtainthereconstructionoftheoriginaldata,firstrow,rwords,thegeneralideaistoperformstruc-tureinpaintingandtexturesynthesisnotontheoriginalim-age,butonasetofimageswithverydiffompositionissushowhowthisapproachoutperfoposedalgorithmhasthenthreemainbuildingblocks:Imagedecomposition,image(structure)inpaint-ing,extthreesectionswebrieflowintheexperimentalsection,thesepar-ticularselections,whichhavebeenshowntoproducestate-of-the-artresultsineachoneoftheirparticularapplications,outperformpreviouslyavailabletechniqueswhencombinedProceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’03)

1063-6919/03 $17.00 © 2003 IEEE

Authorized licensed use limited to: Guangdong Univ of Tech. Downloaded on December 27, 2009 at 21:33 from IEEE Xplore. Restrictions apply.

oncludingremarkssectionwediscussthepossibleuseofotherapproachestoaddresseachoneoftheretheinfimumiscomputedoveralldecompositions(2)howedthatifthecomponentrepresentstextureornoise,then,andproposedthefollowingnewimagerestorationmodel:2ImagedecompositionInthissectionwereviewtheimagedecompositionapproachproposedin[28],whichisoneofthethreekeyingredieainedintheintroduction,thisdecompo-sitionproducesimagesthatareverywellsuitedfortheim-ageincriptionbelowisadaptedfrom[28],wherethetechniquewasfier-estedreadersarereferredtothisworkformoredetails,ex-amples,mainingredientsofthedecompositiondevel-opedin[28]arethetotalvariationminimizationof[26]forimagedenoisingandrestoration,andthespaceofoscillat-ingfunctionsintroducedin[21]agivenobservedimage,ldbejustanoisyversionofatrueunderlyingimage,orcouldbeatexturedimage,thenbeingasimplesketchyapproximationoracartoonimageof(withsharpedges).Asimplerelationbetweenandcanbeexpressedbyalinearmodel,introducinganotherfunction,suchthatIn[26],theproblemofrecon-structingfromisposedasaminimizationprobleminthespaceoffunctionsofboundedvariationIR,[10],allowingforedges:(3)In[28],theauthorsdevisedandsolvedavariantofthismodel,wmodelleadsustothedecompositionweneedforsimultaneousstructureandtexturefilowingminimizationproblemistheoneproposedin[28],inspiredby(3):(4)wherearetuningparameters,firsttermensuresthatIR,thesecondtermen-suresthatdiv,yonthenorminofFor,asusedinthispaper,thecorrespondingEuler-Lagrangeequationsare[28]div(5)(6)(7)(1)ondtermintheenergyisafidelityterm,whilethefirsttermisaregular-izingterm,toremovenoiseorsmalldetails,[21],actboththecomponentasanoscillatingfunction(textureornoise)from,Meyerproposedtheuseofadifferentspaceoffunctions,o-ducedthefollowingdefinition,andalsoprovedanumberofresultsshowingtheexplicitrelationshipbetweenthenormbelowandthemodelin[26](see[21,28]fordetails):DefiotetheBanachspaceconsistingofwhichcanbewrittenasallgeneralizedfunctionsAscanbeseenfromtheexamplesin[28]andtheimagesinthispaper,theminimizationmodel(5)allowstoextractfromagivenrealtexturedimagethecomponentsand,suchthatisasketchy(cartoon)approximationof,andrepresentsthetextureorthenoise(notethatthisisnotjustalow/highfrequencydecomposition).Forsometheoreticalresultsandthedetailedsemi-implicitnu-mericalimplementationoftheaboveEuler-Lagrangeequa-tions,see[28].3TexturesynthesisWenowdescribethesecondkeycomponentofourscheme,thebasicalgorithmusedtofill-intheregionofmissingin-formationin,ortheexamplesinthispaper,weusethealgorithmdevelopedin[8],thisisnotcrucialandothertexturesynthesistechniquescouldbeIR(2)inducedbythenormdefinedasthelowerboundofallnormsofthefunctionswhere,2Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’03)

1063-6919/03 $17.00 © 2003 IEEE

Authorized licensed use limited to: Guangdong Univ of Tech. Downloaded on December 27, 2009 at 21:33 from IEEE Xplore. Restrictions apply.

weverthatmodulotheselec-tionofafewparameters,thisalgoer,thisalgorithmisverywellsuitedtonaturrethebasicreasonsthatleadustotheselectionoLettheregiontobefi-filled,pixelbypixel,representativetemplate,withknownpix-tobefi,touchingthepixelproceedtofindasetoffromtheavailableneighborhood,suchthatagivendistanceisbelowapre-defi[8],isthenormalizedsumofsquareddifferences(SSD)chasetof’sisfound,werandomlychoseoneofthepixelswhoselfi,ofallfullyavailabledataintheimage,welookatthosecloserthanapre-definedthresholdto,replacethecurrentpixelbeingfilled-ininthelgorithmisconsiderablyfasterwhenusingtheimprovementsin[11,30].,atatsteadystate,Thismeansthatisconstantinthedirectionoftheisophotes,therebyachieviailsonthenumericalimplementationofthisin-paintingtechnique,whichfollowsthetechniquesintro-ducedin[19,26],aswellasnumerousexamplesandappli-cations,see[4].Noteinparticularthatateverynumericalstepof(8),astepofanisotropicdiffusion,[1,24],isap-plied[4].Multiresolutioncanalsobeappliedtospeed-uptheconvergence[4].Forimageinpaintingalternativestothisapproach,see[2,3].Inparticular,[3]showstherelationshipoftheaboveequationwithclassicalfluiddynamics,andpresentsadif-ferentflkin[2]presentsaformalvariationalap-prseworkswereinpartin-spiredby[20,22]./guille/onalrelatedworkisdescribedin[6,13,14,17,18],while[5,9,16,29]tsonthesecontributionsandcomparisonswiththeworkjustdescribedareprovidedin[4].5ExperimentalresultsWenowpresentadditionalexperimentalresultsandcom-parewiththecasewhentheimageisnotdecomposedpriortofilling-in,andjustonealgorithm,eitherimageinpaintingortexturesynthesis,streatedsimilarlyto[4,8](withadditionalvectorialoperations).Whileeachofthethreecomponentsofthealgorithmhereproposedhasanumberofparameters,ypa-rametersthatvaryareandthenumberofstepsininpaint-ing,aonalfigures,incolor,/guille/4ImageinpaintingWenowdescribethethirdkeycomponentofourproposedscheme,thealgorithmusedtofiex-amplesinthispaperweusethetechniquedevelopedin[4].Otherimageinpaintingalgorithmssuchasas[2,3]ainletbetheregiontobefilledin(inpainted)icideaininpaintingistoandsmoothlypropagangbytheimage,thispropagationisachievedbynumericallysolvingthepartialdifferentialequation(isanartificialtimemarchingparameter)6ConclusionsandfuturedirectionsInthispaperwehaveshownthecombinatheimageswehaveused,thenumberofnumeri-calstepsofthedecompositionisequalto,ingthevaryingparame-ters,forfigure3andfortheothers,whilethenumberofinpaintingsteps(withadiscretetimestepof)are200forfigure3and2000fortheothers(almostidenticalimageswereobtainedwhen2000stepswereusedforFigure3).(8)standforthegradient,Laplacian,andwhere,,andorthogonal-gradient(isophotedirection)uationissolvedonlyinside,withproperboundarycon-ditionsinforthegrayvaluesandisophotedirections[4].3Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’03)

1063-6919/03 $17.00 © 2003 IEEE

Authorized licensed use limited to: Guangdong Univ of Tech. Downloaded on December 27, 2009 at 21:33 from IEEE Xplore. Restrictions apply.

Thebasicideaistofirstdecomposetheimageintothesumoftwofunctions,onethatcanbeefficientlyreconstructedviainpaintingandonethatcanbeeffirmitsthesimultaneoususeoftrastwithpreviousapproaches,bothimageinpaintingandtexturesynthesisareappliedtotheregionofmissinginformation,onlythattheyareappliednottotheoriginainedresultsout-performthoseobtainedwherexperimentsaretobecarriedouttoobtainthebestcombinationofimagedecomposition,imageinpaint-ing,numberofalgorithmsexistforeachoneofthesethreekeycomponents,thecom-binationthatprovidesthebestvisualresultsisaninterestingexperimentalandtheoreticalresearchtopic.[5]man,Photoshopretouchinghandbook,IDGBooksWorlwide,1998.[6],“LocalinpaintingmodelsandTVinpainting,”.62:3,pp.1019-1043,2001.[7]t,“Multiresolutionsamplingprocedureforanalysisandsynthesisoftextureimages,”Proceed-ingsofACMSIGGRAPH,July1997.[8],“Texturesynthesisbynon-parametricsampling,”IEEEInternationalConferenceonComputerVision,Corfu,Greece,pp.1033–1038,Sept.1999.[9]-Male,TheRestorer’sHandbookofEaselPainting,VanNostrandReinhold,NewYork,1976.[10]y,MeasureTheoryandFinePropertiesofFunctions,CRCPress,London,1992.[11],ante,,“Growingfit-tedtextures,”izationandComputerGraphics,toappear.[12],“Pyramidbasedtextureanalysis/synthesis,”ComputerGraphics(SIGGRAPH1995),pp.229–238,July1995.[13]a,“Combiningfrequencyandspatialdomaininformationforfastinteractiveimagenoiseremoval,”ComputerGraphics,pp.269-276,SIG-GRAPH96,1996.[14],n,er,,“Detectionandremovaloflinescratchesinmotionpicturefilms,”ProceedingsofCVPR’99,uterVisionandPatternRecognition,FortCollins,Colorado,USA,June1999.[15],,,“Isthereanytextureintheimage?,”PatternRecognition29:9,pp.1437–1446,1996.[16],TheCommissarVanishes,HenryHoltandCompany,1997.[17]m,,rald,,“Detectionofmissingdatainimagesequences,”IEEETransactionsonImageProcessing11:4,pp.1496-1508,1995.[18]m,,rald,,“Interpolationofmissingdatainimagesequences,”IEEETransactionsonImageProcessing11:4,pp.1509-1519,1995.4AcknowledgmentsThisworkwaspartiallysupportedbytheOfficeofNavalResearch,theNationalScienceFoundation,theNationalIn-stituteofHealth,theOfficeofNavalResearchYoungInves-tigatorAwardtoGS,thePresidentialEarlyCareerAwardsforScientistsandEngineers(PECASE)toGS,aNationalScienceFoundationCAREERAwardtoGS,bytheNationalScienceFoundationLearningandIntelligentSystemsPro-gram(LIS),andbytheProgramaRamonyCajal(Minis-teriodeCienciayTecnologia,Spain).Caselles,nces[1]z,,,“Imageselec-tivesmoothingandedgedetectionbynonlineardiffu-sion,”.29,pp.845-866,1992.[2]ter,mio,es,,a,“Filling-inbyjointinterpolationofvectorfieldsandgreylevels,”rocessing10,pp.1200-1211,August2001.[3]mio,zi,,“Navier-Stokes,fluiddynamics,andimageandvideoinpaint-ing,”mputerVisionandPatternRecog-nition(CVPR),Hawaii,December2001.[4]mio,,es,ter,“Imageinpainting,”ComputerGraphics(SIGGRAPH2000),pp.417–424,dings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’03)

1063-6919/03 $17.00 © 2003 IEEE

Authorized licensed use limited to: Guangdong Univ of Tech. Downloaded on December 27, 2009 at 21:33 from IEEE Xplore. Restrictions apply.

[19],“Explicitalgorithmsforanewtimedependentmodelbasedonlevelsetmotionfornonlineardebluringandnoiseremoval,”.,22,pp.387-405,2000.[20],“Level-linesbaseddisocclu-sion,”rocessing,October1998.[21],OscillatingPatternsinImageProcessingandNonlinearEvolutionEquations,AMSUniversityLectureSeries22,2002.[22]rg,d,,Filter-ing,Segmentation,andDepth,Springer-Verlag,Berlin,1993.[23],n,,,“Pyramid-basedcomputergraphics,”RCAEngi-neer30(5),pp.4-15,1985.[24]“Scale-spaceandedgedetec-tionusinganisotropicdiffusion,”IEEE-PAMI12,pp.629-639,1990.[25],,mio,“Structureandtexturefilling-inofmissingimageblocksinwire-lesstransmissionandcompressionapplications,”rocessing,toappear.[26],,,“Nonlineartotalvariationbasednoiseremovalalgorithms,”PhysicaD,no.60,pp.259–268,1992.[27]la,“Texturecharacterizationviajointstatisticsofwaveletcoefficientmagnitudes,”Proc.5thIEEEInt’eProcessing,1998.[28],“Modelingtextureswithtotalvariationminimizationandoscillatingpatternsinimageprocessing,”JournalofScientificComputing,toappear.[29],TheRavishedImage,’sPress,NewYork,1985.[30],“Fasttexturesynthesisusingtree-structuredvectorquantization,”ComputerGraph-ics(SIGGRAPH2000), Blockbest match

Templatecurrent pixelcandidateFigure1:Exampleofimagewithbothtextureandstructure.8−neighborhood of lost blockFigure2:Basictexturesynthesisprocedure5Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’03)

1063-6919/03 $17.00 © 2003 IEEE

Authorized licensed use limited to: Guangdong Univ of Tech. Downloaded on December 27, 2009 at 21:33 from IEEE Xplore. Restrictions apply.

Figure3:ginalimageinthefirstrow,left(asectionofFigure1)isdecomposedintoastructureimageandatextureimage,[28],wtheimageontheleftmainlycontainstheunderlyiwoimagesarereconstructedviainpainting,[4],andtexturesynthesis,[8],respectively,geontheleftmanagedtoreconstructthestructure(seeforexamplethechairverticalleg),ultingtwoimagesareaddedtoobtainthereconstructedresult,firstrow,right,4:ginalimageisshownfirst,followedbytheresultofouralgorithmandtheresultwithpuretexturesynthesis.6Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’03)

1063-6919/03 $17.00 © 2003 IEEE

Authorized licensed use limited to: Guangdong Univ of Tech. Downloaded on December 27, 2009 at 21:33 from IEEE Xplore. Restrictions apply.