% -*- Document-Type: LaTeX; Master-File: cours_inria.tex -*- 
\documentclass[a4paper,11pt]{article}
%% Je suppose par defaut qu'on peut avoir de l'ISO-Latin-1 dans le document
\usepackage[latin1]{inputenc}% format standard, centré
	\setlength{\oddsidemargin}{2mm}
	\setlength{\evensidemargin}{2mm}
	\setlength{\textwidth}{154mm}
	\setlength{\textheight}{225mm}
	\setlength{\topmargin}{-3mm}
	\setlength{\unitlength}{1mm}
% 1 mm entre chaque paragraphe
	\setlength{\parskip}{1mm}
        \input{psfig}	

\title{Analyse et reconnaissance de documents}
\author{A. Bela\"{\i}d\\
{\sc Crin-Cnrs \& Inria Lorraine}\\
Campus Scientifique, Bât. {\sc loria}, B.P. 239\\
54506 Vand{\oe}uvre-Lès-Nancy Cedex\\
Email~: abelaid@loria.fr}
\date{}

\begin{document}


\newfont{\fonte}{cmbx8}

\maketitle

\bibliographystyle{alpha3}

{\small \tableofcontents}

\normalsize

\section{Introduction}

L'objectif de l'analyse et de la reconnaissance de documents ({\sc
ard}) est de convertir l'information présentée sur un support papier
sous une forme symbolique équivalente, réutilisable par ordinateur. Le
résultat obtenu doit permettre la relecture de l'information initiale
et son éventuelle réimpression suivant des formats différents. Il
s'agit en quelque sorte de ``reverse engineering'' de la production
de documents. Ainsi, il apparaît donc souhaitable, à des fins
d'archivage, de tri, d'aiguillage de l'information, ou encore pour
pouvoir modifier un document dont on ne possède qu'une version papier,
de concevoir des systèmes de reconnaissance automatique de documents
écrits.  

L'enjeu  représenté par la conception de tels systèmes est
considérable. L'avènement de systèmes bureautiques conviviaux et bon
marché a déjà conduit plusieurs sociétés et administrations à se munir
de premiers systèmes de conversion, ne serait-ce dans un premier
temps, que d'un lecteur optique de caractères ({\sc
ocr}\footnote{Optical Characater Recognition}) facilitant
l'intégration des documents sur papier dans ces systèmes. Par
ailleurs, certains 
services sont aujourd'hui contraints à une utilisation électronique de
leur documentation afin de maîtriser son évolution et sa gestion.
L'exemple le plus marquant est sans doute celui des bibliothèques qui
sont confrontées à la conversion rétrospective de leurs
catalogues dans un format bibliographique lisible et accessible à
tous~\cite{belaid93b}. L'organisation informatique des notices conduit
à disposer d'enregistrements accessibles par rubrique~: {\it auteur},
{\it revue}, {\it mot-clé}, etc. facilitant ainsi la recherche
bibliographique. De plus, cela permet sans doute d'accroître, de
faciliter et d'harmoniser les échanges de fonds documentaires entre
les bibliothèques elles-mêmes. Un autre exemple où la conversion
papier est fortement souhaitée est sans doute la lecture et la mise à
jour de plans techniques dans les bureaux 
d'études~\cite{vaxiviere92a,tom87}. Ces plans sont 
d'une telle complexité que l'absence aujourd'hui d'une version
électronique peut contraindre ces bureaux d'étude à les abandonner car
leur saisie manuelle est trop coûteuse. Citons enfin d'autres
exemples où l'automatisation de la lecture documentaire peut conduire
à un allègement de tâches humaines pénibles et fastidieuses comme par
exemple le tri postal par analyse de la zone adresse et identification
du code
postal~\cite{srihari87b,palumbo92a,dow90,hull87a,wan86,oriot92b},
la saisie de chèques bancaires par localisation et reconnaissance du
montant littéral~\cite{gilloux92a,leroux91a}, la 
comptabilisation automatique de formulaires par localisation et
reconnaissance de montants~\cite{Yuan91a}, etc. 

Ainsi, il y a un besoin réel de systèmes d'analyse de documents
qui pourraient être utilisés comme des interfaces intelligentes entre le
papier et le média électronique. Cependant, malgré les progrès
techniques enregistrés par les matériels de saisie (scanners) et les
logiciels de manipulation d'images, la reconnaissance de documents est
réduite de nos jours à quelques tâches d'identification.
L'interprétation et la structuration de l'information papier reste
encore un privilège humain et son automatisation demeure un problème
ouvert. Cela est dû d'une part au grand volume de documents à lire et
surtout à la diversité de leur contenu et présentation. L'état de
l'art dans ce domaine de 
recherche~\cite{belaid92b,belaid92a,srihari86a,baird92a,gorman92a}
montre bien qu'il est possible de trouver des systèmes analysant des
classes spécifiques de documents pour lesquels il est possible de
décrire la typographie, la présentation et le contenu. Ainsi, le
challenge des années 90 est d'augmenter la performance des systèmes
existants et de diversifier leur action afin de les rendre de plus en
plus autonomes et donc capables de s'adapter rapidement à de nouvelles
applications.  

Nous allons d'abord présenter l'état de l'art dans ce domaine en
décrivant brièvement les techniques développées puis nous présenterons
le système {\sc graphein} avec deux applications typiques, l'une
consacrée à la reconnaissance de la macro-structure d'articles
scientifiques et l'autre à la micro-structure de notices
bibliographiques.

\section{Reconnaissance de documents}

\subsection{Les données du problème}

Il existe plusieurs obstacles qui freinent le développement d'un système
général d'{\sc ard} parmi lesquels on trouve~:

~~\\
{\it Le support physique}

Un document est une information écrite ou illustrée sur un support
physique (papier). Sa lecture nécessite d'abord de la convertir 
en une information numérique intelligible qui sera ensuite analysée
par le système. L'opération de conversion relève du traitement de
l'image. Elle consiste, entre autres, à localiser chaque caractère
dans l'image du document, puis a` retrouver le symbole correspondant
à sa forme et ceci malgré la complexité de la structure du
document (colonnée, illustrée, etc.) et surtout malgré les
perturbations dues à la scannérisation (bruit du capteur, inclinaison
du papier, mauvaise résolution, etc.). De plus, l'information utile
n'est pas toujours bien distincte\/; elle peut être mélangée avec d'autres
médias ou écrite sur un fond dont il faut d'abord se séparer. 

~~\\
{\it La dualité physique-logique}

Une page d'un document représente une structure
physique, alors que le but de la reconnaissance est d'arriver à
trouver une description {\it logique} du document la plus proche
possible de la pensée de son auteur et du formalisme utilisé par les
outils d'édition. Pour cela, l'analyse de document doit conduire à
résoudre deux problèmes~:
\begin{itemize}
\item convertir l'image du document en une structure intermédiaire
physique faisant ressortir au mieux les entités du document en se
basant dans un premier temps sur leur aspect typographique;
\item passer de la structure physique à la structure logique en
identifiant le contenu des entités physiques extraites, puis en
essayant de retrouver des liens logiques entre ces entités. Ceci
consiste à retrouver en quelque sorte la ``sémantique'' du document en
découvrant à la fois l'ordre de lecture des entités et le sens de leur
contenu.
\end{itemize}

~~\\
{\it Les aléas de la segmentation}

Le document est analysé en termes d'association d'entités homogènes
d'une certaine granularité de type {\it région, bloc, ligne} et
{\it symbole}. Ces entités sont extraites par des algorithmes de
segmentation utilisant des seuils de paramètres correspondant à
des mesures d'espacement ou de taille. Ces seuils sont généralement
fixes et ne peuvent être facilement adaptés à chaque document, d'où le
risque d'une mauvaise segmentation conduisant à une structure ne
correspondant pas exactement à la structure recherchée. Ceci conduit
souvent à des problèmes de {\it sur-segmentaion} (fragmentation des
entités en entités plus petites) ou de {\it sous-segmentaion} (fusion
des entités en entités plus grandes) et la tâche de la
reconnaissance doit consister à rétablir le bon niveau de
granularité permettant de retrouver la structure du document.

\subsection{Les documents structurés}

La reconnaissance de documents se limite actuellement aux documents
structurés pour lesquels on dispose d'informations sur la nature de
leur contenu ainsi que sur leur structure. Edités souvent par des
traitements de texte, ces documents ont une structure ``normalisée'',
c'est-à-dire pouvant s'exprimer en termes d'objets typographiques et de
relations à l'aide d'une grammaire formelle~\cite{qui87,andre89a}.
L'analyse et la reconnaissance de documents structurés revient alors à
faire une analyse structurelle ou syntaxique de la structure à partir
d'indices extraits de l'image du document et de la grammaire
représentant la structure générique de la classe de documents étudiés. 

\subsubsection{Types de structures}

La structure exprime la connaissance que l'on a sur l'organisation et
la présentation du document sur le support papier. Bien que cette
notion soit subjective et qu'elle ne possède pas de définition
générale~\cite{brown89a}, on peut néanmoins distinguer deux types de
structures~: la {\it structure physique} et la {\it structure
logique}. 

