### Efficient Restoration of Multicolor Images with Independent Noise

*Technical Report*, 1998 (ncstrl.cornell/TR98-1712)

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

Visit our image gallery to see
some image restoration results.

##### WHOLE PAPER: pdf file (606Kb)