Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images

Inside the paper

The problem

Restoring a degraded image requires choosing a plausible original among many images compatible with noisy observations. A local improvement procedure can become trapped in a solution that is not the most probable overall.

The idea

Describe images and their boundaries with a probabilistic model, combine it with a model of degradation, and search for a high-probability restoration using random local updates. Gradually lowering a temperature makes the search increasingly favor better configurations.

How it works

• Define an image model with local interactions between pixel intensities and boundary elements, and combine it with the likelihood of the observed image.
• At each update, sample a new local value from its conditional distribution given the current neighboring values.
• Use a temperature parameter to control the distribution of updates and reduce it gradually as the process runs.
• Read the resulting image as an estimate of the original; boundary elements help the model represent discontinuities between regions.

What it showed

The authors establish convergence results for the sampler and a sufficiently slow cooling schedule under their assumptions. They also show restorations of simple images degraded by noise and blur, including intermediate stages of the search.

Read it for

Read Sections II and VIII for the observation and posterior models, then Sections X and XI for the computational method. Section XIII and its figures show the restorations; the detailed proofs in Section XII can wait.

Written in our own words from the paper itself. A draft the editors have not yet reviewed.