Analysis of Iterative Methods for Solving a Ginzbu

AnalysisofIterativeMethodsforSolvingaGinzburg-LandauEquationAloBorzi1,HaraldGrossauer2,andOtmarScherzer21InstituteforMathematics,UniversityofGrazHeinrichstr.36,A-8010Graz,Austria2DepartmentofComputerScience,UniversityofInnsbruckTechnikerstr.25,A-6020Innsbruck,Austriafharald.grossauer,[e-mail](volumetric)data(whichhasapplicationsinframeinterpolation),improvingsparselysampleddataandtollinfragmentarysurfaces.Inthispaperwereviewdigitalinpaintingalgorithmsandcomparetheirper-formancewithaGinzburg-Landauinpaintingmodel.ForthesolutionoftheGinzburg-Landauequationwecomparetheperformanceofseveralnumericalalgorithms.Astabilityandconvergenceanalysisisgivenandtheconsequencesforapplicationstodigitalinpaintingarediscussed.Keywords:Ginzburg-Landauequation,inpainting,diusionltering,non-linearpartialdierentialequations,variationalproblemsAMS:35K57,65M061IntroductionInpaintingistheprocessofrestorationofmissingimagedata;itistypicallydonebyartists.DigitalInpaintingisperformedbycomputerprogramsrequiringauseronlytomarkinpaintingdomainsinadigitizedimage.Digitalinpaintinghasseveralapplicationsinphotography[1],suchasscratchremovalorretouch-ing.Combininginpaintingalgorithmswithscratchdetectionalgorithms(see,e.g.,[2]andthereferencestherein)allowstoalmostautomaticallyrestorelargesetsofdegradedimagesorevencompletemovies.Adicultyassociatedwithdigitalinpaintingistosetupameasureofvisualsensitivitytowardsdefectswhichcanbeusedinacomputercode.AnattemptinthisdirectionistheperceptuallybasedphysicalerrormetricintroducedbyRamasubramanian,Pat-tanaik&Greenberg[3].Today,thecommonpsychologicalopinionisthatthehumanperceptualsystemismoresensitivetoedgesthantotextureandmostsensitivetojunctions;seeCaselles,Coll&Morel[4]asaparadigmofthisstate-mentinthecomputerscienceandmathematicalliterature.Asaconsequenceagoodinpaintingalgorithmaimstoconnectcorrespondingedgesandextrapolatetexturessmoothly.Inthefollowingwesurveysomerecentlyproposedinpaintingmethodsbasedonlevellinestrategies,partialdierentialequations(PDEs)andvariationalmethods.Othertopicsrelatedtoimageinpaintingsuchastexturesynthesiswithstatisticalmethods(see,e.g.,[5,6]andreferencestherein),combinedPDE/texturesynthesismethods(see[7{9])andimageinterpolationwithsamplingmethods(see,e.g.,[10,11])arenotconsideredfurtherinthispaper.{In[12]weproposedtousetheGinzburg-Landauequationfordigitalin-paintingpurposes.OriginallythisequationwasdevelopedbyGinzburg&Landau[13]tophenomenologicallydescribephasetransitionsinsupercon-ductorsneartheircriticaltemperature.Theequationhasproventobeusefulinseveraldistinctareas:itisusedtomodelsometypesofchemicalreactions,likethefamousBelousov-Zhabotinskyreaction,tomodelboundarylayersinmulti-phasesystems,andtodescribethedevelopmentofpatternsandshocksinnon-equilibriumsystems(see[14{16]andreferencestherein).SolutionsoftherealvaluedGinzburg-Landauequationdevelopareaswithvalues1,whichareseparatedbyphasetransitionregions,i.e.,interfacesofminimalarea(cf.remarkafterequation(11)).ThispropertymakestherealvaluedGinzburg-Landauequationareasonablemethodforhighqualityinpaintingofbinaryimages,i.e.,levelsets.In[12]andinthispaperwefocusoninpaintingofgray-valuedorcolorimages.ForthispurposeweusethecomplexvaluedGinzburg-Landauequation.In[17]wehavecombinedthisalgorithmwithatexturesynthesisapproach.{AninpaintingalgorithmbasedonlevellineshasbeenproposedbyMasnou&Morel[18,19].Itconsistsofseveralstages:1.AllT-junctions{thatarepointswherelevellineshittheboundaryoftheinpaintingdomain{aretabulated.2.AtableofpairsofcompatibleT-junctionsisgenerated.TwoT-junctionsarecompatible,iftheirassociatedlevellinesbelongtothesamegraylevelintensityandhavethesameorientation.3.FromthesetofcandidatesoflevellinesconnectingcompatibleT-junctions,theonehavingthelowesttotalgeneralizedelasticaenergyXZLi;j(+jjp)ds(1)isselected.HereLi;jdenotesthelevellineconnectingtheT-junctionswiththeindicesiandj,andthesumiswithrespecttoalllevellines.Forconvexinpaintingdomainsthesearejuststraightlines.Thealgorithmiscomputationallyexpensive:atriangulationoftheinpaintingdomainhastobecalculatedandanoptimalsetoflevellinesoutofallpossibleconnectionshastobefound.Combinationwithadynamicprogrammingapproachandsortingoutinadmissibleconnectionsatanearlystagekeepsruntimecomplexityrelativelylow.Theimplementationpresentedin[18]doesnotallowinpaintingdomainswithholes(doughnutshapedinpaintingdomains).HandlingsuchinpaintingdomainsisnotadicultyforPDEbasedalgorithmsastheonesoutlinedbelowandours.{Ballesteretal.[20]haveproposedavariationalmethodforinpainting.TheyderiveasystemofcoupledPDEstoextrapolategraylevelvaluesandthegradientdirectionvectoreldsmoothlyintotheinpaintingdomain.ThesystemofPDEsissolvedusinglevelsetsoftheimageintensityfunction.Thismakesthenumericalresultsdependonimplementationaldetails,inparticulartheorderinwhichthelevelsetsareprocessed(cf.gure7).{Bertalmioetal.[21]introduc