| Titre : | Appariement de formes ,recherches par forme clef |
| Auteurs : | Bilal Mokhtari, Auteur ; kamal Eddine Melkemi, Directeur de thèse |
| Type de document : | Thése doctorat |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2016 |
| ISBN/ISSN/EAN : | TINF/99 |
| Format : | 1 vol. (161 p.) / ill. / 29 cm |
| Langues: | Français |
| Résumé : |
Cette thèse porte sur l’appariement des formes, et la recherche par forme clef. Elle décrit quatre contributions à ce domaine. La première contribution est une amélioration de la méthode des nuées dynamiques pour partitionner au mieux les voxels à l’intérieur d’une forme donnée ; les partitions obtenues permettent d’apparier les objets par un couplage optimal dans un graphe biparti. La seconde contribution est la fusion de deux descripteurs,l’un local, l’autre global, par la règle du produit. La troisième contribution considère le graphe complet, dont les sommets sont les formes de la base ou la requête, et les arêtes sont étiquetées par plusieurs distances, une par descripteur ; ensuite cette méthode calcule par programmation linéaire la combinaison convexe des distances qui maximise soit la somme des longueurs des plus courts chemins entre la requête et les objets de la base de données,soit la longueur du plus court chemin entre la requête et l’objet comparé à la requête. La quatrième contribution consiste à perturber la requête avec un algorithme génétique pour la rapprocher des formes de la base de données, pour un ou des descripteur(s) donné(s);cette méthode est massivement parallèle, et une architecture multi-agent est proposée. Ces méthodes sont comparées aux méthodes classiques, et ont de meilleures performances, en terme de précision. |
| Sommaire : |
Introduction 3 1 Descripteurs de formes, appariement et recherche par forme clef 5 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Similarité d’objets et recherche par forme clef . . . . . . . . . . . . 6 1.2.1 Descripteurs de formes . . . . . . . . . . . . . . . . . . . . 6 1.2.1.1 Descripteurs géométriques . . . . . . . . . . . . . 7 1.2.1.2 Descripteurs structurels et topologiques . . . . . . 10 1.2.1.3 Descripteurs par prise de vues . . . . . . . . . . . 13 1.2.2 Dissimilarité des objets : calcul de distance . . . . . . . . . 14 1.3 Distribution de forme et distances statistiques . . . . . . . . . . . . 17 1.3.1 Descripteurs de distribution de forme . . . . . . . . . . . . 17 1.3.2 La géométrie de diffusion et la décomposition spectrale . . 19 1.3.3 Distances entre distribution : distances statistiques . . . . . 26 1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2 Quelques concepts utiles 29 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2 Représentation des objets . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.1 Les objets 2D . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.2 Les objets 3D . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2.3 Modèles polygonaux : maillages . . . . . . . . . . . . . . . 33 2.2.4 Représentation volumique discrète des objets 3D . . . . . . 34 2.3 Bases de données . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.4 Mesurer la performance du processus de recherche par forme clef 37 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 II Contributions 39 3 Décomposition d’objets en squelette d’ellipsoïdes 41 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.2 Décomposition d’objets par l’algorithme des nuées dynamiques . . 42 3.2.1 Algorithme des nuées dynamiques . . . . . . . . . . . . . . 42 3.2.2 Partitionnement optimal . . . . . . . . . . . . . . . . . . . . 43 3.2.2.1 Un exemple 1D . . . . . . . . . . . . . . . . . . . 45 3.2.2.2 Le nombre k optimal . . . . . . . . . . . . . . . . . 45 3.3 Matrice de covariance et squelette d’ellipsoïdes . . . . . . . . . . . 48 3.3.1 Matrice de covariance . . . . . . . . . . . . . . . . . . . . . 48 3.3.2 Partitionnement final . . . . . . . . . . . . . . . . . . . . . . 50 3.3.3 Les k-partitions initiales . . . . . . . . . . . . . . . . . . . . 51 3.4 Classification d’une base de données . . . . . . . . . . . . . . . . 53 3.5 Appariement de formes . . . . . . . . . . . . . . . . . . . . . . . . 53 3.5.1 Vecteur caractéristique d’une classe . . . . . . . . . . . . . 53 3.5.2 Calcul de distance : couplage optimal dans un graphe biparti 54 3.6 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4 Descripteurs et distribution de formes 59 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.3 Descripteurs de formes . . . . . . . . . . . . . . . . . . . . . . . . 61 4.3.1 Descripteur de la géométrie de diffusion (GD) . . . . . . . . 61 4.3.2 Le diamètre local (LFD) . . . . . . . . . . . . . . . . . . . . 63 4.3.3 Le descripteur de l’énergie discrète (DE) . . . . . . . . . . 63 4.3.4 Descripteur de la normale en un sommet (VND) . . . . . . 64 4.3.5 La distribution locale de la forme (LSD) . . . . . . . . . . . 65 4.3.6 Le descripteur de distribution de température (TD) . . . . . 65 4.3.7 Descripteur de distribution (D2) . . . . . . . . . . . . . . . . 66 4.3.8 Le descripteur de l’enveloppe convexe (CH) . . . . . . . . 66 4.4 Mesure de dissimilarité : distance . . . . . . . . . . . . . . . . . . . 67 4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5 La fusion des descripteurs par la règle du produit 69 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.2 Descripteurs de formes utilisés et dissimilarité de formes . . . . . 70 5.3 La fusion des descripteurs . . . . . . . . . . . . . . . . . . . . . . . 71 5.3.1 Fusion précoce et règles de fusion . . . . . . . . . . . . . . 72 5.3.2 Le descripteur proposé : S . . . . . . . . . . . . . . . . . . 74 5.4 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . 75 5.4.1 Paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.4.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.4.3 Résultats de comparaison . . . . . . . . . . . . . . . . . . . 79 5.4.4 Pré-traitement et temps de calcul . . . . . . . . . . . . . . . 81 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 6 Combinaison des mesures de dissimilarité 83 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.2 Vue d’ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6.2.1 Descripteurs de formes utilisés . . . . . . . . . . . . . . . . 85 6.2.2 Règles de fusion . . . . . . . . . . . . . . . . . . . . . . . . 85 6.3 Notre approche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.3.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.3.2 Description de notre approche . . . . . . . . . . . . . . . . 86 6.4 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.4.1 Descripteurs de formes et bases de données 3D utilisées . 87 6.4.2 Résultats et comparaisons . . . . . . . . . . . . . . . . . . 91 6.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 7 Le clonage améliore la reconnaissance 95 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 7.2 Contexte et principes . . . . . . . . . . . . . . . . . . . . . . . . . . 96 7.2.1 L’amélioration du processus de recherche par forme clef . . 96 7.2.2 L’utilisation du hasard, et du bruit . . . . . . . . . . . . . . . 97 7.2.3 Les algorithmes génétiques . . . . . . . . . . . . . . . . . . 98 7.2.4 Principe de notre méthode . . . . . . . . . . . . . . . . . . 99 7.3 Clonage de formes et algorithme génétique . . . . . . . . . . . . . 101 7.3.1 Initialisation de l’algorithme génétique : clonage de formes 101 7.3.2 Le calcul des paramètres E et P . . . . . . . . . . . . . . . . 105 7.3.3 Notre algorithme génétique . . . . . . . . . . . . . . . . . . 106 7.3.3.1 Population de l’algorithme algorithme . . . . . . . 106 7.3.3.2 Opérateurs de l’algorithme génétique . . . . . . . 106 7.3.3.3 La qualité d’un clone : son aptitude . . . . . . . . 110 7.4 Algorithme génétique distribué pour le clonage de formes . . . . . 112 7.4.1 Description de l’algorithme distribué proposé . . . . . . . . 113 7.4.2 La structure du MAS-SR-GA . . . . . . . . . . . . . . . . . 113 7.5 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . 116 7.5.1 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 7.5.2 Comparaison de l’algorithme génétique et du lissage . . . . 117 7.5.3 Comparaison des résultats . . . . . . . . . . . . . . . . . . 119 7.5.4 Pré-traitement et temps de calcul . . . . . . . . . . . . . . . 120 7.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 III Conclusion générale 123 Conclusion 125 IV Annexes 151 A Annexe 153 A.1 La décomposition spectrale des maillages 3D . . . . . . . . . . . . 154 A.1.1 Coordonnées différentielles et matrice Laplacienne . . . . . 154 A.1.2 Matrice Laplacienne d’une marche aléatoire . . . . . . . . . 155 A.1.3 Les valeurs et les vecteurs propres d’une matrice Laplacienne156 A.2 Marche aléatoire et géométrie de diffusion . . . . . . . . . . . . . . 157 A.2.1 Chaîne de Markov . . . . . . . . . . . . . . . . . . . . . . . 158 A.2.2 Chaîne de Markov d’un maillage 3D . . . . . . . . . . . . . 160 |
| En ligne : | http://thesis.univ-biskra.dz/id/eprint/3110 |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| TINF/99 | Théses de doctorat | bibliothèque sciences exactes | Consultable |
