The Taub Faculty of Computer Science Events and Talks
Anat Levin (CS & Mathematics, Weizmann Institute of Science)
Tuesday, 13.12.2011, 11:30
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
We first consider the computational aspect and study the relation
between performance gain and sample size requirements in a non
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