Fouille et classification de graphes. Application à la reconnaissance de symboles dans les documents techniques
Institution:
RouenDisciplines:
Directors:
Abstract EN:
This thesis brings a contribution to the design of a generic, adadtive and unsupervised system for document image understanding using graph mining and classification. The first part deals with the extraction of structural represesantations of document images. The second part proposes the searche of frequent subgraphs associated to graphic symbols. These are exploited to describe document images with a bag of symbol formalism. This representation is evaluated faced to classification and indexing tasks. The third part proposes to tackle the complexity problem of graph classification by using a dissimilarity measure which approximates the reference edit distance and by reducing the training set thanks to a prototype generation process based genetic algorithm. Evaluation have been performed on synthetic data and on graphic symbol recognition problems.
Abstract FR:
Cette thèse apporte une contribution à la définition d’un système générique, adaptatif et non supervisé pour l’interprétation d’images de document en utilisant des techniques de fouille et de classification de graphes. La première partie traite de l’extraction de représentations structurelles d’images de document. La seconde partie propose la recherche de sous-graphes fréquents associés à des symboles graphiques lesquels sont à la base d’une représentation des documents par sac de symboles. La pertinence de cette représentation est évaluée sur des tâches de classification et d’indexation. La troisième partie propose d’adresser le problème de la complexité de la classification de graphes par l’usage de mesures de dissimilarité approximant la distance d’édition et par la réduction de bases d’apprentissage par génération de graphes prototypes par algorithmes génétiques. Les évaluations portent sur des bases synthétiques ainsi que sur des problèmes de reconnaissance de symboles graphiques.