La {\it structure physique} décrit l'organisation du document dans les
pages. Elle est représentée de manière symbolique à l'aide d'objets
et de relations entre eux. Les objets sont des régions 
typographiquement homogènes contenant les entités textuelles. On
distingue les objets {\it composites} qui 
peuvent se décomposer en éléments plus petits (par exemple, l'objet
{\it colonne} se décompose en plusieurs {\it blocs de texte}) et les
objets {\it de base} qui contiennent des objets indissociables (comme
les figures ou les composantes graphiques dans un documents technique) ou des
entités logiques ``complètes'' (comme les paragraphes, les items, les
titres, etc.). Les relations décrivent à la fois les liens de décomposition
hiérarchique des objets et leur position absolue et relative dans la
page. Notamment, dans un article scientifique, la structure doit
situer la région du titre {\it en haut} de la zone des auteurs, et
{\it en-dessous} de la note de haut de page. 

La {\it structure logique} correspond à la description du contenu en 
vue de son interprétation. Elle est également décrite sous la forme
d'objets symboliques et de relations. Les objets correspondent à des
entités logiques spécifiques de la classe des documents étudiés (par
exemple, {\it chapitres, sections, paragraphes} et {\it titres} dans
un article ou un roman\,; ou {\it adresse, date, signature} et
{\it corps} dans une lettre administrative). Pour les relations,
certaines sont de type syntaxique décrivant la décomposition
hiérarchique des objets comme dans le cas de la structure physique
(par exemple, un chapitre se décompose en sections et les sections en
sous-sections et paragraphes, etc.). D'autres relations sont d'ordre
sémantique. Elles correspondent, suivant l'application, soit à l'ordre
d'enchaînement logique des entités dans un contexte de lecture
continue, soit à l'ordre de repérage d'informations clés dans un
contexte d'indexation automatique, ou encore à l'ordre d'assemblage
des éléments graphiques pour déduire le fonctionnement des symboles
représentés comme dans les plans mécaniques (un axe de rotation peut
être détecté dans une zone contenant un rectangle traversé par une
ligne tiretée).

\subsubsection{Niveaux de structures}

Au-delà de la classification purement binaire de l'information en {\it
physique} ou {\it logique}, la structuration peut également
s'exprimer plus finement en termes de niveaux ou de couches d'information
relativement à l'ordre de traitement ou de lecture. On peut répartir
les composantes logiques du document en {\it informations principales}
et en {\it informations secondaires}. Les premières, de type {\it texte} et
{\it notes}, ont essentiellement des fonctions de lecture, tandis que les
secondes, de type {\it titres}, {\it sous-titres}, etc. servent au
repérage et à la consultation. Peels~\cite{peels85a} décompose la
structure logique des articles scientifiques en trois niveaux~: le
{\it corps} du document, l'{\it information illustrative} (titres,
notes, figures, annexes, en-tête, etc.) et l'information de {\it mise
en page} (sommaire, index, numéro de page, etc.). 

La structure physique peut être également affinée en vue
d'un meilleur repérage des entités logiques. Derrien~\cite{der90}
répartit la structure physique en une structure {\it typographique} et
une structure {\it géométrique}. La première décrit le style
typographique. La valeur des attributs utilisés (police,
corps, style, espace, etc.) est échelonnée de manière à pouvoir différencier
un titre ou une note de bas de page d'une ligne courante de texte. La
seconde sert également au repérage des entités logiques en se basant
sur la taille des espaces séparatrices. Là-aussi, l'importance des
espaces est échelonnée suivant la même hiérarchie que le style
typographique (un blanc entre deux alinéas est plus petit qu'un
blanc entre deux paragraphes). Tombre et al.~\cite{tom87,vaxiviere92a}
distinguent trois couches dans la structure physique de plans
mécaniques~: le {\em graphique\/} qui porte la majeure partie de
l'information et qui est habituellement converti en primitives
graphiques (principalement des chaînes de vecteurs) par un module de
{\em vectorisation\/}, la couche de {\em texte} et d'autres couches
éventuelles, comme celle des petits 
symboles dans certains cas. 

Cette hiérarchisation de l'information peut être également exprimée en
fonction de la finesse de la perception ou de la granularité des
objets recherchés, comme dans~\cite{chenevoy92b} qui distingue la {\it
macro-struc\-ture} de la {\it micro-structure}. La {\it
macro-struc\-tu\-re} correspond à un découpage de haut-niveau où
l'aspect visuel est très riche. Les éléments de la structure
physique (bloc, figure, colonne, etc.) sont décrits en terme d'objets
globaux et leurs séparations correspondent à des régions souvent bien
marquées dans l'image à l'aide d'espaces ou de cadres. La {\it
micro-structure} correspond à une structure plus fine à l'intérieur
des paragraphes. Les fragments de contenu sont diffus sans séparation
physique très nette. La structure physique, peu riche, peut \^etre
renforcée par des informations contextuelles (syntaxico-sémantiques)
ou typographiques comme le style, la police, la justification, etc.  

\subsubsection{Normes}

~~\\
{\it Les standards}

Devant la multiplication des procédures de transfert de documents
électroniques entre des systèmes de gestion souvent incompatibles, des
standards sont devenus nécessaires pour définir les règles de
structuration et rendre les documents facilement réutilisables sur
n'importe quel site. L'{\sc iso}\footnote{International Standard
Organisation} a conduit des travaux de normalisation et deux standards
internationaux ont été ainsi définis et utilisés dans plusieurs
systèmes~: la famille des normes {\sc sgml}\footnote{Standard
Generalized Markup Language}~\cite{ISO86a}, pour
satisfaire les besoins de l'édition, et la famille {\sc
oda/odif}\footnote{Office Document Interchange
Format}~\cite{ISO89a} pour répondre aux besoins de la
bureautique. 

Ces deux normes, de philosophie
différente~\cite{horack85a,goossens91a,bryan89a}, ont des points
communs~: conçues pour l'échange de documents révisables, elles
permettent de distinguer l'information à la fois sur le plan de la
présentation et sur son enchaînement logique. Elles traduisent
fidèlement l'aspect hiérarchique et générique des structures. Cette
structure est unifiée aux seins de classes et de sous-classes d'objets
permettant de réaliser facilement la programmation en termes 
d'objets~\cite{danish91a,joloboff86a,brown89a,andre89a}.  

\begin{table}[tph]
{\small
\begin{center}
\begin{tabular}{|c|l|l|}
\hline
Norme & Points forts & Points faibles\\
\hline
{\sc oda} & \parbox{60mm}{~\\ - Description rigoureuse à la fois de la
structure logique et physique.\\
- Structure séparée du contenu\/; un éditeur de texte
oriente sa spécification et maintient sa cohérence\\ 
- Attributs définis de manière précise\/; description normalisée des
objets subordonnés, d'où limitation des fantaisies de
présentation\\}& \parbox{60mm}{~\\- Difficulté de décrire les
documents où la composante artistique est importante.~~\\
- Les objets physiques sont toujours rectangulaires et parallèles.\\

- L'archivage indexé est difficile car le fichier résultat ne comprend
pas de balise~: d'où difficulté de créer
des fichiers compatibles {\sc sgml}.}
\\ \hline
{\sc sgml} & \parbox{60mm}{~\\ - la structure est lisible par
l'utilisateur grâce aux balises\\
- Il est facile pour un système d'{\sc ard} de créer un fichier
compatible {\sc sgml}.\\
- Etant un méta-langage, il est possible d'établir
un standard pour l'écriture de balises respectant les structures
d'{\sc oda} ({\sc odl}).} & \parbox{70mm}{~\\- Difficulté de
modélisation de la structure physique aussi précisément qu'avec {\sc
oda}.\\
- L'absence de structure préétablie peut conduire l'utilisateur à
créer des structures farfelues.\\}\\
\hline
\end{tabular}
\caption{\label{odasgml} Points forts et points faibles des normes
{\sc oda} et {\sc sgml} en {\sc ard}.}
\end{center}}
\end{table}

~~\\
{\it Utilisation en {\sc ard}}

Ces deux types de norme procurent un formalisme de structuration qui
peut être utilisé avantageusement en reconnaissance de la structure.
Cela étant, ces formalismes, n'ayant pas été conçus pour l'{\sc ard},
présentent des points forts et des points faibles qui sont résumés
dans la table~\ref{odasgml}.


\section{Principales composantes d'un système d'ARD}

L'état de l'art est riche dans ce domaine proposant plusieurs schémas
de systèmes. Néanmoins, tous ces systèmes s'accordent à utiliser
les mêmes opérations présentées dans la figure~\ref{schem_ard}.
L'analyse du texte, étant souvent spécifique à une application
particulière, ne sera pas exposée ici.  

\begin{figure}[htbp]
\centerline{\psfig{figure=schem_ard.eps,width=13cm}}
\caption{\label{schem_ard} Schéma général d'un système d'{\sc ard}.}
\end{figure}

\subsection{Acquisition et prétraitements}

L'acquisition d'un document est effectuée à l'aide d'un capteur de
type caméra ou scanner. Ce dernier permet d'obtenir une résolution
spatiale élevée allant jusqu'à 900 dpi\footnote{dot per inch},
correspondant à environ 35 points par mm. Les
résolutions utilisées pour les documents composites vont de 200 à 400
dpi\/; une résolution plus grande n'ajoute rien à la qualité de
l'image, au contraire elle augmente la taille des données à traiter et
peut même générer du bruit (grain du papier). Les documents peuvent
être acquis en binaire (1 pour les points noirs et 0 pour le fond) ou
en niveaux de gris (en général 256 ). La quantification binaire
convient bien pour les documents de type texte ou graphique qui
présentent un fort contraste et une régularité dans l'intensité 
entre les objets. L'acquisition en niveaux de gris est nécessaire pour
préserver, dans le cas de documents composites (texte, graphique,
photo, ombrage, etc.) l'intégrité de tous les
médias~\cite{ejiri84a,wong82a,kasturi90a}.

