Reconstruction of images corrupted by noise is an important problem in Image
Analysis. In the standard Bayesian approach the unknown original image is
assumed to be a realization of a Markov random field on a finite two
dimensional finite region. This image is degraded by some noise, which acts
independently in each site of and has the same distribution on all sites. The
reconstructed image is the maximum a posteriori (MAP) estimator. When the
number of colors is bigger than two the standard a priori measure is the Potts
model, but with this choice reconstruction algorithms need exponential growing
time in the number of pixels. We propose a different a priori measure that
allows to compute the MAP estimator in polinomial time. The algorithm binary
decomposes the intensity of each color and reconstructs each component,
reducing the problem to the computation of the two-color MAP estimator. The
latter is done in polinomial time solving a min-cut max-flow problem in a
binary graph as proposed by Greig, Porteous and Seheult (1989).