A Probabilistic Approach for Table of Contents Recognition
Une Approche Probabiliste pour la Reconnaissance des Sommaires
OPEN ACCESS
Document Analysis and Recognition consist in translating their images into an electronic form that can be reusable. The analysis extracts the document layout structure from its image, and the recognition assigns to the layout structure components their logical functions in the document. In this article, we present our work on recognition of a category of documents in which the logical structure is based on typographical tagging such as table of contents.We propose a perceptual approach that extracts these typographical tagging directly from document images. However, the structures of such documents are complex and variable.Their complexity can cause errors in the analysis output, which influence directly the recognition task, while their variability requires defining a generic form of logical structures and the related recognition tasks. Our goal is to consider the document structure recognition problem even though these difficulties occur.We developed a automatic recognition system based on a hybrid model combining a bayesian classifier and a probabilistic automaton.The classifier is responsible of drawing a correspondence between text blocks extracted from document images and basic logical entities, while the automaton deals with grouping these entities into a hierarchical logical structure.This hybrid model is built by semi-supervised learning based on knowledge provided by the user on the one hand, and the typographical properties of our documents, on the other hand.This system has been experimented for automatic indexing of tables of contents in periodicals and journals.The complexity and the variability of these documents allow us to show the efficiency of the approach.
Résumé
L'analyse et la reconnaissance des documents écrits consistent à traduire leurs images numérisées sous une forme électronique réutilisable. L'analyse permet d'extraire à partir de l'image d'un document une structure dite physique,tandis que la reconnaissance associe aux composants de la structure physique leurs fonctions logiques dans le document. Le travail présenté dans cet article porte sur la phase de reconnaissance de documents dont la structuration logique est caractérisée par des marquages typographiques tels que les sommaires ou les tables des matières. Nous proposons une approche perceptuelle qui se base sur l'extraction de ces marquages typographiques directement à partir des images des documents. Ces documents présentent cependant une structuration variable et complexe. La complexité pose des difficultés au niveau de la phase d'analyse et peut conduire à des erreurs dans les données présentées à la phase de reconnaissance. Quant à la variabilité,elle impose d'entreprendre une modélisation générique de la structure logique et du processus de reconnaissance associé. Notre objectif est d'aborder ce problème de reconnaissance en présence de ces difficultés. Nous avons développé un système de reconnaissance automatique basé sur un modèle hybride combinant un classifieur bayésien et un automate probabiliste. Le rôle du classifieur est la correspondance entre les blocs de texte extraits dans les images des documents et les entités logiques à un niveau de structuration de base,alors que l'automate permet de regrouper ces entités logiques sur plusieurs niveaux hiérarchiques reconstruisant ainsi toute la structure logique. Ce modèle hybride est construit par apprentissage semi-supervisé,en s'appuyant d'une part sur la connaissance fournie de manière interactive par l'utilisateur,et d'autre part sur les propriétés typographiques des documents considérés. Nous avons expérimenté le système proposé pour l'indexation de sommaires de revues. La complexité et la variabilité de la structuration de ces documents nous ont permis de montrer l'efficacité de l'approche développée.
Document analysis, document recognition, layout structure, logical structure, recognition, bayesian classifier, probabilistic automaton, typography, supervised learning.
Mots clés
Analyse de documents,reconnaissance de documents,structure physique,structure logique,classifieur bayésien,automate probabiliste,typographie,apprentissage supervisé.
[AEM] O. ALTAMURA, F. ESPOSITO and D. MALERBA, Transforming paper documents into XML with WISDOM++.
[Bela] A. BELAÏD, Recognition of table of contents for electronic library consulting.
[Belb] A. BELAÏD, Retrospective document conversion: application to the library domain.
[Bel94] A. BELAÏD, Cours INRIA: Le traitement électronique du document, pages 49-92. Collection ADBS, Aix-en-Provence, Octobre 1994.
[BZI97] R. BRUGGER, A. ZRAMDINI and R. INGOLD, Modeling documents for structure using generalized N-Grams. In 4th ICDAR: International Conference on Document Analysis and Recognition, volume 1, pages 56-60, Ulm, Germany, August 1997.
[DD95] A. DENGEL and F. DUBIEL, Clustering and Classification of Document Structure – A Machine Learning Approach –. In 3th ICDAR: International Conference on Document Analysis and Recognition,volume 2, pages 587-591, Montréal, Canada, August 1995.
[DH73] R. O. DUDA and P. E. HART, Pattern Classification and Scene Analyis. John Wiley and Sons, New York, 1973.
[Duf97] L. DUFFY, Recherche d'information logique dans les documents à typographie riche et récurrente, application aux sommaires. Thèse de doctorat, INSA de Lyon, Lyon, France, Décembre 1997.
[H+86] J. HIGASHINO et al.,A knowledge-based segmentation method for document understading. In 8th ICPR: International Conference on Pattern Recognition,volume 1, pages 745-748, Paris, France, October 1986.
[Har94] R. HARALICK, Document Image Understanding: A Geometric and Logical Layout. In CVPR'94: Computer Vision and Pattern Recognition,pages 385-390, Seattle, USA, June 1994.
[JR99] A. JACQUESSON and A. RIVIER, Bibliothèques et documents numériques: Concepts, composants, techniques et enjeux. Electre – Éditions du Cercle de la Librairie, Paris, 1999.
[JY98] A. K. JAIN and B. YU, Document representation and its Application to page decomposition. 20(3):294-308, 1998.
[LE99] F. LEBOURGEOIS and H. EMPTOZ, Document Analysis in Gray Level and Typography Extraction Using Character Pattern Redundancies. In 5th ICDAR: International Conference on Document Analysis and Recognition,pages 177-180, Bangalore, India, September 1999.
[Mic84] L. MICLET, Méthodes structurelles pour la reconnaissance de formes. Eyrolles, Paris, France, 1984.
[PLT92] W. IBA, P. LANGLEY and K. THOMPSON, An analysis of Bayesian classifiers. In Proceedings of the Tenth Annual Conference on Artificial Intelligence,pages 223-228, Menlo Park, CA, USA, 1992. AAAI Press.
[Ric89] F. RICHAUDEAU, Manuel de typographie et de mise en page. Éditions Retz, Paris, 1989.
[SB02] S. SOUAFI-BENSAFI, Contribution à la reconnaissance des structures des documents écrits: Approche probabiliste. Thesis, INSA de Lyon, France et Université Laval, Québec-Canada, 2002.
[T+82] J. TOYADA et al., Study of extracting Japanese newspaper article. In 6th ICPR: International Conference on Pattern Recognition,volume 2, pages 1113-1115, Munich, Germany, October 1982.
[TL96] S. L. TAYLOR and M. LIPSHUTZ, Document understanding system for multiple document representations. pages 155-171, Malvern, Pensylvania, October 1996.
[TYCS93] Y. Y. TANG, C.D. YAN, M. CHERIET and C. Y. SUEN, Handbook of Pattern Recognition and Computer Vision,chapter 3.6: Automatic analysis and understanding of documents, pages 625-654. World Scientific Pub., Singapore, 1993.
[Wal99] H. WALISCHEWSKI, Automatic Acquisition for Spatial Document Interpretation. In 5th ICDAR: International Conference on Document Analysis and Recognition,pages 317-320, Bangalore, India, september 1999.
[WH97] T. WATANABE and X. HUANG,Automatic Acquisition of Layout Knowledge for Understading Business Cards. In 4th ICDAR: International Conference on Document Analysis and Recognition, volume 1, pages 216-220, Ulm, Germany, 1997.
[YTS93] C. L. YU, Y. Y. TANG and C. Y. SUEN, Document Architecture Language (DAL) Approach to Document Processing. In 2th ICDAR: International Conference on Document Analysis and Recognition, pages 103-106, Tsukuba Science City, Japan, October 1993.