these, université Paul Sabatier

Informations

• Publié par: Shuwyor
• Nombre de lectures: 50
• Langue: Français

Extrait

´UNIVERSITE PAUL SABATIER
´El´ements de g´eom´etrie qualitative pour
la description structurale d’objets
`THESE
pr´esent´ee et soutenue publiquement le 7 mai 2003
pour l’obtention du
Doctorat de l’Universit´e Paul Sabatier
(sp´ecialit´e informatique – intelligence artificielle)
par
Pierre Gambarotto
Composition du jury
Rapporteurs : G´erard LIGOZAT
Robert JEANSOULIN
Examinateurs : Claudette Cayrol (Pr´esidente du jury)
Mario Borillo
Philippe Balbiani (Directeur de th`ese)
Vincent Dugat
Institut de Recherche en Informatique de Toulouse – Universit´e Paul SabatierMis en page avec la classe thloria.Remerciements
Je tiens tout d’abord à remercier Mario Borillo et Philippe Balbiani, qui ont accepté succes-
sivement d’encadrer mes travaux, chacun avec son style. Merci ensuite à Robert Jeansoulin et
Gérard Ligozat pour avoir accepté de relire les épreuves bourrées de fautes de mon manuscrit,
certaines ayant encore échappé à ma faible connaissances des règles de grammaire et d’ortho-
graphe.
Je tiens à remercier tout spécialement Vincent Dugat, qui en collaboration avec Yannick
Larvor, m’a permis de donner libre cours à mon imagination, et qui fort heureusement ont
toujours su tempérer celle-ci.
Le contenu n’est pas tout, ce travail n’aurait pas été supportable sans la présence de longues
pauses, rendues obligatoires par le manque de sommeil et le découragement. Merci donc aux
nombreux collègues qui ont permis de surmonter les baisses de forme, d’avoir de nouvelles
idées, de ne pas squatter tout seul les machines à café de l’UPS. En premier lieu, je remercie
Philippe Muller, dont j’ai encombré la vue pendant quelques années, avec qui j’ai pu partager
des discussions enrichissantes sur la nature des mouvements d’engins explosifs dans des simu-
lations exotiques, en compagnie de Christophe Luc et Mohammed Bouajani. Merci à beaucoup
de titres à différents membres des équipes de recherche de l’IRIT, que je ne détaillerai pas pour
ne pas faire de jaloux, et parce que ces remerciements commencent à être plus long que certaines
parties de ma thèse.
Et pour finir, merci à ceux qui accompagnent ma vie en dehors du travail, ma famille et mes
amis.
iiiRésumé
De nombreux travaux se sont intéressés ces dernières années à des représentations non clas-
siques de l’espace. Certaines théories ont notamment remplacé le point comme primitive spa-
tiale par des régions (entités spatialement étendues), et ont rebâti sur cette base l’expression de
notions de topologie. Le Raisonnement Spatial Qualitatif utilise des représentations s’appuyant
sur ces théories pour conduire des raisonnements en présence d’informations incomplètes et/ou
imprécises. Parallèlement, les objets sont usuellement représentés en informatique par une ap-
proximation de leur frontière par un ensemble réduit de points (sous forme de polygones, de
polyèdres par exemple), dans des domaines tels que l’image ou la robotique. Le travail que
nous avons effectué dans cette thèse bâtit un pont entre ces deux types de représentation, et
permet de passer d’une description d’un objet sous forme polyédrique à une description basée
sur des régions. Cette représentation, plus abstraite, est alors utilisée pour étudier la structure
de l’objet. Nous proposons une théorie pour exprimer, dans le cadre d’un espace basé sur des
régions, des notions de métrique et d’orientation. Cette théorie est alors utilisée sur la nouvelle
représentation pour obtenir une description de la structure de l’objet. Chaque partie convexe
de l’objet est représentée avec un vocabulaire restreint, et les différentes parties sont repérées
l’une par rapport à l’autre en fonction de leur orientation respective. Pour finir, nous montrons
un exemple d’utilisation de cette représentation, en détaillant un algorithme de calcul des sy-
métries géométriques internes de l’objet.Table des matières
Table des figures ix
Chapitre 1
Introduction
1.1 Reconnaissance structurelle d’un objet . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Cadre formel utilisé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Représentation qualitative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Plan adopté pour traiter le problème . . . . . . . . . . . . . . . . . . . . . . . 3
Chapitre 2
Espace de représentation d’un objet
2.1 Nature de l’espace représenté . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Ontologie : choix de primitives de représentation . . . . . . . . . . . . . . . . 10
2.2.1 Primitive ponctuelle : géométrie cartésienne . . . . . . . . . . . . . . . 10
2.2.2 Structure d’intervalles . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.3 Généralisation des structures d’intervalles . . . . . . . . . . . . . . . . 13
2.2.4 Représentation basée sur des entités non ponctuelles . . . . . . . . . . 15
2.3 Relations à exprimer entre primitives . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Relations topologiques . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.2 Relations d’orientation . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.3 Relations métriques : distance et taille . . . . . . . . . . . . . . . . . . 31
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Chapitre 3
Expressions de notions métriques dans un espace à base de régions
3.1 Axiomatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
vTable des matières
3.2 Définition de relations métriques : comparer des sphères . . . . . . . . . . . . 50
Chapitre 4
Passage d’une représentation géométrique cartésienne à une représentation qualita-
tive
4.1 D’une représentation informatique à une représentation qualitative . . . . . . . 59
4.2 Définition de la notion de squelette : morphologie mathématique . . . . . . . . 65
4.3 Obtention du squelette d’un objet : diagramme de l’axe médian . . . . . . . . . 70
4.3.1 Classification des points de l’axe médian . . . . . . . . . . . . . . . . 74
4.3.2 Principe de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.3.3 Propriétés du MAT et comparaison avec la représentation initiale . . . . 77
4.3.4 Algorithme de l’axe médian d’un objet convexe. . . . . . . . . . . . . 78
4.3.5 Traitement des objets concaves. . . . . . . . . . . . . . . . . . . . . . 80
4.3.6 Graphe des parties d’un objet convexe . . . . . . . . . . . . . . . . . . 83
4.4 Arbre de représentation d’un objet . . . . . . . . . . . . . . . . . . . . . . . . 83
4.4.1 Caractérisation des convexes . . . . . . . . . . . . . . . . . . . . . . . 85
4.5 Conclusion : algorithme de représentation sous forme de graphe d’un polygone
(ou polyèdre) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Chapitre 5
Identification structurelle d’un objet
5.1 Définir la structure d’un objet . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.2 Comparaison de la structure grossière de deux objets concaves. . . . . . . . . . 91
5.3 Comparaison de la forme de deux objets convexes. . . . . . . . . . . . . . . . 92
5.4 Calcul de symétries géométriques. . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4.1 Vocabulaire de théorie des graphes . . . . . . . . . . . . . . . . . . . . 92
5.4.2 Analyse structurelle . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.4.3 Construction d’un graphe coloré . . . . . . . . . . . . . . . . . . . . . 96
5.4.4 Algorithme de force brute . . . . . . . . . . . . . . . . . . . . . . . . 96
5.4.5 Algorithme intelligent de recherche de symétries. . . . . . . . . . . . . 98
5.5 Étude structurelle d’un objet . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Chapitre 6
Conclusion
viAnnexe A
Algorithme de l’axe médian d’un polyèdre convexe.
A.1 PROPAGATION_PJ(p) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
A.2 CORDE_VALIDE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
A.3 TROUVER_PJ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
A.4 VERIFIER_PJ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
A.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
Bibliographie 109
viiTable des matières
viii