"The problem with a mini-deal is we have a maxi-problem," said John Cornyn, Senator from Texas, recently. Indeed, minimax analysis is all over the news of late. Our response consists of two new papers. The first shows that the popular nonlocal means (NLM) image denoising algorithm is sub-optimal for images with sharp edges from the so-called Horizon class. The second develops an enhanced anisotropic nonlocal means (ANLM) algorithm that is near-optimal for Horizon class images.
A. Maleki, M. Narayan, and R. G. Baraniuk, "Suboptimality of Nonlocal Means for Images with Sharp Edges," preprint, 2011.
Abstract: 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^(-1)log^(1/2)(n), for an n-pixel image. 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 the optimal minimax rate of n^(-4/3).
A. Maleki, M. Narayan, and R. G. Baraniuk, "Anisotropic Nonlocal Means Denoising," preprint, 2011.
Abstract: It has recently been proved that the popular nonlocal means (NLM) denoising algorithm does not optimally denoise images with sharp edges. Its weakness lies in the isotropic nature of the neighborhoods it uses in order to set its smoothing weights. In response, in this paper we introduce several theoretical and practical anisotropic nonlocal means (ANLM) algorithms and prove that they are near minimax optimal for edge-dominated images from the Horizon class. On real-world test images, an ANLM algorithm that adapts to the underlying image gradients outperforms NLM by a significant margin, up to 2dB in mean square error.