SOBOLEV GRADIENTS AND IMAGE INTERPOLATION

Parimah Kazemi

Description

SOBOLEV GRADIENTS AND IMAGE INTERPOLATION? PARIMAH KAZEMI† AND IONUT DANAILA ‡ Abstract. We present here a new image inpainting algorithm based on the Sobolev gradient method in conjunction with the Navier-Stokes model. The original model of Bertalmıo et al. [Proc. Conf. Comp. Vision Pattern Rec., 2001] is reformulated as a variational principle based on the minimization of a well chosen functional by a steepest descent method using Sobolev gradients. This new theoretical framework offers an alternative of the direct solving of a high-order partial differential equation, with the practical advantage of an easier and more flexible computer implementation. In particular, the proposed algorithm does not require any constant tuning, nor advanced knowledge of numerical methods for Navier-Stokes equations (slope limiters, dynamic relaxation for Poisson equation, anisotropic diffusion steps, etc). Using a straightforward finite difference implementation, we demonstrate, through various examples for image inpainting and image interpolation, that the novel algorithm is faster than the original implementation of the Navier-Stokes model, while providing results of similar quality. The paper also provides the mathematical theory for the analysis of the algorithm. Using an evolution equation in an infinite dimensional setting we obtain global existence and uniqueness results as well as the existence of an ?-limit. This formalism is of more general interest and could be applied to other image processing models based on variational formulations.

• diffusion term


• sobolev gradients


• hm norm


• ??u ·


• image inpainting


• digital image


• h2 when


• algorithm based


• equation


• navier-stokes model

Sujets

• R?chitoasa
• Kazmi
• Digital image
• Équation
• maths

Informations

• Publié par: pefav
• Nombre de lectures: 15
• Langue: English

Extrait

SOBOLEVGRADIENTSANDIMAGEINTERPOLATION ∗ PARIMAHKAZEMI † AND IONUTDANAILA ‡ Abstract.WepresenthereanewimageinpaintingalgorithmbasedontheSobolevgradient methodinconjunctionwiththeNavier-Stokesmodel.TheoriginalmodelofBertalmı´oetal.[Proc. Conf.Comp.VisionPatternRec.,2001]isreformulatedasavariationalprinciplebasedonthe minimizationofawellchosenfunctionalbyasteepestdescentmethodusingSobolevgradients.This newtheoreticalframeworkoffersanalternativeofthedirectsolvingofahigh-orderpartialdifferential equation,withthepracticaladvantageofaneasierandmoreflexiblecomputerimplementation.In particular,theproposedalgorithmdoesnotrequireanyconstanttuning,noradvancedknowledge ofnumericalmethodsforNavier-Stokesequations(slopelimiters,dynamicrelaxationforPoisson equation,anisotropicdiffusionsteps,etc).Usingastraightforwardfinitedifferenceimplementation, wedemonstrate,throughvariousexamplesforimageinpaintingandimageinterpolation,thatthe novelalgorithmisfasterthantheoriginalimplementationoftheNavier-Stokesmodel,whileproviding resultsofsimilarquality. Thepaperalsoprovidesthemathematicaltheoryfortheanalysisofthealgorithm.Usinganevolution equationinaninfinitedimensionalsettingweobtainglobalexistenceanduniquenessresultsaswell astheexistenceofanω-limit.Thisformalismisofmoregeneralinterestandcouldbeappliedto otherimageprocessingmodelsbasedonvariationalformulations. Keywords.imageinterpolation,Sobolevgradients,Navier-Stokesmodel,preconditioning AMSsubjectclassifications.65M06,65K10,35Q30 1.Introduction.Imageinpaintingreferstotheprocessoffillinginanoccluded regioninanimagesothattheseambetweentheoriginalimageandtheinpaintedre- gionisundetectablebyatypicalviewer.Someexamplesofapplicationsarerestoring oldphotographs,removingunwantedobjectsfromimagessuchastext,orremoving certainfeaturesofanimagesuchaseyeglasses.Imageinpaintinghasbeentradition- allytheworkofprofessionalartists.However,inrecentyears,muchworkhasbeen doneintheareaofdigitalimageinpainting.Theideaofdigitalimageinpainting isthatthealgorithm,usinginformationfromelsewhereinthedigitalimage,fillsin theunknownregionsothatatypicalviewercannotjudgewhatpartsoftheimage arefromtheoriginalimageandwhatpartsarepaintedin.Ingeneral,theareato bealteredconsistsofmanypixels,complexgeometries,andpossiblyspanstheentire image.Thisestablishesimageinpaintingasachallengingcomputationalproblem. Currentlythereareanumberofmodelsandalgorithmsthatareusedindigital inpainting.Thepioneeringworksindigitalimageinpaintinginclude[4],[11],[19],and [20].In[20],theauthorspresentamethodwheretheregiontobeinpaintedisviewed asanoccludedarea.ThenoneconnectsT-junctionswiththesamegrayscalevalues attheboundaryusingelasticaminimizingcurves.In[19],theauthorsextendonthis ideabyusingavariationalformulation.Theyinpainttheregionwithunknownpixel valuesbyconnectingisophotesattheboundaryusinggeodesiccurves.In[11],the authorsuseageometricmodelassociatedwithEuler’selastica.Theideaistoview theimageasasurfaceandtominimizealinearcombinationofthecurvatureandarc length.Morerecently,theworkin[8],[15],and[31]providestateoftheartresultsin theareaofdigitalimageinpainting.In[13]and[6]acomprehensivesurveyofmodern methodsisgiven. ∗ ThisworkwassupportedinpartbytheNationalSecurityAgency,Contractno.TO-0129 † ( [e-mail] ). ‡ Laboratoiredemathe´matiquesRaphae¨lSalem,Universite´deRouen,F-76801Saint-E ´ tienne-du- Rouvray,France( [e-mail]). 1