L'image obtenue du scanner peut comporter du bruit ou présenter des
artefacts qu'il faut corriger avant l'analyse du contenu. Parmi les
techniques les plus usuelles, on peut mentionner la segmentation
multi-niveaux, la binarisation, le filtrage et la correction de
l'inclinaison. La segmentation multi-niveaux consiste à isoler les
régions différentes par leur teinte soit pour les traiter de manière
spécifique soit pour les masquer afin de ne pas les binariser et
pouvoir les afficher en préservant leur aspect~\cite{oriot92b}. La
binarisation est une opération de seuillage permettant la
transformation de l'image en deux teintes~: le blanc (fond) et le noir
(objet)~\cite{che89,aubert91a}. Cette technique permet de sélectionner les
régions textuelles ou graphiques qui sont incrustées dans un fond. La
littérature abonde en méthodes de binarisation car, étant souvent
confrontée à des problèmes de non uniformité du fond et
d'irrégularité, la binarisation conduit à une multitude
d'algorithmes~\cite{sah88,whi83}.

Un autre prétraitement souvent utilisé pour les documents de type texte
est la correction de l'inclinaison qui peut être due soit à une
mauvaise introduction du papier dans le scanner ou tout simplement à
la présentation penchée du texte dans le document. Les techniques
de segmentation du document se basent sur l'hypothèse de
l'horizontalité des lignes du texte pour les localiser et les
identifier. Il faut alors s'assurer à chaque début d'analyse que cette
hypothèse est vérifiée. Plusieurs techniques de mesure de
l'inclinaison et de correction ont été
développées~\cite{baird87a,tri84,gorman93a} 

\subsection{Segmentation physique}

C'est la première étape de traitement de tout système d'{\sc ard}. Dans
cette étape, une page de document est subdivisée en blocs ou régions
typographiquement homogènes. Toutes les opérations de reconnaissance
de la structure s'appuient sur ces résultats, d'où l'importance des
recherches menées dans ce sens. Une synthèse des méthodes de
segmentation se trouve dans~\cite{nadler84a}. On distingue deux
familles de méthodes~: les méthodes {\it descendantes} et les méthodes
{\it ascendantes}. Ces deux familles de méthodes s'appuient sur
l'hypothèse de l'horizontalité des lignes du texte ainsi que sur le
fait que les objets physiques recherchés correspondent à des
regroupements de ces lignes sous la forme de blocs rectangulaires.

Les méthodes {\it descendantes} sont de nature globale et tiennent peu
compte du contenu. Elles sont dirigées par des connaissances {\it a
priori} sur la structure physique et essaient de faire coïncider
cette structure avec la décomposition physique de l'image du
document~\cite{der90,higashino86a}. 

La technique la plus courante consiste à projeter les pixels de
l'image sur les axes principaux permettant de faire ressortir les
limites horizontales et verticales des entités textuelles. Les décrues 
de ces histogrammes correspondent généralement à ces limites à
condition bien sûr que le document soit parfaitement recalé et que sa
structure soit relativement simple (une seule colonne). Pour des
documents contenant des enchevêtrements de blocs, Nagy~\cite{nag84}
alterne les projections en {\sc x} et {\sc y} lui permettant
d'obtenir en plus de la découpe horizontale et verticale, une
représentation hiérarchique du document. A chaque n{\oe}ud est associé un
indice de récursivité constitué d'une séquence de coupures verticales
et horizontales. Ces informations constituent le contexte de découpage 
ultérieur et permettront par exemple d'appliquer un seuil de découpage
différent pour séparer les colonnes, les lignes, etc. 

Pavlidis et Zhou~\cite{pavlidis91a} ont proposé une méthode fondée
sur les bandes blanches (``White Streams'') qui est moins sensible que
la précédente à l'inclinaison du texte. Cette méthode identifie par
balayage les lignes et les colonnes blanches adjacentes et forme des
bandes. Ces bandes permettent d'estimer l'inclinaison du texte et les
blocs sont ensuite déterminés entre ces bandes, puis replacés en
fonction de l'inclinaison. Akindele et Bela\"{\i}d~\cite{akindele93a} ont
proposé une extension de cette méthode pour la recherche de blocs
droits mais dont le contour est polygonal (paragraphe avec une
lettrine). 

Enfin, d'autres techniques de segmentation descendante par
transformation d'es\-pa\-ce, de type Hough~\cite{Dud72} et
Fourier~\cite{hase85a,postl86a}, permettent de détecter les
colinéarités du document malgré le bruit résiduel ou l'inclinaison du
document auxquelles les techniques ascendantes restent très
sensibles. 

Les méthodes {\it ascendantes} sont dirigées par les données
et utilisent peu de connaissances sur la structure, mais plutôt des
connaissances typographiques. Elles déterminent les régions du
document directement à partir des pixels l'image, soit par {\it
lissage} dont l'effet est de noircir les zones relativement denses
comme le fait le {\sc rlsa}\footnote{Run Length Smoothing
Algorithm}~\cite{wong82a}, ou par extraction de composantes connexes
ou lignes et ensuite fusion de celles-ci en entités plus
importantes~\cite{baird87a,zuc76,tri84}. 

Etant donné leur caractère local, les méthodes {\it ascendantes} sont
moins dépendantes de l'inclinaison du texte que les méthodes
précédentes, mais la structure physique du document reste plus
délicate à reconstituer.  

Les méthodes {\it descendantes} permettent d'identifier la structure de
documents différents dès lors que les connaissances {\it a priori}
sont données. Cependant, elles sont fiables seulement quand ces
connaissances correspondent à la structure attendue. Elles ne peuvent,
par conséquent, s'appliquer qu'à un nombre limité de documents où la
structure physique est de forte granularité (lettres administratives,
rapports, etc.) et où l'image n'a pas été altérée par le bruit de la
scannérisation. 

Souvent, les systèmes d'{\sc ard} combinent ces deux
méthodes. Ils utilisent d'abord les connaissances {\it a priori} sur
le document et un contrôle descendant de la segmentation par recherche
directe d'indices (frontières). Ensuite, en cas d'échec, ils
déclenchent un processus ascendant en essayant de retrouver la
structure à partir des pixels de la zone circonscrite par le processus
descendant. Le résultat final est aussi contrôlé par les connaissances
{\it a priori}~\cite{belaid89b}. 

\subsection{Etiquetage logique}

Cette opération est appliquée sur les blocs trouvés à l'issue de la
segmentation. Elle consiste à affecter à chaque bloc une
étiquette en relation avec le type du média contenu~: {\it texte},
{\it graphique} et {\it photographie}.

La littérature mentionne deux approches principales. Dans la première,
on suppose que le contenu des blocs est homogène comme c'est souvent
le cas  dans les documents composites de type {\it articles
scientifiques}, {\it pages de journaux}, {\it rapports}, etc. Chaque
bloc est classé dans le média le plus proche en fonction de certaines
mesures de texture extraites de l'image du bloc. Wang et
Srihari~\cite{wang89a} expriment la texture à l'aide de mesures de
largeur, de régularité et de fréquences des espaces. Ils classent les
blocs en cinq catégories~: {\it petit texte} (notes), {\it texte
moyen} (texte et sous-titres), {\it grand texte} (titres), {\it
graphique}  et {\it photographie}. Les espaces sont étroites,
régulières et abondantes dans un texte, étroites, irrégulières et peu
abondantes dans une photographie et très larges dans un graphique.
Wong et al.~\cite{wong82a} utilisent les caractéristiques des
composantes noires obtenues par {\sc rlsa}, comme la taille, la
densité et l'excentricité pour les classer en~: {\it texte}, {\it
lignes horizontales}, {\it graphique} et {\it image tramée}, et {\it
lignes verticales}, exploitant le fait que les lignes ont souvent une
largeur fine et constante.  

Dans la seconde approche, on considère au contraire qu'un bloc peut
contenir un mélange de texte et de non-texte, souvent d'ailleurs de
type graphique, comme dans les documents techniques, les
tableaux et les formulaires. Dans ce cas, l'opération d'étiquetage
consiste à séparer le texte du non texte. Certaines techniques
utilisent une analyse en composantes connexes pour réaliser
la séparation du texte. Fisher et al.~\cite{fis90} utilisent la
transformée de Hough pour regrouper les composantes connexes 
colinéaires de même taille dans des chaînes logiques de texte. Une
autre famille d'algorithmes consiste à fusionner les composantes
connexes en blocs plus importants. Meynieux et al.~\cite{meynieux87a}
utilisent un algorithme fondé sur l'étude de la proximité de composantes
connexes. Nagy et al.~\cite{nag86} utilisent un système à base de
règles pour réaliser des fusions successives de caractères en blocs de
différentes tailles. On peut également se référer aux travaux de
Scherl~\cite{scherl80a} et Nadler~\cite{nadler84a}.

