A HIERARCHICAL MARKOV RANDOM-FIELD MODEL AND MULTITEMPERATURE ANNEALING FOR PARALLEL IMAGE CLASSIFICATION

In this paper, we are interested in massively parallel multiscale rela xation algorithms applied to image classification. It is well known th at multigrid methods can improve significantly the convergence rate an d the quality of the final results of iterative relaxation techniques. First, we present a classical multiscale model which consists of a la bel pyramid and a whole observation field, The potential functions of coarser grids are derived by simple computations. The optimization pro blem is first solved at the higher scale by a parallel relaxation algo rithm; then the next lower scale is initialized by a projection of the result. Second, we propose a hierarchical Markov random field model b ased on this classical model, We introduce new interactions between ne ighbor levels in the pyramid. It can also be seen as a way to incorpor ate cliques with far apart sites for a reasonable price. This model re sults in a relaxation algorithm with a new annealing scheme: the multi temperature annealing (MTA) scheme, which consists of associating high er temperatures to higher levels, in order to be less sensitive to loc al minima at coarser grids, The convergence to the global optimum is p roved by a generalization of the annealing theorem of S. Geman and D. Geman (IEEE Trans. Pattern Anal, Mach. Intell. 6, 1984, 721-741). (C) 1996 Academic Press, Inc.