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.
If compared with other well-known denoising techniques, non-local means adds "method noise" (i.e. error in the denoising process) which looks more like white noise, which is desirable because it is typically less disturbing in the denoised product. Recently non-local means has been extended to other image processing applications such as deinterlacing, view interpolation, and depth maps regularization.
Definition.
Suppose formula_1 is the area of an image, and formula_2 and formula_3 are two points within the image. Then, the algorithm is:
where formula_5 is the filtered value of the image at point formula_2, formula_7 is the unfiltered value of the image at point formula_3, formula_9 is the weighting function, and the integral is evaluated formula_10.
formula_11 is a normalizing factor, given by:
Common weighting functions.
The purpose of the weighting function, formula_9, is to determine how closely related the image at the point formula_2 is to the image at the point formula_3. It can take many forms.
Gaussian.
The Gaussian weighting function sets up a normal distribution with a mean, formula_16 and a variable standard deviation:
where formula_18 is the filtering parameter (i.e., standard deviation) and formula_19 is the local mean value of the image point values surrounding formula_2.
Discrete algorithm.
For an image, formula_1, with discrete pixels, a discrete algorithm is required.
where formula_11 is given by:
Then, for a Gaussian weighting function,
where formula_19 is given by:
where formula_28 and is a square region of pixels surrounding formula_2 and formula_30 is the number of pixels in the region formula_31.
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.