De nombreuses applications nécessitent de comparer et classer des images au sein de bases de données, par exemple pour chercher une image particulière, ou pour analyser automatiquement son contenu. Afin d'exploiter efficacement les masses d'images disponibles, il est nécessaire de disposer de mesures de similarité qui soient à la fois pertinentes et calculables rapidement. De nombreux travaux sont basés sur une modélisation des images par graphes d'adjacence de régions (RAG). Cependant, mesurer la similarité (ou inversement la distance) de deux graphes est un problème combinatoire NP-difficile dans le cas général.

Les RAG ont été étendus en utilisant des cartes combinatoires ce qui permet d'avoir un modèle de représentation plus précis, intégrant la topologie. Différents algorithmes de construction, de mise à jour et d'exploitation de ces structures de données ont été proposés et sont actuellement implantés dans une plateforme.

Cependant, il n'existe à ce jour aucune mesure permettant d'évaluer la similarité de cartes combinatoires. L'objectif de cette thèse est donc de proposer des mesures de similarité de cartes et de concevoir des algorithmes efficaces permettant de calculer ces mesures. On s'inspirera
pour cela des travaux existants sur la similarité de graphes. Ces travaux devront être menés de manière théorique en dimension quelconque afin de proposer des outils génériques pouvant s'adapter à différents cadres d'utilisation. On validera plus particulièrement la pertinence des mesures et l'efficacité des algorithmes proposés sur des applications de recherche d'objets et de classification de bases d'images 2D ou 3D.