Dates
on the May 25, 2016
10h15
Location
Salle Lovelace, Département Informatique de Polytech Tours, 64 Avenue Jean Portalis, 37200 Tours
Approches anytime et distribuées pour l'appariment de graphes - Anytime and Distributed Approaches for Graph Matching
En raison de la capacité et de l'amélioration des performances informatiques, les représentations structurelles sont devenues de plus en plus populaires dans le domaine de la Reconnaissance des Formes (RF). Représenter les objets à l'aide de graphes revient à transformer le problème de la comparaison d'objets en un appariement de graphes (Graph Matching).
Au cours de la dernière décennie, les chercheurs travaillant dans le domaine de l'appariement de graphes ont porté une attention particulière à la distance d'édition (entre Graphes (GED)), notamment grâce à sa capacité à traiter de différents types de graphes. GED a été ainsi appliquée sur des problématiques spéci fiques qui varient de la reconnaissance de molécules à la classi cation d'images.
Les chercheurs se sont focalisés sur les méthodes approchées qui peuvent trouver des
solutions sous-optimales, mais souvent sans garantie de précision. Pour cette raison, dans cette thèse, nous nous focalisons sur les algorithmes exacts. La complexité du problème d'appariement de graphes étant NP-di fficile, les méthodes exactes proposées ne peuvent être utilisées que sur des très petits graphes. A fin de réduire le temps de calcul, deux possibilités sont envisagées : élaguer l'espace de recherche et distribuer les calculs.
Dans cette thèse, nous avons dans un premier temps, proposé un algorithme de recherche arborescente travaillant en profondeur d'abord (Depth-First GED) qui nécessite moins de mémoire et de temps de calcul pour produire une solution. Une évaluation de toutes les solutions possibles est eectuée sans les énumérer explicitement. Les candidats sont éliminés à l'aide des bornes inférieure et supérieure. Pour trouver un compromis entre la vitesse et l'optimalité, nous avons proposé une version améliorée de Depth-First GED (appelée Anytime) qui est capable de délivrer une première solution réalisable très rapidement. Ensuite en laissant plus de temps, l'algorithme améliore progressivement sa solution initiale afi n de proposer de meilleures solutions jusqu'à converger vers une solution optimale.
Pour illustrer l'utilisation des méthodes Anytime, nous convertissons notre Depth-First
GED en Anytime Depth-First GED. Nous analysons les propriétés de ces méthodes pour résoudre le problème de l'appariement de graphes en tenant en compte des résultats en terme de précision de la solution fournie par rapport à la valeur optimale ou la meilleure trouvée par une méthode de l'état de l'art.
Cette thèse propose également des solutions initiales pour réduire le temps d'exécution
des méthodes de GED exactes à l'aide de téchniques de parallélisation et de distribution
des calculs. Deux approches parallèle et distribuée sont présentées. Ces deux méthodes
sont aussi basées sur la méthode Depth-First GED. L'espace de recherche est décomposé en arbres de recherche qui sont résolus indépendamment en parallèle ou d'une manière répartie.
A fin de tester les performances des méthodes proposées, nous avons non seulement évalué les méthodes GED dans un contexte de classifi cation mais aussi à un niveau plus fin mesurant la qualité de l'appariement. En raison de la complexité exponentielle des algorithmes GED, nous avons analysé le comportement de huit méthodes comparées sous contraintes de temps et de mémoire. En plus, nous avons proposé une base de graphes (GDR4GED) avec une vérité terrain dédiée à l'évaluation des méthodes de GED. Dans cette vérité terrain, nous ajoutons des informations concernant les appariements entre paires de graphes à des bases de données publiques et utilisées dans la littérature. L'ajout d'informations se compose de la meilleure distance d'édition trouvée ainsi que l'appariement "sommet à sommet" et "arc à arc" de chaque paire de graphes. Cette information permet d'évaluer la précision des méthodes de GED exactes et approchées.
De par ses conclusions et les exterminations proposées, cette thèse remet en cause les
réticences à utiliser les méthodes exactes d'appariement de graphes dans la pratique lors de l'appariement de grands graphes, ou même dans un contexte de classi fication. De fait, nous montrons que les méthodes "Anytime", peuvent être e fficaces, aussi bien dans un objectif de comparaison que de mise en correspondance de graphes.
Mots-clés : Reconnaissance de formes, appariement de graphes, distance d'édition,
Branch-and-Bound, systèmes parallèle et distribué, équilibrage de charge, évaluation de
performance
Au cours de la dernière décennie, les chercheurs travaillant dans le domaine de l'appariement de graphes ont porté une attention particulière à la distance d'édition (entre Graphes (GED)), notamment grâce à sa capacité à traiter de différents types de graphes. GED a été ainsi appliquée sur des problématiques spéci fiques qui varient de la reconnaissance de molécules à la classi cation d'images.
Les chercheurs se sont focalisés sur les méthodes approchées qui peuvent trouver des
solutions sous-optimales, mais souvent sans garantie de précision. Pour cette raison, dans cette thèse, nous nous focalisons sur les algorithmes exacts. La complexité du problème d'appariement de graphes étant NP-di fficile, les méthodes exactes proposées ne peuvent être utilisées que sur des très petits graphes. A fin de réduire le temps de calcul, deux possibilités sont envisagées : élaguer l'espace de recherche et distribuer les calculs.
Dans cette thèse, nous avons dans un premier temps, proposé un algorithme de recherche arborescente travaillant en profondeur d'abord (Depth-First GED) qui nécessite moins de mémoire et de temps de calcul pour produire une solution. Une évaluation de toutes les solutions possibles est eectuée sans les énumérer explicitement. Les candidats sont éliminés à l'aide des bornes inférieure et supérieure. Pour trouver un compromis entre la vitesse et l'optimalité, nous avons proposé une version améliorée de Depth-First GED (appelée Anytime) qui est capable de délivrer une première solution réalisable très rapidement. Ensuite en laissant plus de temps, l'algorithme améliore progressivement sa solution initiale afi n de proposer de meilleures solutions jusqu'à converger vers une solution optimale.
Pour illustrer l'utilisation des méthodes Anytime, nous convertissons notre Depth-First
GED en Anytime Depth-First GED. Nous analysons les propriétés de ces méthodes pour résoudre le problème de l'appariement de graphes en tenant en compte des résultats en terme de précision de la solution fournie par rapport à la valeur optimale ou la meilleure trouvée par une méthode de l'état de l'art.
Cette thèse propose également des solutions initiales pour réduire le temps d'exécution
des méthodes de GED exactes à l'aide de téchniques de parallélisation et de distribution
des calculs. Deux approches parallèle et distribuée sont présentées. Ces deux méthodes
sont aussi basées sur la méthode Depth-First GED. L'espace de recherche est décomposé en arbres de recherche qui sont résolus indépendamment en parallèle ou d'une manière répartie.
A fin de tester les performances des méthodes proposées, nous avons non seulement évalué les méthodes GED dans un contexte de classifi cation mais aussi à un niveau plus fin mesurant la qualité de l'appariement. En raison de la complexité exponentielle des algorithmes GED, nous avons analysé le comportement de huit méthodes comparées sous contraintes de temps et de mémoire. En plus, nous avons proposé une base de graphes (GDR4GED) avec une vérité terrain dédiée à l'évaluation des méthodes de GED. Dans cette vérité terrain, nous ajoutons des informations concernant les appariements entre paires de graphes à des bases de données publiques et utilisées dans la littérature. L'ajout d'informations se compose de la meilleure distance d'édition trouvée ainsi que l'appariement "sommet à sommet" et "arc à arc" de chaque paire de graphes. Cette information permet d'évaluer la précision des méthodes de GED exactes et approchées.
De par ses conclusions et les exterminations proposées, cette thèse remet en cause les
réticences à utiliser les méthodes exactes d'appariement de graphes dans la pratique lors de l'appariement de grands graphes, ou même dans un contexte de classi fication. De fait, nous montrons que les méthodes "Anytime", peuvent être e fficaces, aussi bien dans un objectif de comparaison que de mise en correspondance de graphes.
Mots-clés : Reconnaissance de formes, appariement de graphes, distance d'édition,
Branch-and-Bound, systèmes parallèle et distribué, équilibrage de charge, évaluation de
performance