language: en

Efficient Restoration of Multicolor Images with Independent Noise

Yuri Boykov Olga Veksler Ramin Zabih
Cornell University,
USA
Keywords: Bayesian image restoration; Markov random fields; max flow-min cut

Abstract 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.

1 Introduction