Non-local means

Non-local means is an algorithm in image processing for image denoising. Unlike "local mean" filters, which take the mean value of a group of pixels surrounding a target pixel to smooth the image, non-local means filtering takes a mean of all pixels in the image, weighted by how similar these pixels are to the target pixel. This results in much greater post-filtering clarity, and less loss of detail in the image compared with local mean algorithms.^[1]

If compared with other well-known denoising techniques, such as the Gaussian smoothing model, the anisotropic diffusion model, the total variation denoising, the neighborhood filters and an elegant variant, the Wiener local empirical filter, the translation invariant wavelet thresholding, the non-local means method noise looks more like white noise.^[2] Recently non-local means has been extended to other image processing applications such as deinterlacing^[3] and view interpolation.^[4]

Definition

Suppose $\Omega$ is the area of an image, and $p$ and $q$ are two points within the image. Then, the algorithm is:^[5]

$u(p)={1 \over C(p)}\int _{\Omega }v(q)f(p,q)dq.$

where $u(p)$ is the filtered value of the image at point $p$, $v(q)$ is the unfiltered value of the image at point $q$, $f(p,q)$ is the weighting function, and the integral is evaluated over $\forall q\in \Omega$.

$C(p)$ is a normalizing factor, given by:

$C(p)=\int _{\Omega }f(p,q)dq.$

Common weighting functions

The purpose of the weighting function, $f(p,q)$, is to determine how closely related the image at the point $p$ is to the image at the point $q$. It can take many forms.

Gaussian

The Gaussian weighting function sets up a normal distribution with a mean, $\mu =B(p)$ and a variable standard deviation:^[6]

$f(p,q)=e^{{-{{\left\vert B(q)-B(p)\right\vert ^{2}} \over h^{2}}}}$

where $h$ is the filtering parameter (i.e., standard deviation) and $B(p)$ is the local mean value of the image point values surrounding $p$

Discrete algorithm

For an image, $\Omega$, with discrete pixels, a discrete algorithm is required.

$u(p)={1 \over C(p)}\sum _{{q\in \Omega }}v(q)f(p,q)$

where $C(p)$ is given by:

$C(p)=\sum _{{q\in \Omega }}f(p,q)$

Then, for a Gaussian weighting function,

$f(p,q)=e^{{-{{\left\vert B(q)-B(p)\right\vert ^{2}} \over h^{2}}}}$

where $B(p)$ is given by:

$B(p)={1 \over |R(p)|}\sum _{{i\in R(p)}}v(i)$

where $R(p)\subseteq \Omega$ and is a square region of pixels surrounding $p$ and $|R(p)|$ is the number of pixels in the region $R$.

See also

• Total variation denoising
• Anisotropic diffusion
• Signal Processing
• Digital Image Processing
• Noise reduction

References

1. Buades, Antoni (20–25 June 2005). "A non-local algorithm for image denoising". Computer Vision and Pattern Recognition, 2005. 2: 60–65. doi:10.1109/CVPR.2005.38.
2. Buades, Antoni. "On image denoising methods" (PDF). 123 Seminars Only.
3. Dehghannasiri, R.; Shirani, S. (2012). "A novel de-interlacing method based on locally-adaptive Nonlocal-means".
4. Dehghannasiri, R.; Shirani, S. (2013). "A view interpolation method without explicit disparity estimation".
5. Buades, Antoni. "Non-Local Means Denoising". Image Processing On Line.
6. Buades, Antoni. "On image denoising methods (page 10)" (PDF). 123 Seminars Only.

External links

• Recent trends in denoising tutorial
• Non-local image denoising, with code and online demonstration
• Patents citing 2005 IEEE paper where NLM was claimed as a new technique