SOBOLEV GRADIENTS AND IMAGE INTERPOLATION

pages

English

Documents

Écrit par
Parimah Kazemi

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

English

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

English

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

Publié par

pefav

Nombre de lectures

Langue

English

SOBOLEVGRADIENTSANDIMAGEINTERPOLATION∗PARIMAHKAZEMI†ANDIONUTDANAILA‡Abstract.WepresenthereanewimageinpaintingalgorithmbasedontheSobolevgradientmethodinconjunctionwiththeNavier-Stokesmodel.TheoriginalmodelofBertalmı´oetal.[Proc.Conf.Comp.VisionPatternRec.,2001]isreformulatedasavariationalprinciplebasedontheminimizationofawellchosenfunctionalbyasteepestdescentmethodusingSobolevgradients.Thisnewtheoreticalframeworkoﬀersanalternativeofthedirectsolvingofahigh-orderpartialdiﬀerentialequation,withthepracticaladvantageofaneasierandmoreﬂexiblecomputerimplementation.Inparticular,theproposedalgorithmdoesnotrequireanyconstanttuning,noradvancedknowledgeofnumericalmethodsforNavier-Stokesequations(slopelimiters,dynamicrelaxationforPoissonequation,anisotropicdiﬀusionsteps,etc).Usingastraightforwardﬁnitediﬀerenceimplementation,wedemonstrate,throughvariousexamplesforimageinpaintingandimageinterpolation,thatthenovelalgorithmisfasterthantheoriginalimplementationoftheNavier-Stokesmodel,whileprovidingresultsofsimilarquality.Thepaperalsoprovidesthemathematicaltheoryfortheanalysisofthealgorithm.Usinganevolutionequationinaninﬁnitedimensionalsettingweobtainglobalexistenceanduniquenessresultsaswellastheexistenceofanω-limit.Thisformalismisofmoregeneralinterestandcouldbeappliedtootherimageprocessingmodelsbasedonvariationalformulations.Keywords.imageinterpolation,Sobolevgradients,Navier-Stokesmodel,preconditioningAMSsubjectclassiﬁcations.65M06,65K10,35Q301.Introduction.Imageinpaintingreferstotheprocessofﬁllinginanoccludedregioninanimagesothattheseambetweentheoriginalimageandtheinpaintedre-gionisundetectablebyatypicalviewer.Someexamplesofapplicationsarerestoringoldphotographs,removingunwantedobjectsfromimagessuchastext,orremovingcertainfeaturesofanimagesuchaseyeglasses.Imageinpaintinghasbeentradition-allytheworkofprofessionalartists.However,inrecentyears,muchworkhasbeendoneintheareaofdigitalimageinpainting.Theideaofdigitalimageinpaintingisthatthealgorithm,usinginformationfromelsewhereinthedigitalimage,ﬁllsintheunknownregionsothatatypicalviewercannotjudgewhatpartsoftheimagearefromtheoriginalimageandwhatpartsarepaintedin.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-ogoustothetransportofvorticityinanincompressibleﬂuid.TheresultingmodelisaNavier-Stokestypetimeevolution.Theapproximatedsteadystatesolutionofthismodelgivesthecorrectedimage.Thismodelhasseveralattractivefeatures.Itisabletoﬁllinregionssurroundedbydiﬀerentbackgroundsaswellasregionsthatcrossthroughboundaries,itiscapableofhandlingarbitrarytopologies,andasathirdorderPDE,itforcescontinuityconditionsonboththeimageintensityaswellasthegradientoftheintensityacrosstheboundary.Themaindrawbackofthemethodisthatitrequiresalargenumberofiterations(severalthousands)toconverge,makingitnotverycompetitiveagainstnoniterativefast-marchingmethods(e.g.[8]).Inthispaper,drawingmotivationfromthemodelpresentedin[5],weproposetosolvethethirdorderPDEbyusingadiﬀerentformalism,basedontheminimizationofthecorrespondingleast-squaresderivedfunctional.TheideaistousefortheminimizationasteepestdescentmethodwithSobolevgradients,amethodthatwefoundeﬀectiveinreducingthecomputationaltimefordiﬀerentapplications(e.g.[14]).ThenoveltyandthechallengeofthepresentapproachisthatwedealwithathirdorderPDE,whichis,ingeneral,mathematicallyandcomputationallydiﬃculttotackle.Weestablishinthiscontributionthemathematicalframeworkfortheanalysisofthemethodandshowthatthenumericalperformanceisconsiderablyimprovedcomparedtotheoriginalimplementationofthemodeldescribedin[5].WethusoﬀeranewpossibilityforusingtheNavier-Stokesmodelasanalternativetofast-marchingmethods,thatremainunbeatableascomputingperformance,butarestilltechnicalsincetheyneedacarefultuningofconstantsorfunctionalparameters(seealso[6]).Inthemethodofcalculusofvariations,oneoftensolvesminimizationproblemsbycomputingtheEuler-Lagrangeequationswhichareusedasadirectionofdescentfortheenergy.ExplicititerativeschemesusingtheEuler-LagrangeequationsrequiremanyiterationstoconvergeduetoatightrestrictiononthestepsizeresultingfromtheCFLstabilitycondition.Inourminimizationscheme,wecomputeagradientwithrespecttoaSobolevmetric.Inpractice,thisamounttopreconditioningtheEuler-Lagrangeequationsforuseinminimization.Thepreconditioningingeneralallowsforalargertimestepwhentheresultingevolutionequationisdiscretizedintime.TheSobolevgradientmethodhasprovedtobeveryeﬀectiveinavarietyofimageprocessingapplications,forexample[10],[9],[22],and[25].ThefocusofthisworkistostudytheeﬀectofpreconditioningthatisoftenassociatedwiththeSobolevgradient,bothintermsofthequalityoftheimageandthecomputationaleﬃciency.IncontrastwiththeBBSmodel,wedonotuseadiﬀusionterm,butinsteadapplyasmoothingoperatortotheNavier-Stokesgradientﬂow.Anadvantageisthatourevolutionequationiswell-posedforalltimeandweobtainthattheminimizerisC1acrosstheboundaryandcanbeobtainedasanω-limitoftheevolutionequation.TheminimizationoftheenergyfunctionalwiththeSobolevgradientfallsintothemoregeneralcategoryofimageregularization[3],[21],[26],[33],and[30]sinceweexpecttheinterpolatedimagetobesmoothduetocontinuitypropertiesofthegradient.Althoughourresultsandapplicationsarerestrictedtosolvingforthetwo-dimensi-onalsteadystatearrivedatbytheNavier-Stokesmodel,ourschemeisquitegeneral.Theideaswepresentherecaneasilybeadaptedtocomputationallysolveavastva-rietyofhigherorderpartialdiﬀerentialequations.Sincewetreattheproblemasavariationalproblem,ourschemecanalsobeappliedtoexistingvariationalmod-elsinimageprocessing(whichalmostalwaysusetheEuler-Lagrangeequationsfor

Voir