L'étiquetage par ces deux types d'approche peut être insuffisant
dans certains cas où le contenu est très hétérogène et où l'on cherche
un étiquetage plus fin du contenu pour distinguer, par exemple, dans
un même texte, les notes, le texte lui-même, les titres et les
sous-titres. Nous avons développé une méthode
d'étiquetage capable de donner ces précisions avec une localisation
aussi juste que possible de chaque ``sous-média'' dans la surface du
bloc~\cite{belaid93a}. Cette méthode peut être vue à
la fois comme une méthode d'étiquetage et aussi comme une méthode de
segmentation fine de la macro-structure. La figure~\ref{etiquetage}
donne un exemple de segmentation d'un bloc en différents types de
texte~: {\it petit texte} (fig.\ref{etiquetage}.b), {\it texte moyen}
(fig.\ref{etiquetage}.c), {\it grand texte} (fig.\ref{etiquetage}.d)
et {\it photographie} (fig.\ref{etiquetage}.e)

\begin{figure}[htbp]
\centerline{\psfig{figure=lab_fig9.eps,width=13cm}}
\caption{\label{etiquetage} Segmentation multi-média d'un bloc composite.}
\end{figure}

\subsection{Reconnaissance de la structure}

\subsubsection{Modélisation}

L'immense variété de types de documents différents laisse à penser que
l'on ne peut déduire avec précision aucune structure de document si l'on
ne dispose pas de connaissances {\it a priori} sur la classe étudiée
permettant de guider l'action du système. Cela étant, la
modélisation de ces connaissances n'est pas un exercice trivial car il
est difficile de savoir comment les représenter de manière profitable
et jusqu'où l'on peut aller dans leur description. 

Un modèle de document doit mettre en valeur les caractéristiques
physiques et logiques communes à la classe des documents qu'il entend
décrire. Plusieurs approches permettent de tenir compte de ces deux
impératifs. Tout d'abord le modèle peut contenir de manière séparée
les deux structures physique et logique du document. De prime abord,
cette décomposition peut sembler avantageuse car elle permet de mieux
cerner les connaissances utiles pour segmenter et reconnaître les
objets dans le document. Il se révèle cependant que cette
décomposition en physique/logique n'est pas si évidente et que 
souvent, le contenu des objets est commun aux deux structures. De
plus, l'aspect visuel est si intimement lié à son interprétation
qu'il faudrait définir des liens pour chaque niveau de ces deux
hiérarchies, permettant de passer alternativement de la zone à
analyser vers son contenu logique, comme le fait
Ingold~\cite{ing90}. 

Il nous a semblé plus réaliste de mêler ces deux structures, ce qui
signifie qu'il faut en privilégier une afin de servir de support
à l'autre. C'est ainsi qu'en édition, Quint~\cite{qui87} décrit la
structure logique du document à l'aide d'une hiérarchie de composantes
logiques, dont les feuilles représentent le contenu. Chaque fragment
de contenu est complété au moyen de règles de présentation physique.
Le problème des fragments de contenu débordant d'une région physique
vers une autre est caché, au prix d'une description complète de tous
les problèmes de chevauchement et de débordement sous forme d'une base
de règles propres à chacune des entités logiques.

Pour l'{\sc ard}, il nous a paru plus avantageux de privilégier la
structure physique étant donné que l'analyse s'appuie sur la
segmentation physique pour interpréter le contenu. Nous avons choisi une
représentation semblable à celle proposée par {\sc oda}. Comme le
montre la figure~\ref{odagraphein}.b, nous avons utilisé une seule
structure ({\it physico-logique}) où n'apparaissent que les éléments
physiques et leurs liens de composition et de succession. Au niveau
supérieur de cette hiérarchie, on distingue les mêmes types d'objets
qu'{\sc oda}. La structure logique sous-jacente (et donc cachée) est
décrite par des étiquettes ou des règles de description logiques.

\begin{figure}[htbp]
\centerline{\psfig{figure=objgenoda.eps,width=10cm,height=5cm}}
\caption{\label{odagraphein} Structures hiérarchiques~:
(a)~dans {\sc oda}, (b)~dans {\sc graphein}.}
\end{figure}

\subsubsection{Méthodes de reconnaissance}

La littérature mentionne un grand nombre de systèmes de reconnaissance
de la structure de documents, mais une taxonomie de ces systèmes est
difficile à réaliser car le mot ``reconnaissance'' n'a pas la même
signification d'un système à l'autre. Souvent, il s'agit d'une analyse
de la structure physique accompagnée parfois d'un étiquetage logique.
Très peu de systèmes vont en effet jusqu'à la reconnaissance du texte
et à l'exploration profonde de la structure logique au sens où on
l'a définie précédemment. De plus, ces systèmes sont souvent
réservés à des applications précises comme l'analyse des
adresses où la structure logique est limitée à quelques zones bien
spécifiques du document~\cite{hull87a,niyogi86a,srihari87b}. 

~~\\
{\bf Analyse de la structure physique}

L'analyse de la structure physique est une étape préalable nécessaire
à la reconnaissance de la structure logique. Elle est beaucoup
pratiquée dans la nouvelle génération de systèmes de lecture optique
de caractères ({\sc ocr}) qui se servent de règles typographiques
rudimentaires pour offrir une sortie organisée des caractères
correspondant au format de mise en page simplifié du document étudié.

~~\\
{\it Analyse récursive ascendante}

Une première idée pour identifier la structure physique d'un document,
consiste à utiliser une technique ascendante par fusion récursive des
entités physiques~: des caractères aux lignes, puis des lignes aux
paragraphes et enfin des paragraphes à la page. C'est ainsi que
Wilcox~\cite{wil88} procède pour générer la structure physique
d'articles scientifiques. La formation des lignes est fondée sur une
relation d'adjacence horizontale des caractères et des mots. La fusion
des entités adjacentes n'est autorisée que si l'espace qui les sépare
ne dépasse pas un seuil maximum déterminé à partir d'une
fonction de distribution du corps des caractères. Ensuite, les
lignes sont à leur tour fusionnées si elles répondent à des critères
de type~: égalité des longueurs, cadrage à gauche et régularité des
interlignes. Cette régularité est observée à l'aide de la fonction
d'auto-corrélation de l'ordonnée minimale de chaque composante connexe.
Toute ligne ne respectant pas ces critères est isolé en conservant son
étiquette {\it ligne}. Enfin, les blocs de texte adjacents
verticalement sont fusionnés en colonnes s'ils ont une largeur
identique.

~~\\
{\it Analyse récursive descendante}

Cette technique est applicable quand la structure est régulière, la
généricité est limitée et quand l'ordre de la lecture est
déterminant. 

Kreich, Luhn et Maderlechner~\cite{kreich88a} utilisent une méthode
descendante associée à un module de classification texte/ graphique
pour analyser la structure d'une lettre administrative. La méthode
cherche d'abord à former les régions les moins sensibles au bruit,
notamment les blocs de texte, par regroupement de leurs caractères. La
fusion est réalisé sur la base de seuils de proximité comme dans le
système de  Wilcox, mais contrairement à ce dernier, les seuils sont
déterminés sur tout le texte. Une lettre administrative a souvent une
typographie uniforme dans toutes les régions. Ensuite, une fois les
blocs constitués, une nouvelle fusion est opérée à l'intérieur de
chaque bloc pour déterminer ses mots et ses lignes. A cette étape, les 
auteurs utilisent des seuils déterminés de manière plus fine à
l'intérieur de chaque bloc. La méthode conserve ces seuils pour un
éventuel retour en arrière et correction si l'étiquetage au cours de
l'analyse de la structure logique ne donne pas satisfaction.  


~~\\
{\it Représentation arborescente}

L'étude de la structure de documents a montré que celle-ci est souvent
hiérarchique et qu'elle peut donc se mettre sous la forme d'un arbre.
Plusieurs auteurs analysent la structure physique à partir d'une
représentation arborescente du document, déterminée lors de l'étape de
segmentation. 

C'est ainsi que Nagy prend l'arbre {\sc x-y}~\cite{nag88} comme point
de départ pour analyser la structure physique et logique. L'arbre {\sc
x-y} étant obtenu par découpes récursives et alternées horizontalement
et verticalement, chacun de ces n{\oe}uds représente normalement un bloc
rectangulaire. L'analyse de la structure physique est réalisée à
partir des feuilles de l'arbre par regroupement de celles-ci en deux
entités différentes~: {\it entités physiques}, pour les fragments de
caractères ou de blocs de texte, {\it entités de mise en page} pour
les blocs formés par des caractères, des mots ou des lignes de texte.
Les règles utilisées pour le regroupement des feuilles sont de type
générique, comme~: ``la police et le corps de caractères ne varient pas
à l'intérieur d'un mot''.  Cette classification demeure complexe car
certains caractères se retrouvent mal répartis dans les feuilles et
des considérations uniquement topographiques ne permettent pas de les
séparer. 

~~\\
{\bf Analyse de la structure logique}

~~\\
{\it Méthodes syntaxiques}

Ingold~\cite{ing90} utilise une grammaire attribuée décrivant la
structure de textes de {\it lois fédérales suisses}. Cette grammaire
contient des règles de composition et des règles de présentation.
L'analyse se décompose en deux niveaux\,: reconnaissance des
fragments qui comprend l'analyse des parties du document et la
délimitation de chaque bloc de texte\,; reconnaissance des caractères qui
comprend l'analyse des chaînes et l'identification de chaque signe.
Dans les deux cas, la méthode d'analyse est descendante, de haut en
bas pour les fragments et de gauche à droite pour les chaînes.
Cette analyse est régie par des automates construits automatiquement
à partir de la grammaire.

