The Taub Faculty of Computer Science Events and Talks

Restoration tasks, such as image denoising, are ill posed problems, often solved with image priors. As image priors are only approximate, this yields suboptimal restoration results. Given the numerous works on image priors and image denoising, it is thus important to understand the inherent limits posed by natural image statistics, and what potential gains we may expect from additional years of research efforts. Recent studies avoided image priors with a non-parametric approach, but were restricted to small patches, still leaving unclear how results improve for larger patches.

In this paper we aim to understand the ``patch complexity" of natural image statistics and the potential gain from an increase in patch size.

We first consider the computational aspect and study the relation between performance gain and sample size requirements in a non parametric approach. In the second part we put computational restrictions aside, and study the inherent statistical aspect. We show that scale invariance of natural images yields both a strictly positive lower bound on denoising performance and a power law convergence to it as a function of patch size. Extrapolating our finite support results gives a ballpark estimate of the best achievable denoising. We also suggest directions for potential improvements of current algorithms.

Joint work with Boaz Nadler, Fredo Durand and Bill Freeman