M ULTISCALE M ODEL.S IMUL.c 2005Society for Industrial and Applied Mathematics Vol.4,No.2,pp.490–530
A REVIEW OF IMAGE DENOISING ALGORITHMS,WITH A NEW
ONE∗
A.BUADES†,
B.COLL†,AND J.M.MOREL‡
Abstract.The arch for efficient image denoising methods is still a valid challenge at the crossing of functional analysis and statistics.In spite of the sophistication of the recently propod methods,most algorithms have not yet attained a desirable level of applicability.All show an out-standing performance when the image model corresponds to the algorithm assumptions but fail in general and create artifacts or remove imagefine structures.The main focus of this paper is,first, to define a general mathematical and experimental methodology to compare and classify classical image denoising algorithms and,cond,to propo a nonlocal means(NL-means)algorithm ad-dressing the prervation of structure in a digital image.The mathematical analysis is bad on the analysis of the“method noi,”de
fined as the difference between a digital image and its denoid version.The NL-means algorithm is proven to be asymptotically optimal under a generic statistical image model.The denoising performance of all considered methods are compared in four ways; mathematical:asymptotic order of magnitude of the method noi under regularity assumptions; perceptual-mathematical:the algorithms artifacts and their explanation as a violation of the image model;quantitative experimental:by tables of L2distances of the denoid version to the original image.The most powerful evaluation method ems,however,to be the visualization of the method noi on natural images.The more this method noi looks like a real white noi,the better the method.
Key words.image restoration,nonparametric estimation,PDE smoothingfilters,adaptive filters,frequency domainfilters
AMS subject classification.62H35
DOI.10.1137/040616024
1.Introduction.
1.1.Digital images and noi.The need for efficient image restoration meth-ods has grown with the m欠条的格式
assive production of digital images and movies of all kinds, often taken in poor conditions.No matter how good cameras are,an image improve-ment is always desirable to extend their range of action.
A digital image is generally encoded as a matrix of grey-level or color values.In the ca of a movie,this matrix has three dimensions,the third one corresponding to time.Each pair(i,u(i)),where u(i)is the value at i,is called a pixel,short for“picture element.”In the ca of grey-level images,i is a point on a two-dimensional(2D)grid and u(i)is a real value.In the ca of classical color images,u(i)is a triplet of values for the red,green,and blue components.All of what we shall say applies identically to movies,three-dimensional(3D)images,and color or multispectral images.For the sake of simplicity in notation and display of experiments,we shall here be content with rectangular2D grey-level images.
∗Received by the editors September30,2004;accepted for publication(in revid form)Janu-ary10,2005;published electronically July18,2005.
c语言学习心得/journals/mms/4-2/61602.html
†Universitat de les Illes Balears,Anlm Turmeda,Ctra.Valldemossa Km.7.5,07122Palma de Mallorca,Spain(vdmiabc4@uib.ll@uib.es).The authors were supported by the Minister
io de Ciencia y Tecnologia under grant TIC2002-02172.During this work,thefirst author had a fellowship of the Govern de les Illes Balears for the realization of his Ph.D.thesis.
豆沙小面包‡Centre de Math´e matiques et Leurs Applications,ENS Cachan61,Av du Pr´e sident Wilson94235 Cachan,France(s-cachan.fr).This author was supported by the Centre National d’Etudes Spatiales(CNES),the Office of Naval Rearch under grant N00014-97-1-0839,the Direction G´e n´e rale des Armements(DGA),and the Minist`e re de la Recherche et de la Technologie.
490
ON IMAGE DENOISING ALGORITHMS 491
The two main limitations in image accuracy are categorized as blur and noi.Blur is intrinsic to image acquisition systems,as digital images have a finite number of samples and must satisfy the Shannon–Nyquist sampling conditions [31].The cond main image perturbation is noi.
Each one of the pixel values u (i )is the result of a light intensity measurement,usually made by a charge coupled device (CCD)matrix coupled with a light focusing system.Each captor of the CCD is r
oughly a square in which the number of incoming photons is being counted for a fixed period corresponding to the obturation time.When the light source is constant,the number of photons received by each pixel fluctuates around its average in accordance with the central limit theorem.In other terms,one can expect fluctuations of order √n for n incoming photons.In addition,each captor,if not adequately cooled,receives heat spurious photons.The resulting perturbation is usually called “obscurity noi.”In a first rough approximation one can write
v (i )=u (i )+n (i ),
where i ∈I ,v (i )is the obrved value,u (i )would be the “true”value at pixel i ,namely the one which would be obrved by averaging the photon counting on a long period of time,and n (i )is the noi perturbation.As indicated,the amount of noi is signal-dependent;that is,n (i )is larger when u (i )is larger.In noi models,the normalized values of n (i )and n (j )at different pixels are assumed to be independent random variables,and one talks about “white noi.”
1.2.Signal and noi ratios.A good quality photograph (for visual inspec-tion)has about 256grey-level values,where 0reprents black and 255reprents white.Measuring the amount of noi by its standard deviation,σ(n ),one can define the signal noi ratio (SNR)as
SNR =σ(u )σ(n )
,where σ(u )denotes the empirical standard deviation of u ,σ(u )= 1|I | i ∈I
(u (i )−u )2
12
,and u =1|I | i ∈I u (i )is the average grey-level value.The standard deviation of the noi can also be obtained as an empirical measurement or formally computed when
the noi model and parameters are known.A good quality image has a standard deviation of about 60.
The best way to test the effect of noi on a standard digital image is to add a Gaussian white noi,in which ca n (i )are independently and identically distributed (i.i.d.)Gaussian real variables.When σ(n )=3,no visible alteration is usually ob-rved.Thus,a 603 20SNR is nearly invisible.Surprisingly enough,one can add white noi up to a 21ratio and still e everything in a picture!This fact is il-lustrated in Figure 1and constitutes a major enigma of human vision.It justifies the many attempts to define convincing denoising algorithms.As we shall e,the results have been r
ather deceptive.Denoising algorithms e no difference between small details and noi,and therefore they remove them.In many cas,they create new distortions,and the rearchers are so ud to them that they have created a
492 A.BUADES,B.COLL,AND J.M.MOREL
Fig.1.A digital image with standard deviation55,the same with noi added(standard deviation3),the SNR therefore being equal to18,and the same with SNR slightly larger than2. In this cond image,no alteration is visible.In the third,a conspicuous noi with standard deviation25has been added,but,surprisingly enough,all details of the original image still are visible.
taxonomy of denoising artifacts:“ringing,”“blur,”“stairca effect,”“checkerboard effect,”“wavelet outliers,”etc.
This fact is not quite a surpri.Indeed,to the best of our knowledge,all denoising algorithms are bad on
•a noi model;
•a generic image smoothness model,local or global.
孙翎茜In experimental ttings,the noi model is perfectly preci.So the weak point of the algorithms is the inadequacy of the image model.All of the methods assume that the noi is oscillatory and that the image is smooth or piecewi smooth.So they try to parate the smooth or patchy part(the image)from the oscillatory one.Actually, manyfine structures in images are as oscillatory as noi is;c
onverly,white noi has low frequencies and therefore smooth components.Thus a paration method bad on smoothness arguments only is hazardous.
1.3.The“method noi.”All denoising methods depend on afiltering pa-rameter h.This parameter measures the degree offiltering applied to the image.For most methods,the parameter h depends on an estimation of the noi varianceσ
2. One can define the result of a denoising method D h as a decomposition of any image v as
(1.1)
v=D h v+n(D h,v),
where
蒙恬简介
1.D h v is more smooth than v,
2.n(D h,v)is the noi guesd by the method.
Now it is not enough to smooth v to ensure that n(D h,v)will look like a noi. The more recent metho
ds are actually not content with a smoothing but try to recover lost information in n(D h,v)[19,25].So the focus is on n(D h,v).
昭君出塞的故事简介
Definition 1.1(method noi).Let u be a(not necessarily noisy)image and D h a denoising operator depending on h.Then we define the method noi of u as the image difference
(1.2)
n(D h,u)=u−D h(u).
This method noi should be as similar to a white noi as possible.In addition, since we would like the original image u not to be altered by denoising methods,the
ON IMAGE DENOISING ALGORITHMS 493
method noi should be as small as possible for the functions with the right regularity.
According to the preceding discussion,four criteria can and will be taken into account in the comparison of denoising methods:
•A display of typical artifacts in denoid images.•A formal computation of the method noi on smooth images,evaluating how small it is in accordance with image local smoothness.
•A comparative display of the method noi of each method on real images with σ=2.5.We mentioned that a noi standard deviation smaller than 3is subliminal,and it is expected that most digitization methods allow themlves this kind of noi.
•A classical comparison receipt bad on noi simulation:it consists of taking a good quality image,adding Gaussian white noi with known σ,and then computing the best image recovered from the noisy one by each method.A table of L 2distances from the restored to the original can be established.The L 2distance does not provide a good quality asssment.However,it reflects well the relative performances of algorithms.
On top of this,in two cas,a proof of asymptotic recovery of the image can be obtained by statistical arguments.
1.4.Which methods to compare.We had to make a lection of the denoising methods we wished to compare.Here a difficulty aris,as most original methods have caud an abundant literature proposing many improvements.So we tried to get the best available version,while keeping the simple
and genuine character of the original method:no hybrid method.So we shall analyze the following:
1.the Gaussian smoothing model (Gabor quoted in Lindenbaum,Fischer,and
Bruckstein [17]),
where the smoothness of u is measured by the Dirichlet integral |Du |2;
2.the anisotropic filtering model (Perona and Malik [27],Alvarez,Lions,and
Morel [1]);
3.the Rudin–Osher–Fatemi total variation model [30]and two recently propod
iterated total variation refinements [35,25];
4.the Yaroslavsky neighborhood filters [41,40]and an elegant variant,the
SUSAN filter (Smith and Brady [33]);
5.the Wiener local empirical filter as implemented by Yaroslavsky [40];
6.the translation invariant wavelet thresholding [8],a simple and performing
variant of the wavelet thresholding [10];
7.DUDE,the discrete universal denoir [24],and the UINTA,unsupervid
information-theoretic,adaptive filtering [3],two very recent new approaches;
8.the nonlocal means (NL-means)algorithm,which we introduce here.
This last algorithm is given by a simple clod formula.Let u be defined in a bounded domain Ω⊂R 2;then
NL (u )(x )=1C (x )
兵器科学与技术e −(G a ∗|u (x +.)−u (y +.)|2)(0)2u (y )d y ,where x ∈Ω,G a is a Gaussian kernel o
f standard deviation a ,h acts as a filterin
g parameter,and C (x )= e −(G a ∗|u (x +.)−u (z +.)|2)(0)
h 2d z is the normalizing factor.In order
to make clear the previous definition,we recall that
(G a ∗|u (x +.)−u (y +.)|2)(0)= R 2
G a (t )|u (x +t )−u (y +t )|2d t .
494 A.BUADES,B.COLL,AND J.M.MOREL
This amounts to saying that NL(u)(x),the denoid value at x,is a mean of the values of all pixels who Gaussian neighborhood looks like the neighborhood of x.
矮的英语怎么说1.5.What is left.We do not draw into comparison the hybrid methods,in particular the total variation+wavelets[7,12,18].Such methods are significant improvements of the simple methods but are impossible to draw into a benchmark: their efficiency depends a lot upon the choice of wavelet dictionaries and the kind of image.
Second,we do not draw into the comparison the method introduced recently by Meyer[22],who aim it is to decompo the image into a BV part and a texture part(the so called u+v methods),and even into three terms,namely u+v+w, where u is the BV part,v is the“texture”part belonging to the dual space of BV, denoted by G,and w belongs to the Besov space˙B∞−1,∞,a space characterized b
y the fact that the wavelet coefficients have a uniform bound.G is propod by Meyer as the right space to model oscillatory patterns such as textures.The main focus of this method is not yet denoising.Becau of the different and more ambitious scopes of the Meyer method[2,36,26],which makes it parameter-and implementation-dependent, we could not draw it into the discussion.Last but not least,let us mention the bandlet[15]and curvelet[34]transforms for image analysis.The methods also are paration methods between the geometric part and the oscillatory part of the image and intend tofind an accurate and compresd version of the geometric part. Incidentally,they may be considered as denoising methods in geometric images,as the oscillatory part then contains part of the noi.Tho methods are cloly related to the total variation method and to the wavelet thresholding,and we shall be content with tho simpler reprentatives.
1.6.Plan of the paper.Section2computes formally the method noi for the best elementary local smoothing methods,namely Gaussian smoothing,anisotropic smoothing(mean curvature motion),total variation minimization,and the neighbor-hoodfilters.For all of them we prove or recall the asymptotic expansion of thefilter at smooth points of the image and therefore obtain a formal expression of the method noi.This expression permits us to characterize places where thefilter performs well and where it fails.In ction3,we treat the Wiener-like methods,which proceed by a soft
or hard threshold on frequency or space-frequency coefficients.We examine in turn the Wiener–Fourierfilter,the Yaroslavsky local adaptive discrete cosine trans-form(DCT)-badfilters,and the wavelet threshold method.Of cour,the Gaussian smoothing belongs to both class offilters.We also describe the universal denoir DUDE,but we cannot draw it into the comparison,as its direct application to grey-level images is unpractical so far.(We discuss its feasibility.)Finally,we examine the UINTA algorithms who principles stand clo to the NL-means algorithm.In ction5,we introduce the NL-meansfilter.This method is not easily classified in the preceding terminology,since it can work adaptively in a local or nonlocal way.We first give a proof that this algorithm is asymptotically consistent(it gives back the conditional expectation of each pixel value given an obrved neighborhood)under the assumption that the image is a fairly general stationary random process.The works of Efros and Leung[13]and Levina[16]have shown that this assumption is sound for images having enough samples in each texture patch.In ction6,we com-pare all algorithms from veral points of view,do a performance classification,and explain why the NL-means algorithm shares the consistency properties of most of the aforementioned algorithms.
