The USC Andrew and Erna Viterbi School of Engineering USC Signal and Image Processing Institute USC Ming Hsieh Department of Electrical Engineering University of Southern California

Technical Report USC-SIPI-128

“Graduated Nonconvexity Algorithm for Image Estimation Using Compound Gauss Markov Field Models”

by Tal Simchony, Rama Chellappa, and Zeev Lichtenstein

This paper is concerned with developing a deterministic algorithm for obtaining the global maximum a posteriori probability (MAP) estimate from an image corrupted by additive Gaussian noise. The MAP algorithm requires the probability density function of the original undegraded image and the probability density function of the corrupting noise. By assuming that the original image is represented by a compound model consisting of a 2-D noncausal Gaussian Markov random field (GMRK) to represent the homogeneous regions and a line process model to represent the discontinuities, the MAP algorithm is written in terms of the compound GMRF model parameters. The solution to the MAP equations is then realized by a deterministic relaxation algorithm. The deterministic algorithm which is an extension of the graduated non convexity (GNC) algorithm, is able to find the global MAP estimate. As a by product, the line process configuration determined by the MAP estimate produces an accurate edge map without any additional cost. Unlike the simulated annealing method, the deterministic algorithm converges in a small number.

Due to the modeling assumption the restoration algorithm depends on the GMRF model parameters. We obtain estimates of the compound GMRF model parameters from the original image using a new expectation maximization (EM) estimation technique. The EM algorithm enables estimation of the GMRF model parameters without being affected by the edges present in the image. Experimental results are given to illustrate the usefulness of our method.

To download the report in PDF format click here: USC-SIPI-128.pdf (0.8Mb)