A DETERMINISTIC ALGORITHM FOR RECONSTRUCTING IMAGES WITH INTERACTING DISCONTINUITIES

The most common approach for incorporating discontinuities in visual r econstruction problems makes use of Bayesian techniques, based on Mark ov random field models, coupled with stochastic relaxation and simulat ed annealing. Despite their convergence properties and flexibility in exploiting a priori knowledge on physical and geometric features of di scontinuities, stochastic relaxation algorithms often present insurmou ntable computational complexity. Recently, considerable attention has been given to suboptimal deterministic algorithms, which can provide s olutions with much lower computational costs. These algorithms conside r the discontinuities implicitly rather than explicitly and have been mostly derived when there are no interactions between two or more disc ontinuities in the image model. In this paper we propose an algorithm that allows for interacting discontinuities, in order to exploit the c onstraint that discontinuities must be connected and thin. The algorit hm, called E-GNC, can be considered an extension of the graduated nonc onvexity (GNC), first proposed by Blake and Zisserman for noninteracti ng discontinuities. When applied to the problem of image reconstructio n from sparse and noisy data, the method is shown to give satisfactory results with a low number of iterations. (C) 1994 Ademic Press, Inc.