Markov image models and non-linear estimation algorithms on the quad-tree

Non-causal Markov Random Field (MRF) models are now widely used for representing images, but are known to yield iterative , often computational intensive, estimation algorithms . In this paper we consider a special class of Markov models which allow t o circumvent the latter drawback : MRF attached to the nodes of a quad-tree . The specific structure of these models results in a n appealing causality property through scale, which allows the design of exact, non-iterative inference algorithms which are simila r to those used in the context of Markov chain models . We first introduce an original extension of the Viterbi algorithm for the exac t computation of Maximum A Posteriori (MAP) estimates, along with two other algorithms respectively related to a modified MA P estimator, and to the Marginal Posterior Mode (MPM) estimator. The estimation of the parameters of the model is then addresse d with two original Expectation-Maximization (EM)-type algorithms, allowing an unsupervised use of these models . The practica l relevance of the different algorithms is investigated in the context of a standard image classification problem, both on syntheti c and natural images .Les modèles markoviens spatiaux non causaux utilisés dans le domaine de l'analyse d'images conduisent à des algorithmes d'estimation itératifs, réputés pour leur complexité calculatoire. Dans cet article, nous considérons une classe de processus markoviens hiérarchiques et non linéaires, définis sur le quadarbre. Ces modèles markoviens présentent des propriétés de causalité en échelle qui permettent de construire des algorithmes non itératifs exacts, similaires à ceux existant pour les chaînes de Markov, dans le cas des signaux mono-dimensionnels. Nous présentons ainsi une version originale de l'algorithme de Viterbi sur le quadarbre, associé à une estimation exacte au sens du Maximum A Posteriori (MAP), ainsi que deux autres algorithmes d'estimation, respectivement associés à un critère du MAP modifié et au critère du MPM (mode de la marginale a posteriori). Deux nouveaux algorithmes EM, permettant une estimation non supervisée sur le quadarbre, sont également introduits pour cette classe de représentations. Les propriétés de ces modèles et algorithmes sont illustrées et comparées, pour un problème simple de classification d'images, sur des images synthétiques et réelles