Dans cette thèse, nous nous intéressons aux modèles markoviens appliqués aux problèmes de vision pré-attentive. Nous considerons ces problèmes dans un cadre générale, appellé étiquetage d'images, où le problème consiste à attribuer des étiquettes aux pixels. Notre approche est fondée sur les champs de Markov et l'estimation bayesienne, en particulier l'estimation de Maximum A Posteriori (MAP). L'avantage de la modèlisation markovienne est de fournir un modèle simple qui nous permet de définir les informations a priori par des potentiels locaux. Nous présentons aussi les modèles pyramidaux qui réduisent le temps de calcul et améliorent le résultat final. L'estimation des paramètres est un autre problème important pour les applications réelles. Nous appliquons quelques méthodes connues à l'estimation de paramètres du modèle monogrille et proposon des nouveaux algorithms d'estimation pour le modèle hiérarchique. Les premiers resultats sont satisfaisantes mais il reste beaucoup de travail à faire sur le sujet.
Tous les modèles markoviens nécessitent la minimisation d'une fonction d'énergie non-convexe. Nous avons deux choix pour résoudre ce problème: soit par recuit simulé soit par relaxation déterministe. Nous discutons la possibilité de paralleliser ces algorithmes.
Notre principal résultat est un modèle markovien hiérarchique et un algorithme de récuit multi-température (MTA) pour la minimisation de la fonction d'énergie du modèle hiérarchique. Pour le MTA, nous avons prouvé la convergence vers un minimum global dans le cas le plus général où chaque clique a sa propre loi de température. Il reste quelques problèmes ouverts comme la relation entre les valeurs estimées au sens du MAP pour les modèles monogrille et hiérarchique, l'implantation de l'algorithme MTA sur une architecture pyramidale ou bien la mise en oeuvre une méthode beaucoup plus rapide pour l'estimation de paramètres.
Mots clefs: vision par ordinateur, vision pré-attentive, modèlisation markovien, modèle multiéchelle, modèle hiérarchique, algorithmes d'optimisation massivement parallèles, recuit multi-température, etimation de paramètres.
La vision par ordinateur se réfère aux algorithmes variés pour restaurer ou interpréter les images digitales. On peut distinguer deux niveaux de traitement d'images: Le but de la vision haut niveau est d'extraire les attributs symboliques (par exemple la reconnaissance des lettres écrites à la main) et le but de la vision bas niveau (ou vision pré-attentive) est d'extraire des attributs nécessaires pour la vision haut niveau (par exemple l'extraction des contours). Le premier étape du traitement d'images est le traitement bas niveau.
Dans cette thèse, nous nous intéressons à une approche statistique de la vision pré-attentive. Dans une image réelle, les pixels voisines ont un niveau de gris similaire. Dans un cadre probabilistique, une telle régularité est bien modélisée par les champs de Markov. D'un autre côté, le comportement local des champs markoviens permet de mettre en oeuvre des algorithmes massivement parallèles pour résoudre les problèmes d'optimisation combinatorial associés à une telle modélisation. Nous discuterons aussi les méthodes d'estimation des paramètres, un problème très important dans les applications réelles.
Dans le chapitre sur la modelisation, nous proposons un nouveau modèle markovien hiérarchique et dans le chapitre sur l'estimation, nous présentons une méthode d'estimation des paramètres de ce modèle. Dans le chapitre sur l'optimisation, nous proposons un nouveau recuit multi-température et nous prouverons la convergence vers un minimum global. Nous proposons aussi une méthode de relaxation déterministe avec une étude détaillée de la convergence. Tous les modèles et algorithmes présentés dans cette thèse ont été mis en oeuvre sur une machine parallèle CM200. Des tests comparatifs seront présentés à la fin de chaque chapitre.
Nous nous intéressons aussi à la théorie de la décision au sens bayesien qui est la base de l'estimation du Maximum A Posteriori (MAP) largement utilisé dans l'étiquetage d'images. Nous définissons quelques notions comme la probabilité, les variables aléatoires, la distribution, la densité, les processus stochastiques, la convergence des variables aléatoires, etc... La distribution gaussienne est présentée en détails car c'est la distribution la plus souvent utilisée dans la traitement d'images.
Le contenu de ce chapitre est fondé sur le livre de Papoulis sur la théorie de probabilité.
La vision pré-attentive se réfère aux tâches de traitement des images digitales, traitant directement de larges quantités des pixels. Le but d'un tel traitement est de transformer les données en attributs significatifs (contours, texture, régions, etc...).
Les algorithmes utilisés sont souvent déstinés à une seule application et parfois mis au point dans un environment spécifique. Un cadre général dans la vision pré-attentive est l'étiquetage d'images où nous voulons associer une étiquette à chaque pixel. Le sens de cet étiquette dépend du problème traité. Pour la restauration d'images, il représente les niveaux de gris; pour la détection de contour, il représente la présence ou la direction d'un élément de contour; pour la segmentation d'images, il représente les classes ou régions; etc...Le problème de base est comment choisir une étiquette pour chaque pixel. Notre approche est probabiliste: nous attribuons l'étiquette la plus probable à chaque pixel. Pour cela, nous avons besoin d'une mesure de probabilité sur l'ensemble des étiquetages possibles. Dans les images réelles, les pixels voisins ont souvent une intensité similaire. Dans un cadre probabiliste, cette régularité est bien exprimée par les champs de Markov. Une autre raison pour utiliser les modèles markoviens est le théorème de Hammersley-Clifford qui permet de définir les champs markoviens par les énergies potentielles. Dans le problème d'étiquetage, nous cherchons l'estimateur Maximum A Posteriori (MAP) du champ des étiquettes.
Malheureusement, trouver un tel étiquetage est une tâche très difficile. L'utilisation des modèles multi-grilles, proposée par les auteurs, rend le problème de minimisation plus facile. Nous proposons un nouveau type de modèle multi-grille que nous appelons modèle markovien hiérarchique. ce modèle permet de travailler avec des cliques contenant des sites éloignés pour un coût raisonable.
Les méthodes bayesiennes associées avec la modélisation markovienne donnent une fonction d'énergie non-convexe qui doit être minimisée pour trouver l'estimateur de champ des étiquettes. Malheureusement, c'est un problème très dur, appelé optimisation combinatoire. Par exemple, si nous considérons une image de taille 16 X 16 avec deux étiquettes possibles, nous obtenons un espace de configurations de 2**256 éléments. Il est donc impossible de calculer toutes les valeurs possibles de la fonction d'énergie. D'un autre côté, l'utilisation de méthodes classiques n'est pas possible à cause de la non-convexité de la fonction d'énergie.
L'idée de la solution vient de la physique statistique: En 1953, Metropolis et al. ont proposé une simulation Monte-Carlo pour trouver les états d'équilibre des systèmes thermodinamiques. Dans les années 80, Černy et Kirkpatrick et al. ont montré l'analogie entre la minimisation d'une fonction non-convexe et l'état d'équilibre des systèmes thermodynamiques.
Ils ont substitué la fonction d'énergie du solide à la fonction de coût à minimiser et exécuté l'algorithme de Metropolis en utilisant une séquence de température décroissant lentement. Ils ont appelé ce nouvel algorithme recuit simulé.
La recherche dans ce domaine est devenue intensive et a aboutis à des contributions variées dont la plus importante est probablement l'échantillonneur de Gibbs proposé par Geman et Geman. Bien que les algorithmes de recuit simulé donnent un optimum global, ils exigent beaucoup de calcul. Pour éviter cet inconvénient, deux solutions ont été proposées: la parallélisation d'algorithmes de type recuit, et l'utilisation d'algorithmes déterministes, qui sont sous-optimaux mais convergent avec un nombre faible d'itérations.
Dans les applications réelles, les paramètres sont souvent inconnus, il faudra les estimer à partir de l'image observée. D'un point de vue statistique, ce problème est équivalent au problème de l'estimation des paramètres à partir d' un mélange de distribution. Si nous avons une réalisation du champ des étiquettes, la tâche est alors relativement facile, il existe plusieurs méthodes standards (maximum de vraisemblance, codage, etc...). Malheureusement, nous n'avons pas un tel échantillon, il est donc impossible d'utiliser directement ces méthodes. Nous devons les approximer par une fonction de l'image observée.
La plupart des méthodes utilisées sont itératives. Pour une telle méthode, nous avons besoin d'une bonne initialisation pour chaque paramètre. Étant donné que les classes sont représentées par une distribution gaussienne, l'initialisation des valeurs moyennes et des variances des classes est très importante car ils ont une grande influence sur les étiquetages sous-jacents et donc sur le résultat final. Il existe plusieurs approches: la méthode des moments, la méthode de Prony ou l'analyse géométrique de l'histogramme.
Dans ce chapitre, nous présentons des algorithmes d'estimation pour le modèle mono-grille et proposons une méthode pour l'estimation des paramètres du modèle hiérarchique.
Nous avons discuté les trois étapes principales du traitement statistique d'images: la modélisation, l'optimisation et l'estimation des paramètres. Nous avons étudié les problèmes de la vision pré-attentive dans un cadre général appelé étiquetage d'images. Notre approche est probabiliste, nous utilisons les champs de Markov et l'estimation bayesienne, en particulier l'estimation par le Maximum A Posteriori (MAP). L'avantage d'une telle modélisation est que l'information a priori peut être ``codée'' localement par les potentiels des cliques. Nous avons développé les modèles markoviens pyramidaux qui réduisent le temps de calcul et améliorent la qualité du résultat final. Nous avons proposé des méthodes pour l'estimation des paramètres des modèles hiérarchiques et mono-grilles. Les premiers résultats sont satisfaisants mais il reste beaucoup de travail à faire.
Tous les modèles markoviens exigent la minimisation d'une fonction d'énergie non-convexe qui est résolue par recuit simulé ou par relaxation déterministe. Nous avons présenté également les méthodes de parallélisation de ces algorithmes.
Notre résultat principal est un modèle markovien hiérarchique et un algorithme de recuit multi-température proposé pour la minimisation de l'énergie du modèle hiérarchique. La convergence de cet algorithme vers un optimum global a été prouvé dans le cas général où chaque clique a sa propre loi de température locale. Il reste quelques problèmes ouverts comme la relation entre les estimateurs MAP du modèle mono-grille et celui du modèle hiérarchique. la mise en oeuvre du modèle hiérarchique sur un ordinateur pyramidal et l'implantation d'une méthode beaucoup plus rapide pour l'estimation des paramètres.