Non-local means

Non-local means is an image processing algorithm for image denoising. Where a local mean filter smooths a pixel by averaging the pixels immediately around it, non-local means takes a mean over all the pixels in the image, weighting each one by how similar it is to the target pixel. This keeps much more clarity and detail than local mean methods. The error it leaves behind, called method noise, looks more like white noise, which is less disturbing in the denoised picture. The weighting function can take several forms, one being a Gaussian. Applied directly, the method is quadratic in the number of pixels, so practical versions restrict the average to a search window centred on each pixel, or use summed-area tables and the fast Fourier transform to compare pixel neighbourhoods, which speeds it up by a factor of about 50 at comparable quality. The idea has since been extended to deinterlacing, view interpolation and depth map regularization.