Mémoire de fin d’étude Fouille de graphes et Classification de graphes Application au "Symbol Spotting" Réalisé par : Nguyen Quoc Toan Responsable du stage : Jean-Marc Ogier Jean-Christophe Burie Romain Raveaux Ce stage a été réalisé au département Pascal de Laboratoire Informatique, Image et Interaction, Université de la Rochelle La Rochelle, France, Novembre 2009 TIEU LUAN MOI download : skknchat@gmail.com Table des matières 1 Introduction.2 Objectif et contribution du stage.3 Environnement de stage.4 Plan du document.1 Définition de graphe.2 Correspondance de Graphe.3 Graphe de distance.2 Distance entre signatures de graphe «graph probing ». 17 3 Etat de l'art.1 Les méthodes de construction de graphe .2 Les methodes de mise en correspondances des graphes.3 Récaputulation des méthodes. 24 4 Une méthode de mise en correspondance de graphes fondée sur l’assignement de sous- graphes.1 Définition : Décomposition en sous-graphes.2 La correspondance de sous-graphes.3 Le coût de fonction (c) pour la correspondance des signatures.4 Sous graphe de longueur ι.5 Construction de matrice de coûts. 28 5 Représentation de l’information contenue dans une image.1 Constitution de l'ensemble des nœuds.2 Extraction des composantes connexes.3 Étiquetage des composantes connexes.1 Extraction de caractéristiques .2 Statistique de la forme .3 Classification non supervisée des caractéristiques morphologiques.4 Organisation de l’information : Construction d’un Graphe de voisinage.1 Relations d'Allen bidimensionnelles.2 Intervalle basé sur les distances entre deux régions.1 Test en classification.2 Bases de tests.1 Pour la classification.2 Pour le Symbol Spotting.1 Test en classification.
54 NGUYEN Quoc Toan – Promotion 13 Page 2 TIEU LUAN MOI download : skknchat@gmail.com REMERCIEMENTS Je voudrais tout d'abord remercier professeur Jean-Marc Ogier, Jean-Christophe Burie, mes responsables de stage, de m'avoir accueillie au sein de l’équipe du projet ALPAGE du Laboratoire L3i (Laboratoire Informatique, Image et Interaction) de l’Université de la Rochelle et de m’a donné l’environnement de travail très chaleureuse pendant toute la durée du stage. Je remercie également Romain Raveaux pour ses conseils, son explication très clairement des nouveaux concepts, ses aides, ses commentaires et ses discussions qui ont fait progresser mon travail. Je lui suis reconnaissant d’avoir toujours été disponible et agréable. Je voudrais remercier tout le personnel du laboratoire L3I et particulièrement l’équipe du projet ALPAGE pour leur accueil chaleureux.
Je voudrais aussi adresser mes sincères remerciements à tous les professeurs de l’IFI pour leurs enseignements et les cours intéressants qu’ils m’ont donné pendant mes études au niveau master. Finalement, je voudrais remercier ma famille, mes parents et mes amis qui sont toujours près de moi et m’ont apporté le courage dans les moments difficiles de ma scolarité à l’IFI. NGUYEN Quoc Toan – Promotion 13 Page 3 TIEU LUAN MOI download : skknchat@gmail.com Résumé Reconnaissance des symboles est un domaine de recherche visant le développement d'algorithmes et de techniques et il y a une nombreuse méthode de reconnaissance de graphiques ont été développées pour la reconnaissance des symboles graphiques. Le problème « Symbole Spotting » est comme la localisation d'un ensemble de régions d'intérêt d'un document image, qui sont susceptibles de contenir une instance d'un certain symbole demandé sans le reconnaître explicitement.
Nous présentons donc dans ce mémoire un processus d’extraction et d’organisation de l’information contenue dans une image afin de la structurer sous forme d’un graphe pour tenir compte de la spécificité que contiennent les documents techniques. Chaque nœud du graphe représente une composante connexe dans l’image de document, ces nœuds sont étiquetés automatiquement par l’algorithme de clustering « k-Mean ». Ce dernier utilise des descripteurs de formes extraits des composantes connexes. La relation entre deux composantes connexes est matérialisée dans un graphe de « voisinage » par un arc étiqueté automatiquement en utilisant les relations d'Allen bidimensionnelles ou la distance entre composantes connexes.
Nous proposons une méthode de mise en correspondance de graphes fondée sur l’assignement de sous-graphes de longueur l. Nous proposons aussi une définition de sous- graphe de longueur l. Le problème de reconnaissance des symboles devient donc de trouver les sous-graphes les plus similaires au graphe symbole donné en requête. Nous extrayons le graphe de plan en des sous-graphes de longueur l.
Le résultat de notre application est ensemble de sous-graphes isomorphisme que la distance entre les sous-graphes et le graphe de symbole est inférieur une valeur seuil. Afin d’évaluer la classification de graphes, nous utilisons un classifieur de type K-NN pour évaluer la performance de notre méthode de mise en correspondance de graphes fondée sur l’assignement de sous-graphes. NGUYEN Quoc Toan – Promotion 13 Page 4 TIEU LUAN MOI download : skknchat@gmail.spotting Abstract Symbol Recognition is a research area for the development of algorithms and techniques, a lot of method of graphics recognition are developed for the recognition of graphic symbols. The problem "Symbol Spotting" aims to find the locations of a set of regions interest in a document image, which may contain an instance of a symbol without explicitly recognize.
We therefore present in this paper a process for extracting and organizing information in an image to the structure of a graph for the specificity technical documents. Each graph node is a connected component. These nodes are labeled automatically by the clustering algorithm "k-means”. We extract the connected components using shape descriptors.
We use the family of graph "Neighborhood based on k nearest neighbors" to build edges and they are automatically labeled by the Bi-dimensional Allen Algebra or the distance between regions. We propose a method for mapping graph-based assignment of subgraphs of length l. We also propose a definition of subgraph of length l. The symbols recognition problem is like to find subgraphs which are the nearest similar to the graph of symbol.
We extract the graph of technical documents in many subgraphs of length l. The recognition task consists of finding all subgraphs isomorphism which the distance between sub-graphs and symbol graphs is less than a certain threshold. To test the classification of graphs based on graph prototypes, we use a K-NN classifier in order to evaluate our method for mapping graph-based assignment of subgraphs of length l by the rate of recognition.spotting NGUYEN Quoc Toan – Promotion 13 Page 5 TIEU LUAN MOI download : skknchat@gmail.spotting Liste des figures Figure 1: La distance entre signatures de graphe GP, (a) les graphes non orienté, sans étiquetage, (b) les graphes orientés, sans étiquetage, (c) les graphes étiquetés, orientés.16 Figure 2: La distance entre deux graphes selon ED et GP, (a) les graphes non orienté, sans étiquetage, (b) les graphes orientés, sans étiquetage, (c) les graphes étiquetés, orientés.17 Figure 3 : Graphiques attribués relationnelle, chaque nœud est comme une ligne segmentée, un arcs établis la relation d’adjection entre deux segmentations (source[14]). 19 Figure 4: Chaque nœud est une région fermée.
L’arc lie deux régions adjacentes (source[32]) .19 Figure 5: Graphe transaction, source [33].20 Figure 6: vectorisation de quadrilatères, source [45]. 20 Figure 7: La zone influence de quadrilatère et le graphe correspondant, source [45]. 21 Figure 8: exemple de construction d’un graphe basé sur les relations topologique, source [35] .21 Figure 9: La décomposition en sous-graphes. p1, p2, p3, p4 est des sous-graphes d’extractions de longueur 1 qui associés à chaque nœuds du graphe G.
25 Figure 10: à partir deux graphes G1, G2 (a), on extrait des sous-graphes de longueur 1 (a), (b). Le graphe bipartite complet Gem obtenu par P1 et P2.28 Figure 12: un exemple de la correspondance de graphe, (a), (b) les sous-graphes d’extraction de longueur 1, (c) la correspondance de sous-graphe selon distance d’édition (ED). 30 Figure 13: Analyse des composantes connexes. 31 Figure 14: Mesure de l'élongation, comme le ratio de la longueur-largeur.
33 Figure 15:Graphe des k plus proches voisins (a) les composantes connexes, (b) k=2, (c) k=134 Figure 16: Jeu restreint de relations d'Allen.35 Figure 17: (a) deux composantes connesxes, (b) détermination du système de coordonnées lié aux. 35 Figure 18: L’image à gauche : représentation de la distance entre deux composantes connexes, d-max = 39. Le graphe droit obtenu par n = 10 (n est le nombre d’intervalles). 36 Figure 19: La vérité terrain pour un plan.
41 Figure 20: Les exemples de lettres A, M, K et Z: l'origine et la déformation des niveaux faible, moyen et élevé (de gauche à droite). 42 Figure 21 : Illustration du composant d’une molécule. 43 Figure 22:la comparaison le temps de calcul sur PMDED et PMDGP. 45 Figure 23: La courbe de précision, rappel selon la méthode Hu_Dist.
47 Figure 24: La courbe de précision, rappel selon la méthode Hu_ Allen.48 Figure 25: La courbe de précision, rappel selon la méthode Shape_Allen.49 Figure 26: La courbe de précision, rappel selon la méthode Shape_Dist. 50 Figure 27: Les meilleurs courbes de chaque méthode d'étiquetage.spotting NGUYEN Quoc Toan – Promotion 13 Page 6 TIEU LUAN MOI download : skknchat@gmail.spotting Liste des tableaux Table 1: Matrice des coûts de G1, G2.13 Table 2: étape 1 : réduction des lignes. 13 Table 3: étape 2 : réductions des colonnes.13 Table 4: étape 3 : déterminer le nombre minimal de lignes sur les lignes, colonnes pour couvrir tous les zéros.14 Table 5: étape 4 : Trouver la cellule de valeur minimum non-couverte par une ligne. 14 Table 6: étape 4 : recaler la valeur pour les cellules basées sur cette valeur minimum .14 Table 7: étape 4 : déterminer le nombre minimal de lignes.14 Table 8: étape 5 : déterminer la solution optimale.15 Table 9: le coût minimal de G1, G2.15 Table 10 : La matrice de coûts entre deux graphes G1, G2.
29 Table 11: Résumé des données de graphes des caractéristiques.43 Table 12: Les taux de reconnaissance pour deux méthode PMDED et PMDGP. 45 Table 13: La valeur moyenne de précision, rappel selon la méthode Hu_Dist. 46 Table 14 : La valeur moyenne de précision, rappel selon la méthode Hu_Allen. 47 Table 15: La valeur moyenne de précision, rappel selon la méthode Shape_Allen.
48 Table 16: La valeur moyenne de précision, rappel selon la méthode Shape_Dist.49 Table 17: La comparaison des méthodes d'étiquetage des noeuds, des arcs.50 Table 18: Comparaison nos résultats avec les résultats de Marçal [51].spotting NGUYEN Quoc Toan – Promotion 13 Page 7 TIEU LUAN MOI download : skknchat@gmail.1 Problématique Reconnaissance de symbole est une des applications importantes dans le domaine de la reconnaissance de formes qui est appliqué dans plusieurs domaines comme l'architecture, la cartographie, l'électronique, la mécanique etc. En raison des types de documents graphiques sont trop large, chacune d’entre eux possèdent un ensemble caractéristique de symboles propres, il n'est pas facile de trouver une définition précise d'un symbole. Dans une manière très générale, un symbole peut être défini comme une entité graphique avec un sens particulier dans le contexte d'un domaine d'application spécifique. Il y a un grand nombre d'approches ont été proposées pour la reconnaissance des symboles.
Chacune d’entres elles possèdent des propriétés qui lui sont propres et ne peut s’appliquer qu’à certains contextes, réunissant certaines conditions. Dans notre cas, nous utilisons la méthode basées sur le graphe pour représenter les images de documents techniques et de symbole demandé en des graphes. Chaque nœud du graphe représente une composante connexe dans l’image de document. La relation entre deux composantes connexes est matérialisée dans un graphe de « voisinage ».
Le problème de la reconnaissance de symbole est tourné en une question d’isomorphisme de sous graphe, afin de trouver les sous-graphes qui correspondent à des symboles graphiques.2 Objectif et contribution du stage L'objectif de stage est dans un premier temps d'étudier le problème de la correspondance de graphes « Graph Matching », les mesures de calculer la distance entre deux graphes. Et puis, nous proposons une méthode de mise en correspondance de graphes fondée sur l’assignement de sous-graphes de longueur l. Ensuite nous construisons un protocole de test en classifications basé sur les prototypes de graphes en utilisant la méthode K plus proche voisins (K-NN) basé sur notre méthode de mise en correspondance de graphes. Enfin, nous créons une application de type reconnaissance de symbole basé sur le graphe pour trouver toutes les localisations d’un symbole dans un plan donné.