A Non-Local Algorithm for Image Denoising

“A Non-Local Algorithm for Image Denoising” is a six-page paper by Antoni Buades and Bartomeu Coll of the University of the Balearic Islands and Jean-Michel Morel of CMLA, ENS Cachan, presented at the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) in 2005. It made two proposals: method noise, the difference between an image and its denoised version, as a tool for judging what a denoiser removes; and the non-local means (NL-means) algorithm, which estimates each pixel as a weighted average of pixels whose neighborhoods resemble its own, wherever they lie in the image. The paper received a Best Paper Honorable Mention at CVPR 2005 and, in 2015, the Longuet-Higgins Prize, awarded at CVPR by the PAMI Technical Committee to CVPR papers from ten years earlier that have had a significant impact on computer vision.

A longer journal paper by the same authors, “A Review of Image Denoising Algorithms, with a New One,” appeared in Multiscale Modeling & Simulation the same year. It develops the same ideas with a broader comparison; this article covers the CVPR paper and says where a point comes from the review.

Problem

The authors observed that most denoising methods, however different their tools, work by averaging. The averaging may be local, as in Gaussian smoothing, anisotropic diffusion, and neighborhood filters such as Yaroslavsky’s filter, the SUSAN filter, and the bilateral filter; it may come from a variational model, as in total variation minimization; or it may happen in a transform domain, as in empirical Wiener filtering and wavelet thresholding. In the authors’ assessment, most of them degrade or remove the fine detail and texture of the image.

Comparing such methods was itself a problem. The usual protocol adds noise to a clean image and measures how close the result comes to the original, but a small mean squared error does not guarantee good visual quality, and the comparison says little about what kind of structure a method destroys.

Contribution

• Method noise. For a denoising operator $D_h$ with filtering parameter $h$ and an image $u$, the method noise is $u - D_h u$. A good method should leave an image that is already nearly noise-free almost unchanged, so its method noise should be small and look like noise, with as little structure as possible. The authors argued that this criterion needs no added noise at all.
• Closed-form method noise for local filters. The paper gives the method noise of Gaussian smoothing (for small $h$, proportional to the Laplacian of the image), of anisotropic filtering (for small $h$, proportional to the gradient magnitude times the curvature of the level lines), and of total variation minimization (proportional to the curvature of the result). These show exactly where each method alters the image: Gaussian smoothing harms edges and texture, while the curvature-based methods keep straight edges but degrade curved edges and texture.
• NL-means. The algorithm replaces the single-pixel comparison of neighborhood filters with a comparison of whole neighborhoods, and lets the average run over the entire image rather than a local window. The authors described it as systematically using every self-prediction the image can provide, in the spirit of Efros and Leung’s non-parametric texture synthesis.
• Consistency. Under stationarity assumptions, the NL-means estimate converges as the image grows to the conditional expectation of a pixel given its neighborhood, which under additive white noise is the estimate with the least mean squared error.

Method

For a discrete noisy image $v$, the estimate at pixel $i$ is a weighted average of all pixels $j$, with weights between 0 and 1 that sum to one. The weight of $j$ decreases exponentially with the squared Euclidean distance between the square neighborhoods centered at $i$ and $j$, with each offset in the neighborhood weighted by a Gaussian of standard deviation $a$; the parameter $h$ sets how fast the weights decay. The paper shows that, in expectation, the distance between two noisy neighborhoods equals the distance between the clean ones plus $2\sigma^2$, so the order of similarity is preserved. Its illustrations of the weights show them concentrating along the same side of a straight or curved edge, over a flat region, on every repetition of a periodic pattern, and on similar structures far from the pixel.

The consistency result models the image as a realization of a strictly stationary, mixing random field, relying on a theorem from nonparametric regression by Roussas. The authors noted that NL-means therefore corrects the noisy image rather than trying to separate an oscillatory noise component from a smooth image.

In the experiments, the search was restricted to a $21 \times 21$ window around each pixel, with $7 \times 7$ neighborhoods, which the authors judged large enough to be robust to noise and small enough to keep fine structure, and $h$ was set to $10\sigma$ for noise of standard deviation $\sigma$, a value that depends on how the patch distance is normalized. They gave the cost as about $49 \times 441$ operations per pixel.

Results

The paper compares NL-means with Gaussian filtering, anisotropic filtering, total variation minimization, and the Yaroslavsky neighborhood filter on three criteria: method noise, visual quality, and mean squared error. On the Lena image, with $h$ set to remove noise of standard deviation 2.5, the method noise of NL-means shows no noticeable geometric structure, while those of the local filters show edges and texture, as the formulas predict. Visual comparisons on a natural texture with noise of standard deviation 35 and on Lena with standard deviation 20 show the local filters blurring detail or creating artifacts. In the reported mean squared errors, NL-means had the lowest values on both test images: 68 on Lena against 110 to 129 for the other methods, and 292 on Baboon against 365 to 507. The authors noted that mean squared error cannot be computed for real noisy images and does not by itself ensure visual quality, so all three criteria are needed.

The companion review extends the comparison to the SUSAN filter, two iterated total variation refinements, an empirical Wiener filter, and translation-invariant wavelet thresholding, discusses two other recent window-comparison methods (DUDE and UINTA), gives recommended neighborhood sizes for gray and color images, describes a faster multiscale version, and applies the algorithm to color images and films.

Impact

NL-means made image self-similarity a working principle of denoising. Dabov, Foi, Katkovnik and Egiazarian (2007), citing the journal version, present non-local means as a recently introduced estimation strategy and note that their BM3D method rests on the same assumptions about the signal; BM3D replaced the weighted average with joint filtering of groups of similar patches in a 3D transform domain. Low-rank methods such as weighted nuclear norm minimization continued the patch-group line (see Image Denoising). In 2011 the authors published a reference implementation with parameter tables in Image Processing On Line, which adjusts the weights for the expected noise contribution and grows the patch size with the noise level.

Limitations

The method is only as good as the redundancy of the image: unique structures such as corners and small isolated details have few similar neighborhoods, and they remain noisy or are blurred, a weakness the companion review addresses with a variance-based correction. The direct computation is expensive, and the CVPR paper restricts the search to a local window, so in practice the algorithm is not fully non-local. Its weights assume white noise of known, uniform variance. The experiments use a handful of images and visual comparisons, and the consistency theorem assumes stationarity and an image that grows without bound, which real images only approximate. The authors themselves identified textured and periodic images as its most favorable case, and less redundant content as harder.

What Came After

Fast implementations computed patch distances with integral images, making the cost independent of patch size, and patchwise variants averaged overlapping patch estimates. Block matching and collaborative filtering in BM3D, low-rank patch models, and learned patch priors built on the idea that similar patches can be denoised together. Deep convolutional denoisers such as DnCNN later reported higher accuracy than these methods without explicit patch matching, although attention layers in later restoration networks compare features across an image in a related way.