ipol.im » pub » algo »  
Non-local Means Denoising
edit This workshop may eventually be submitted and published.
  1. Overview
  2. References
  3. Implementation
  4. Source Code
  5. On Line Demo: Try It!
  6. Examples

Overview

In any digital image, the measurement of the three observed color values at each pixel is subject to some perturbations. These perturbations are due to the random nature of the photon counting process in each sensor. The noise can be amplified by digital corrections of the camera or any image processing software. For example, the tools removing blur from images or increasing the contrast.

The principle of most denoising methods is quite simple: Replace the color of a pixel with an average of the nearby pixels colors. This method is well-known to statisticians. The variance law in probability theory ensures that if nine times more pixels are averaged, the noise is divided by 3. Thus, one should find for each pixel nine other pixels in the image with the same color (up to the fluctuations due to noise). This looks promising, but where can these nine pixels be found?

The most similar pixels to a given pixel have no reason to be close at all. Think of the periodic patterns, or the elongated edges which appear in most images. It is therefore licit to scan a vast portion of the image in search of all the pixels that really resemble the pixel one wants to denoise. Denoising is then done by computing the average color of these most resembling pixels. The resemblance is evaluated by comparing a whole window around each pixel, not just the color. This new filter is called non-local means and it writes

NL u(p) = \frac{1}{C(p)} \int f(d(B(p),B(q)) \, u(q) \,dq

where d(B(p), B(q)) is an euclidean distance between image blocks centered respectively at p and q, f is a decreasing function and C(p) is the normalizing factor.

References

  1. A. Buades, B. Coll, J.M. Morel "A review of image denoising methods, with a new one"
    Multiscale Modeling and Simulation, Vol4 (2), pp: 490-530, 2006. on line article

  2. A. Buades, B. Coll, J.M. Morel "A non local algorithm for image denoising"
    IEEE Computer Vision and Pattern Recognition 2005, Vol 2, pp: 60-65, 2005. on line article

Implementation

The denoising of a color image u=(u1, u2, u3) and a certain pixel p writes

\hat{u_i}(p) = \frac{1}{C(p)} \sum_{q \in B(p, r)} u_i(q) \, w(p,q), \qquad C(p) = \sum_{q \in B(p, r)} w(p,q)

where i=1, 2, 3 and B(p, r) indicates a neighborhood centered at p and size 2r+1 × 2r+1 pixels.

The weight w(p, q) depends on the squared Euclidean distance d² = d²(B(p), B(q)) of the N × N color patches centered respectively at p and q

d^2(B(p),B(q)) = \frac{1}{3 N^2} \sum_{i=1}^3 \sum_{j=1}^{N^2} \, (u_i(p+j) - u_i(q+j))^2.

That is, each pixel value is restored by an average of the most resembling pixels where this resemblance is computed in the color image. So for each pixel, each channel value is the result of the average of the same pixels.

We use a piece-wise linear function for computing the weights w(p, q)

w(p,q) = \left\{ \begin{array}{ll} 1 & d^2 < 2 \sigma^2 \\ & \\ \frac{d^2 - 2 \sigma^2}{2 \gamma} & 2 \sigma^2 \leq d^2 \leq 2 \sigma^2 + 2 \gamma \\ & \\ 0 & d^2 > 2 \sigma^2 + 2 \gamma \end{array}\right.

where σ denotes the standard deviation of the noise and γ is the standard deviation of the distance between two noise patches.

The weight function is set in order to average similar patches up to noise. That is, patches which dissimilarity only due to noise. In order to compute such a standard deviation we can rewrite

\frac{3 N^2}{2 \sigma^2} d^2(B(p),B(q)) = \sum_{i=1}^3 \sum_{j=1}^{N^2} \left( \frac{u_i(p+j) - u_i(q+j)}{\sqrt{2} \sigma} \right)^2

being u a noise image. Using the fact that such an expressions follows a \chi^2_{3 N^2 - 1} and its variance equals 6 N², we can isolate the variance of the square distance of the two noise patches as γ = 8 σ⁴ / N².

By applying the above averaging procedure we recover the denoised value at each pixel p. The presented formulas can be easily modified in order to denoise the whole N × N patch centered at p at the same time. In that way, by applying the procedure for all pixels in the image, we shall dispose of N² possible estimates for each pixel. These estimates are finally averaged at each location.

The parameters on the online demo are set in the following way: the size of the research window B(p, r) is 21×21 pixels and the comparison patch has size 3×3 pixels for color images. When the algorithm is applied to gray images a slightly larger patch of 5×5 pixels is used.

Source Code

A C/C++ implementation is provided.

It should compile on any system since it's only strict ANSI C/C++ and is distributed under the GPL licence.

Basic compilation and usage instructions are included in the README.txt file. This code requires libtiff and is limited to 8bit RGB or grayscale TIFF image files.

The same code is used for the online demo.

On Line Demo: Try It!

An on-line demo of this algorithm is available.

The demo permits to upload any color image, optionally add gaussian noise, then automatically estimate the noise and denoise it.

Examples

The example below illustrates how the NLmeans algorithm is able to remove the noise while keeping the fine structures and details.

original noisy, standard deviation 15 denoised
original noisy, standard deviation 15 denoised

credits

π