Full search page →

Non-local means denoising

Optional · supplementary note 6 of 7 for IP 05 · Image Restoration and Reconstruction. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.

Navigate: this page and this track: Navigate: this page and this track

In plain words: to guess what a noisy pixel really was, do not just ask its neighbours; ask every place in the neighbourhood that looks like this one. Proofreading a smudged word works the same way. You compare it with other places where the same word appears, and combine the readings.

A Gaussian filter averages pixels that are close. Near an edge it mixes both sides, so it blurs. Non-local means (NLM) [7] averages pixels whose surrounding patches are similar, however far away they are inside a search window. The precise form is

u^(p)=1Z(p)∑q∈Ω(p)w(p,q) f(q),w(p,q)=exp⁡ ⁣(−∥Pp−Pq∥2h2),Z(p)=∑q∈Ω(p)w(p,q),\hat u(p) = \frac{1}{Z(p)} \sum_{q \in \Omega(p)} w(p, q)\, f(q), \qquad w(p, q) = \exp\!\left(-\frac{\lVert P_p - P_q \rVert^2}{h^2}\right), \qquad Z(p) = \sum_{q \in \Omega(p)} w(p, q),

where ff is the noisy image, u^(p)\hat u(p) the estimate at pixel pp, Ω(p)\Omega(p) the search window (the pixels allowed to vote for pp), PpP_p the vector of gray values of the small patch centred at pp (for example 5×55 \times 5 pixels), ∥⋅∥\lVert\cdot\rVert the Euclidean norm, h>0h > 0 the strength parameter, and Z(p)Z(p) the normalizer that makes the weights add up to 1. The weight is near 1 when two patches agree and falls toward 0 when they differ by much more than hh. Because hh sets what “similar” means, a small hh keeps too much noise (few patches qualify) and a large hh blurs (unlike patches vote). A common rule of thumb is hh close to the noise standard deviation σ\sigma. The scikit-image implementation can also take σ\sigma and uses it to account for the noise variance when it computes the patch weights.

Why does it help? If MM patches in the image are true look-alikes, averaging their centres reduces the noise variance by roughly a factor of MM, and an edge is not blurred because only patches that contain the same edge vote. This is why NLM does well on textures and on repeated structure (windows, bricks, fur), where plenty of look-alikes exist. It does worse on one-off details, which have no look-alikes, so they keep their noise or get averaged with imperfect matches.

Cost. With NN pixels, a search window of S×SS \times S and patches of k×kk \times k, the direct method needs about NS2k2N S^2 k^2 operations. Cheaper versions compute all patch distances for one shift at once with cumulative sums (integral images), which removes the factor k2k^2; limiting SS is the other lever. Block-matching methods such as BM3D [8] push the same idea further. The journal paper by the same authors [20] compares NLM with other denoising families.

The snippet adds seeded Gaussian noise (σ=0.08\sigma = 0.08 on a 0–1 scale) to a 256×256256 \times 256 crop of the camera test image, then compares the best Gaussian filter from a small sweep against NLM (fast_mode=True, a 13×1313 \times 13 search window, 5×55 \times 5 patches).

Code · Python · 20 lines
import numpy as np
from skimage import data, img_as_float
from skimage.filters import gaussian
from skimage.metrics import peak_signal_noise_ratio as psnr
from skimage.restoration import denoise_nl_means

clean = img_as_float(data.camera())[:256, :256]           # 256 x 256 crop
sigma = 0.08                                              # noise standard deviation
rng = np.random.default_rng(0)
noisy = np.clip(clean + rng.normal(0, sigma, clean.shape), 0, 1)

# Gaussian smoothing, best of a small sweep over its width s
g = max((psnr(clean, gaussian(noisy, s)), s) for s in (0.8, 1.0, 1.2, 1.5))

# Non-local means: 5x5 patches, search window 13x13 (patch_distance=6), h near sigma
nlm = {hf: denoise_nl_means(noisy, patch_size=5, patch_distance=6, h=hf * sigma,
                            sigma=sigma, fast_mode=True) for hf in (0.6, 0.8, 1.0)}
for hf, out in nlm.items():
    print(f"NLM h = {hf} sigma: {psnr(clean, out):.2f} dB")
print(f"noisy {psnr(clean, noisy):.2f} dB | Gaussian s={g[1]}: {g[0]:.2f} dB")

Output:

Code · 4 lines
NLM h = 0.6 sigma: 32.80 dB
NLM h = 0.8 sigma: 32.85 dB
NLM h = 1.0 sigma: 32.52 dB
noisy 22.30 dB | Gaussian s=1.0: 29.91 dB

On this crop and seed, NLM is about 3 dB above the best Gaussian filter, and the three hh values stay within 0.35 dB of each other. This is one image and one noise draw, so read it as an illustration, not a ranking of methods. The common mistake is to set hh far above σ\sigma “for more smoothing”: the result then turns into a blur with extra steps.

