Suboptimality of nonlocal means for images with sharp edges

Arian Maleki, Manjari Narayan, Richard G. Baraniuk

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


We conduct an asymptotic risk analysis of the nonlocal means image denoising algorithm for the Horizon class of images that are piecewise constant with a sharp edge discontinuity. We prove that the mean square risk of an optimally tuned nonlocal means algorithm decays according to n- 1log1 /2+εn, for an n×n-pixel image with ε>0. This decay rate is an improvement over some of the predecessors of this algorithm, including the linear convolution filter, median filter, and the SUSAN filter, each of which provides a rate of only n- 2/3. It is also within a logarithmic factor from optimally tuned wavelet thresholding. However, it is still substantially lower than the optimal minimax rate of n- 4/3.

Original languageEnglish (US)
Pages (from-to)370-387
Number of pages18
JournalApplied and Computational Harmonic Analysis
Issue number3
StatePublished - Nov 2012


  • Denoising
  • Horizon class
  • Linear filter
  • Minimax risk
  • Nonlocal means
  • SUSAN filter
  • Wavelet thresholding

ASJC Scopus subject areas

  • Applied Mathematics


Dive into the research topics of 'Suboptimality of nonlocal means for images with sharp edges'. Together they form a unique fingerprint.

Cite this