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-149

“Generalized Graduated Non-Convexity Algorithm for Maximum A Posteriori Image Estimation”

by Anand Rangarajan and Rama Chellappa

December 1989

We are interested in restoring a degraded scene while preserving the edges. Edges are represented as line processes and are estimated along with the intensities in a Maximum a posteriori (MAP) framework. Assumptions regarding the prior and degradation distributions reduce the problem to one of energy function minimization. The energy function incorporates constraints on the restoration process like smoothness constraints, penalty for imposing a discontinuity and penalties on broken contours. This makes the energy function highly non-convex and finding the global minimum is a non-trivial problem. When constraints on the interactions between line processes are removed, the deterministic, Graduated Non-Convexity (GNC) algorithm has been shown to find close to optimum solutions.

We have generalized the GNC model keeping some of its essentials. Any number of constraints on the line processes can now be added. This has been achieved by using the adiabatic approximation, a well known technique in synergetics. The adiabatic approximation also suggests the minimization scheme to be used. Our resulting algorithm is a combination of the completely deterministic. The algorithm was executed on two aerial images. Results are presented along with comparisons to the GNC algorithm.

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