References

  1. R. C. Gonzalez and R. E. Woods, Digital Image Processing, 4th ed., Pearson, 2018, Ch. 5. publisher page
  2. H. Hwang and R. A. Haddad, “Adaptive median filters: new algorithms and results,” IEEE Transactions on Image Processing, vol. 4, no. 4, pp. 499–502, 1995. DOI
  3. B. R. Hunt, “The application of constrained least squares estimation to image restoration by digital computer,” IEEE Transactions on Computers, vol. C-22, no. 9, pp. 805–812, 1973. DOI
  4. A. C. Kak and M. Slaney, Principles of Computerized Tomographic Imaging, IEEE Press, 1988 (SIAM reprint 2001). free online edition
  5. L. A. Shepp and B. F. Logan, “The Fourier reconstruction of a head section,” IEEE Transactions on Nuclear Science, vol. 21, no. 3, pp. 21–43, 1974. DOI
  6. scikit-image developers, “Radon transform,” scikit-image documentation (gallery example). docs
  7. A. Buades, B. Coll and J.-M. Morel, “A non-local algorithm for image denoising,” IEEE CVPR, vol. 2, pp. 60–65, 2005. DOI
  8. K. Dabov, A. Foi, V. Katkovnik and K. Egiazarian, “Image denoising by sparse 3-D transform-domain collaborative filtering,” IEEE Transactions on Image Processing, vol. 16, no. 8, pp. 2080–2095, 2007. DOI
  9. K. Zhang, W. Zuo, Y. Chen, D. Meng and L. Zhang, “Beyond a Gaussian denoiser: Residual learning of deep CNN for image denoising,” IEEE Transactions on Image Processing, vol. 26, no. 7, pp. 3142–3155, 2017. doi · arXiv
  10. C. Tian, L. Fei, W. Zheng, Y. Xu, W. Zuo and C.-W. Lin, “Deep learning on image denoising: An overview,” Neural Networks, vol. 131, pp. 251–275, 2020. arXiv
  11. M. Elad, B. Kawar and G. Vaksman, “Image denoising: The deep learning revolution and beyond — A survey paper,” SIAM Journal on Imaging Sciences, vol. 16, no. 3, pp. 1594–1654, 2023. arXiv
  12. K. Zhang, W. Ren, W. Luo, W.-S. Lai, B. Stenger, M.-H. Yang and H. Li, “Deep image deblurring: A survey,” International Journal of Computer Vision, 2022. arXiv
  13. G. Ongie, A. Jalal, C. A. Metzler, R. G. Baraniuk, A. G. Dimakis and R. Willett, “Deep learning techniques for inverse problems in imaging,” arXiv:2005.06001, 2020. arXiv
  14. U. S. Kamilov, C. A. Bouman, G. T. Buzzard and B. Wohlberg, “Plug-and-play methods for integrating physical and learned models in computational imaging: Theory, algorithms, and applications,” IEEE Signal Processing Magazine, vol. 40, no. 1, pp. 85–97, 2023. arXiv
  15. K. Zhang, Y. Li, W. Zuo, L. Zhang, L. Van Gool and R. Timofte, “Plug-and-play image restoration with deep denoiser prior,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 44, no. 10, pp. 6360–6376, 2022. arXiv
  16. K. H. Jin, M. T. McCann, E. Froustey and M. Unser, “Deep convolutional neural network for inverse problems in imaging,” IEEE Transactions on Image Processing, vol. 26, no. 9, pp. 4509–4522, 2017. arXiv
  17. J. Adler and O. Öktem, “Learned primal-dual reconstruction,” IEEE Transactions on Medical Imaging, 2018. arXiv
  18. V. Monga, Y. Li and Y. C. Eldar, “Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing,” arXiv:1912.10557, 2019. arXiv
  19. G. Wang, J. C. Ye and B. De Man, “Deep learning for tomographic image reconstruction,” Nature Machine Intelligence, vol. 2, no. 12, pp. 737–748, 2020. DOI
  20. A. Buades, B. Coll and J.-M. Morel, “A review of image denoising algorithms, with a new one,” Multiscale Modeling & Simulation, vol. 4, no. 2, pp. 490–530, 2005. DOI
  21. L. I. Rudin, S. Osher and E. Fatemi, “Nonlinear total variation based noise removal algorithms,” Physica D: Nonlinear Phenomena, vol. 60, no. 1–4, pp. 259–268, 1992. DOI
  22. A. Chambolle, “An algorithm for total variation minimization and applications,” Journal of Mathematical Imaging and Vision, vol. 20, no. 1–2, pp. 89–97, 2004. DOI
  23. A. Buades, B. Coll and J.-M. Morel, “Non-Local Means Denoising,” Image Processing On Line, vol. 1, pp. 208–212, 2011. DOI · article and implementation