Skip to main content
SpringerLink
Log in

Non-local Methods with Shape-Adaptive Patches (NLM-SAP)

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

We propose in this paper an extension of the Non-Local Means (NL-Means) denoising algorithm. The idea is to replace the usual square patches used to compare pixel neighborhoods with various shapes that can take advantage of the local geometry of the image. We provide a fast algorithm to compute the NL-Means with arbitrary shapes thanks to the Fast Fourier Transform. We then consider local combinations of the estimators associated with various shapes by using Stein’s Unbiased Risk Estimate (SURE). Experimental results show that this algorithm improve the standard NL-Means performance and is close to state-of-the-art methods, both in terms of visual quality and numerical results. Moreover, common visual artifacts usually observed by denoising with NL-Means are reduced or suppressed thanks to our approach.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aharon, M., Elad, M., Bruckstein, A.: K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Trans. Signal Process. 54(11), 4311–4322 (2006)

    Article  Google Scholar 

  2. Awate, S.P., Whitaker, R.T.: Unsupervised information-theoretic, adaptive image filtering for image restoration. IEEE Trans. Pattern Anal. Mach. Intell. 28(3), 364–376 (2006)

    Article  Google Scholar 

  3. Bilcu, R.C., Vehvilainen, M.: Combined non-local averaging and intersection of confident intervals for image de-noising. In: ICIP, pp. 1736–1739 (2008)

    Google Scholar 

  4. Blu, T., Luisier, F.: The SURE-LET approach to image denoising. IEEE Trans. Image Process. 16(11), 2778–2786 (2007)

    Article  MathSciNet  Google Scholar 

  5. Boulanger, J., Kervrann, C., Bouthemy, P., Elbau, P., Sibarita, J.B., Salamero, J.: Patch-based nonlocal functional for denoising fluorescence microscopy image sequences. IEEE Trans. Med. Imaging 29(2), 442–454 (2010)

    Article  Google Scholar 

  6. Brox, T., Kleinschmidt, O., Cremers, D.: Efficient nonlocal means for denoising of textural patterns. IEEE Trans. Image Process. 17(7), 1083–1092 (2008)

    Article  MathSciNet  Google Scholar 

  7. Buades, A., Coll, B., Morel, J.M.: A review of image denoising algorithms with a new one. Multiscale Model. Simul. 4(2), 490–530 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  8. Buades, A., Coll, B., Morel, J.M.: Non-local means denoising. Image Processing on Line (2009). http://www.ipol.im/pub/algo/bcm_non_local_means_denoising/

  9. Condat, L.: A simple trick to speed up and improve the non-local means. Submitted (2010). hal-00512801

  10. Crow, F.C.: Summed-area tables for texture mapping. In: SIGGRAPH, pp. 207–212 (1984)

    Google Scholar 

  11. Dabov, K., Foi, A., Katkovnik, V., Egiazarian, K.O.: Image denoising by sparse 3-D transform-domain collaborative filtering. IEEE Trans. Image Process. 16(8), 2080–2095 (2007)

    Article  MathSciNet  Google Scholar 

  12. Dabov, K., Foi, A., Katkovnik, V., Egiazarian, K.O.: BM3D image denoising with shape-adaptive principal component analysis. In: Proc. Workshop on Signal Processing with Adaptive Sparse Structured Representations (SPARS’09) (2009)

    Google Scholar 

  13. Dalalyan, A.S., Tsybakov, A.B.: Aggregation by exponential weighting, sharp oracle inequalities and sparsity. In: COLT, pp. 97–111 (2007)

    Google Scholar 

  14. Dalalyan, A.S., Tsybakov, A.B.: Aggregation by exponential weighting sharp pac-bayesian bounds and sparsity. Mach. Learn. 72(1–2), 39–61 (2008)

    Article  Google Scholar 

  15. Darbon, J., Cunha, A., Chan, T.F., Osher, S., Jensen, G.J.: Fast nonlocal filtering applied to electron cryomicroscopy. In: ISBI, pp. 1331–1334 (2008)

    Google Scholar 

  16. Deledalle, C.A., Denis, L., Tupin, F.: Iterative weighted maximum likelihood denoising with probabilistic patch-based weights. IEEE Trans. Image Process. 18(12), 2661–2672 (2009)

    Article  MathSciNet  Google Scholar 

  17. Donoho, D.L., Johnstone, I.M.: Adapting to unknown smoothness via wavelet shrinkage. J. Am. Stat. Assoc. 90(432), 1200–1224 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  18. Doré, V., Cheriet, M.: Robust NL-means filter with optimal pixel-wise smoothing parameter for statistical image denoising. IEEE Trans. Signal Process. 57, 1703–1716 (2009)

    Article  Google Scholar 

  19. Duval, V., Aujol, J.F., Gousseau, Y.: On the parameter choice for the non-local means. Tech. rep. hal-00468856, HAL (2010)

  20. Foi, A., Katkovnik, V., Egiazarian, K.O.: Pointwise shape-adaptive DCT for high-quality denoising and deblocking of grayscale and color images. IEEE Trans. Image Process. 16(5), 1395–1411 (2007)

    Article  MathSciNet  Google Scholar 

  21. Gilboa, G., Osher, S.: Nonlocal operators with applications to image processing. Multiscale Model. Simul. 7(3), 1005–1028 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  22. Goldenshluger, A., Nemirovski, A.S.: On spatially adaptive estimation of nonparametric regression. Math. Methods Stat. 6(2), 135–170 (1997)

    MathSciNet  MATH  Google Scholar 

  23. Goossens, B., Luong, H.Q., Pizurica, A., Philips, W.: An improved non-local denoising algorithm. In: LNLA, pp. 143–156 (2008)

    Google Scholar 

  24. Hudson, H.M.: A natural identity for exponential families with applications in multiparameter estimation. Ann. Stat. 6(3), 473–484 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  25. Katkovnik, V., Foi, A., Egiazarian, K.O., Astola, J.T.: Directional varying scale approximations for anisotropic signal processing. In: EUSIPCO, pp. 101–104 (2004)

    Google Scholar 

  26. Kervrann, C., Boulanger, J.: Optimal spatial adaptation for patch-based image denoising. IEEE Trans. Image Process. 15(10), 2866–2878 (2006)

    Article  Google Scholar 

  27. Kervrann, C., Boulanger, J., Coupé, P.: Bayesian non-local means filter, image redundancy and adaptive dictionaries for noise removal. In: SSVM, vol. 4485, pp. 520–532 (2007)

    Google Scholar 

  28. Le Pennec, E., Mallat, S.: Sparse geometric image representations with bandelets. IEEE Trans. Image Process. 14(4), 423–438 (2005)

    Article  MathSciNet  Google Scholar 

  29. Lee, J.S.: Digital image smoothing and the sigma filter. Comput. Vis. Graph. Image Process. 24(2), 255–269 (1983)

    Article  Google Scholar 

  30. Lepski, O.V., Mammen, E., Spokoiny, V.G.: Optimal spatial adaptation to inhomogeneous smoothness: an approach based on kernel estimates with variable bandwidth selectors. Ann. Stat. 25(3), 929–947 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  31. Leung, G., Barron, A.R.: Information theory and mixing least-squares regressions. IEEE Trans. Inf. Theory 52(8), 3396–3410 (2006)

    Article  MathSciNet  Google Scholar 

  32. Li, K.C.: From Stein’s unbiased risk estimates to the method of generalized cross validation. Ann. Stat. 13(4), 1352–1377 (1985)

    Article  MATH  Google Scholar 

  33. Louchet, C., Moisan, L.: Total variation as a local filter. To appear (2010). doi:10.1109/ICCV.2009.5459452

  34. Mahmoudi, M., Sapiro, G.: Fast image and video denoising via nonlocal means of similar neighborhoods. IEEE Signal Process. Lett. 12, 839–842 (2005)

    Article  Google Scholar 

  35. Mairal, J., Bach, F., Ponce, J., Sapiro, G., Zisserman, A.: Non-local sparse models for image restoration. In: ICCV (2009)

    Google Scholar 

  36. Mairal, J., Sapiro, G., Elad, M.: Learning multiscale sparse representations for image and video restoration. Multiscale Model. Simul. 7(1), 214–241 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  37. Mallows, C.L.: Some comments on c_p. Technometrics 15(4), 661–675 (1973)

    Article  MATH  Google Scholar 

  38. Nemirovski, A.S.: Topics in Non-parametric Statistics, Lecture Notes in Math., vol. 1738. Springer, Berlin (2000)

    Google Scholar 

  39. Nikolova, M.: Local strong homogeneity of a regularized estimator. SIAM J. Appl. Math. 61(2), 633–658 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  40. Pang, C., Au, O., Dai, J., Yang, W., Zou, F.: A fast nl-means method in image denoising based on the similarity of spatially sampled pixels. In: MMSP (2009)

    Google Scholar 

  41. Perona, P., Malik, J.: Scale space and edge detection using anisotropic diffusion. IEEE Trans. Pattern Anal. Mach. Intell. 12, 629–639 (1990)

    Article  Google Scholar 

  42. Polzehl, J., Spokoiny, V.G.: Adaptive weights smoothing with applications to image restoration. J. R. Stat. Soc., Ser. B, Stat. Methodol. 62(2), 335–354 (2000)

    Article  MathSciNet  Google Scholar 

  43. Polzehl, J., Spokoiny, V.G.: Propagation-separation approach for local likelihood estimation. Probab. Theory Relat. Fields 135(3), 335–362 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  44. Portilla, J., Strela, V., Wainwright, M., Simoncelli, E.P.: Image denoising using scale mixtures of gaussians in the wavelet domain. IEEE Trans. Image Process. 12(11), 1338–1351 (2003)

    Article  MathSciNet  Google Scholar 

  45. Ramani, S., Blu, T., Unser, M.: Monte-Carlo SURE: a black-box optimization of regularization parameters for general denoising algorithms. IEEE Trans. Image Process. 17(9), 1540–1554 (2008)

    Article  MathSciNet  Google Scholar 

  46. Raphan, M., Simoncelli, E.P.: Learning to be Bayesian without supervision. In: NIPS, vol. 19, p. 1145 (2007)

    Google Scholar 

  47. Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60(1–4), 259–268 (1992)

    Article  MATH  Google Scholar 

  48. Salmon, J.: On two parameters for denoising with non-local means. IEEE Signal Process. Lett. 17, 269–272 (2010)

    Article  Google Scholar 

  49. Salmon, J., Le Pennec, E.: NL-Means and aggregation procedures. In: ICIP, pp. 2977–2980 (2009)

    Google Scholar 

  50. Salmon, J., Strozecki, Y.: From patches to pixels in non-local methods: weighted-average reprojection. In: ICIP (2010)

    Google Scholar 

  51. Solo, V.: A sure-fired way to choose smoothing parameters in ill-conditioned inverse problems. In: ICIP, vol. 3, pp. 89–92 (1996)

    Google Scholar 

  52. Starck, J.L., Candès, E.J., Donoho, D.L.: The curvelet transform for image denoising. IEEE Trans. Image Process. 11(6), 670–684 (2002)

    Article  MathSciNet  Google Scholar 

  53. Stein, C.M.: Estimation of the mean of a multivariate distribution. In: Proc. Prague Symp. Asymptotic Statist. (1973)

    Google Scholar 

  54. Stein, C.M.: Estimation of the mean of a multivariate normal distribution. Ann. Stat. 9(6), 1135–1151 (1981)

    Article  MATH  Google Scholar 

  55. Tomasi, C., Manduchi, R.: Bilateral filtering for gray and color images. In: ICCV, pp. 839–846 (1998)

    Google Scholar 

  56. Tsybakov, A.B.: Optimal rates of aggregation. In: COLT, pp. 303–313 (2003)

    Google Scholar 

  57. Van De Ville, D., Kocher, M.: SURE-based non-local means. IEEE Signal Process. Lett. 16, 973–976 (2009)

    Article  Google Scholar 

  58. Viola, P., Jones, M.: Rapid object detection using a boosted cascade of simple features. In: CVPR, vol. 1, pp. 511–518 (2001)

    Google Scholar 

  59. Wang, J., Guo, Y.W., Ying, Y., Liu, Y.L., Peng, Q.S.: Fast non-local algorithm for image denoising. In: ICIP, pp. 1429–1432 (2006)

    Google Scholar 

  60. Wang, Z., Bovik, A.C., Sheikh, H.R., Simoncelli, E.P.: Image quality assessment: from error visibility to structural similarity. IEEE Trans. Signal Process. 13(4), 600–612 (2004)

    Google Scholar 

  61. Wasserman, L.: All of Nonparametric Statistics. Springer Texts in Statistics. Springer, Berlin (2007)

    Google Scholar 

  62. Yaroslavsky, L.P.: Digital Picture Processing, Springer Series in Information Sciences, vol. 9. Springer, Berlin (1985)

    Book  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut Telecom, Telecom ParisTech, CNRS LTCI, 46, rue Barrault, 75634, Paris cedex 13, France

    Charles-Alban Deledalle & Vincent Duval

  2. Laboratoire de Probabilité et Modèles Aléatoires, CNRS-UMR 7599, Université Paris 7–Diderot, 175 rue du Chevaleret, 75013, Paris, France

    Joseph Salmon

Authors
  1. Charles-Alban Deledalle
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Vincent Duval
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Joseph Salmon
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vincent Duval.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Deledalle, CA., Duval, V. & Salmon, J. Non-local Methods with Shape-Adaptive Patches (NLM-SAP). J Math Imaging Vis 43, 103–120 (2012). https://doi.org/10.1007/s10851-011-0294-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-011-0294-y

Keywords

Search

Navigation