skip to main content
research-article
Free access

Self-similarity-based image denoising

Published: 01 May 2011 Publication History

Abstract

The search for efficient image denoising methods is still a valid challenge at the crossing of functional analysis and statistics. In spite of the sophistication of the recently proposed methods, most algorithms have not yet attained a desirable level of applicability. All show an outstanding performance when the image model corresponds to the algorithm assumptions but fail in general and create artifacts or remove image fine structures. The main focus of this paper is, first, to define a general mathematical and experimental methodology to compare and classify classical image denoising algorithms and, second, to describe the nonlocal means (NL-means) algorithm introduced in 2005 and its more recent extensions. The mathematical analysis is based on the analysis of the "method noise," defined as the difference between a digital image and its denoised version. NL-means, which uses image self-similarities, is proven to be asymptotically optimal under a generic statistical image model. The denoising performance of all considered methods are compared in four ways: mathematical, asymptotic order of magnitude of the method noise under regularity assumptions; perceptual-mathematical, the algorithms artifacts and their explanation as a violation of the image model; perceptual-mathematical, analysis of algorithms when applied to noise samples; quantitative experimental, by tables of L2 distances of the denoised version to the original image.

References

[1]
Adams, A., Gelfand, N., Dolson, J., Levoy, M. Gaussian kd-trees for fast high-dimensional filtering. ACM Trans. Graphics 28, 3 (2009), 1--12.
[2]
Alvarez, L., Lions, P., Morel, J. Image selective smoothing and edge detection by nonlinear diffusion. II. SIAM J. Numer. Anal. 29, 3 (1992), 845--866.
[3]
Arias, P., Caselles, V., Sapiro, G. A variational framework for non-local image inpainting. In Proceedings of the 7th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR '09) (Bonn, Germany, August 24--27, 2009), Springer, Heidelberg.
[4]
Attneave, F. Some informational aspects of visual perception. Psychol. Rev. 61, 3 (1954), 183--193.
[5]
Boulanger, J., Sibarita, J., Kervrann, C., Bouthemy, P. Non-parametric regression for patch-based fluorescence microscopy image sequence denoising. In 5th IEEE International Symposium on Biomedical Imaging: From Nano to Macro, 2008 (Paris, France, May 14--17, 2008), ISBI 2008, 748--751.
[6]
Buades, A., Coll, B., Morel, J. A review of image denoising algorithms, with a new one. Multiscale Model. Simul. 4, 2 (2005), 490--530.
[7]
Buades, A., Coll, B., Morel, J. Neighborhood filters and PDE's. Numer. Math. 105, 1 (2006), 1--34.
[8]
Buades, A., Coll, B., Morel, J. The staircasing effect in neighborhood filters and its solution. IEEE Trans. I.P. 15, 6 (2006), 1499--1505.
[9]
Buades, A., Coll, B., Morel, J. Nonlocal image and movie denoising. Int. J. Comput. Vision 76, 2 (2008), 123--139.
[10]
Buades, A., Coll, B., Morel, J., Sbert, C. Self-similarity driven color demosaicking. IEEE Trans. I.P. 18, 6 (2009), 1192--1202.
[11]
Chatterjee, P., Milanfar, P. Image denoising using locally learned dictionaries. Comput. Imag. VII, SPIE7246 (2009), 72460V--72460V.
[12]
Coifman, R., Donoho, D. Translation-invariant de-noising. In Wavelets and Statistics. Lecture Notes in Statistics (Springer Verlag, New York, 1995), 125--150.
[13]
Coupé, P., Yger, P., Barillot, C. Fast non local means denoising for 3D MR images. In Medical Image Computing and Computer-Assisted Intervention--MICCAI 2006. Lecture Notes in Computer Science (Springer, New York, 2006), 33--40.
[14]
Dabov, K., Foi, A., Katkovnik, V., Egiazarian, K. Image denoising by sparse 3-D transform-domain collaborative filtering. IEEE Trans. I.P. 16, 8 (2007), 2080--2095.
[15]
Darbon, J., Cunha, A., Chan, T., Osher, S., Jensen, G. Fast nonlocal filtering applied to electron cryomicroscopy. In 5th IEEE International Symposium on Biomedical Imaging: From Nano to Macro (Paris, France, May 14--17, 2008), 1331--1334.
[16]
Delon, J., Desolneux, A. Stabilization of flicker-like effects in image sequences through local contrast correction. SIAM J. Imag. Sci. 3, 4 (2010), 703--734.
[17]
Donoho, D. De-noising by soft-thresholding. IEEE Trans. Inf. Theory 41 (1995), 613--627.
[18]
Ebrahimi, M., Vrscay, E. Solving the inverse problem of image zooming using "Self-Examples". In Volume 4633 of Lecture Notes in Computer Science (2007), 117.
[19]
Efros, A., Leung, T. Texture synthesis by non parametric sampling. In Volume 2 of Proceedings of the 7th IEEE International Conference on Computer Vision (Corfu, Greece, 1999), 1033--1038.
[20]
Elad, M., Datsenko, D. Example-based regularization deployed to superresolution reconstruction of a single image. Comput. J. 50, 4 (Apr. 2007), 1--16.
[21]
Elmoataz, A., Lezoray, O., Bougleux, S., Ta, V. Unifying local and nonlocal processing with partial difference operators on weighted graphs. In International Workshop on Local and Non-Local Approximation in Image Processing (Lausanne, Switzerland, August 23--24, 2008).
[22]
Gilboa, G., Osher, S. Nonlocal linear image regularization and supervised segmentation. Multiscale Model. Simul. 6, 2 (2008), 595--630.
[23]
Jung, M., Vese, L. Nonlocal variational image deblurring models in the presence of Gaussian or impulse noise. Scale Space and Variational Methods in Computer Vision (2009), 401--412.
[24]
Kervrann, C., Boulanger, J., Coupe, P. Bayesian non-local means filter image, redundancy and adaptive dictionaries for noise removal. In Volume 4485 of Lecture Notes in Computer Science (Ischia, Italy, May 30--June 2, 2007), 520.
[25]
Kindermann, S., Osher, S., Jones, P. Deblurring and denoising of images by nonlocal functionals. SIAM MMS 4, 4 (2006), 1091--1115.
[26]
Lezoray, O., Ta, V., Elmoataz, A. Nonlocal graph regularization for image colorization. In International Conference on Pattern Recognition (Tampa, FL, December 8--11, 2008).
[27]
Lindenbaum, M., Fischer, M., Bruckstein, A. On Gabor's contribution to image enhancement. Pattern Recognit. 27, 1 (1994), 1--8.
[28]
Lou, Y., Zhang, X., Osher, S., Bertozzi, A. Image recovery via nonlocal operators. J. Sci. Comput. 42, 2 (2010), 185--197.
[29]
Mahmoudi, M., Sapiro, G. Fast image and video denoising via nonlocal means of similar neighborhoods. IEEE Signal Process. Lett. 12, 12 (2005), 839--842.
[30]
Mairal, J., Elad, M., Sapiro, G. Sparse representation for color image restoration. IEEE Trans. I.P. 17, 1 (2007), 53--69.
[31]
Manjón, J., Carbonell-Caballero, J., Lull, J., García-Martí, G., Martí-Bonmatí, L., Robles, M. MRI denoising using Non-Local Means. Med. Image Anal. 12, 4 (2008), 514--523.
[32]
Mignotte, M. A non-local regularization strategy for image deconvolution. Pattern Recognit. Lett. 29, 16 (2008), 2206--2212.
[33]
Orchard, J., Ebrahimi, M., Wong, A. Efficient non-local-means denoising using the SVD. In Proceedings of IEEE International Conference on Image Processing (San Diego, CA, October 12--15, 2008).
[34]
Ordentlich, E., Seroussi, G., Verdu, M.W.S., Weissman, T. A discrete universal denoiser and its application to binary images. In Volume 1 of Proceedings of IEEE International Conference on Image Processing (Barcelona, Spain, 2003), 117--120.
[35]
Perona, P., Malik, J. Scale-space and edge detection using anisotropic diffusion. IEEE Trans. PAMI 12, 7 (1990), 629--639.
[36]
Protter, M., Elad, M. Image sequence denoising via sparse and redundant representations. IEEE Trans. Image Process. 18, 1 (2009), 27--35.
[37]
Protter, M., Elad, M., Takeda, H., Milanfar, P. Generalizing the non-local-means to super-resolution reconstruction. IEEE Trans. Image Process. 18, 1 (January 2009), 36--51.
[38]
Roussas, G. Nonparametric regression estimation under mixing conditions. Stochastic Process. Appl. 36 (1990), 107--116.
[39]
Rudin, L., Osher, S., Fatemi, E. Nonlinear total variation based noise removal algorithms. Physica D 60 (1992), 259--268.
[40]
Smith, S., Brady, J. SUSAN : A new approach to low level image processing. Int. J. Comput. Vision 23, 1 (1997), 45--78.
[41]
Thacker, N., Manjon, J., Bromiley, P. A statistical interpretation of non-local means. In 5th International Conference on Visual Information Engineering (Xian, China, 2008), 250--255.
[42]
Tomasi, C., Manduchi, R. Bilateral filtering for gray and color images. In International Conference on Computer Vision (Bombay, India, 1998), 839--846.
[43]
Wang, J., Guo, Y., Ying, Y., Liu, Y., Peng, Q. Fast non-local algorithm for image denoising. In IEEE International Conference on Image Processing (Atlanta, GA, October 8--11, 2006), 1429--1432.
[44]
Wong, A., Orchard, J. A nonlocal-means approach to exemplar-based inpainting. In IEEE International Conference on Image Processing, 2600--2603, 2008.
[45]
Xu, H., Xu, J., Wu, F. On the biased estimation of Nonlocal Means filter. In IEEE International Conference on Multimedia and Expo (San Diego, CA, October 12--15, 2008), 1149--1152.
[46]
Yaroslavsky, L.P. Digital Picture Processing. Springer, New York, 1985.
[47]
Yoshizawa, S., Belyaev, A., Seidel, H. Smoothing by example: Mesh denoising by averaging with similarity-based weights. In IEEE International Conference on Shape Modeling and Applications (Matsushima, Japan, June 14--16, 2006), 9--9.
[48]
Zhang, L., Dong, W., Zhang, D., Shi, G. Two-stage image denoising by principal component analysis with local pixel grouping. Pattern Recognit. 43, 4 (2010), 1531--1549.

