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
where is the noisy image, the estimate at pixel , the search window (the pixels allowed to vote for ), the vector of gray values of the small patch centred at (for example pixels), the Euclidean norm, the strength parameter, and 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 . Because sets what “similar” means, a small keeps too much noise (few patches qualify) and a large blurs (unlike patches vote). A common rule of thumb is close to the noise standard deviation . The scikit-image implementation can also take and uses it to account for the noise variance when it computes the patch weights.
Why does it help? If patches in the image are true look-alikes, averaging their centres reduces the noise variance by roughly a factor of , 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 pixels, a search window of and patches of , the direct method needs about operations. Cheaper versions compute all patch distances for one shift at once with cumulative sums (integral images), which removes the factor ; limiting 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 ( on a 0–1 scale) to a crop of the camera test image, then compares the best Gaussian filter from a small sweep against NLM (fast_mode=True, a search window, 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 dBOn this crop and seed, NLM is about 3 dB above the best Gaussian filter, and the three 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 far above “for more smoothing”: the result then turns into a blur with extra steps.
References
- R. C. Gonzalez and R. E. Woods, Digital Image Processing, 4th ed., Pearson, 2018, Ch. 5. publisher page
- 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
- 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
- A. C. Kak and M. Slaney, Principles of Computerized Tomographic Imaging, IEEE Press, 1988 (SIAM reprint 2001). free online edition
- 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
- scikit-image developers, “Radon transform,” scikit-image documentation (gallery example). docs
- A. Buades, B. Coll and J.-M. Morel, “A non-local algorithm for image denoising,” IEEE CVPR, vol. 2, pp. 60–65, 2005. DOI
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- J. Adler and O. Öktem, “Learned primal-dual reconstruction,” IEEE Transactions on Medical Imaging, 2018. arXiv
- V. Monga, Y. Li and Y. C. Eldar, “Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing,” arXiv:1912.10557, 2019. arXiv
- 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
- 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
- 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
- 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
- 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