Unsupervised Linear and Iterative Combinations of Patches for Image Denoising

Sébastien Herbreteau, Charles KervrannarXiv 2022 · arXiv · OpenReview

Abstract

We introduce a parametric view of non-local two-step denoisers, for which BM3D is a major representative, where quadratic risk minimization is leveraged for unsupervised optimization. Within this paradigm, we propose to extend the underlying mathematical parametric formulation by iteration. This generalization can be expected to further improve the denoising performance, somehow curbed by the impracticality of repeating the second stage for all two-step denoisers. The resulting formulation involves estimating an even larger amount of parameters in a unsupervised manner which is all the more challenging. Focusing on the parameterized form of NL-Ridge, the simplest but also most efficient non-local two-step denoiser, we propose a progressive scheme to approximate the parameters minimizing the risk. In the end, the denoised images are made up of iterative linear combinations of patches. Experiments on artificially noisy images but also on real-world noisy images demonstrate that our method compares favorably with the very best unsupervised denoisers such as WNNM, outperforming the recent deep-learning-based approaches, while being much faster.

Introduction

Image denoising is a fundamental inverse problem in imaging: recovering a clean signal $x$ from a noisy observation $y = x + w$. In the last decade, supervised deep learning (DL) has dominated this field. However, these models are often "data-hungry," requiring massive datasets of clean/noisy pairs. If training data is poor or doesn't match real-world noise, these models fail. This has led to the development of single-image (zero-shot) methods that learn to denoise using only the noisy image itself.

The challenge is that current single-image DL methods are often computationally expensive and sometimes less effective than traditional non-local methods like BM3D or WNNM. Furthermore, traditional methods usually hit a performance ceiling; iterative application often degrades results. This paper introduces LIChI (Linear and Iterative Combinations of patcHes for Image denoising), a method designed to break this ceiling.

The LIChI Framework

The core of LIChI is the Non-Local (NL) principle: images contain many repetitive patterns. By grouping similar patches together, we can use this redundancy to cancel out noise.

The LIChI denoising pipeline: from group extraction of noisy patches to iterative linear combinations and final aggregation.

Technical Innovations

  1. Linear Combinations (NL-Ridge): Instead of complex low-rank approximations or transform-domain thresholding, LIChI computes a weighted linear combination of similar patches. This is essentially a multivariate ridge regression.
  2. The Chaining Rule: Traditional two-step methods fail when iterated because statistical noise assumptions break down. The authors propose a progressive optimization scheme that gradually "closes the gap" to the clean image over $M$ iterations, preventing reconstruction breakdown.
  3. Internal Adaptation with Pilots: To estimate the best weights, the algorithm uses a "pilot" (an initial guess of the clean image). These pilots are built using SURE (Stein’s Unbiased Risk Estimate) or Noisier2Noise techniques, allowing the model to learn from the noisy image itself.

Experimental Evaluation

The authors evaluated LIChI on synthetic benchmarks (Set12, BSD68, Urban100) and real-world data via the Darmstadt Noise Dataset (DND).

Key Results

LIChI demonstrates a superior balance between denoising quality and computational efficiency. As shown in the performance analysis, LIChI outperforms recent self-supervised neural networks like S2S and RDIP while remaining significantly faster than traditional high-performance methods like WNNM.

Comparison of execution time vs. average PSNR. LIChI (ours) achieves a competitive balance between speed and performance compared to traditional and neural network-based methods.
  • Performance: LIChI is on par with WNNM, the long-standing gold standard for single-image denoising, and outperforms recent self-supervised neural networks.
  • Speed: On a CPU, LIChI is approximately 8 times faster than WNNM. GPU implementations offer even greater speedups.
  • Real-World Success: On the DND benchmark, LIChI achieved the highest PSNR among all single-image methods, even beating some dataset-based supervised models.

Discussion and Conclusion

The "unreasonable effectiveness" of LIChI stems from simple linear combinations and the variance-reducing power of patch aggregation, which acts as an ensemble method (similar to "bagging" in machine learning). Unlike "black-box" neural networks, every step of LIChI is a transparent statistical operation. While WNNM maintains a slight edge at very high noise levels, LIChI's speed and performance on real-world noise make it a highly practical solution for unsupervised denoising.

Summary updated

Abstract

We introduce a parametric view of non-local two-step denoisers, for which BM3D is a major representative, where quadratic risk minimization is leveraged for unsupervised optimization. Within this paradigm, we propose to extend the underlying mathematical parametric formulation by iteration. This generalization can be expected to further improve the denoising performance, somehow curbed by the impracticality of repeating the second stage for all two-step denoisers. The resulting formulation involves estimating an even larger amount of parameters in a unsupervised manner which is all the more challenging. Focusing on the parameterized form of NL-Ridge, the simplest but also most efficient non-local two-step denoiser, we propose a progressive scheme to approximate the parameters minimizing the risk. In the end, the denoised images are made up of iterative linear combinations of patches. Experiments on artificially noisy images but also on real-world noisy images demonstrate that our method compares favorably with the very best unsupervised denoisers such as WNNM, outperforming the recent deep-learning-based approaches, while being much faster.
BibTeX
@misc{herbreteau2022unsupervised,
  author = {Sébastien Herbreteau and Charles Kervrann},
  title = {{Unsupervised Linear and Iterative Combinations of Patches for Image Denoising}},
  year = {2022},
  eprint = {2212.00422},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2212.00422},
}
Figure