AVERTISSEMENT Ce document est le fruit d'un long travail approuvé par le jury de soutenance et mis à disposition de l'ensemble de la communauté universitaire élargie. Il est soumis à la propriété intellectuelle de l'auteur. Ceci implique une obligation de citation et de référencement lors de l’utilisation de ce document. D'autre part, toute contrefaçon, plagiat, reproduction illicite encourt une poursuite pénale. Contact : [email protected] LIENS Code de la Propriété Intellectuelle. articles L 122. 4 Code de la Propriété Intellectuelle. articles L 335.2- L 335.10 http://www.cfcopies.com/V2/leg/leg_droi.php http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm q2_ DvfJLo9rN Institut National CRIN-CNRS Polytechnique de Lorraine Inria Lorraine Ecole doctorale IAE+M Département de Formation Doctorale Informatique Reconnaissance par indexation en vision par ordinateur ' THE SE présentée et soutenue le Vendredi 13 novembre 1992 pour l'obtention du Doctorat de l'Institut National Polytechnique de Lorraine (Spécialité Informatique) par Stéphane Paris Composition du jury : Président : Roger MoHR · Rapporteurs : James L. CROWLEY Michel HABIB Examinateurs : Jean-Paul RATON Gérald MASINI Amedeo NAPOLI 11111111111111111111111111111 D 136 008254 9 ·.,. VUBIS.JIQio vu :-J O.(. ::)4- '} ..A AUTORISATION DE SOUTENANCE DE THESE DU DOCTORAT DE L'INSTITUT NATIONAL POLYTECHNIQUE DE LORRAINE oOo VU LES RAPPORTS ETABLIS PAR : Monsieur CROWLEY James, Professeur, LIFIA/INPG Grenoble, Monsieur HABIB Michel, Professeur, C.R.I.M. Montpellier. Le Président de l'Institut National Polytechnique de Lorraine, autorise : Monsieur PARIS Stéphane à soutenir devant l'INSTITUT NATIONAL POLYTECHNIQUE DE LORRAINE, une thèse intitulée: "Reconnaissance par indexation en vision par ordinateur" en vue de l'obtention du titre de : DOCTEUR DE L'INSTITUT NATIONAk~POLYTECHNIQUE DE LORRAINE Spécialité: "INFORMATIQUE" · 2, avenue de la Forêt de Haye- B.P. 3- 54501 VANDŒUVRE CEDEX Téléphone : 83. 59. 59. 59-Télex : 961 715 F-Télécopie : 83. 59. 59. 55 Remerciements Ce mémoire est pour moi l'occasion d'exprimer des remerciements à tous ceux qui m'ont conseillé et aidé à réaliser ce travail dans de bonnes conditions, et je suis heureux aujourd'hui de remercier plus particulièrement : Monsieur Roger Mohr, Professeur à l'institut Polytechnique de Grenoble, qui me fait l'honneur de présider ce jury, Monsieur James L. Crowley, Professeur à ["institut Polytechnique de Grenoble, et Monsieur Michel Habib, Professeur au Centre de Recherche en Informatique de Montpellier, pour avoir accepté d'être les rapporteurs de cette thèse, Messieurs Jean-Paul Haton, Professeur de l'Université de Nancy I, et Amedeo Napoli, chargé de recherche CRi CNRS au Centre de Recherche en Informatique de Nancy, pour avoir accepté d'examiner mon mémoire, Monsieur Gérald Masini, chargé de recherche CRl CNRS au Centre de Recherche en Informatique de Nancy et directeur de mes travaux, pour le constant intérêt qu'il a porté à ce travail. J'exprime des remerciements chaleureux à Mademoiselle Houda Chabbi, étudiante en thèse dans l'équipe, et à Mademoiselle Marie-Odile Berger, Chargée de Recherche CR2 INRIA au Centre de Recherche en Information de Nancy, pour les nombreuses et fructueuses discussions que nous avons eues ensemble et sans lesquelles ce travail ne serait pas tout à fait le même. Et merci de tout cœur à tous mes amis, Sylvie Karst, Annie L'Homée, Véronique Bouras, Régine Karst, Anja Habacha, Georges Paris, Julian Anigbogu, Eric Domen jou, Yves Laprie, Pierre, Marquis et Philippe Hoggan, pour les soutiens moral et matériel qu'ils m'ont apportés. Table des matières 1 Les systèmes de reconnaissance d'objets 15 1.1 La recherche des occurrences d'un modèle 17 1.1.1 La technique du template malching 18 1.1.2 La transformée de Hough . 19 1.1.3 Les modèles élastiques 21 1.1. 4 Les réseaux neuronaux . . 22 1.1.5 La décomposition en objets image . 25 1.1.6 Synthèse . . . . . 32 1.2 La perception des objets 34 1.2.1 Prédictions dirigées par les modèles 35 1.2.2 Organiser, sélectionner et vérifier 38 1.2.3 Les systèmes fondés sur les graphes d'aspects 43 1.3 En résumé . . . . . . . 46 2 Les techniques d'indexation 49 2.1 Les techniques de classifications . . . . 50 2.1.1 Les techniques d'analyse de données . 50 2.1.2 Le regroupement perceptuel par classification 52 2.1.3 Une hiérarchie de graphes relationnels 54 2.1.4 Les classifications conceptuelles 54 2.2 Les tables de hachage . 56 2.2.1 Les points 57 2.2.2 Les chaînes 57 2.2.3 Les graphes 58 2.2.4 Synthèse sur les tables de hachage . 59 2.3 Les graphes de décision . . . 59 2.3.1 La construction par induction 60 2.3.2 Les graphes de reconnaissance 61 2.3.3 Les règles de décision 62 2.3.4 En résumé . . . . . 64 3 L'indexation 61 3.1 La structure de MAGIC ........ . 67 3.1.1 Les données et leur acquisition. 68 3.1.2 Le bas niveau ..... . 71 3.1.3 Le niveau intermédiaire. 72 3.1.4 La base de connaissance 73 3.1.5 L'index et l'indexation 73 3.1.6 La reconnaissance . 75 3.1. 7 Synthèse . . . . . . . . 76 3.2 Une approche intuitive .... 76 3.2.1 Description de l'index 76 3.2.2 Une présentation de l'algorithme d'indexation 79 3.3 Le filtrage . . . . . . . . . . . . 80 3.4 Le processus d'indexation . . . 84 3.4.1 Définitions et notations . 85 3.4.2 Les règles . . . . . . . . 85 3.4.3 Contrôle d'application des règles . 90 3.4.4 Terminaison du processus de construction 92 3.4.5 Complexité . . . . . . . . . . 94 3.5 Expérimentations . . . . . . . . . . . . . 98 3.5.1 L'indexation d'un seul aspect .. 98 3.5.2 L'indexation de plusieurs aspects ~ ')3 3.6 En résumé . . . . . . . . . . . . . . . . . 105 4 La reconnaissance 107 4.1 Le fonctionnement 108 4.1.1 Intuitivement 108 4.1.2 Un exemple . 109 4.2 Les règles de fusion . 111 4.3 Ordonner les hytpothèses . 115 4.4 Algorithme ....... . 116 4.5 Les caractéristiques de l'algorithme 118 4.6 Les expérimentations 119 4.6.1 scene.1 . 119 4.6.2 scene.2 . 120 4.6.3 scene.3 . 122 4.7 En résumé 123 5 Conclusions 125 5.1 Evaluation de l'indexation structurelle 125 5.2 Les améliorations . . . . . . . . . . . . 126 5.2.1 Restreindre la taille du graphe . 126 5.2.2 Accélérer la reconnaissance et l'indexation 127 5.3 Perspectives . . . . . . . . . . . . . . . . . . . .. 128 Bibliographie 129