2 Sobolevgradientsandimageinterpolation WefocushereonthemodelproposedbyBertalmı´o,BertoziandSapiro(here- inafterBBS),aspresentedin[5].Themodelisbaseduponatransportequationanal- ogoustothetransportofvorticityinanincompressiblefluid.Theresultingmodel isaNavier-Stokestypetimeevolution.Theapproximatedsteadystatesolutionof thismodelgivesthecorrectedimage.Thismodelhasseveralattractivefeatures.It isabletofillinregionssurroundedbydifferentbackgroundsaswellasregionsthat crossthroughboundaries,itiscapableofhandlingarbitrarytopologies,andasathird orderPDE,itforcescontinuityconditionsonboththeimageintensityaswellasthe gradientoftheintensityacrosstheboundary.Themaindrawbackofthemethodis thatitrequiresalargenumberofiterations(severalthousands)toconverge,making itnotverycompetitiveagainstnoniterativefast-marchingmethods(e.g.[8]). Inthispaper,drawingmotivationfromthemodelpresentedin[5],weproposeto solvethethirdorderPDEbyusingadifferentformalism,basedontheminimization ofthecorrespondingleast-squaresderivedfunctional.Theideaistouseforthe minimizationasteepestdescentmethodwithSobolevgradients,amethodthatwe foundeffectiveinreducingthecomputationaltimefordifferentapplications(e.g. [14]).Thenoveltyandthechallengeofthepresentapproachisthatwedealwitha thirdorderPDE,whichis,ingeneral,mathematicallyandcomputationallydifficultto tackle.Weestablishinthiscontributionthemathematicalframeworkfortheanalysis ofthemethodandshowthatthenumericalperformanceisconsiderablyimproved comparedtotheoriginalimplementationofthemodeldescribedin[5].Wethusoffer anewpossibilityforusingtheNavier-Stokesmodelasanalternativetofast-marching methods,thatremainunbeatableascomputingperformance,butarestilltechnical sincetheyneedacarefultuningofconstantsorfunctionalparameters(seealso[6]). Inthemethodofcalculusofvariations,oneoftensolvesminimizationproblems bycomputingtheEuler-Lagrangeequationswhichareusedasadirectionofdescent fortheenergy.ExplicititerativeschemesusingtheEuler-Lagrangeequationsrequire manyiterationstoconvergeduetoatightrestrictiononthestepsizeresultingfrom theCFLstabilitycondition.Inourminimizationscheme,wecomputeagradient withrespecttoaSobolevmetric.Inpractice,thisamounttopreconditioningthe Euler-Lagrangeequationsforuseinminimization.Thepreconditioningingeneral allowsforalargertimestepwhentheresultingevolutionequationisdiscretizedin time.TheSobolevgradientmethodhasprovedtobeveryeffectiveinavarietyof imageprocessingapplications,forexample[10],[9],[22],and[25].Thefocusofthis workistostudytheeffectofpreconditioningthatisoftenassociatedwiththeSobolev gradient,bothintermsofthequalityoftheimageandthecomputationalefficiency. IncontrastwiththeBBSmodel,wedonotuseadiffusionterm,butinsteadapply asmoothingoperatortotheNavier-Stokesgradientflow.Anadvantageisthatour evolutionequationiswell-posedforalltimeandweobtainthattheminimizerisC 1 acrosstheboundaryandcanbeobtainedasanω-limitoftheevolutionequation.The minimizationoftheenergyfunctionalwiththeSobolevgradientfallsintothemore generalcategoryofimageregularization[3],[21],[26],[33],and[30]sinceweexpect theinterpolatedimagetobesmoothduetocontinuitypropertiesofthegradient. Althoughourresultsandapplicationsarerestrictedtosolvingforthetwo-dimensi- onalsteadystatearrivedatbytheNavier-Stokesmodel,ourschemeisquitegeneral. Theideaswepresentherecaneasilybeadaptedtocomputationallysolveavastva- rietyofhigherorderpartialdifferentialequations.Sincewetreattheproblemas avariationalproblem,ourschemecanalsobeappliedtoexistingvariationalmod- elsinimageprocessing(whichalmostalwaysusetheEuler-Lagrangeequationsfor