Patch Complexity, Finite Pixel Correlations and Optimal Denoising

By Anat Levin, Boaz Nadler, Frédo Durand, William T. Freeman. 2012

147 citations recorded by the source corpus.

Image restoration tasks are ill-posed problems, typically solved with priors. Since the optimal prior is the exact unknown density of natural images, actual priors are only approximate and typically restricted to small patches. This raises several questions: How much may we hope to improve current restoration results with future sophisticated algorithms? And more fundamentally, even with perfect knowledge of natural image statistics, what is the inherent ambiguity of the problem? In addition, since most current methods are limited to finite support patches or kernels, what is the relation between the patch complexity of natural images, patch size, and restoration errors? Focusing on image denoising, we make several contributions. First, in light of computational constraints, we study the relation between denoising gain and sample size requirements in a non parametric approach. We present a law of diminishing return, namely that with increasing patch size, rare patches not only require a much larger dataset, but also gain little from it. This result suggests novel adaptive variable-sized patch schemes for denoising. Second, we study absolute denoising limits, regardless of the algorithm used, and the converge rate to them as a function of patch size. Scale invariance of natural images plays a key role here and implies both a strictly positive lower bound on denoising and a power law convergence. Extrapolating this parametric law gives a ballpark estimate of the best achievable denoising, suggesting that some improvement, although modest, is still possible.

Subfields: Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

Citations in the corpus

The Perception-Distortion Tradeoff (2017, background): “Several past works attempted to answer the question: What is the minimal attainable distortion Dmin in various restoration tasks? [49], [50], [51], [52], [53].”
Beyond a Gaussian Denoiser: Residual Learning of Deep CNN for Image Denoising (2016, methodology): “According to [34], [38], few methods can outperform BM3D by more than 0.”
Weighted Nuclear Norm Minimization with Application to Image Denoising (2014, unknown): “3dB in average [18, 17].”
Weighted Nuclear Norm Minimization and Its Applications to Low Level Vision (2016, methodology): “Such an improvement is notable since few methods can surpass BM3D more than 0.3dB on average (Levin et al, 2012; Levin and Nadler, 2011).”
Residual Dense Network for Image Restoration (2018, unknown): “7 dB) over BM3D in [73].”
The Little Engine That Could: Regularization by Denoising (RED) (2016, background): “Indeed, these documented results have led researchers to the educated guess that these methods are getting very close to the optimally possible denoising performance [21, 22, 23].”
Plug-and-Play ADMM for Image Restoration: Fixed-Point Convergence and Applications (2016, background): “[33], [34], who showe d that non-local means [35] approaches the MMSE estimate as the number of patches grows to infinity.”
Image denoising with multi-layer perceptrons, part 2: training trade-offs and analysis of their mechanisms (2012, background): “In addition, the MLPs outperform one type of theoretical bound in image denoising (Chatterjee and Milanfar, 2010) and come a long way toward closing the gap to a second type of theoretical bound (Levin et al., 2012).”