Explicit algorithms for a new time dependent model

EXPLICITALGORITHMSFORANEWTIMEDEPENDENTMODELBASEDONLEVELSETMOTIONFORNONLINEARDEBLURRINGANDNOISEREMOVALANTONIOMARQUINAyANDSTANLEYOSHERDedicatedtothememoryofEmadFatemiAbstract.InthispaperweformulateatimedependentmodeltoapproximatethesolutiontothenonlineartotalvariationoptimizationproblemfordeblurringandnoiseremovalintroducedbyRudinandOsher,([18]),andRudin,OsherandFatemi,([19]),respectively.OurmodelisbasedonlevelsetmotionwhosesteadystateisquicklyreachedbymeansofanexplicitprocedurebasedonRoe’sscheme,([16]),usedinuiddynamics.Weshownumericalevidenceofthespeedofresolutionandstabilityofthissimpleexplicitprocedureinsomerepresentative1Dand2Dnumericalexamples.1.Introduction.Theclassicalalgorithmsforimagedeblurringand/ordenoisinghavebeenmainlybasedonleastsquares,FourierseriesandotherL2-normapproxi-mations,and,consequently,theiroutputsmaybecontaminatedbyGibbs’phenomenaanddonotapproximatewellimagescontainingedges.Theircomputationaladvantagecomesfromthefactthattheyarelinear,thusfastsolversarewidelyavailable.How-ever,theeectoftherestorationisnotlocalinspatialscale.Otherbasesoforthogonalfunctionshavebeenintroducedinordertogetridofthoseproblems,e.g.,compactlysupportedwavelets.However,Gibbs’phenomenon,(ringing),isstillpresentforthesenorms.TheTotalVariation(TV)deblurringanddenoisingmodelsarebasedonavari-ationalproblemwithconstraintsusingthetotalvariationnormasanonlinearnon-dierentiablefunctional.TheformulationofthesemodelswasrstgivenbyRudin,OsherandFatemiin([19])forthedenoisingmodelandRudinandOsherin([18])forthedenoisinganddeblurringcase.Themainadvantageisthattheirsolutionspreserveedgesverywell,buttherearecomputationaldiculties.Indeed,inspiteofthefactthatthevariationalproblemisconvex,theEuler-Lagrangeequationsarenonlinearandill-conditioned.Linearsemi-implicitxed-pointproceduresdevisedbyVogelandOman,(see[26]),andinterior-pointprimal-dualimplicitquadraticmethodsbyChan,GolubandMulet,(see[6]),wereintroducedtosolvethemodels.Thosemethodsgivegoodresultswhentreatingpuredenoisingproblems,butthemethodsbecomehighlyill-conditionedforthedeblurringanddenoisingcasewherethecomputationalcostisveryhighandparameterdependent.Furthermore,thosemethodsalsosuerfromtheundesirablestaircaseeect,namelythetransformationofsmoothregions(ramps)intopiecewiseconstantregions(stairs).Inthispaperwepresentaverysimpletimedependentmodelconstructedbyevolv-ingtheEuler-LagrangeequationoftheRudin-Osheroptimizationproblem,multipliedbythemagnitudeofthegradientofthesolution.ThetwomainanalyticfeaturesofyDepartmentofMathematics,UniversityofCalifornia,LosAngeles,405HilgardAv-enue,LosAngeles,CA90095-1555andDepartamentdeMatematicaAplicada,UniversitatdeValencia,Dr.Moliner,50,46100Burjassot,Spain.E-mailaddresses:[e-mail],URL:~marquina.SupportedbyNSFGrantINT9602089andDGICYTGrantPB97-1402.DepartmentofMathematics,UniversityofCalifornia,LosAngeles,405HilgardAvenue,LosAngeles,CA90095-1555.E-mailaddress:[e-mail]9706827.1thisformulationarethefollowing:1)thelevelcontoursoftheimagemovequicklytothesteadysolutionand2)thepresenceofthegradientnumericallyregularizesthemeancurvatureterminawaythatpreservesandenhancesedgesandkillsnoisethroughthenonlineardiusionactingonsmallscales.Weusetheentropy-violatingRoescheme,([16])fortheconvectivetermandcentraldierencingfortheregularizedmeancurvaturediusionterm.Thismakesaverysimple,stable,explicitprocedure,computationallycompetitivecomparedwithothersemi-implicitorimplicitprocedures.Weshownumericalevidenceofthepowerofresolutionandstabilityofthisexplicitprocedureinsomerepresentative1Dand2Dnumericalexamples,consistingofnoisyandblurredsignalsandimages,(weuseGaussianwhitenoiseandGausssianblur).Wehaveobservedinourexperimentsthatouralgorithmshowsasubstantiallyreducedstaircaseeect.2.DeblurringandDenoising.Arecordingdeviceoracamerawouldrecordasignalorimagesothat1)therecordedintensityofasmallregionisrelatedtothetrueintensitiesofaneighborhoodofthepixel,throughadegradationprocessusuallycalledblurringand2)therecordedintensitiesarecontaminatedbyrandomnoise.ToxourideaswerestrictthediscussiontoR2.Animagecanbeinterpretedaseitherarealfunctiondenedon,aboundedandopendomainofR2,(forsimplicitywewillassumetobetheunitsquarehenceforth)orasasuitablediscretizationofthiscontinuousimage.Ourinterestistorestoreanimagewhichiscontaminatedwithnoiseandblurinsuchawaythattheprocessshouldrecovertheedgesoftheimage.Letusdenotebyu0theobservedimageandutherealimage.Amodelofblurringcomesfromthedegradationofuthroughsomekindofaveraging.Indeed,umaybeblurredthroughtheapplicationofakernel:k(x;s;y;r)bymeansofv0(x;y)=Zu(s;r)k(x;s;y;r)dsdr(2.1)and,wedenotethisoperationbyv0=ku.Themodelofdegradationweassumeisku+n=u0;(2.2)wherenisGaussianwhitenoise,i.e.,thevaluesniofnatthepixelsiareindependentrandomvariables,eachwithaGaussiandistributionofzeromeanandvariance2.Ifthekernelkistranslationinvariant,i.e.,thereisafunctionj(x;y),(alsocalledakernel),suchthatk(x;s;y;r)=j(xs;yr)andtheblurringisdenedasa’superposition’ofj0s:v0(x;y)=(ju)(x;y)=