An extended GNC algorithm for image reconstruction with interacting discontinuities

The importance of discontinuities in visual reconstruction problems is nowadays universally recognized in the scientific community. The most popular approach to deal with discontinuities makes use of Bayesian techniques, based on Markov Random Field models, coupled with stochastic relaxation and simulated annealing to compute the Maximum A Posteriori estimate. The MRF formulation is appealing because it describes the image by local interactions and is flexible in exploiting certain physical and geometric features of discontinuities, such as their smoothness characteristics. Nevertheless, despite their convergence properties, stochastic relaxation algorithms often present insurmountable computational complexity. Recently, suboptimal deterministic algorithms, which can provide solutions with much lower computational costs, have raised the interest of many researchers. These algorithms are based on considering the discontinuities implicitly rather than explicitly. In particular, the Graduated Non-Convexity algorithm, first derived by Blake and Zisserman, has been proved to present good convergence properties, but only when the image model does not include interactions between two or more discontinuities. In this paper we propose an extension of the GNC algorithm (E-GNC) to take into account interacting discontinuities. In particular we exploit the constraint that discontinuities must be both connected and thin. The algorithm is suitable for a parallel implementation that could further decrease the computational time with respect to stochastic relaxation. When applied to the problem of image reconstruction from sparse and noisy data, the method is shown to perform better than the traditional GNC algorithm.