Appariement de formes, recherche par forme clef

Abstract

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. ABSTRACT : This thesis concerns shape matching and shape retrieval. It describes four contributions to this domain. The first is an improvement of the k-means method, in order to find the best partition of voxels inside a given shape; these best partitions permit to match shapes using an optimal matching in a bipartite graph. The second contribution is the fusion of two descriptors, one local, the other global, with the product rule. The third contribution considers the complete graph, the vertices of which are the shapes in the database and the query. Edges are labelled with several distances, one per descriptor. Then the method computes, with linear programming, the convex combination of distances which maximizes either the sum of the lengths of all shortest paths from the query to all shapes of the database, or the length of the shortest path in the graph from query to the current shape compared to query. The fourth contribution consists in perturbing the shape query, to make it closer to shapes in the database, for any given descriptors. This method is massively parallel and a multi-agent architecture is proposed. These methods are compared to classical methods in the field, they achieve better retrieval performances.