Fast Approximate Maximum A-posteriori Restoration of Multicolor Images

We propose a new algorithm for the approximation of the maximum a posteriori (MAP) restoration of noisy images. The image restoration problem is considered in a Bayesian setting. We assume as prior distribution multicolour Markov random fields on a graph whose main restriction is the presence of only pairwise site interactions. The noise is modelled as a Bernoulli field. Computing the mode of the posterior distribution is NP complete, i.e. can (very likely) be done only in a time exponential in the number of sites of the underlying graph. Our algorithm runs in polynomial time and is based on the coding of the colours. It produces an image with the following property: either a pixel is coloured with one of the possible colours or it is left blank. In the first case we prove that this is the colour of the site in the exact MAP restoration. The quality of the approximation is then measured by the number of sites being left blank. We assess the performance of the new algorithm by numerical experiments on the simple three-colour Potts model. More rigorously, we present a probabilistic analysis of the algorithm. The results indicate that the approximation is quite often sufficiently good for the interpretation of the image.