Nagy~\cite{nag88} utilise une analyse syntaxique descendante de 
l'arbre {\sc x-y} à partir d'une grammaire de page et des analyseurs {\tt
Lex} et {\tt Yacc}. Pour étiqueter logiquement le contenu d'un n{\oe}ud
représentant un bloc, il calcule son histogramme de projection et code
les pics et les vallées, après seuillage, par une chaîne de 0 et de 1. 
Ensuite, il fait des traitements en cascade à l'aide de {\tt Lex}
pour obtenir un code à partir de la grammaire.
Il extrait d'abord des chaînes composées uniquement de 0 ou de 1
(appelées atomes) auxquelles est attribué un identificateur
temporaire, puis ces identificateurs sont repris pour générer
différents types d'étiquettes. {\tt Yacc}
utilise des contraintes liées à l'ordre et au nombre des entités
indiquées par la grammaire pour générer une interprétation.
En cas d'entente des deux analyseurs sur l'interprétation, le même
procédé est répété sur les sous-blocs.

Tsujimoto et Asada~\cite{tsuji90a} utilisent une segmentation
hiérarchique fondée sur une modélisation à base d'arbres.
La structure géométrique est représentée par un arbre de blocs
adjacents dans la même colonne, alors que la structure logique est
un arbre de blocs conceptuels. Quatre règles de transformation
fondées sur l'enchaînement habituel d'un article multi-colonnes
permettent de passer de l'arbre géométrique à l'arbre logique. 

Dengel~\cite{dengel90a,dengel92a} propose une méthode fondée sur
l'analyse par recherche de chemin dans un arbre de décision construit
par apprentissage. Les documents traités sont des
lettres administratives dans lesquelles seules quelques régions sont
importantes. L'étiquetage logique est réalisé par l'examen du
contenu des régions trouvées et comparaison de leurs
caractéristiques avec celles trouvées par apprentissage et rangées
dans une base de données statistiques.

~~\\
{\it Méthodes à bases de connaissances}

Un système d'analyse de documents contient à la fois des
connaissances procédurales concernant le traitement des données
physiques (traitements de bas biveau) et des connaissances
représentant les processus cognitifs d'interprétation et de
décision (traitements de haut niveau). La présence de plusieurs médias
nécessite de répartir l'expertise et de décentraliser le contrôle aux
niveaux de plusieurs processus spécialisés. Le contrôle n'est pas
toujours séquentiel, ascendant ou descendant\,; il est souvent de type
opportuniste.

