  Almost all existing methods for image restoration are based on optimizing the
mean squared error (MSE), even though it is known that the best estimate in
terms of MSE may yield a highly atypical image due to the fact that there are
many plausible restorations for a given noisy image. In this paper, we show how
to combine explicit priors on patches of natural images in order to sample from
the posterior probability of a full image given a degraded image. We prove that
our algorithm generates correct samples from the distribution $p(x|y) \propto
\exp(-E(x|y))$ where $E(x|y)$ is the cost function minimized in previous
patch-based approaches that compute a single restoration. Unlike previous
approaches that computed a single restoration using MAP or MMSE, our method
makes explicit the uncertainty in the restored images and guarantees that all
patches in the restored images will be typical given the patch prior. Unlike
previous approaches that used implicit priors on fixed-size images, our
approach can be used with images of any size. Our experimental results show
that posterior sampling using patch priors yields images of high perceptual
quality and high PSNR on a range of challenging image restoration problems.
