Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

SOBOLEV GRADIENTS AND IMAGE INTERPOLATION

De
24 pages
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


Voir plus Voir moins
SOBOLEVGRADIENTSANDIMAGEINTERPOLATIONPARIMAHKAZEMIANDIONUTDANAILAAbstract.WepresenthereanewimageinpaintingalgorithmbasedontheSobolevgradientmethodinconjunctionwiththeNavier-Stokesmodel.TheoriginalmodelofBertalmı´oetal.[Proc.Conf.Comp.VisionPatternRec.,2001]isreformulatedasavariationalprinciplebasedontheminimizationofawellchosenfunctionalbyasteepestdescentmethodusingSobolevgradients.Thisnewtheoreticalframeworkoffersanalternativeofthedirectsolvingofahigh-orderpartialdifferentialequation,withthepracticaladvantageofaneasierandmoreflexiblecomputerimplementation.Inparticular,theproposedalgorithmdoesnotrequireanyconstanttuning,noradvancedknowledgeofnumericalmethodsforNavier-Stokesequations(slopelimiters,dynamicrelaxationforPoissonequation,anisotropicdiffusionsteps,etc).Usingastraightforwardfinitedifferenceimplementation,wedemonstrate,throughvariousexamplesforimageinpaintingandimageinterpolation,thatthenovelalgorithmisfasterthantheoriginalimplementationoftheNavier-Stokesmodel,whileprovidingresultsofsimilarquality.Thepaperalsoprovidesthemathematicaltheoryfortheanalysisofthealgorithm.Usinganevolutionequationinaninfinitedimensionalsettingweobtainglobalexistenceanduniquenessresultsaswellastheexistenceofanω-limit.Thisformalismisofmoregeneralinterestandcouldbeappliedtootherimageprocessingmodelsbasedonvariationalformulations.Keywords.imageinterpolation,Sobolevgradients,Navier-Stokesmodel,preconditioningAMSsubjectclassifications.65M06,65K10,35Q301.Introduction.Imageinpaintingreferstotheprocessoffillinginanoccludedregioninanimagesothattheseambetweentheoriginalimageandtheinpaintedre-gionisundetectablebyatypicalviewer.Someexamplesofapplicationsarerestoringoldphotographs,removingunwantedobjectsfromimagessuchastext,orremovingcertainfeaturesofanimagesuchaseyeglasses.Imageinpaintinghasbeentradition-allytheworkofprofessionalartists.However,inrecentyears,muchworkhasbeendoneintheareaofdigitalimageinpainting.Theideaofdigitalimageinpaintingisthatthealgorithm,usinginformationfromelsewhereinthedigitalimage,fillsintheunknownregionsothatatypicalviewercannotjudgewhatpartsoftheimagearefromtheoriginalimageandwhatpartsarepaintedin.Ingeneral,theareatobealteredconsistsofmanypixels,complexgeometries,andpossiblyspanstheentireimage.Thisestablishesimageinpaintingasachallengingcomputationalproblem.Currentlythereareanumberofmodelsandalgorithmsthatareusedindigitalinpainting.Thepioneeringworksindigitalimageinpaintinginclude[4],[11],[19],and[20].In[20],theauthorspresentamethodwheretheregiontobeinpaintedisviewedasanoccludedarea.ThenoneconnectsT-junctionswiththesamegrayscalevaluesattheboundaryusingelasticaminimizingcurves.In[19],theauthorsextendonthisideabyusingavariationalformulation.Theyinpainttheregionwithunknownpixelvaluesbyconnectingisophotesattheboundaryusinggeodesiccurves.In[11],theauthorsuseageometricmodelassociatedwithEuler’selastica.Theideaistoviewtheimageasasurfaceandtominimizealinearcombinationofthecurvatureandarclength.Morerecently,theworkin[8],[15],and[31]providestateoftheartresultsintheareaofdigitalimageinpainting.In[13]and[6]acomprehensivesurveyofmodernmethodsisgiven.ThisworkwassupportedinpartbytheNationalSecurityAgency,Contractno.TO-0129(parimah.kazemi@gmail.com).Laboratoiredemathe´matiquesRaphae¨lSalem,Universite´deRouen,F-76801Saint-E´tienne-du-Rouvray,France(ionut.danaila@univ-rouen.fr).1
2SobolevgradientsandimageinterpolationWefocushereonthemodelproposedbyBertalmı´o,BertoziandSapiro(here-inafterBBS),aspresentedin[5].Themodelisbaseduponatransportequationanal-ogoustothetransportofvorticityinanincompressiblefluid.TheresultingmodelisaNavier-Stokestypetimeevolution.Theapproximatedsteadystatesolutionofthismodelgivesthecorrectedimage.Thismodelhasseveralattractivefeatures.Itisabletofillinregionssurroundedbydifferentbackgroundsaswellasregionsthatcrossthroughboundaries,itiscapableofhandlingarbitrarytopologies,andasathirdorderPDE,itforcescontinuityconditionsonboththeimageintensityaswellasthegradientoftheintensityacrosstheboundary.Themaindrawbackofthemethodisthatitrequiresalargenumberofiterations(severalthousands)toconverge,makingitnotverycompetitiveagainstnoniterativefast-marchingmethods(e.g.[8]).Inthispaper,drawingmotivationfromthemodelpresentedin[5],weproposetosolvethethirdorderPDEbyusingadifferentformalism,basedontheminimizationofthecorrespondingleast-squaresderivedfunctional.TheideaistousefortheminimizationasteepestdescentmethodwithSobolevgradients,amethodthatwefoundeffectiveinreducingthecomputationaltimefordifferentapplications(e.g.[14]).ThenoveltyandthechallengeofthepresentapproachisthatwedealwithathirdorderPDE,whichis,ingeneral,mathematicallyandcomputationallydifficulttotackle.Weestablishinthiscontributionthemathematicalframeworkfortheanalysisofthemethodandshowthatthenumericalperformanceisconsiderablyimprovedcomparedtotheoriginalimplementationofthemodeldescribedin[5].WethusofferanewpossibilityforusingtheNavier-Stokesmodelasanalternativetofast-marchingmethods,thatremainunbeatableascomputingperformance,butarestilltechnicalsincetheyneedacarefultuningofconstantsorfunctionalparameters(seealso[6]).Inthemethodofcalculusofvariations,oneoftensolvesminimizationproblemsbycomputingtheEuler-Lagrangeequationswhichareusedasadirectionofdescentfortheenergy.ExplicititerativeschemesusingtheEuler-LagrangeequationsrequiremanyiterationstoconvergeduetoatightrestrictiononthestepsizeresultingfromtheCFLstabilitycondition.Inourminimizationscheme,wecomputeagradientwithrespecttoaSobolevmetric.Inpractice,thisamounttopreconditioningtheEuler-Lagrangeequationsforuseinminimization.Thepreconditioningingeneralallowsforalargertimestepwhentheresultingevolutionequationisdiscretizedintime.TheSobolevgradientmethodhasprovedtobeveryeffectiveinavarietyofimageprocessingapplications,forexample[10],[9],[22],and[25].ThefocusofthisworkistostudytheeffectofpreconditioningthatisoftenassociatedwiththeSobolevgradient,bothintermsofthequalityoftheimageandthecomputationalefficiency.IncontrastwiththeBBSmodel,wedonotuseadiffusionterm,butinsteadapplyasmoothingoperatortotheNavier-Stokesgradientflow.Anadvantageisthatourevolutionequationiswell-posedforalltimeandweobtainthattheminimizerisC1acrosstheboundaryandcanbeobtainedasanω-limitoftheevolutionequation.TheminimizationoftheenergyfunctionalwiththeSobolevgradientfallsintothemoregeneralcategoryofimageregularization[3],[21],[26],[33],and[30]sinceweexpecttheinterpolatedimagetobesmoothduetocontinuitypropertiesofthegradient.Althoughourresultsandapplicationsarerestrictedtosolvingforthetwo-dimensi-onalsteadystatearrivedatbytheNavier-Stokesmodel,ourschemeisquitegeneral.Theideaswepresentherecaneasilybeadaptedtocomputationallysolveavastva-rietyofhigherorderpartialdifferentialequations.Sincewetreattheproblemasavariationalproblem,ourschemecanalsobeappliedtoexistingvariationalmod-elsinimageprocessing(whichalmostalwaysusetheEuler-Lagrangeequationsfor
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin