Mesurer la similarité de graphes - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2006

Mesurer la similarité de graphes

Résumé

Mesurer la similarité d'images est un problème qui se pose dans de nombreuses applications, que ce soit pour rechercher des images, les classifier ou encore les confronter à des modèles pour les "reconnaître". Quand les images sont représentées par des graphes, on peut mesurer la similarité de deux images en appariant les sommets des graphes associés aux images de façon à retrouver leurs caractéristiques communes. Différentes sortes d'appariements de graphes, impliquant différentes mesures de similarité, ont été proposées, e.g., l'isomorphisme de (sous-)graphes pour mesurer l'équivalence ou l'inclusion de deux graphes, et la distance d'édition de graphes pour mesurer le coût de transformation d'un graphe en un autre. Ces différents appariements sont "univoques" dans le sens où un sommet d'un graphe ne peut être apparié qu'à au plus un sommet de l'autre graphe. Nous proposons ici une nouvelle mesure de similarité de graphes basée sur un appariement multivoque des sommets des graphes, chaque sommet pouvant être apparié à un ensemble de sommets de l'autre graphe. Cet aspect nous permet notamment de comparer des graphes décrivant des images à différents niveaux de granularité, et de prendre en compte les problèmes de sur- et de sous-segmentation des images. Notre mesure de similarité est générique dans le sens où elle est paramétrée par des fonctions de similarité qui permettent d'exprimer des connaissances de similarité propres à l'application considérée. En particulier, nous montrons que toutes les mesures de similarité proposées jusqu'alors peuvent être vues comme un cas particulier de notre mesure. Nous nous intéressons également au problème du calcul de cette similarité, et nous proposons et comparons trois algorithmes : un algorithme glouton, un algorithme basé sur une recherche locale Taboue réactive et un algorithme basé sur l'optimisation par colonies de fourmis.
Fichier non déposé

Dates et versions

hal-01541562 , version 1 (19-06-2017)

Identifiants

  • HAL Id : hal-01541562 , version 1

Citer

Sébastien Sorlin, Olfa Sammoud, Christine Solnon, Jean-Michel Jolion. Mesurer la similarité de graphes. Extraction de COnnaissance à partir d'Images (ECOI 2006), Atelier de Extraction et Gestion de Connaissances (EGC 2006), Jun 2006, Lille, France. pp.21-30. ⟨hal-01541562⟩
149 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More