Plusieurs systèmes tentent d'exploiter ce schéma d'analyse. Litcher et
al.~\cite{lit87} utilisent le système expert {\sc Yaps}
pour étiqueter les zones de l'adresse dans les images de lettres postales. 
Une partie initialisation segmente l'image en blocs de
composantes connexes dans l'image et leur affecte des scores
d'homogénéité, l'autre, à base de règles, étiquette ces blocs en 
{\em adresse\/}, {\em expéditeur\/}, {\em zone d'affranchissement\/},
ou {\em publicité\/}, en fonction de leur position dans l'image et
leur degré d'homogénéité. Les règles, à chaînage arrière, utilisent
les scores de segmentation et calculent des scores de certitude
qu'elles réutilisent elles-mêmes.

Niyogi et Srihari~\cite{niy87} ont développé un système à base de {\it
blackboard} pour l'analyse de documents composites. Le blackboard est
divisé en deux parties\,: le {\em domaine\/} qui contient les
résultats intermédiaires des modules de traitement et le {\em
contrôle\/} qui assure la coordination entre les modules de traitement
et la partie raisonnement (stratégie). Le contrôle est assuré par des
sources de connaissances qui s'activent de manière opportuniste en
fonction de l'état des données du blackboard. Chaque source de
connaissance est composée d'une partie précondition et d'une partie
action qui consiste en l'appel d'un module de traitement. Le document
est binarisé puis segmenté en blocs\,; chaque bloc est défini par sa
position et des paramètres descriptifs. Le moteur d'inférence utilise
la base de connaissances pour examiner le résultat de la segmentation.
En cas de mauvais résultat, il alerte le contrôle du blackboard qui
actionne à son tour des modules de traitement d'images en vue de
fournir des renseignements supplémentaires.  

\section{Le projet {\sc Graphein}}

Le but de ce projet est de développer un système générique d'{\sc ard}
pouvant s'adapter facilement et de manière efficace à différents types
de documents. Pour atteindre cet objectif, il nous a semblé important
d'assurer au système un certain nombre de fonctionnalités parmi
lesquelles on trouve~: 
\begin{itemize}
\item la possibilité de disposer de connaissances {\it a priori} sur
la structure des documents étudiés. Le modèle est générique,
construit à partir d'exemples et de contre-exemples. Sa structure est
unifiée autour d'objets et de classes d'objets, permettant un héritage
facile des connaissances et évite leur duplication.
\item la séparation entre le modèle et le contrôle permettant de
changer facilement d'application sans modifier de stratégie\/; 
\item la possibilité d'utiliser une stratégie dirigée par les
connaissances. Cette stratégie ne doit pas être linéaire, mais plutôt
opportuniste, c'est-à-dire évoluant en fonction du résultat courant,
d'où une meilleure focalisation des traitements et une bonne gestion
des retours en arrière en cas de problème\/;
\item enfin, pour conduire une telle stratégie, il nous a paru
essentiel de munir le système d'un moyen d'auto-contrôle de la
convergence. Nous avons développé des mécanismes de gestion
d'hypothèses fondés sur la minimisation du désordre (entropie).
\end{itemize}

Nous avons expérimenté cette approche sur deux classes de
documents, les {\it articles scientifiques} et les {\it notices
bibliographiques}. Dans le premier cas, il s'agit de reconnaître la
macro-structure par recherche de régions visuellement distinctes. La
stratégie utilisée est fondée sur la recherche 
de séparateurs et fonctionne par gestion d'hypothèses relativement aux
choix de segmentation proposés par le modèle. Elle peut être descendante,
ascendante ou mixte en fonction de la pertinence ou non des
séparateurs. Dans le second cas, il s'agit de reconnaître la
micro-structure à l'intérieur des blocs de notices bibliographiques.
L'aspect logique est beaucoup plus riche que l'aspect physique d'où
un renforcement de l'analyse au niveau lexical et syntaxique. La
stratégie fonctionne aussi par gestion d'hypothèses mais
essentiellement de manière descendante. Développée dans le cadre d'un
projet industriel, nous avons optimisé cette approche en vue de
considérer toutes les solutions possibles avec une valuation de ces
solutions. De plus, les zones défectueuses sont circonscrites en vue
d'une éventuelle correction manuelle.

\subsection{Reconnaissance de la macro-structure}

Il s'agit de reconnaître les entités logiques d'articles
scientifiques de type {\it paragraphe}, {\it titre}, {\it figure},
{\it légende}, etc. Notre but est de montrer comment un système
d'analyse peut se laisser guider par un modèle générique de la classe
de document et par les résultats de la segmentation afin de
reconnaître la structure logique du document. L'application visée
concerne la revue {\sc t.s.i.}\footnote{Traitement et Science
Informatiques} en nous limitant aux pages de titre et du contenu sans
nous préoccuper de la bibliographie qui sera traitée dans la section
suivante correspondant à la micro-structure. 

\subsubsection{Modélisation}

La spécification de la macro-structure se base sur la même
structuration hiérarchique d'{\sc oda}, mais s'arrête pour nous au
niveau des blocs. Cependant, étant donné que {\sc oda} n'était pas
faite spécialement pour l'{\sc  ard}, nous avons effectué un certain
nombre d'adaptations de cette structure en ajoutant des constructeurs
et des qualificatifs spécifiques à l'analyse de documents. Notamment,
nous avons défini le constructeur {\it mosaïque} pour décrire les
agencements non orthogonaux de blocs (voir fig.\ref{constructeurs}.b).
Nous avons également renforcé
la définition des constructeurs de type {\it séquence} et {\it
aggrégat} en précisant le sens de la composition~: de {\it
haut-en-bas} ou de {\it gauche-à-droite} (voir
fig.\ref{constructeurs}.a). 

\begin{figure}[htbp]
\centerline{\psfig{figure=constructeurs.eps,width=10cm,height=5cm}}
\caption{\label{constructeurs} Constructeurs d'objets subordonnés~:
(a) schémas des constructeurs; (b) exemple de document en
mosaïque composé de cinq objets $O_1$, $O_2$, $O_3$, $O_4$ et $O_5$.}
\end{figure}

Par ailleurs, nous avons défini un qualificatif permettant de préciser 
les conditions de débordement de paragraphes sur les pages et les 
colonnes. Ce qualificatif de type ``optionnel-conditionnel'' (optc)
permet également de spécifier la notion de dépendance conditionnelle
entre les objets qui est nécessaire en {\sc ard}. Ce qualificatif,
permettra, par exemple, d'indiquer que la région des auteurs dans un
article scientifique peut être placée de manière optionnelle en haut
ou en bas de la page-titre mais elle doit être présente une et une
seule fois.

Enfin, s'agissant de déterminer des régions visuellement importantes,
nous avons pensé que leur analyse peut se faire aussi bien par la
distinction de leur contenu que par celle de leurs frontières. Aussi,
nous avons introduit la notion de {\it séparateur} de régions qui
accompagnera le constructeur et sera défini par des attributs
typographiques au même titre qu'un bloc. La figure~\ref{regle3} montre
les différents constituants d'une colonne. Une région de type colonne
({\it Colf}) peut comprendre ou non une note de bas de page ({\it
footnotes}). Dans ce dernier cas, l'objet {\it Col} est répétitif. Le
séparateur de la région {\it Colfoot} ({\it Hline1}) est décrit comme
un simple objet subordonné car il ne sépare pas les objets répétitifs
{\it Col} entre eux. L'objet {\it Col} décrit un choix entre ses six
objets subordonnés~: les pavés {\it Tit, S-Tit, Par} et {\it ContPar},
la région d'items {\it ListF} et la région figure {\it FigF}. Le pavé
{\it ContPar} est décrit avec une condition de présence ({\it optc})
indiquant qu'il n'est possible de le trouver qu'au début d'une colonne
(numéro du bloc dans la colonne ``num-bloc-in-column'' égal à 1) ou
qu'après une figure (label du bloc précédent égal à {\it FigF}). 

\begin{figure}[htbp]
\small{
{\fonte 
(:frame ColF\\
\hspace*{5mm}(: constructeur cho)\\
\hspace*{5mm}(: subordinate-objects (Col rep)))\\
\hspace*{1cm}(:frame ColFoot\\
\hspace*{1cm}(: constructor cho)\\
\hspace*{1cm}(: subordinate-objects (Col rep) Hline1 Footnotes))\\
\hspace*{5mm}(:frame Col\\
\hspace*{1cm}(: constructor cho)\\
\hspace*{1cm}(: subordinate-objects\\
\hspace*{15mm}Tit STit SSTit Par\\
\hspace*{15mm}(ContPar\\
\hspace*{2cm}(optc (or (= $*$num-bloc-in-column$*$ 1)\\
\hspace*{25mm}(= (\$label-of $*$last-bloc$*$) 'FigF)))\\
\hspace*{2cm}ListF FigF)\\
\hspace*{15mm}(: separator {\sc hs3})))\\
}}
\caption{\label{regle3} Règles de description de colonnes.}
\end{figure}
\normalsize



La figure~\ref{modele} décrit la structure hiérarchique générique
correspondante à la page de titre d'un article de {\sc t.s.i}. Pour
ne pas alourdir le graphique, nous avons volontairement omis le
qualificatif sur les objets obligatoires de la structure.

\begin{figure}[htbp]
\centerline{\psfig{figure=modele.eps,width=15cm,height=8cm}}
\caption{\label{modele} Exemple de modélisation dans {\sc graphein}~:
(a)~document de la première page d'un article de {\sc t.s.i.}\/; 
(b)~le modèle physico-logique correspondant.}
\end{figure}

\subsubsection{Analyse de la macro-structure}

Elle consiste à extraire les régions principales du document
conformément à leur description dans le modèle de la structure. Etant
essentiellement des régions de taille assez importante et donc très
visibles, l'analyse utilise des règles typographiques relativement
simples pour les délimiter. Ces règles sont relatives aux espacements
horizontaux et verticaux et à la texture. Suivant la précision de ces
règles, l'analyse peut être conduite de manière {\it descendante} ou
{\it ascendante}.  

L'analyse {\it descendante} s'appuie sur une représentation de l'image
en blocs rectangulaires extraits lors d'une étape de prétraitement par
la méthode {\sc rlsa}. Les blocs sont triés horizontalement et 
verticalement de manière à retrouver leur position et leurs limites. A
chaque passe (horizontale ou verticale), le système cherche les {\it
points de coupure} correspondant aux plages blanches qui séparent les
entités recherchées. Ces entités sont bien entendu, fonction de
l'application traitée. Les constructeurs et les séparateurs qui
décrivent la structure syntaxique de l'objet recherché guident
l'action de l'analyse en précisant à la fois le sens du balayage et le
type de séparation qu'il faut trouver. Si l'objet est composite, le
découpage se poursuit alors de manière récursive pour retrouver les
objets subordonnés. 

L'analyse {\it ascendante} est employée quand les connaissances du modèle
ne permettent pas de trouver directement et facilement la structure.
Le principe de cette approche est fondé sur l'analyse des composantes 
connexes~\cite{kida86a,tom87}. Il s'agit de construire une structure,
par exemple un arbre, permettant de représenter les relations d'{\it
inclusion} et d'{\it adjacence} des différentes composantes connexes
noires et blanches. Ensuite, la segmentation par l'analyse de ces
composantes est adaptée en fonction de l'application visée. Par
exemple, s'agissant ici de composantes essentiellement textuelles, les
règles ont été adaptées pour privilégier la direction horizontale pour
la fusion en mots et en lignes et la direction verticale pour la
fusion en paragraphes. Le principe de fusion est le même
quelle que soit la granualrité de l'entité à fusionner. A chaque
instant, on dispose d'une {\it unité active} et d'une composante
connexe dont il faut étudier le rapprochement. Par exemple, pour un
mot et un symbole, la règle de fusion est fondée sur l'examen de leur 
alignement, de leur proximité ainsi que sur la taille de leurs
caractères. Nous pouvons trouver l'ensemble des règles utilisées pour
la fusion dans ~\cite{chenevoy92b}. 

Dans l'exemple de {\sc t.s.i.}, la région colonne ({\it Région-col})
est analysée de manière ascendante. En effet, cette région est
décrite comme une répétition de choix entre les différents
constituants du contenu d'un texte~: titre, sous-titre,
paragraphe, liste d'items, figure, etc. L'analyse démarre par
l'extraction des lignes de texte, puis les fusionne en blocs. La
fusion est réalisée par considération des interlignes, du style des
mots, de l'indentation du paragraphe, etc. puis les types des blocs
sont trouvés. Pour l'exemple de la deuxième colonne, deux
paragraphes ont été reconnus, le premier étant une continuation de
paragraphe (coupure due à la mise en page).

\subsubsection{Stratégie d'analyse}

Les méthodes d'analyse {\it ascendante} ou {\it descendante} sont
initiées par la stratégie du système qui actionne l'une ou l'autre
d'entre elles en fonction des connaissances disponibles dans le
modèle. La stratégie de sélection repose sur une gestion des
hypothèses obtenues à partir des choix de décomposition proposés par
le modèle pour chaque objet traité. La gestion consiste à estimer
parmi les nombreuses hypothèses proposées par le modèle celle qu'il
faut adopter pour le traitement, or ceci n'est pas facile étant le
nombre important proposé pour chaque objet. De plus, il faut disposer
de critères de qualité permettant d'évoluer vers la solution du
problème et donc éviter les retours en arrière coûteux en temps. La
solution que nous avons retenue consiste à estimer la meilleure
hypothèse à l'aide d'une mesure d'entropie. Une entropie nulle est
assimilée à l'état de résolution finale du système. L'idèe est donc de
choisir à tout instant l'hypothèse qui ferait diminuer l'entropie et
qui conduirait ainsi plus rapidement à la solution. L'entropie
associée à une hypothèse est définie comme étant la moyenne entropique
de ses objets subordonnés. Dans notre cas, cette moyenne est pondérée
par deux valeurs fournies par le modèle, la probabilité {\it a priori}
et un score de complexité associé à chaque type d'objet (trait
graphique, bloc de texte, dessin, etc.). Ces scores de complexité sont
fixés expérimentalement de manière à privilégier les objets faciles à
reconnaître. 

Trois schémas sont donc possibles à l'issue de cette gestion~: une
seule hypothèse se distingue avec une entropie faible, dans ce cas le
système adopte une stratégie {\it descendante}\/; trop d'hypothèses
sont proposées et aucune d'entre elles ne se distingue par une
entropie faible, dans ce cas le système procède à une segmentation
ascendante\/; enfin, quelques hypothèses sont en conflit, dans ce cas,
le système essaie d'identifier les objets qui les distinguent et
focalise l'analyse sur ces objets. Les objets de plus faible entropie
sont recherchés en priorité. 

Lorsqu'une hypothèse est confirmée, l'ensemble des hypothèses est mis à
jour afin de supprimer les hypothèses conflictuelles avec l'hypothèse
choisie. Par contre, en cas d'échec, le système supprime les
hypothèses compatibles avec elle. Cette technique de gestion assure
une diminution de l'entropie et assure par la même une croissance de
l'information structurelle sur les hypothèses restantes. 

La figure~\ref{ex1} montre les résultats obtenus sur la page de titre
d'un article de {\sc t.s.i.}. La partie gauche contient l'état de la 
gestion des hypothèses et la partie droite, le résultat de
la reconnaissance de la structure. Les étiquettes 
logiques apparaissent en gras en haut de chaque composante. On peut
remarquer que le système est capable d'identifier les différentes
composantes textuelles comme les paragraphes, les titres, les notes de
bas de pages, etc. La partie haute de la page titre a été analysée de
manière descendante car les séparateurs sont bien visibles entre les
différentes régions du texte. Pour le reste, nous avons utilisé une
stratégie ascendante à cause des espaces qui sont relativement étroites.

\begin{figure}[htbp]
\centerline{\psfig{figure=../=equipe/first_page.ps,width=12cm,height=5cm}}
\vspace*{4cm}
\caption{\label{ex1} Résultat de la reconnaissance de la structure de
la première page d'un article de {\sc t.s.i}.}
\end{figure}


\subsubsection{Architecture coopérative}

Nous avons utilisé une architecture générique à bases de
connaissances~\cite{laasri89a} pour l'analyse et la reconnaissance de
la macro-structure (voir fig.~\ref{graphein}). Cette architecture
permet de faire coopérer plusieurs sources de connaissances par
l'intermédiaire d'un mécanisme de gestion de tâches et de
spécialistes. Elle est répartie sur deux niveaux ~; un niveau lié au
domaine et l'autre au contrôle séparant bien la stratégie de
l'application. Le niveau de contrôle offre une stratégie de
focalisation à l'aide de tâches (méta-sources de connaissances) qui
s'adapte bien à la reconnaissance structurelle de documents (donc
contextuelle), permettant d'orienter les actions à effectuer sur
plusieurs niveaux de finesse en partant du général vers le particulier
(par exemple, de la page vers le caractère). Le domaine est représenté
à la fois par le modèle, le blackboard et les sources de connaissances
spécialisées (spécialistes). Le blackboard contient la structure
spécifique et constitue la zone d'échange entre les experts. Les
sources de connaissances spécialisées dans le traitement des documents
(experts) sont partitionnées en un ensemble de spécialistes qui 
coopèrent pour réaliser les traitements. Leur activation se traduit
par la création, la modification et/ou la suppression de n{\oe}uds
dans le blackboard. Le choix des tâches par le sélecteur et des
spécialistes par les tâches se fait de manière {\it opportuniste} à
partir des derniers changements (événements) opérés dans le
blackboard. Une description complète de cette architecture se trouve
dans~\cite{chenevoy92b}.

\begin{figure}[htbp]
\centerline{\psfig{figure=graphein-arch.eps,width=10cm,height=8cm}}
\caption{\label{graphein} Architecture du système {\sc graphein}.}
\end{figure}

\subsection{Reconnaissance de la micro-structure}

Cette section concerne la structure à l'intérieur des blocs de texte.
Contrairement à la macro-structure où l'aspect visuel pré-domine et
guide la segmentation, le contenu ne bénéficie pas d'une séparation
physique ``aussi nette''. La structuration en lignes et en mots
n'apporte pas d'aide particulière quant à l'interprétation du contenu.
Etant plus près des pixels, on remarque que l'image est souvent
entâchée de bruit et il faut parfois reconnaître certains symboles ou
mots clés, voire même, aller jusqu'à l'interprétation sémantique des
phrases pour lever l'ambiguïté entre les fragments de contenu. Dans
ce cadre, le modèle de la structure doit exprimer des connaissances
contextuelles plus riches que dans le cas de la macro-structure.  

Nous avons voulu expérimenter nos idées d'{\sc ard} dans ce cadre
spécifique et voir comment l'analyse par gestion d'hypothèses de
segmentation pourrait être conduite sur les fragments de contenu.
L'application sur laquelle nous avons travaillée concerne la
reconnaissance de la structure des notices bibliographiques en vue de
la conversion rétrospective du catalogue de la Bibliothèque Royale
Albert 1er en Belgique. 

\subsubsection{Description des notices}

La description des notices a été initialisée par des
catalogueurs du monde bibliographique qui utilisent un langage
normalisé (pré-{\sc isbd}) pour décrire la structure logique et
physique des notices. 

La structure {\it physique} d'une notice est relativement simple (voir
fig.\ref{corps-bib}). Elle est composée de cinq pavés~: le pavé {\sc
cdu}, situé sur à droite de la première ligne et représente un  code
de classification de la notice\,; le pavé {\sc body} qui contient le
corps de la notice sur plusieurs lignes\/; les pavés {\sc collection}
et {\sc cote} qui sont optionnels\/; et le pavé {\sc zref} qui
contient le numéro d'ordre de la notice. La structure {\it logique}
est relativement dense car le contenu a une multitude de descriptions
variables suivant les types de notices, la langue utilisée, la nature
des rubriques décrites, etc.  

La typographie utilisée dans la notice est normalisée. En effet, le
corps des caractères est décroissant entre le pavé titre de la classe
{\sc cdu}, le pavé titre de sous-classe {\sc cdu} et le pavé des
notices. Le contenu du titre et du sous-titre de classe {\sc cdu} est
en majuscules. Le corps de la notice est en minuscules, sauf pour les
initiales qui sont en majuscules. Il comporte du style standard, du
gras et de l'italique.

\begin{figure}[htbp]
\centerline{\psfig{figure=notice.eps,width=15cm,height=6cm}}
\caption{\label{corps-bib} Structure physique d'une notice.}
\end{figure}

La spécification du modèle de structures a été rendue très difficile à
cause de la multiplicité des alternatives pour la description du
contenu et surtout à cause de la typographie utilisée. Nous avons
répertorié quelques-uns de ces problèmes en fonction de leur
catégorie~:

~~\\
{\it Typographique}

Les notices peuvent être
imprimées ou dactylographiées conduisant à des typographies différentes.
Certains champs sont écrits dans des styles {\it italique} ou {\bf
gras} et dans différents modes (majuscule, minuscule, alphabétique ou 
numérique). De plus, s'agissant d'une bibliographie belge, les notices
sont écrites dans deux langues avec parfois un mélange des deux.
Chaque langue conduit à l'utilisation d'un vocabulaire et 
d'une typographie spécifiques. Comme le montre la
figure~\ref{notices}, le nom ``Bruxelles'' est écrit de manière
abrégée dans la première notice et de manière complète dans la
deuxième. L'avenue est abrégée dans la première, alors qu'elle est
absente dans la deuxième. La ponctuation prend des interprétations
différentes suivant le contexte et la langue. Le point, par exemple,
peut être un signe d'abréviation (comme dans ``p.'' pour page, ou dans
``n.'' pour numéro, etc.) ou une fin effective de champ. Les césures 
ne correspondent pas toujours à une coupure de mots mais parfois à une
séparation de mots. La date apparaît sous différentes formes selon le
champ où elle se trouve~: entre  parenthèses, entre crochets ou libre.
Certains champs sont optionnels et peuvent ne pas apparaître. D'autres
variations sont à considérer, notamment celles inhérentes à la
police, comme les empattements et les ligatures qui peuvent conduire à
une mauvaise reconnaissance des caractères.   

~~\\
{\it Lexicale}

La reconnaissance de certains champs est parfois
conditionnée par la reconnaissance de mots clés spécifiques (comme
{\it Catalogue}, {\it Editions}, {\it Titre introductions}, etc.) de
dates et de noms propres qui nécessitent la présence de lexiques
spécialisés.  

~~\\
{\it Syntaxique}

La syntaxe est également prise en compte pour
reconnaître des groupements de mots, comme par exemple, ``[Par] nom \&
prénom'' pour identifier un auteur secondaire. Or, cette règle connaît 
quelques exceptions comme ``[Par] Gérad Liger-Belair'' dans la
dernière notice qui ne doit pas être interprété comme auteur
secondaire mais plutôt comme le reste du titre. 

\begin{figure}[htbp]
\centerline{\psfig{figure=notices.eps,width=12cm,height=10cm}}
\caption{\label{notices} Différences de structures entre les notices.}
\end{figure}


\subsubsection{Modélisation}

Nous avons utilisé le même type de modèle physico-logique que pour
la macro\-structure~\cite{chenevoy92a}. Les objets sont représentés
par des entités formelles identifiées par leur nom. Chaque objet est
décrit par une règle syntaxique explicitant sa structure en termes
d'assemblage générique d'objets subordonnés. Il est accompagné d'{\it
attributs} et d'actions précisant davantage sa structure et son cadre
d'application, comme le montre la table~\ref{regles}.

\begin{table}[tph]
\begin{center}
\begin{tabular}{|l l l|}
\hline
      &    &\{ {\bf constructeur} liste-d'objets-subordonnés-{\bf
      qualificatif} /\\
{\bf Terme} & ::= &\{ constante / Terminal /\\
      &    &\{ {\bf Import} terme-existant-{\bf qualificatif}\\
& & \\
{\bf Attribut} & & \{[-]valeur ~[val-poids]\}*\\
{\bf Poids}    & & \{objet-subordonné~[sous-poids]\}*\\
{\bf Action}   & & \{[+] nom-action\}*\\
\hline
\end{tabular}
\caption{\label{regles} Format des règles de description syntaxique
des notices.}
\end{center}
\end{table}

~~\\
``{\bf Import}'' permet l'héritage de la définition (constructeur, objets
subordonnés, qualificatifs, etc.) d'un terme existant. On peut ainsi
définir les caractéristiques d'un terme en fonction de celles d'un
autre. 

\paragraph{\it Atributs}~~\\~~\\
La description syntaxique n'est pas suffisante pour décrire la
micro-structure. On la complète par des attributs permettant de
caractériser la géométrie, la typographie et le contexte lexical.
Plusieurs sortes d'attributs ont été définies, parmi lesquelles on
peut trouver~:{\it Type} (chaîne, ligne, mot, symbole, etc.), {\it Mode}
(majuscule, numérique, alphabétique, ponctuation, etc.), {\it Style}
(gras, italique, standard, etc.), {\it Position} (début de ligne, à
l'intérieur, à la fin), {\it Affiliation} lexicale (index auteur,
pays, villes, abréviations, articles, etc.), {\it Séparateur} entre
objets subordonnés (espace, virgule, césure, etc.), {\it Poids} qui
spécifie le degré d'importance des objets subordonnés, etc.

Il est possible de donner plusieurs attributs à un même objet. De plus,
il est possible d'affecter plusieurs valeurs à un même attribut. Par
exemple, on peut indiquer pour un objet qu'il n'est pas numérique et
qu'il ne contient pas de ponctuation~:

\[Mode ~~ -num~ 5 -punct~ 3\]
~~\\
où 5 et 3 sont des poids affectés respectivement à l'attribut non
numérique et à l'attribut ponctuation. Comme on peut le remarquer,
chaque valeur peut être pondérée permettant de préciser l'importance
que l'utilisateur lui accorde. Des pondérations de même type peuvent
également être attribuées par l'attribut ``{\it Poids}'' aux objets
subordonnés. 

\paragraph{\it Actions}~~\\~~\\
Nous avons également intégré au modèle des actions propres à chaque
objet. Elles correspondent à des traitements particuliers à certains
documents et peuvent servir de stratégie locale pour simplifier
la stratégie générale du système. Celle-ci peut ainsi mieux
se préoccuper du contrôle général (choix des hypothèses à vérifier,
calcul et mise à jour des scores, etc.) et déléguer la stratégie
locale aux objets eux-mêmes (vérification du contexte local,
heuristiques de rattrapage en cas d'échec, codage et balisage du
résultat, etc.). De cette manière, le système d'{\sc ard} peut devenir
très indépendant du type de document.

On distingue deux types d'action~:
\begin{itemize}
\item les actions de {\it pré-analyse}, dont le nom est précédé du
signe ``+'', correspondent à deux formes de prétraitement. Elles
peuvent réprésenter des préconditions permettant d'étudier le contexte
local de l'objet et de déterminer s'il est nécessaire de poursuivre
l'analyse. Elles peuvent également correspondre à des stratégies
locales (ou heuristiques) si l'objet est complexe et son analyse
risque d'alourdir la stratégie générale.

\item Les actions de {\it post-analyse} sont précédées du signe ``-''.
Elles peuvent correspondre soit à des traitements à effectuer en cas
de succès pour restituer l'objet suivant le format {\sc unimarc}
correspondant, soit à des procédures de rattrapage si l'analyse a
échoué. La figure~\ref{exemple} montre un exemple complet contenant la
description syntaxique d'objets du modèle des notices.

\begin{figure}[htbp]
{\fonte 
//Zone Titre\\
Titre ::= Seq TitreP TitrePa*
Sep Tiretlong\\
Mode -minprint 10 -debpunct 10\\
Poids TitreTP S TitreTPPa A// Poids symbolique entre A et Z\\
//ZAT: Zone Auteur Titre\\
ZAT ::= Choix VAT Titre1\\
Position debligne\\
Style -talique 0 // Style doit être italique mais n'est pas
important\\
Action Restitute(200,0b)}
\caption{\label{exemple} Exemple de règles du modèle.}
\end{figure}
\end{itemize}

\subsubsection{Stratégie de reconnaissance}

Les notices sont présentées au système sous la forme d'un flux {\sc
sgml} correspondant au contenu balisé. Il contient la ponctuation et
les mots reconnus par {\sc ocr} ainsi que l'affiliation lexicale de
ces derniers ({\it pays, ville, auteur, abréviation, etc.}), le style
typographique ({\it italique} et {\bf gras}) localisé dans des zones,
ainsi que d'autres informations spécifiques à la production. 

La ponctuation {\sc isbd} facilite l'étiquetage des éléments
d'information et permet de les ranger sous forme lisible. Cependant,
pour la conversion rétrospective, les notices ne respectent pas
scrupuleusement ce format et il faut trouver le moyen de s'en
rapprocher le plus possible. Notamment, il faut être capable de
rattraper les erreurs de reconnaissance de caractères et les
fautes de frappe qui sont nombreuses. La stratégie de reconnaissance
exploite toutes les possibilités à partir des indices disponibles dans
le flux de donnée. Par exemple, pour pallier l'absence de certains
séparateurs, toute la ponctuation est considérée comme telle et donne
lieu à des hypothèses de séparation. De plus, les séparateurs sont
doublés et leur recherche est transformée en une recherche d'{\it
initiales} et de {\it finales} de champs consécutifs. 
Par exemple, un séparateur de type {\it point} entre un {\it champ1}
et un {\it champ2} peut se transformer en une finale de type point
pour {\it champ1} qui sera suivie, par exemple, d'une initiale de type
majuscule pour {\it champ2}. Ainsi, l'absence d'une initiale peut être
rattrapée par la présence d'une finale et inversement. La stratégie
d'analyse consiste à considérer toutes les initiales et finales de
champs comme séparateurs potentiels et à ne retenir parmi eux que ceux
qui conduiront à une segmentation cohérente de la notice en champs
d'après le modèle.

La structure spécifique est un arbre où les n{\oe}uds correspondent aux
objets analysés. A chaque étape, le système analyse les choix de
décomposition rangés dans un {\it agenda} et associe au résultat de
l'analyse un score de confiance basé sur la correspondance entre les
attributs  donnés par le modèle et ceux trouvés dans l'image. Si ce
score est faible, l'hypothèse est rejetée. L'hypothèse est également
rejetée si les actions de {\it pré-analyse} qui l'accompagnent ne
sont pas vérifiées. 

La figure~\ref{resreference} montre les résultats de l'analyse de la
dernière référence de la figure~\ref{notices}. Tous les sous-champs ont
été correctement identifiés. Ils sont codés et balisés en {\sc
unimarc}. ``QSTR'' indique le score de confiance entre 0 et 10~000
attribué à chaque entité.

\begin{figure}[htbp]
\small{
\begin{verbatim}
<675 I=bb QSTR=10000> <$a QSTR=10000>159.962</$a> </675>
<200 I=0b QSTR=9834>  <$f QSTR=9487>Gérard Liger-Belair</$f>
                      <$a QSTR=10000>Je suis fakir</$a> </200>
<700 I=b0 QSTR=10000> <$a QSTR=10000>Liger-Belair</$a>
                      <$b QSTR=10000>Gérard</$b> </700>
<210 I=bb QSTR=9705>  <$a QSTR=10000>[Verviers]</$a>
                      <$c QSTR=9519>[Editions Gérard & C°]</$c>
                      <$d QSTR=10000>[1973]</$d> </210>
<215 I=bb QSTR=9750>  <$d QSTR=7353>32° carré</$d>
                      <$c QSTR=8601>couv., i11.</$c>
                      <$a QSTR=10000>158 p.</$a> </215>
<010 I=bb QSTR=10000> <$d QSTR=10000>30 BEF</$d> </010>
<225 I=2b QSTR=10000> <$a QSTR=10000>Marabout-flash</$a>
                      <$v QSTR=10000>352</$v> </225>
<517 I=0i1 QSTR=10000><$a QSTR=10000>Souvenirs, révélations,
                      conseils</$a> </517>
<900 I=bb QSTR=9772>  <$a QSTR=10000>B.D. 14.814 352</$a>
                      <$b QSTR=9285>73-2108</$b> </900>
\end{verbatim}}
\normalsize
\caption{\label{resreference} Résultat de l'analyse structurelle
d'une notice.}

\end{figure}


Des essais ont été faits sur à peu près quatre cent notices. Le taux
de reconnaissance est de l'ordre de 85\% avec une moyenne de 20
secondes par notice sur une station Sparc IPX. Le modèle est décrit à
l'aide de 227 règles et fait intervenir 35 actions spécifiques (22\% du
code total).

