25-06-2012, 05:53 PM
Image and movie denoising by nonlocal means
[attachment=25507]
Abstract
Neighborhood ¯lters are image and movie ¯lters which reduce the noise by averaging
similar pixels. The object of the paper is to present a uni¯ed theory of these ¯lters and
reliable criteria to compare them to other classes of ¯lters. First a CCD noise model
will be presented justifying this class of algorithm. A classi¯cation of neighborhood ¯lters
is proposed, including classical image and movie denoising methods and a new one,
the nonlocal-means (NL-means). In order to compare denoising methods three principles
will be introduced. The ¯rst principle, \method noise", speci¯es that only noise must
be removed from an image. Second a \noise to noise" principle states that a denoising
method must transform a white noise into a white noise. This principle characterizes
artifact-free methods. A third principle, the \statistical optimality", permits to compare
the performance of neighborhood ¯lters. The three principles will be applied to compare
ten di®erent image and movie denoising methods. It will be ¯rst shown that only
wavelet thresholding methods and NL-means give an acceptable method noise. Second,
that neighborhood ¯lters are the only ones to satisfy the \noise to noise" principle. Third,
that among them NL-means is closest to statistical optimality. A particular attention is
paid to movie denoising methods. Motion compensated denoising methods turn out to
be neighborhood ¯lters where the neighborhood is constrained to stay on a single trajectory.
It is demonstrated that this constraint is harmful for denoising purposes and that
space-time NL-means preserves more movie details.
1 Introduction
The main objective of this paper is to set under a common framework all neighborhood ¯lters,
including movie ¯lters which are usually treated as a di®erent class. We shall call neighborhood
¯lters all image and movie ¯lters which reduce the noise by averaging similar pixels. General
CCD noise models (brie°y presented in Section 2) imply that noise in digital images and movies
is signal dependent. Fortunately two pixels which received the same energy from the outdoor
scene undergo the same kind of perturbations and therefore have the same noise model. Under
the fairly general assumption that at each energy level the noise model is additive and white,
denoising can be achieved by ¯rst ¯nding out the pixels which received the same original energy
and then averaging their observed grey levels. This observation has led to the wide class of
neighborhood ¯lters classi¯ed in [39]. Since the original image value is lost these ¯lters proceed
by picking for each pixel i the set of pixels J(i) spatially close to i and with a similar grey level
value.
Neighborhood ¯lters proceed by replacing the grey level value of i, u(i), by the average
NFu(i) = 1
jJ(i)j Pj2J(i) u(j). (Depending on the noise model other statistical estimates are
of course possible like the median, etc.) Under the assumption that pixels j 2 J(i) indeed
received the same original energy as i, NFu(i) is a denoised version of u(i). The more famous
1
neighborhood ¯lters are Lee's ¾-¯lter [20], SUSAN [33] and the bilateral ¯lter [35] where the
neighborhoods are gaussian in space and grey level.
In a recent communication [7] (see also [6] for a mathematical analysis) the authors of the
present paper extended the above mentioned neighborhood ¯lters to a wider class which they
called non-local means (NL-means). This algorithm de¯nes the neighborhood J(i) of i by the
condition: j 2 J(i) if the grey level of a whole window around j is close to the grey level of the
window around i. The spatial constraint is instead relaxed.
NL-means ¯lters can be given two origins beyond classical neighborhood ¯lters. The same
Markovian pixel similarity model was used in the seminal paper [11] for texture synthesis from
a texture sample. In that case the neighborhood J(i) is not used for denoising. The aim is to
estimate from the texture sample the law of i knowing its neighborhood. This law is used to
synthesize similar texture images by an iterative algorithm.
Last but not least most state of the art movie denoising methods are neighborhood ¯lters
and some of them, in some sense, NL-means ¯lters. Indeed, motion compensated denoising
methods start with the search for a temporal neighborhood J(i), the trajectory, followed by
an averaging process. By the Lambertian assumption a pixel belonging to a certain object
conserves the same grey level value during its trajectory. Therefore this is computed as a grey
level neighborhood of i in the sense of neighborhood ¯lters. The comparison of grey levels is
not a su±cient criterion, a di±culty usually called the aperture problem. Thus several motion
compensated ¯lters involve block matching. They construct J(i) by comparing a whole block
around j to a whole block around i.
In all of these algorithms the neighborhood J(i) picks a single pixel per frame. One of our
objectives is to prove that this restriction is actually counterproductive. In fact the performance
of movie denoising ¯lters improves signi¯cantly by forgetting about trajectories and using all
similar pixels in space-time, no matter how many are picked per frame. For this reason we
extend the NL-means ¯lter to movies by applying it directly to the movie thought of as a union
of images. The time ordering of this union is somewhat irrelevant. The aperture problem
results in the existence of more samples for each pixel and therefore increases the denoising
performance by nonlocal means.
No new denoising method should be presented without a systematic comparison to the huge
variety of denoising methods. On the other hand a comparison between methods based on very
di®erent principles cannot be performed without formal comparison criteria. Visual comparison
of arti¯cially noisy images with their denoised version is subjective. Tables comparing distances
of the denoised image to the original are useful. They have two drawbacks, though. The added
noise is usually not realistic, generally a white uniform noise with too large variance. Such
comparison methods depend strongly on the choice of the image and do not permit to address
the main issues: the loss of image structure in noise and the creation of artifacts.
Thus we shall propose and apply three principles aiming at more objective benchmarks.
The ¯rst principle (already presented in [7]) asks that noise and only noise be removed from
an image. It has to be perceptually tested directly on an image with no arti¯cial noise added.
The comparison of methods is performed on the di®erence between the image and its denoised
version. We call this di®erence method noise. It is much easier to evaluate whether a method
noise contains some structure removed from the image or not. The outcome of such experiments
is clear cut on a wide class of denoising ¯lters of all origins including all mentioned neighborhood
¯lters.
The second principle, noise to noise, requires that a denoising algorithm transforms a white
noise into white noise. This paradoxical requirement seems to be the best way to characterize
2
artifact-free algorithms. It is a®ordable to mathematical analysis. Mathematical and experimental
arguments will show that bilateral ¯lters and NL-means are the only ones satisfying the
noise to noise principle.
The third principle, the statistical optimality is restricted to neighborhood ¯lters. It questions
whether a given neighborhood ¯lter is able or not to retrieve faithfully the neighborhood
J(i) of any pixel i. NL-means will be shown to best match this requirement.
We shall proceed as follows. Section 2 presents a realistic CCD noise model and the basic
hypothesis justifying neighborhood ¯lters. Neighborhood ¯lters including NL-means and motion
compensated movie denoising ¯lters are de¯ned in Section 3. This section includes the extension
of the NL-means ¯lters to movies. Section 4 proposes the three principles to evaluate the
performance of any denoising method. All three principles are designed to serve comparative
experiments. Finally, the last section is devoted to a more mathematical comparison of classical
neighborhood ¯lters and the NL-means.
2 Noise model
Most digital images and movies are obtained by a CCD device. Following [8, 13, 12], CCD's
show three kinds of noise. The ¯rst one is the shot noise proportional to the square root of the
number of incoming photons in the captors during the exposure time, namely
n0 = r ©
hº
t ¢ A ¢ ´;
where © is the light power (W/m2), hº the photon energy (Ws), t the exposure time in seconds
(s), A the pixel area (m2) and ´ the quantum e±ciency. The other constants being ¯xed we
can simply retain n0 = cp© where © is the \true image" and C a constant (see Figure 1).
Second, a dark or obscurity noise n1 is due to spurious photons produced by the captor
itself. We can assume the dark noise to be white, additive and with zero mean. The zero mean
property is due to the substraction of a dark frame from the raw image. The dark frame is
obtained by averaging the obscurity noise over a long period of time.
Third, the read out noise n2 is another electronic additive and signal independent noise.
This noise can be assumed to have zero mean by the substraction from the raw image of a bias
frame.
Digital images eventually undergo a \gamma" correction, i.e. a nonlinear increasing contrast
change g: \Gamma correction is the name of an internal adjustment made in the rendering
of images through photography, television, and computer imaging. The adjustment causes
the spacing of steps of shade between the brightest and dimmest part of an image to appear
\appropriate" [12]." Summarizing,
[attachment=25507]
Abstract
Neighborhood ¯lters are image and movie ¯lters which reduce the noise by averaging
similar pixels. The object of the paper is to present a uni¯ed theory of these ¯lters and
reliable criteria to compare them to other classes of ¯lters. First a CCD noise model
will be presented justifying this class of algorithm. A classi¯cation of neighborhood ¯lters
is proposed, including classical image and movie denoising methods and a new one,
the nonlocal-means (NL-means). In order to compare denoising methods three principles
will be introduced. The ¯rst principle, \method noise", speci¯es that only noise must
be removed from an image. Second a \noise to noise" principle states that a denoising
method must transform a white noise into a white noise. This principle characterizes
artifact-free methods. A third principle, the \statistical optimality", permits to compare
the performance of neighborhood ¯lters. The three principles will be applied to compare
ten di®erent image and movie denoising methods. It will be ¯rst shown that only
wavelet thresholding methods and NL-means give an acceptable method noise. Second,
that neighborhood ¯lters are the only ones to satisfy the \noise to noise" principle. Third,
that among them NL-means is closest to statistical optimality. A particular attention is
paid to movie denoising methods. Motion compensated denoising methods turn out to
be neighborhood ¯lters where the neighborhood is constrained to stay on a single trajectory.
It is demonstrated that this constraint is harmful for denoising purposes and that
space-time NL-means preserves more movie details.
1 Introduction
The main objective of this paper is to set under a common framework all neighborhood ¯lters,
including movie ¯lters which are usually treated as a di®erent class. We shall call neighborhood
¯lters all image and movie ¯lters which reduce the noise by averaging similar pixels. General
CCD noise models (brie°y presented in Section 2) imply that noise in digital images and movies
is signal dependent. Fortunately two pixels which received the same energy from the outdoor
scene undergo the same kind of perturbations and therefore have the same noise model. Under
the fairly general assumption that at each energy level the noise model is additive and white,
denoising can be achieved by ¯rst ¯nding out the pixels which received the same original energy
and then averaging their observed grey levels. This observation has led to the wide class of
neighborhood ¯lters classi¯ed in [39]. Since the original image value is lost these ¯lters proceed
by picking for each pixel i the set of pixels J(i) spatially close to i and with a similar grey level
value.
Neighborhood ¯lters proceed by replacing the grey level value of i, u(i), by the average
NFu(i) = 1
jJ(i)j Pj2J(i) u(j). (Depending on the noise model other statistical estimates are
of course possible like the median, etc.) Under the assumption that pixels j 2 J(i) indeed
received the same original energy as i, NFu(i) is a denoised version of u(i). The more famous
1
neighborhood ¯lters are Lee's ¾-¯lter [20], SUSAN [33] and the bilateral ¯lter [35] where the
neighborhoods are gaussian in space and grey level.
In a recent communication [7] (see also [6] for a mathematical analysis) the authors of the
present paper extended the above mentioned neighborhood ¯lters to a wider class which they
called non-local means (NL-means). This algorithm de¯nes the neighborhood J(i) of i by the
condition: j 2 J(i) if the grey level of a whole window around j is close to the grey level of the
window around i. The spatial constraint is instead relaxed.
NL-means ¯lters can be given two origins beyond classical neighborhood ¯lters. The same
Markovian pixel similarity model was used in the seminal paper [11] for texture synthesis from
a texture sample. In that case the neighborhood J(i) is not used for denoising. The aim is to
estimate from the texture sample the law of i knowing its neighborhood. This law is used to
synthesize similar texture images by an iterative algorithm.
Last but not least most state of the art movie denoising methods are neighborhood ¯lters
and some of them, in some sense, NL-means ¯lters. Indeed, motion compensated denoising
methods start with the search for a temporal neighborhood J(i), the trajectory, followed by
an averaging process. By the Lambertian assumption a pixel belonging to a certain object
conserves the same grey level value during its trajectory. Therefore this is computed as a grey
level neighborhood of i in the sense of neighborhood ¯lters. The comparison of grey levels is
not a su±cient criterion, a di±culty usually called the aperture problem. Thus several motion
compensated ¯lters involve block matching. They construct J(i) by comparing a whole block
around j to a whole block around i.
In all of these algorithms the neighborhood J(i) picks a single pixel per frame. One of our
objectives is to prove that this restriction is actually counterproductive. In fact the performance
of movie denoising ¯lters improves signi¯cantly by forgetting about trajectories and using all
similar pixels in space-time, no matter how many are picked per frame. For this reason we
extend the NL-means ¯lter to movies by applying it directly to the movie thought of as a union
of images. The time ordering of this union is somewhat irrelevant. The aperture problem
results in the existence of more samples for each pixel and therefore increases the denoising
performance by nonlocal means.
No new denoising method should be presented without a systematic comparison to the huge
variety of denoising methods. On the other hand a comparison between methods based on very
di®erent principles cannot be performed without formal comparison criteria. Visual comparison
of arti¯cially noisy images with their denoised version is subjective. Tables comparing distances
of the denoised image to the original are useful. They have two drawbacks, though. The added
noise is usually not realistic, generally a white uniform noise with too large variance. Such
comparison methods depend strongly on the choice of the image and do not permit to address
the main issues: the loss of image structure in noise and the creation of artifacts.
Thus we shall propose and apply three principles aiming at more objective benchmarks.
The ¯rst principle (already presented in [7]) asks that noise and only noise be removed from
an image. It has to be perceptually tested directly on an image with no arti¯cial noise added.
The comparison of methods is performed on the di®erence between the image and its denoised
version. We call this di®erence method noise. It is much easier to evaluate whether a method
noise contains some structure removed from the image or not. The outcome of such experiments
is clear cut on a wide class of denoising ¯lters of all origins including all mentioned neighborhood
¯lters.
The second principle, noise to noise, requires that a denoising algorithm transforms a white
noise into white noise. This paradoxical requirement seems to be the best way to characterize
2
artifact-free algorithms. It is a®ordable to mathematical analysis. Mathematical and experimental
arguments will show that bilateral ¯lters and NL-means are the only ones satisfying the
noise to noise principle.
The third principle, the statistical optimality is restricted to neighborhood ¯lters. It questions
whether a given neighborhood ¯lter is able or not to retrieve faithfully the neighborhood
J(i) of any pixel i. NL-means will be shown to best match this requirement.
We shall proceed as follows. Section 2 presents a realistic CCD noise model and the basic
hypothesis justifying neighborhood ¯lters. Neighborhood ¯lters including NL-means and motion
compensated movie denoising ¯lters are de¯ned in Section 3. This section includes the extension
of the NL-means ¯lters to movies. Section 4 proposes the three principles to evaluate the
performance of any denoising method. All three principles are designed to serve comparative
experiments. Finally, the last section is devoted to a more mathematical comparison of classical
neighborhood ¯lters and the NL-means.
2 Noise model
Most digital images and movies are obtained by a CCD device. Following [8, 13, 12], CCD's
show three kinds of noise. The ¯rst one is the shot noise proportional to the square root of the
number of incoming photons in the captors during the exposure time, namely
n0 = r ©
hº
t ¢ A ¢ ´;
where © is the light power (W/m2), hº the photon energy (Ws), t the exposure time in seconds
(s), A the pixel area (m2) and ´ the quantum e±ciency. The other constants being ¯xed we
can simply retain n0 = cp© where © is the \true image" and C a constant (see Figure 1).
Second, a dark or obscurity noise n1 is due to spurious photons produced by the captor
itself. We can assume the dark noise to be white, additive and with zero mean. The zero mean
property is due to the substraction of a dark frame from the raw image. The dark frame is
obtained by averaging the obscurity noise over a long period of time.
Third, the read out noise n2 is another electronic additive and signal independent noise.
This noise can be assumed to have zero mean by the substraction from the raw image of a bias
frame.
Digital images eventually undergo a \gamma" correction, i.e. a nonlinear increasing contrast
change g: \Gamma correction is the name of an internal adjustment made in the rendering
of images through photography, television, and computer imaging. The adjustment causes
the spacing of steps of shade between the brightest and dimmest part of an image to appear
\appropriate" [12]." Summarizing,