In this paper 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 multicolor 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. Our algorithm runs in polynomial time and is based on the coding of the colors. It produces an image with the following property: either a pixel is colored with one of the possible colors or it is left blank. In the first case we prove that this is the color 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-color Potts model. More rigorously, we present a probabilistic analysis of the algorithm. The results indicate that the approximation is quite often good enough for the interpretation of the image.