Non-local means

Definition

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

:u(p) = {1 \over C(p)}\int_\Omega v(q) f(p,q),\mathrm{d}q.

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 \forall q\in\Omega.

C(p) is a normalizing factor, given by

:C(p) = \int_\Omega f(p,q),\mathrm{d}q.NL \left [ u \right ] (x) = {1 \over C(x)}\int_\Omega e^{-v(y)dy. --

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:

:f(p,q) = e^{-

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, once again, v(q) is the unfiltered value of the image at point q. C(p) is given by:

:C(p)= \sum_{q \in \Omega}f(p,q)

Then, for a Gaussian weighting function,

:f(p,q) = e^{-

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.w(i,j)= {1 \over Z(i)}e^{-, --

Efficient implementation

The computational complexity of the non-local means algorithm is quadratic in the number of pixels in the image, making it particularly expensive to apply directly. Several techniques were proposed to speed up execution. One simple variant consists of restricting the computation of the mean for each pixel to a search window centred on the pixel itself, instead of the whole image. Another approximation uses summed-area tables and fast Fourier transform to calculate the similarity window between two pixels, speeding up the algorithm by a factor of 50 while preserving comparable quality of the result.

References

References

1. (20–25 June 2005). "2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05)".
2. "On image denoising methods".
3. (2012). "2012 Conference Record of the Forty Sixth Asilomar Conference on Signals, Systems and Computers (ASILOMAR)".
4. (2013). "2013 IEEE International Conference on Multimedia and Expo Workshops (ICMEW)".
5. "Depth Estimation From a Video Sequence with Moving and Deformable Objects". IET Image Processing Conference.
6. (2011). "Non-Local Means Denoising". Image Processing on Line.
7. "On image denoising methods (page 10)".
8. (2006). "Fast non-local algorithm for image denoising".