Fast image inpainting based on coherence transport

FASTIMAGEINPAINTINGBASEDONCOHERENCETRANSPORTFOLKMARBORNEMANNANDTOMMÄRZ∗Abstract.High-qualityimageinpaintingmethodsbasedonnonlinearhigher-orderpartialdifferentialequationshavebeendevelopedinthelastfewyears.Thesemethodsareiterativebynature,withatimevariableservingasiterationparameter.Forreasonsofstabilityalargenumberofiterationscanbeneededwhichresultsinacomputationalcomplexitythatisoftentoolargeforinteractiveimagemanipulation.Basedonadetailedanalysisofstationaryfirstordertransportequationsthecurrentpaperdevelopsafastnoniterativemethodforimageinpainting.Ittraversestheinpaintingdomainbythefastmarchingmethodjustoncewhiletransporting,alongtheway,imagevaluesinacoherencedirectionrobustlyes-timatedbymeansofthestructuretensor.Dependingonameasureofcoherencestrengththemethodswitchescontinuouslybetweendiffusionanddirectionaltransport.Itsatisfiesacomparisonprinciple.Ex-perimentswiththeinpaintingofgraytoneandcolorimagesshowthatthenovelalgorithmmeetsthehighlevelofqualityofthemethodsofBertalmioetal.(2000),Masnou(2002),andTschumperlé(2006),whilebeingfasterbyatleastanorderofmagnitude.1.Introduction.Nontextureimageinpainting,alsotermedimageinterpolation,isthetaskofrestoringthevaluesofadigitalimageforadestroyed,orconsciouslymasked,subregionoftheimagedomain.Itthusbelongstotheareaofdigitalimageprocessing.Ontheotherhand,ifweconsideraregionthatpartiallyoccludessomeobjectsoftheimagetherelatedcomputationaltaskofmakingtheseobjectsfullyvisibleistermeddisocclusionintheareaofimageanalysis.Thequalifyingtermnontexturereferstothecasethatlocalfeaturesandshortrangecorrelationsoftheimagearesufficientforaresultofhighperceptivequality.Thereisnodetectionofmoreglobalstructureslikesymmetryorlongrangespatialcorre-lationsperceivedaspatternsandtextures.Ifthetaskathandrequiredsuchglobalinformation,onewouldhavetorelyonthemethodologyofpatternrecognitionandtexturesynthesis.Itisalsonotpossibletorestoresemanticcontentofanimage,suchasgivenbythephysiologyoftheshownobjectorthephysicsoftheillumination.Nevertheless,impressiveresultsareobtainablebynontextureimageinpaintingasillustrated,e.g.,inFig.1.Theinpaintingresult(usingthemethodofthispaper)thatisshowninFig.1.cisofsuchahighqualitythatanonexpertobservermightconsideritastheoriginalimage.Notethateventheflow-like(local)textureoftheeyebrowhasbeenrestoredinaplausibleway.However,alookattheoriginalshowninFig.1.arevealsthatsomeinformationsuchasreflectionsonthepupilhavenotbeenrestored,makingtheinpaintedresultappearlessvivid.TheStateofAffairs.Considerableinterest,andexcitement,hasbeengeneratedfortheinpaintingproblemintheappliedmathematicscommunitybythecelebratedpapersofMasnouandMorel(1998)andBertalmioetal.(2000).Thesepapershaveshownthatsophisticatedmathematicaltoolssuchasvariationalprinciplesandpar-tialdifferentialequationscanbefruitfulhere.Manyinterestingapplicationsoftheinpaintingmethodologyhavebeendocumentedsincethen,suchastherestorationofoldphotographs,removalofsuperimposedtextorselectedobjects,digitalzoom-in,andedgedecoding.Forasurveyofthemathematicsinvolved,ofmanymethodsandapplications,seeChanandShen(2005a,Chap.6).Atafirstsight,itmightappearsurprisingthattoolsfromcontinuousmathe-maticsbearpoweronsolvingproblemsfordiscreteobjectssuchasdigitalimages.However,theabstractionofacontinuous,analogimagethatisonlyapproximated∗ZentrumMathematik,TechnischeUniversitätMünchen,Boltzmannstr.3,85747Garching,Germany({bornemann,maerzt}@ma.tum.de).ManuscriptasofMarch10,2006;revisionasofApril3,2007.12F.BORNEMANNANDT.MÄRZ(a)original;241×159px2(b)vandalization(courtesyofTelea2004,Fig.8.i)(c)inpaintedbyourfastmethod;1CPUtime0.4secFIG.1.Adigitalimage(a),itsvandalization(b),anditsreconstructionbyinpainting(c).bythedigitaloneallowsforagenuinehandlingofthemultiscalenatureofimages(seeGuichardandMorel2000,Fig.20.1).Thehigh-levelofabstractionthatisgivenbythetoolsofcontinuousmathematicsconsiderablycontributestotheunderstand-ingoftheproblemsofimageprocessingandofthediscretealgorithmsused.Butitalsocontributestotheconstructionofnewdiscretealgorithms.Thisapproachtodigitalimageprocessingiselaborated,e.g.,inthebooksofAubertandKornprobst(2002),ChanandShen(2005a),GuichardandMorel(2000),Kimmel(2004),Sapiro(2001),andWeickert(1998).Wecalltheabstractionoftheunderlyingcontinuousimagethehigh-resolutionlimituofthediscreteimageuh,withhbeingameasureofthefinenessoftheres-olution.2Note,thatthetechnologicalprogresscaninfactbedescribedasrealizingh→0:professionalphotographersalreadyusedigitalcamerasthatmakeimagesofasizeof4992×3328px2,givingaresolutionof832dpifora600×400photoprint.Suchfineresolutionsarebarelymetinday-to-daysimulationswithnumericalpar-tialdifferentialequations.Certainly,someengineerswouldconsidersuchgridsas“numericallyconverged”.Basically,therearetwomajormechanismstogetimageinformationintothein-paintingdomain:diffusionandtransport(seeChanandShen2002a).Fortheinpaint-ingproblem,nonlinearpartialdifferentialequationscombiningthesemechanismshavebeenobtainedphenomenologically(e.g.,Bertalmioetal.(2000)orTschumperlé(2006)),axiomatically(e.g.,Casellesetal.(1998)),orfrom