Cited By

View all
  • (2024)Linear diffusion noise boosted deep image prior for unsupervised sparse-view CT reconstructionPhysics in Medicine & Biology10.1088/1361-6560/ad69f769:16(165029)Online publication date: 9-Aug-2024
  • (2024)An objective quality indicator for evaluating filtering of microscopic video in CASA systemBiomedical Signal Processing and Control10.1016/j.bspc.2023.10560488(105604)Online publication date: Feb-2024
  • (2022)Disentangling Noise Patterns From Seismic Images: Noise Reduction and Style TransferIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2022.321911760(1-14)Online publication date: 2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image Communications of the ACM
Communications of the ACM  Volume 54, Issue 5
May 2011
134 pages
ISSN:0001-0782
EISSN:1557-7317
DOI:10.1145/1941487
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2011
Published in CACM Volume 54, Issue 5

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article
  • Popular
  • Refereed

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)391
  • Downloads (Last 6 weeks)64
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Linear diffusion noise boosted deep image prior for unsupervised sparse-view CT reconstructionPhysics in Medicine & Biology10.1088/1361-6560/ad69f769:16(165029)Online publication date: 9-Aug-2024
  • (2024)An objective quality indicator for evaluating filtering of microscopic video in CASA systemBiomedical Signal Processing and Control10.1016/j.bspc.2023.10560488(105604)Online publication date: Feb-2024
  • (2022)Disentangling Noise Patterns From Seismic Images: Noise Reduction and Style TransferIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2022.321911760(1-14)Online publication date: 2022
  • (2022)Self-similarity verification of special images such as microscopy2022 IEEE 21st International Conference on Ubiquitous Computing and Communications (IUCC/CIT/DSCI/SmartCNS)10.1109/IUCC-CIT-DSCI-SmartCNS57392.2022.00048(254-260)Online publication date: Dec-2022
  • (2022)Spectral-spatial 3D dynamic trimmed median filter for removal of impulse noise in remotely sensed imagesMultimedia Tools and Applications10.1007/s11042-022-13965-y82:11(15945-15982)Online publication date: 26-Sep-2022
  • (2021)A novel decision-based adaptive feedback median filter for high density impulse noise suppressionMultimedia Tools and Applications10.1007/s11042-020-09473-680:1(299-321)Online publication date: 1-Jan-2021
  • (2021)Bilevel Parameter Learning for Nonlocal Image Denoising ModelsJournal of Mathematical Imaging and Vision10.1007/s10851-021-01026-263:6(753-775)Online publication date: 1-Jul-2021
  • (2020)Enhancement of Noisy and Compressed Videos by Optical Flow and Non-Local DenoisingIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2019.291187730:7(1960-1974)Online publication date: 1-Jul-2020
  • (2019)A Simple and Robust Deep Convolutional Approach to Blind Image Denoising2019 IEEE/CVF International Conference on Computer Vision Workshop (ICCVW)10.1109/ICCVW.2019.00488(3943-3951)Online publication date: Oct-2019
  • (2019)Multiple-correlation similarity for block-matching based fast CT to ultrasound registration in liver interventionsMedical Image Analysis10.1016/j.media.2019.02.003Online publication date: Feb-2019
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Digital Edition

View this article in digital edition.

Digital Edition

Magazine Site

View this article on the magazine site (external)

Magazine Site

Login options

Full Access

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media