We consider the problem of maximum a posteriori (MAP) restoration of multicolor images where each pixel has been degraded by independent arbitrary noise. We assume that the prior distribution is given by a Markov random field with only pairwise site interactions. Two classes of site interactions are considered: two-valued site interactions, which form a generalized Potts model; and linear site interactions. We give efficient algorithms based on graph cuts for both classes. The MAP estimate for a generalized Potts model can be computed by solving a multiway minimum cut problem on a graph. While this graph problem is computationally intractable, there are fast algorithms for computing provably good approximations. The MAP estimate with linear site interactions can be computed exactly by solving a minimum cut problem on a graph. This can be performed in nearly linear time.
Visit our image gallery to see some image restoration results.