Institut de la Francophonie Université catholique de pour l’Informatique Louvain Appariement multivoque de graphes par la recherche locale Mémoire de fin d’études Réalisé par : NGUYEN Thi Hong Hiep Sous la direction de : Prof. Yves Deville Département d’Ingénierie Informatique Université catholique de Louvain Louvain – la – Neuve, le 15 Novembre 2009 i LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Remerciements Je tiens à remercier particulièrement mon promoteur, Yves Deville, qui m‟a dirigé mon travail de stage de fin d‟étude. Sa direction scientifique, ses judicieux conseils, ses pertinents commentaires et ses encouragements m‟ont aidé à aller jusqu‟au bout de ce travail. Je remercie aussi Pham Quang Dung pour ses propositions et son aide avec lesquels mon travail de stage a pu avancer plus rapidement.
Je tiens à remercier à Christine Sonon – professeur d‟Université de Lyon I - qui m‟a donné des conseils scientifiques sans lesquelles ce travail n‟aurait pas pu aboutir. Je tiens à remercier les membres du groupe Be-cool (Belgian Constraint Group) du Département d‟Ingénierie Informatique pour leur accueil, leur soutien et leur bonne humeur. Ma reconnaissance s‟adresse aussi aux professeurs de l‟IFI (Institut de la Francophonie pour l‟Informatique) qui m‟ont donné des connaissances et des guides utiles pour mon mémoire et qui m‟ont aidé à suivre la formation de master à L‟IFI. En fin, j‟exprime ma gratitude à ma famille pour leur soutien, leurs encouragements et leur aide qui m‟a permis de réaliser ce mémoire.
i LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nguyen Thi Hong Hiep Appariement multivoque de graphes Résumé Dans les applications de reconnaissance et de recherche d‟information, la mesure de similarité entre des objets joue un rôle clé. Lorsque les objets sont présentés sous forme de graphes, ce problème se transforme en mesure de similarité entre des graphes. En fait, à cause de la différence au niveau de modélisation des objets, chaque sommet d‟un graphe correspond peut-être à plusieurs sommets de l‟autre graphe et inversement. Le matching multivoque de graphes peut résoudre ce problème en permettant de mettre en correspondance un sommet d‟un graphe avec plusieurs sommets de l‟autre.
En utilisant une mesure de similarité pour formuler ce problème en problème d‟optimisation dont la fonction objectif est cette mesure de similarité, le problème original de la recherche du meilleur appariement entre deux graphes se transforme en une recherche d‟un appariement maximisant la fonction objectif. Malheureusement, l‟appariement multivoque de graphes est un problème NP-complet impossible d‟être résolu par un algorithme polynomial. Donc, la recherche locale est une approche alternative intéressante car permettant d‟obtenir une solution approchée en temps polynomial. Elle ne garantit pas toujours le résultat globalement optimal mais donne des solutions acceptables.
En explorant l‟espace de recherche de voisin en voisin, les algorithmes de recherche locale permettent d‟améliorer petit-à-petit la qualité de solution et dirige la recherche vers l‟optimum global. Dans ce rapport, nous présentons trois algorithmes de recherche locale : la recherche gloutonne, la recherche taboue et la recherche taboue réactive où la fonction objectif est de maximiser la similarité entre les graphes. Ces trois algorithmes sont implémentées en COMET – un environnement développé pour la recherche locale et pour la programmation par contraintes. Dans la section résultats, nous comparons la qualité de ces trois algorithmes.
Nous évaluons aussi l‟efficacité de la recherche locale pour le problème d‟appariement multivoque de graphes en montrant la qualité de la meilleure solution trouvée et le temps d‟exécution. ii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nguyen Thi Hong Hiep Appariement multivoque de graphes Abstract The similarity measurement between objects plays a key role in the recognition applications and the information retrieval. When the objects are presented as graphs, this problem turns into a similarity measurement between the graphs. In fact, each node of a graph may correspond to many nodes of the other graph.
This can only be modeled by multivalent graph matching allowing to matching a node of a graph with several nodes of the other graph. By using the similarity measure [1] as the objective function of an optimization problem, the original problem changes from finding the best match between two graphs to the search of a matching maximizing the objective function. Unfortunately, multivalent graph matching is a NP-hard problem and cannot be solved by an algorithm in polynomial time. Therefore, local search is a good alternative approach to resolve this problem in polynomial time.
It does not always find the globally optimal result, but gives acceptable solutions. By exploring the search space from neighbor to neighbor, the local search algorithms can progressively improve the quality of the solution and leads the search to the global optimum. In this report, we present three local search algorithms: greedy, tabu and reactive tabu search implemented in Comet – a programming environment developed for local search and constraints programming. In the result section, we will compare the quality of these three algorithms one to another.
We evaluate also the efficiency of the local search for multivalent graph matching by relying on the possibility to get to the best solution, the quality of the base solution and the execution time. iii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nguyen Thi Hong Hiep Appariement multivoque de graphes Table de matières Remerciements. iii Table de matières. iv Liste des figures.
vi Liste des tableaux. Contexte et problématique. Environnement de stage. 5 Chapitre 2 : Appariement multivoque de graphes.
Introduction aux graphes. Graphes orientés étiquetés. Appariements de graphes étiquetés. État de l’art et complexité des problèmes d’appariement de graphes.
Mesure de similarité. Similarité de graphes par un appariement. Similarité de graphes. 20 Chapitre 3 : Recherche locale et Comet.
Composant de la recherche locale. 25 iv LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nguyen Thi Hong Hiep Appariement multivoque de graphes 3. Sélecteur du voisin. Les stratégies méta-heuristiques.
Choix de Comet. Architecture de Comet. Le programme de Comet. Algorithmes de recherche locale appliqués aux problèmes d’appariement multivoque de graphes.
Modèle du problème. Algorithmes de recherche locale. Recherche taboue réactive. Expérimentation et évaluation.
Instances de test. Cas de test. Résultats expérimentaux et évaluation. Résultats et évaluation.
67 v LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nguyen Thi Hong Hiep Appariement multivoque de graphes Liste des figures 1 - Figure 2. Modélisation d’un objet en graph orienté étiqueté *1+. Un appariement entre deux graphes [1]. Appariement multivoque de graphes présenté étape par étape.
Variation de la fonction objectif dans l'espace de recherche. Espace de recherche représentée en arbre. Processus de la recherché locale. Illusion d'une boucle au cours de la recherche et de la liste taboue.
Architecture de Comet [05]. Illustration du problème n-reines de Comet. Une solution du problème d'appariement multivoque de graphes. Voisinage d'un appariement.
Diagramme de l'algorithme glouton. Évolution de la recherche par l’algorithme glouton. Diagramme de l'algorithme tabou. Modèle de la détection des redondances des solutions.
Un modèle de fonction de hachage. Diagramme de l'algorithme tabou réactif. Processus de la détection des redondances des solutions. Comparaison sur le temps pour trouver la meilleure solution.
Comparaison sur la qualité de la meilleure solution trouvée. Reconnaissance de scènes par l’appariement multivoque de graphes. 66 vi LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nguyen Thi Hong Hiep Appariement multivoque de graphes Liste des tableaux Tableau 4. Base de données à tester.
Cas de test. Résultats d’appariement avec le poids d’éclatement w = 1. Résultats de l’algorithme tabou réactif avec le poids d’éclatement w = 1. Résultats de l’algorithme tabou réactif avec le poids d’éclatement w = 3.
63 vii LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Motivation L‟appariement de graphes est un problème fondamental en reconnaissance des formes. Ce problème est utilisé dans plusieurs applications de vision par ordinateur. L‟appariement univoque est moins adaptatif que l‟appariement multivoque.
Ce premier n‟est pas capable de répondre à l‟hétérogénéité dans la segmentation d‟images où chaque image est représentée par un graphe. En fait, une région de l‟image correspond peut- être à plusieurs régions de l‟autre image car certaines images sont sur-segmentées tandis que certaines autres sont sous-segmentées. Cependant, le matching univoque n‟autorise d‟apparier chaque sommet d‟un graphe (région d‟image) qu‟avec un seul sommet de l‟autre graphe (région de l‟autre image). Le matching multivoque de graphes résout ce problème en permettant d‟apparier un sommet d‟un graphe avec plusieurs sommets de l‟autre.
Il devient plus adaptif et est adapté dans différentes applications. Vu l‟importance de ce problème, je l‟ai choisi comme sujet d‟étude de mon stage. L‟appariement multivoque de graphes est un problème NP-difficile et plus difficile que le problème d‟appariement univoque. Par conséquent, il existe peu d‟algorithmes connus dans la littérature résolvant ce problème et en particulier aujourd‟hui encore, aucun algorithme efficace pour le résoudre n‟a été proposé.
Dans ce contexte, la mesure de similarité proposée par Pierre-Antoine Champin et Christine Solnon [1] apparait comme une solution intéressante pour transformer ce problème NP-difficile en un problème d‟optimisation (le meilleur appariement est celui qui maximise la fonction objectif) résoluble en temps polynomial par une technique de recherche locale. Bien entendu, cette approche de recherche locale ne garantit pas de trouver l‟optimum global, mais permet d‟obtenir de bons résultats. Grâce à ces raisons, j‟utilise la mesure de similarité [1] pour formuler le problème original en un problème d‟optimisation dont la fonction objectif est la fonction de similarité et choisis 3 algorithmes approchés de recherche locale pour résoudre ce problème. 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nguyen Thi Hong Hiep Appariement multivoque de graphes La qualité des algorithmes de recherche locale dépend de plusieurs facteurs comme la stratégie de limitation l‟espace de recherche, la définition du voisinage d‟une solution, les critères pour choisir des candidats à chaque étape, la stratégie heuristique/méta- heuristique pour guider la recherche d‟échapper l‟optimum local et d‟arriver l‟optimum global le plus tôt possible.
Parmi les différents algorithmes de recherche local, nous en avons choisi trois : glouton, tabou et tabou réactif. Ceci nous permettra de les comparer et de déterminer lequel est le meilleur algorithme pour résoudre le problème d‟appariement multivoque de graphes. Contexte et problématique Le problème d‟appariement multivoque de graphes reste un problème ouvert car il est un problème NP-difficile. Il y a donc aucun algorithme générique efficace pour le résoudre, malgré son rôle important dans plusieurs applications de vision par ordinateur.
C‟est aussi difficile de l‟utiliser dans les applications en temps réel sur internet à cause de sa complexité exponentielle. Il est donc nécessaire d‟étudier ce problème et de chercher des algorithmes pouvant le résoudre en temps polynomial, même de manière approchée. Le problème de matching de graphes vise à chercher le meilleur appariement entre deux graphes étiquetés donnés qui accouple le plus de sommets et d‟arrêtes ayant la même étiquette dans deux graphes. En utilisant la fonction de similarité proposée par Pierre- Antoine Champin et Christine Solnon [1] comme fonction objectif pour formuler ce problème en un problème d‟optimisation, la recherche du meilleur appariement revient donc à chercher l‟appariement qui maximise la fonction objectif en utilisant la recherche locale.
Les algorithmes de recherche locale n‟explorent qu‟une seule partie de l‟espace de recherche en se déplaçant de voisin en voisin pour améliorer petit à petit la qualité de la solution. Les stratégies heuristiques/méta-heuristique sont intégrées dans la recherche pour diriger la recherche vers l‟optimum global. En fait, le problème d‟appariement basant sur la mesure de similarité [1] travaille avec des graphes étiquetés mais nous pouvons aussi l‟appliquer avec des graphes non- 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nguyen Thi Hong Hiep Appariement multivoque de graphes étiquetés dont tous les sommets et les arêtes sont considérées comme les composants ayant la même étiquette. Lorsque les graphes à apparier sont de grandes tailles, c‟est difficile déterminer si une solution est l‟optimum global ou non.