\section{Conclusion}

L'analyse et la reconnaissance de documents apparaît aujourd'hui comme
un domaine en pleine expansion et l'état de l'art que 
nous avons tenté de dresser montre que des progrès importants ont été
enregistrés sur les documents à structures normalisées. La
bibliographie mentionne de nombreuses techniques d'analyse d'image
adaptées à différents cas de documents (prétraitement, segmentation,
étiquetage). Par ailleurs, plusieurs architectures et systèmes ont été
développés, laissant entrevoir un futur plein de réussite.

Cependant, ce domaine est encore relativement jeune et les solutions
apportées sont bien modestes à cause de la complexité et de la
diversité des données. A l'heure actuelle, aucun système satisfaisant
n'existe, soit parce que la reconnaissance est imparfaite et limitée à
des classes de documents particuliers, soit que le niveau
d'inter\-pré\-ta\-tion de ces systèmes n'a pas su dépasser les couches
d'information de bas niveau. 

Il est vrai que ce domaine, tout comme la parole et la vision, fait 
intervenir une ``perception de haut niveau'' de la connaissance et que
la solution se situe au c{\oe}ur de l'intelligence et la cognition. Il
est illusoire de vouloir reconnaître un document par simple
segmentation et reconnaissance structurelle sans utiliser des
processus cognitifs relatifs à la lecture et à la compréhension du
sens. En nous fondant sur ces faits, nous avons d'abord développé un
système à bases de connaissances ({\sc Graphein}) où la compréhension
repose à la fois sur une stratégie de focalisation 
et sur l'opportunisme des solutions trouvées. Alors que la plupart
des schémas proposés dans la littérature sont de nature
séquentielle, nous avons exploré un point de vue global, hautement
distribué qui cherche à optimiser une mise en correspondance de
structures. Ensuite, inspiré du modèle {\sc Copycat} de Hofstater et
de son équipe~\cite{mitchell93a} dans un autre cadre, nous proposons
une nouvelle architecture de compréhension de documents fondée sur l'{\it
analogie}~\cite{potdevin93a}. 


\bibliography{/loria/ecriture/biblio/biblio}
\end{document}

