搜索
PhysicaD60(1992)259-268North-HollandNonlineartotalvariationbasednoiseremovalalgorithms*LeonidI.Rudin1,StanleyOsherandEmadFatemi2CognitechInc.,2800,28thStreet,Suite101,SantaMonica,CA90405,USAAconstrainedoptimizationtypeofnumericalalgorithmforremovingnoisefromimagesispresented.Thetotalvariationoftheimageisminimizedsubjecttoconstraintsinvolvingthestatisticsofthenoise.TheconstraintsareimposedusingLagrangemultipliers.Thesolutionisobtainedusingthegradient-projectionmethod.Thisamountstosolvingatimedependentpartialdifferentialequationonamanifolddeterminedbytheconstraints.Ast---~0othesolutionconvergestoasteadystatewhichisthedenoisedimage.Thenumericalalgorithmissimpleandrelativelyfast.Theresultsappeartobestate-of-the-artforverynoisyimages.Themethodisnoninvasive,yieldingsharpedgesintheimage.Thetechniquecouldbeinterpretedasafirststepofmovingeachlevelsetoftheimagenormaltoitselfwithvelocityequaltothecurvatureofthelevelsetdividedbythemagnitudeofthegradientoftheimage,andasecondstepwhichprojectstheimagebackontotheconstraintset.1.IntroductionThepresenceofnoiseinimagesisunavoid-able.Itmaybeintroducedbytheimageforma-tionprocess,imagerecording,imagetransmis-sion,etc.Theserandomdistortionsmakeitdif-ficulttoperformanyrequiredpictureprocessing.Forexample,thefeatureorientedenhancementintroducedinrefs.[6,7]isveryeffectiveinre-storingblurryimages,butitcanbefrozenbyanoscillatorynoisecomponent.Evenasmallamountofnoiseisharmfulwhenhighaccuracyisrequired,e.g.asinsubcell(subpixel)imageanalysis.Inpractice,toestimateatruesignalinnoise,themostfrequentlyusedmethodsarebasedontheleastsquarescriteria.Therationalecomesfromthestatisticalargumentthattheleastsquaresestimationisthebestoveranentire*ResearchsupportedbyDARPASBIRContract#DAAH01-89-C0768andbyAFOSRContract#F49620-90-C-0011.1E-mail:cogni!leonid@aerospace.aero.org.2Currentaddress:InstituteforMathematicsanditsAppli-cations,UniversityofMinnesota,Minneapolis,MN55455,USA.ensembleofallpossiblepictures.ThisprocedureisL2normdependent.Howeverithasbeenconjecturedinref.[6]thatthepropernormforimagesisthetotalvariation(TV)normandnottheL2norm.TVnormsareessentiallyL1normsofderivatives,henceL1estimationproceduresaremoreappropriateforthesubjectofimageestimation(restoration).Thespaceoffunctionsofboundedtotalvariationplaysanimportantrolewhenaccurateestimationofdiscontinuitiesinsolutionsisrequired[6,7].Historically,theL~estimationmethodsgobacktoGalileo(1632)andLaplace(1793).Incomparisontotheleastsquaremethodswhereclosedformlinearsolutionsarewellunderstoodandeasilycomputed,theL1estimationisnon-linearandcomputationallycomplex.RecentlythesubjectofL1estimationofstatisticaldatahasreceivedrenewedattentionbythestatisticalcommunity,seee.g.ref.[13].Drawingonourpreviousexperiencewithshockrelatedimageenhancement[6,7],wepro-posetodenoiseimagesbyminimizingthetotalvariationnormoftheestimatedsolution.Wederiveaconstrainedminimizationalgorithmasa0167-2789/92/$05.00©1992-ElsevierSciencePublishersB.V.Allrightsreserved260L.I.Rudinetal./NoiseremovalalgorithmstimedependentnonlinearPDE,wherethecon-straintsaredeterminedbythenoisestatistics.Traditionalmethodsattempttoreduce/removethenoisecomponentpriortofurtherimageprocessingoperations.Thisistheap-proachtakeninthispaper.However,thesameTV/L1philosophycanbeusedtodesignhybridalgorithmscombiningdenoisingwithothernoisesensitiveimageprocessingtasks.2.Nonlinearpartialdifferentialequationsbaseddenoisingalgorithms.Lettheobservedintensityfunctionu0(x,y)denotethepixelvaluesofanoisyimageforx,y~O.Letu(x,y)denotethedesiredcleanimage,soUo(X,y)=u(x,y)+n(x,y),(2.1)whennistheadditivenoise.We,ofcourse,wishtoreconstructufromu0.MostconventionalvariationalmethodsinvolvealeastsquaresL2fitbecausethisleadstolinearequations.ThefirstattemptalongtheselineswasmadebyPhillips[1]andlaterrefinedbyTwomey[2,3]intheone-dimensionalcase.Inourtwo-dimensionalcontinuousframeworktheircon-strainedminimizationproblemisminimizef(Uxx+Uyy)2(2.2a)subjecttoconstraintsinvolvingthemeanfu=fUo(2.2b)andstandarddeviationf(u-u0)2=trz.(2.2c)Theresultinglinearsystemisnoweasytosolveusingmodernnumericallinearalgebra.How-ever,theresultsareagaindisappointing(butbetterthantheMEM)withthesameconstraints)-seee.g.ref.[5].TheL1normisusuallyavoidedsincethevariationofexpressionslikeSalu[dxproducessingulardistributionsascoefficients(e.g.6func-tions)whichcannotbehandledinapurelyalge-braicframework.However,ifL2andL1approxi-mationsareputsidebysideonacomputerscreen,itisclearthattheL1approximationlooksbetterthanthesameL2approximation.Thesamemeanssubjecttothesameconstraints.Thismaybeatleastpartlypsychological;how-ever,itiswellknowninshockcalculationsthattheL1normofthegradientistheappropriatespace.Thisisbasicallythespaceoffunctionsofboundedtotalvariation:BV.Forfree,wegettheremovalofspuriousoscillations,whilesharpsig-nalsarepreservedinthisspace.Inref.[6]thefirstauthorhasintroducedanovelimageenhancementtechnique,calledShockFilter.Ithadanalogywithshockwavecalculationsincomputationalfluidmechanics.Theformationofdiscontinuitieswithoutoscilla-tionsandrelevanceoftheTVn