Monte Carlo Non-Local Means: Random Sampling for Large-Scale Image Filtering

Stanley H. Chan, Todd E. Zickler, Yue M. LuIEEE TIP 2013 · DOI · OpenReview

Abstract

We propose a randomized version of the non-local means (NLM) algorithm for large-scale image filtering. The new algorithm, called Monte Carlo non-local means (MCNLM), speeds up the classical NLM by computing a small subset of image patch distances, which are randomly selected according to a designed sampling pattern. We analyze the performance of the MCNLM algorithm and show that, for large images or large external image databases, the random outcomes of MCNLM are tightly concentrated around the deterministic full NLM result. In particular, our error probability bounds show that, at any given sampling ratio, the probability for MCNLM to have a large deviation from the original NLM solution decays exponentially as the size of the image or database grows. Numerical experiments show that MCNLM is competitive with other state-of-the-art fast NLM algorithms for single-image denoising. When applied to denoising images using an external database containing ten billion patches, MCNLM returns a randomized solution that is within 0.2 dB of the full NLM solution while reducing the runtime by three orders of magnitude.

Introduction

Image denoising often relies on the Non-Local Means (NLM) algorithm, which works on the intuition that natural images contain many repetitive patterns. To denoise a pixel, NLM identifies similar "patches" elsewhere in the image (internal denoising) or in a massive database (external denoising) and computes a weighted average.

However, the computational complexity is a major bottleneck. Denoising a 10-megapixel image using a full search requires approximately $10^{14}$ operations, making it impractical for real-time applications or massive external databases. The authors address this by introducing a randomized approach that leverages the "blessing of scale."

Methodology

The core of the proposed Monte Carlo Non-Local Means (MCNLM) is a random sampling strategy. Instead of checking every single patch in a database, the algorithm selects a small subset of $k$ patches based on a specific probability distribution.

Conceptual overview of MCNLM. Instead of using all patches, a random subset is sampled to estimate the denoised pixel value.

To ensure the result is unbiased, MCNLM uses importance sampling, where each selected patch weight is scaled by the inverse of its selection probability. Using Bernstein’s Inequality from large deviations theory, the authors prove that the error of this random approximation drops exponentially as the number of available patches $n$ increases. This means that for very large databases, random sampling becomes exceptionally accurate.

The authors also derive optimal non-uniform sampling patterns. By using "partial knowledge"—such as the fact that nearby patches are more likely to be similar—they can focus the random sampling on the most promising candidates, further improving efficiency.

Key Results

MCNLM achieves massive speedups with minimal loss in image quality. In external denoising experiments using a database of 10 billion patches, MCNLM provided a 1000x runtime reduction, turning a week-long task on a cluster into a minutes-long task on a single machine.

PSNR performance of MCNLM as a function of the sampling ratio ξ. The randomized estimate quickly converges to the classical NLM result.

As shown in the figure above, the Peak Signal-to-Noise Ratio (PSNR) of MCNLM converges rapidly to the full NLM solution as the sampling ratio $\xi$ increases. At a 10% sampling ratio, the PSNR is typically within 0.2 dB to 0.7 dB of the computationally expensive full NLM result. Unlike other fast NLM variants like KD-trees, MCNLM requires almost no extra memory and no lengthy pre-processing, making it highly scalable for "Big Data" regimes.

Conclusion

MCNLM demonstrates that random sampling is a powerful tool for large-scale image filtering. While NLM is a foundational algorithm, the authors suggest that this Monte Carlo framework could be extended to more modern denoising methods or other non-local problems in computer vision, such as optical flow, image super-resolution, and non-local regularization in inverse problems.

Summary updated

Abstract

We propose a randomized version of the nonlocal means (NLM) algorithm for large-scale image filtering. The new algorithm, called Monte Carlo nonlocal means (MCNLM), speeds up the classical NLM by computing a small subset of image patch distances, which are randomly selected according to a designed sampling pattern. We make two contributions. First, we analyze the performance of the MCNLM algorithm and show that, for large images or large external image databases, the random outcomes of MCNLM are tightly concentrated around the deterministic full NLM result. In particular, our error probability bounds show that, at any given sampling ratio, the probability for MCNLM to have a large deviation from the original NLM solution decays exponentially as the size of the image or database grows. Second, we derive explicit formulas for optimal sampling patterns that minimize the error probability bound by exploiting partial knowledge of the pairwise similarity weights. Numerical experiments show that MCNLM is competitive with other state-of-the-art fast NLM algorithms for single-image denoising. When applied to denoising images using an external database containing ten billion patches, MCNLM returns a randomized solution that is within 0.2 dB of the full NLM solution while reducing the runtime by three orders of magnitude.
BibTeX
@article{chan2013monte,
  author = {Stanley H. Chan and Todd E. Zickler and Yue M. Lu},
  title = {{Monte Carlo Non-Local Means: Random Sampling for Large-Scale Image Filtering}},
  journal = {IEEE Trans. Image Process.},
  year = {2013},
  doi = {10.1109/tip.2014.2327813},
}
Figure