Faculté des sciences

2(CREM) : une méthode de reconnaissance structurelle de documents complexes basée sur des patterns bidimensionnels

Robadey, Lyse ; Ingold, Rolf (Dir.) ; Bapst, Frédéric (Codir.)

Thèse de doctorat : Université de Fribourg : 2001 ; No 1364.

Cette thèse s'inscrit dans la problématique de la reconnaissance de documents imprimés. Nous avons étudié les systèmes existants, tout d'abord de manière générale en distinguant les systèmes de reconnaissance de la structure physique des systèmes de reconnaissance de la structure logique. Puis, nous nous sommes focalisés sur les méthodes adaptées aux documents complexes ainsi que... Plus

Ajouter à la liste personnelle
    Résumé
    Cette thèse s'inscrit dans la problématique de la reconnaissance de documents imprimés. Nous avons étudié les systèmes existants, tout d'abord de manière générale en distinguant les systèmes de reconnaissance de la structure physique des systèmes de reconnaissance de la structure logique. Puis, nous nous sommes focalisés sur les méthodes adaptées aux documents complexes ainsi que sur les méthodes douées d’apprentissage. A la croisée de ces deux axes, nous n'avons rien trouvé et choisi d'apporter notre contribution. Des premières expériences, faisant appel à des méthodes simples, ont été appliquées pour la reconnaissance de la structure physique des pages de journaux. Elles ont permis de mettre en évidence les problèmes spécifiques à l'analyse de documents à structures complexes, en particulier le problème de l'organisation bidimensionnelle de l'information. Fort de ces constatations, nous avons conçu 2(CREM), une méthode générale de classification d'objets s'appliquant particulièrement bien à la reconnaissance des objets qui constituent un document à structure complexe. En effet, 2(CREM) est douée d'apprentissage incrémental et prévoit la description et l'interprétation d'un objet en tenant compte des deux dimensions; un objet est modélisé en une configuration, un ensemble de caractéristiques se rapportant à l'objet et à son voisinage 2D. Les configurations sont alors comparées au modèle du document analysé qui comprend, pour chaque classe d'objets, un ensemble de configurations de référence appelées patterns. L'apprentissage du modèle se fait par extension (ajout d'un pattern dans la description de la classe) et spécialisation (ajout d'une caractéristique à tous les patterns d'une classe). 2(CREM) a été implémentée puis testées dans quatre des phases de la reconnaissance d'images de journaux à la reconnaissance de filets, la reconnaissance de cadres, la fusion des lignes de texte en blocs et l'étiquetage logique des blocs de texte. Le modèle, les données et les résultats intermédiaires et finaux ont été représentés en XML. Nos expériences ont confirmé le choix de XML comme standard de représentation des données dans le domaine de la reconnaissance de documents. La méthode a été appliquée sur plusieurs exemplaires du Los Angeles Times. L'étiquetage logique a été testé sur 29 pages comprenant en tout 977 objets. Après environ 150 opérations d'étiquetage élémentaire par l'utilisateur, 86% des objets ont été classés correctement, 7% n'ont pas été reconnus, 5% étaient en conflit et 2% ont été confondus avec une autre classe. Ainsi, nous estimons avoir démontré la pertinence de 2(CREM) comme méthode de reconnaissance de structure complexes de documents qui soit douée d'apprentissage incrémental.
    Summary
    This thesis addresses the question of printed document recognition. We studied existing systems, first in a general context, by making the distinction between physical and logical structure recognition systems. Then, we focused on methods specific for complex layout documents and on methods having a learning aptitude. Since there do not seem to exist learning systems which are able to recognise complex layout documents, we chose to work in this direction. First experiments, using simple methods, were applied for the physical structure recognition of newspaper pages. They have revealed the specific problems of the complex layout document analysis, in particular the problem of bidimensional organisation of information. With this constatation in mind, we conceived 2(CREM), a general method for object classification that is specially suited for the recognition of objects that form a complex layout document. Indeed, 2(CREM) has the ability to learn incrementally and enables the description and interpretation of an object in two dimensions; an object is modelled by a configuration, i.e. a characteristic set related to the object and to its bidimensional neighbourhood. The configurations are then compared to the analysed document model which includes, for every object class, a set of reference configurations called patterns. The system learns the model by extension (addition of a pattern to the class description) and by specialisation (addition of a characteristic to all the patterns of a class). 2(CREM) was implemented and then tested on four of the steps necessary in newspaper image recognition: the line segment recognition, the frame recognition, the merger of text lines in blocks and the logical labeling of text blocks. We represent the model, the data and the intermediate and final results by using XML. Our experience confirms the choice of XML as a standard for data representation in document recognition. The method was applied on several Los Angeles Times issues. The logical labeling has been tested on 29 pages which were composed of 977 objects in total. After around 150 elementary labeling operations by the user, 86% of the objects were correctely classified, 7% were not identified, 5% were in conflict and 2% were confused with another class. These results show that 2(CREM) is a relevant learning method for the recognition of documents with complex layout.