Fouille de graphes et Classification de graphes Application au "Symbol Spotting"

• Main Authors: OGIER, Jean-Marc, BURIE, Jean-Christophe, RAVEAUX, Romain, NGUYEN, Quoc Toan
• Format: Theses and Dissertations
• Language: French
• Published: 2015
• Online Access: http://repository.vnu.edu.vn/handle/VNU_123/340
• Institution: Vietnam National University, Hanoi

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 noeud du graphe représente une composante connexe dans l’image de document, ces noeuds 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 sousgraphe 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.