        \documentstyle[french,12pt]{article}
% format standard, centr\'{e}
        \setlength{\oddsidemargin}{2mm}
        \setlength{\evensidemargin}{2mm}
        \setlength{\textwidth}{170mm}
        \setlength{\textheight}{250mm}
        \setlength{\topmargin}{-25mm}
% 1 mm entre chaque paragraphe
        \setlength{\parskip}{1mm}
        \setlength{\baselineskip}{12pt}
        \pagestyle{plain}
        \input{psfig}
        \renewcommand{\baselinestretch}{1.5}
% interline space, double


\title{Une approche mixte pour l'analyse des fragments de contenu}
\author{Yannick Chenevoy et Abdel Bela\"{\i}d}
\affiliation{CRIN-CNRS/INRIA Lorraine, Campus Scientifique, B.P. 239\\
F-54506 Vand{\oe}uvre-l\`{e}s-Nancy Cedex\\
e-mail {\tt \{chenevoy,abelaid\}@loria.fr}\\
}
\bibliographystyle{longf}
\maketitle

\small
\paragraph{R\'esum\'e~:}Nous pr\'esentons une approche mixte pour la
reconnaissance de la ``micro-structure'' de documents mod\'elis\'es sous
forme d'une architecture de fragments de contenu au sens {\sc oda}.
L'analyse fait intervenir des aspects structurels mais \'egalement
linguistiques. 

\paragraph{Mots-cl\'es~:} Analyse de documents, micro structure, {\sc
oda}, fragments de contenu, m\'ethode ascendante descendante. 
\normalsize

\section{Introduction} 

L'analyse de documents s'attache le plus souvent \`a la reconnaissance
de la structure g\'en\'erale sous forme d'une hi\'erarchie d'entit\'es
logiques et physiques~(\cite{brown89a}). Dans un niveau
sup\'erieur de reconnaissance (macro structure), les entit\'es
physiques, relatives \`a l'aspect visuel, donnent par exemple des
colonnes, des blocs de texte, des graphiques ou des images; alors que
les entit\'es logiques, relatives \`a l'interpr\'etation du contenu,
donnent par exemple des titres, des paragraphes ou des l\'egendes. 
Ces deux structures, physique et logique, ne sont pas disjointes,
elles sont li\'ees par ce que {\sc oda} nomme les ``fragments de
contenu''. Il est int\'eressant pour la reconnaissance de la macro
structure de se laisser guider par l'aspect physique qui souvent est
tr\`es riche et permet plus facilement de localiser les diff\'erentes
entit\'es.

En revanche, plusieurs applications n\'ecessitent de conduire l'analyse
\`a travers ces fragments de contenu et de descendre au niveau de la
micro structure. On peut trouver des exemples types o\`u il est
n\'ecessaire de focaliser l'analyse sur une r\'egion d'int\'er\^et comme
la zone d'adresse dans les documents postaux pour le tri, le montant
et le libell\'e dans les ch\`eques bancaires, une formule math\'ematique
ou un tableau dans un document composite, etc. Pour ces applications
particuli\`eres il faut rechercher des indices sur l'image, reconna\^{\i}tre 
des caract\`eres, des mots-cl\'es et aller parfois jusqu'\`a l'analyse
syntaxique et s\'emantique des phrases pour lever certaines
ambigu\"{\i}t\'es sur les champs \`a identifier. Ici, l'aspect physique est
souvent diffus et moins riche que pour la reconnaissance de la macro
structure et il est n\'ecessaire de disposer d'un mod\`ele structurel
plus riche en contexte.

L'application d\'ecrite dans cet article concerne la reconnaissance des
notices bibliographiques des catalogues de la biblioth\`eque nationale
de France. Un exemple de notice est donn\'e dans la
figure~\ref{notice}. Nous d\'ecrivons le mod\`ele
repr\'esentant la structure de toute la classe de notices \'etudi\'ees,
puis nous donnons la m\'ethode mixte utilis\'ee pour les analyser.

\section{Mod\`ele des notices}

Le mod\`ele a \'et\'e \'elabor\'e \`a partir de plusieurs pages de
catalogues. Il fait appara\^{\i}tre cinq classes de notices~: les {\it
principales}, les {\it secondaires}, les {\it analytiques}, les {\it
collections} et les {\it renvois}. 

\begin{figure}[htb]
\centerline{\psfig{figure=notice1.ps}}
\caption[]{\label{notice} {\it Exemple de notice bibliographique.}}
\end{figure}

G\'en\'eralement, une notice comprend un {\it groupe vedette}, un {\it
corps}, un {\it groupe Cotes}, un {\it groupe Notes}, etc. Le {\it
groupe vedette}, par exemple, peut comprendre au choix, un {\it nom
d'auteur}, un {\it nom de collectivit\'e}, etc. Ces diff\'erentes
entit\'es peuvent d\'eborder sur les lignes suivantes, ce qui conduit \`a
fonder la recherche sur la localisation de s\'eparateurs sp\'ecifiques
(tirets, crochets, points, etc.). 

Les catalogues, r\'ealis\'es par collage\/, induisent des carrences
typographiques dans les notices. Certaines notices, imprim\'ees,
adoptent souvent le {\it gras} ou {\it l'italique} pour mettre en
relief des champs; d'autres, dactylographi\'ees, utilisent d'avantage
les lettres capitales ou espac\'ees. Enfin, l'image des notices est tr\`es
d\'egrad\'ee du fait des probl\`emes d'acquisition, connectant ou coupant
les formes \`a identifier.

Le formalisme du mod\`ele s'inspire de celui d\'ecrit dans nos travaux
pr\'ec\'edents \cite{chenevoy91a}. Contrairement \`a la macro structure,
le mod\`ele des fragments de contenu tient moins compte de l'aspect
physique et les constructeurs utilis\'es n'induisent pas d'orientation
haut-bas ou gauche-droite. La progression logique dans les fragments
de contenu est celle de la lecture dans les lignes. Ainsi, chaque
entit\'e du mod\`ele peut \^etre caract\'eris\'ee par un constructeur
(s\'equence, choix, aggr\'egat, etc.), des objets subordonn\'es, des
s\'eparateurs et des attributs. Des qualificatifs viennent compl\'eter
la description des objets subordonn\'es pour indiquer s'ils sont
optionnels (opt), obligatoires (par d\'efaut), r\'ep\'etitifs (rep) ou
optionnels suivant une condition (optc).
%(fig.\ref{model}).
%\begin{figure}[htb]
%\footnotesize
%\input{/users/ecriture/chenevoy/=tex/=tgif/fig-model-lisp}
%\normalsize
%\caption[]{\label{model} {\it R\`egles du mod\`ele.}}
%\end{figure}

\section{Extraction d'indices}

Elle repr\'esente le ``bas niveau'' du syst\`eme et met en {\oe}uvre des
fonctions C qui travaillent directement sur l'image des pixels. On
trouve notamment l'extraction des composantes connexes (ccx), la
mesure de l'inclinaison et le redressement de l'image, la fusion des
ccx en mots et en lignes, la recherche des lignes de bases et des bandes
centrales des mots, la recherche du type de la police dominante, etc.

La recherche d'indices consiste \`a localiser les fragments de contenu
v\'erifiant certains attributs~: style des mots (majuscule, gras,
italique, soulign\'e, etc.), formule de renvoi (voir, In., Ed., etc.),
mention de fonction (Adapt., Collab., Comment., etc.) et caract\`eres
de s\'eparation (``$\rightarrow$'', ``['', ``]'', ``('', ``)'', etc.). 
Le tableau de la figure \ref{contfrag} repr\'esente quelque
caract\'eristiques physiques des fragments de contenu. 

\footnotesize
\begin{figure}[htb]
\centerline{\input{tabfrag}}
\caption[]{\label{contfrag} 
{\it Caract\'eristiques physiques~: (1) Premier \'el\'ement d'une vedette
- Imprim\'e; (2) Cote - Imprim\'e; (3) Titre ou premi\`ere sous vedette
de collectivit\'e; (4) Note - Imprim\'e; (5) Titre forg\'e; (6) Mot
\'etranger dans le titre; (7) Titre original ou parall\`ele,
localisation de collectivit\'e ou deuxi\`eme sous vedette de
collectivit\'e; (8) Mention de fonction ou renvoi; (9) D\'ebut de la
zone titre; (10) Fin zone titre; (11) Fin de zone; (12) d\'epart d'une
collection. }}
\end{figure}
\normalsize

\subsection{Reconnaissance du style des mots}

\begin{figure}[htb]
\footnotesize
\centerline{\input{figure=res_style.eps}}
\normalsize
\caption[]{\label{resstyle} {\it r\'esultats de la reconnaissance du
style des mots sur diff\'erentes notices.}}
\end{figure}

\paragraph{Mots gras~:} Deux valeurs sont associ\'ees \`a chaque
ccx lors de son extraction~: le nombre de pixels noirs $npn$
et le nombre de segments noirs horizontaux $nbseg$. L'analyse de
l'histogramme des valeurs de $npn~/~nbseg$ fait appara\^{\i}tre un pic
caract\'eristique de l'\'epaisseur moyenne des traits. Cette mesure permet
de localiser les mots gras avec de bons r\'esultats s'ils sont
minoritaires dans l'espace de recherche.

\paragraph{Mots italiques~:} Le profil de projection verticale du mot
(\`a l'inclinaison 0) est compar\'e au profil de projection \`a
l'inclinaison $\alpha$ ($\alpha$ variant autour de l'inclinaison
standard des italiques). L'inclinaison retenue est celle qui maximise
le crit\`ere~: $\sum_i N[i]^2$, N[i] est le nombre de points
accumul\'es en i.

\paragraph{Mots soulign\'es~:} Le profil de projection horizontale du
mot est analys\'e afin de localiser pr\'ecis\'ement les bords haut et bas
du trait de soulignement (s'il existe). Un suivi de contour partiel
permet de supprimer le trait en pr\'eservant les \'eventuels jambages qui le
traverseraient. 

\paragraph{Mode des mots~:} L'analyse de la taille des
composantes et de leurs espacements permet de d\'eterminer le mode des
mots (majuscule, petite minuscule, mots espac\'es\ldots).

\subsection{Reconnaissance de mots particuliers}

Le lexique de cette application comporte un nombre relativement
restreint de mots (quelques dizaines). L'int\'er\^et ici n'est pas de
reconna\^{\i}tre tous les mots, mais certains qui peuvent fournir un
contexte lexical sur le type du fragment de contenu analys\'e. Certains
mots ou abr\'eviations se retrouvent souvent dans la zone titre,
d'autres dans la zone collation, etc. Enfin, certaines mentions de
fonctions comme \underline{Ed.} ou \underline{Collab.} conditionnent
directement le type de la notice. Nous avons choisi une m\'ethode
globale simple mais rapide qui prend en compte les profils haut et bas
du mot, sa longueur, et le rapport $N_i/E$, o\`u $N_i$ est le nombre de
pixels rencontr\'es par une sonde $i$, et E l'\'epaisseur moyenne du mot.
Cinq sondes sont utilis\'ees horizontalement, judicieusement r\'eparties
dans le mot (voir fig.\ref{sondes}). Nous verrons plus loin que cette
m\'ethode peut s'inscrire dans un m\'ecanisme ascendant ou descendant;
ascendant lorsque la reconnaissance de certains mots augmente la
probabilit\'e de certains champs; descendant lorsque la reconnaissance
des mots s'effectue sur un champ \`a v\'erifier, et donc avec un
vocabulaire restreint (contexte lexical). 

\begin{figure}[htb]
\centerline{\psfig{figure=sondes.ps}}
\caption[]{\label{sondes} {\it Sondes~: 1 au dessus de la bande
centrale, 2 3 et 4 dans la bande centrale, 5 sous la ligne de base.}}
\end{figure}

\subsection{Reconnaissance de s\'eparateurs}

La multitude des choix repr\'esent\'es dans le mod\`ele nous a conduit \`a
\'elaborer une analyse ascendante-descendante pour laquelle une phase
d'initia\-li\-sa\-tion est n\'ecessaire afin de disposer d'indices de
d\'epart. Les s\'eparateurs b\'en\'eficient d'un int\'er\^et particulier du
fait de leur importance pour la suite du traitement. Les principaux 
s\'eparateurs utilis\'es dans les notices sont les crochets,
les parenth\`eses, les virgules, les points et les tirets. La
principale difficult\'e ici provient des images bruit\'ees o\`u les
s\'eparateurs sont souvent connect\'es \`a des caract\`eres ou sont
coup\'es (fig.\ref{connect}). De plus, certains caract\`eres peuvent se
confondre avec des s\'eparateurs connect\'es, conduisant
\`a une analyse plus fine des points de connection (fig.~\ref{rescor}).
Enfin, la position de ces s\'eparateurs par rapport \`a la ligne de base
n'est pas constante, m\^eme pour un type de police d\'etermin\'e. 

\begin{figure}[htb]
\centerline{\psfig{figure=connect.ps}}
\caption[]{\label{connect} {\it Exemple de connection du crochet avec
le mot.}}
\footnotesize
\begin{center}
\begin{tabular}{|c|r|r|}
\hline
Forme \`a identifier & 
Corr\'elation avec 
\psfig{figure=cro1.ps}
& Corr\'elation avec 
\psfig{figure=par1.ps}
\\ \hline
\psfig{figure=e1.ps}
 & 4,7 & 16 \\
\psfig{figure=e2.ps}
 & 76,7 & 43 \\
\psfig{figure=e3.ps}
 & 37,5 & 91 \\
\psfig{figure=e4.ps}
 & 55,5 & 31 \\
\psfig{figure=e5.ps}
 & 37,5 & 61\\ \hline
\end{tabular}
\end{center}
\normalsize
\caption[]{\label{rescor} {\it Quelques r\'esultats de corr\'elation}}
\end{figure}
\begin{figure}[htb]
\centerline{\psfig{figure=masques.ps}}
\caption[]{\label{masques} {\it Masques r\'ealis\'es lors de
l'apprentissage~: de gauche \`a droite, crochets et parenth\`eses
imprim\'es; crochets et parenth\`eses dactylographi\'es.}}
\end{figure}

Plusieurs techniques sont combin\'ees, parmi lesquelles l'analyse
typo\-gra\-phi\-que dans la ligne et la mise en correspondance avec des
masques appropri\'es, r\'ealis\'es par ``apprentissage''
(fig.~\ref{masques}). Le masque est d\'eplac\'e l\'eg\`erement de gauche
\`a droite et de haut en bas et on retient le meilleur score de
corr\'elation. Cependant, l'apprentissage des masques peut comporter
certains d\'efauts dus \`a la m\'ethode statistique employ\'ee et \`a la
diversit\'e des formes en pr\'esence, ce qui peut conduire \`a certaines
d\'erives lors de la reconnaisance. Nous avons choisi comme seuils de
corr\'elation sc1~=~75 (s\^ur) et sc2~=~50 (non s\^ur). Les formes
analys\'ees sont les composantes du d\'ebut et de la fin des mots
physiques. Une pile de ``parenth\`eses'' est tenue \`a jour afin de
remettre en cause les choix ant\'erieurs non s\^urs en cas de conflit
sur les ouvrants et les fermants.

\section{Strat\'egie d'analyse}

La strat\'egie adopt\'ee est guid\'ee \`a la fois par le mod\`ele et par
les indices trouv\'es. Suivant la pertinance de ces indices, la
strat\'egie est ascendante, descendante ou mixte.

\subsection{Analyse ascendante}

Soit F l'ensemble des fragments $f_i$ localis\'es \`a l'\'etape~$i$ de
fa\c{c}on certaine. Pour chaque fragment $f_i$ trouv\'e, on
extrait du mod\`ele les entit\'es o\`u $f_i$ appara\^{\i}t comme objet
subordonn\'e. On obtient ainsi un ensemble de r\`egles candidates
($r~\rightarrow~\lambda f_i \lambda'$), o\`u $\lambda$ et $\lambda'$
sont respectivement les contextes gauche et droit de $f_i$ \`a
d\'eterminer et $r$ est l'hypoth\`ese de fusion. 

\paragraph{Choix de la meilleure r\`egle~:} les r\`egles candidates sont
class\'ees par quantit\'e d'information croissante. A chaque fragment $f_i$
est associ\'ee une mesure $I(f_i) ~=~ - \log_{2} (P_{R}(f_i))$. Cette
mesure est calcul\'ee \`a partir de la probabilit\'e d'observer le
fragment dans la r\'egion d'int\'er\^et R.
Cette probabilit\'e initialis\'ee par la probabilit\'e {\sl a priori},
fournie par le mod\`ele est mise \`a jour apr\`es chaque v\'erification ou
recherche d'indice.
%, et est mise \`a jour par les scores de mesures
%et de segmentation $\frac{1}{n}\sum_{i=1}^{n} s_i$, o\`u n est le
%nombre d'attributs ou d'objets subordonn\'es v\'erifi\'es et $s_i$
%correspond au r\'esultat de la mesure de l'attribut ou de l'objet $i$.
Ainsi, la quantit\'e d'information d'une r\`egle est fournie par la
moyenne des informations des fragments de sa partie droite. On va
pouvoir ainsi tester en priorit\'e les r\`egles qui sont susceptibles de
conduire le plus rapidement vers la solution.  Une r\`egle choisie
fournit une liste d'entit\'es hypoth\'etiques comme contexte gauche et
droit \`a l'\'el\'ement $f_i$. Ces entit\'es sont ensuite v\'erifi\'ees de
mani\`ere descendante et l'ensemble des hypoth\`eses de fusion est mis
\`a jour en fonction de leur affirmation ou infirmation~\cite{mohr79a}.  

\subsection{Analyse descendante}

On tente ici de v\'erifier les contextes gauche et droit d'un fragment $f_i$
donn\'e, appel\'e fragment de r\'ef\'erence.

\paragraph{choix du fragment \`a tester~:} 
Les entit\'es hypoth\'etiques de ces contextes sont class\'ees par
complexit\'e croissante. La mesure utilis\'ee tient compte de la
``facilit\'e'' de v\'erification d'un objet. En effet, chaque fragment
de contenu (en tout cas, chaque fragment terminal) poss\`ede une liste
d'attributs plus ou moins faciles \`a mesurer. Ainsi, l'attribut
``gras'' aura un score de complexit\'e plus faible que l'attribut
``italique'' car il est plus facile \`a mesurer. Ces scores de
complexit\'e sont fournis par le mod\`ele et d\'ependent essentiellement
des m\'ethodes utilis\'ees pour les mesures (performance des
algorithmes). Une mesure de complexit\'e est associ\'ee \`a chaque
fragment hypoth\'etique de mani\`ere \`a privil\'egier les fragments les
plus faciles \`a v\'erifier~: $SC(f_j) = \sum_{a} sc(a)^2$, ($f_j \in
\lambda \cup \lambda'$, a est un attribut de $f_j$ et sc(a) sa
complexit\'e).

\paragraph{Espace de recherche R~:} 
$f_j$ est ``\`a gauche'', ``\`a droite'' du fragment de
r\'ef\'erence, ou entre deux fragments de r\'ef\'erence. Ces fragments
ayant d\'ej\`a \'et\'e localis\'es, leurs coordonn\'ees sont connues.
L'espace de recherche est donc d\'efini pour l'objet choisi.

\paragraph{Phase descendante~:} 
Si $f_j$ est terminal, son nom, ou \`a d\'efaut, la liste de
ses attributs d\'eclanche une suite de traitements permettant de le
v\'erifier. Les outils utilis\'es \`a ce niveau font intervenir la
reconnaissance de mots, la reconnaissance de style (gras, soulign\'e,
italique, majuscule, petites minuscules, etc.). Les scores retourn\'es
par ces mesures permettent de mettre \`a jour la probabilit\'e {\sl a
posteriori} de $f_j$. Si $f_j$ n'est pas terminal, on extrait du
mod\`ele les r\`egles produites par $f_j$ ($f_i \rightarrow \lambda$) en
tenant compte des choix et des qualificatifs des objets subordonn\'es
(partie droite). De m\^eme que pour l'analyse ascendante, cet ensemble
de r\`egles est  tri\'e par quantit\'e d'information croissante afin de
choisir une r\`egle. Le processus descendant est pousuivi pour chaque
entit\'e de la partie droite de la r\`egle choisie.

\section{Conclusion}

Cette m\'ethode mixte permet de reconna\^{\i}tre la structure des documents
en testant en priorit\'e les hypoth\`eses les plus probables et les
indices les plus s\^urs dans le but de converger le plus rapidement
vers la solution. Elle s'int\`egre dans le syst\`eme {\sc Graphein}
d'analyse de la structure des documents. Ce syst\`eme utilise une
architecture multiexperts d\'ecrite dans nos pr\'ec\'edent travaux. {\sc
Graphein} \'etant un syst\`eme g\'en\'eral, les diff\'erents outils, ainsi
que le mod\`ele pr\'esent\'es ici sont d\'evelopp\'es comme autant de
sources de connaissances modulables suivant le type de document
analys\'e.

\small{\bibliography{/u/ecriture/commun/biblio}}\normalsize
\end{document}
