In Section 2, we have computed explicitly the method
noise of the local smoothing filters. These formulas are
corroborated by the visual experiments of Figure 3. This
figure displays the method noise for the standard image
Boat, that is, the difference u − Dh(u), where the parameter
h is been fixed in order to remove a noise with standard
deviation 2. 5. The method noise helps us in understanding the performance and limitations of the denoising algorithms, since removed details or texture correspond to a
large method noise. We see in Figure 3 that the NL-means
method noise does not present noticeable geometrical
structures. Figure 4 explains this property since it shows
how the NL-means algorithm chooses a weighting configuration adapted to the local and nonlocal geometry of
the image.
4. nL-means ConsIstenCY
Under stationarity assumptions, for a pixel i, the NL-means
algorithm converges to the conditional expectation of i once
observed a neighborhood of it. In this case, the stationarity
conditions amount to say that as the size of the image grows,
we can find many similar patches for all the details of the
image.
Let V be a random field and suppose that the noisy
image v is a realization of V. Let Z denote the sequence of
random variables Zi = { Yi , Xi} where Yi = V (i) is real valued and
Xi = V (Ni \{i}) is Rp valued. The NL-means is an estimator of
the conditional expectation r (i) = E[ Yi|Xi = v(Ni \{i})].
Theorem 5 (Conditional Expectation Theorem).
Let Z = {V (i), V(Ni\{i})} for i = 1, 2, . . . be a strictly stationary
and mixing process. Let NLn denote the NL-means algorithm
applied to the sequence Zn = {V(i), V(Ni\{i})}ni = 1. Then for j ∈
{ 1, . . . , n},
|NLn( j ) − r( j )| → 0 a.s.
The full statement of the hypothesis of the theorem and
its proof can be found in a more general framework in
Roussas. 38 This theorem tells us that the NL-means algorithm corrects the noisy image rather than trying to separate
the noise (oscillatory) from the true image (smooth).
In the case that an additive white noise model is assumed,
the next result shows that the conditional expectation is the
function of V (Ni\{i}) that minimizes the mean square error
with the true image u.
Theorem 6. Let V, U, N be random fields on I such that
V = U + N, where N is a signal-independent white noise. Then,
the following statements hold good.
(i) E[V(i ) | Xi = x] = E[U(i ) | Xi = x] for all i ∈ I and x ∈ Rp.
(ii) The expected random variable E[U(i ) | V (Ni\{i })] is the
function of V (Ni\{i}) that minimizes the mean square
error
min
g
E[U(i ) − g (V(Ni \{i}))] 2
Similar optimality theoretical results have been obtained in
Ordentlich et al. 34 and presented for the denoising of binary
images.
5. DIsCussIon anD exPeRImentatIon
In this section, we compare the local smoothing filters, the
wavelet thresholding algorithms, 17 sliding DCT Wiener filter, 46 and the NL-means algorithm. The wavelet thresholding and the sliding DCT algorithms yield state-of-the-art
results among frequency domain filters.
For computational purposes of the NL-means algorithm, the search of similar windows was restricted to a
larger “search window” with size S × S pixels. In all experiments, the search window has 21 × 21 pixels and the similarity square neighborhood 3 × 3 pixels for color images
and 5 × 5 pixels for gray images. When denoising a color
figure 3. Image method noise. from left to right and from top to bottom: original image, Gaussian convolution, anisotropic filtering, total
variation minimization, neighborhood filter, translation invariant wavelet thresholding, DCt sliding window Wiener filter, and the nL-means
algorithm. the parameters have been set for each method to remove a method noise with variance s2 = 2. 52.