\documentstyle[11pt]{article}
         \setlength{\unitlength}{1mm}
         \setlength{\oddsidemargin}{2mm}
         \setlength{\evensidemargin}{2mm}
         \setlength{\textwidth}{154mm}
         \setlength{\textheight}{225mm}
         \setlength{\topmargin}{-3mm}
         \setlength{\parskip}{1mm}
         \setlength{\parskip}{1mm}
        \setcounter{tocdepth}{2}
        \input{psfig}

\title{Qualitative Analysis of Low-Level Logical
Structures\footnote{This work was funded by the EEC libraries
programme {\sc lib-more}}}

\author{A. Belaïd, J. C. Anigbogu et Y. Chenevoy\\~~\\
CRIN-CNRS/INRIA Lorraine, Campus Scientifique, B.P. 239\\
F-54506 Vand{\oe}uvre-lès-Nancy Cedex, France\\
e-mail : {\tt abelaid@loria.fr}}

\date{}

\begin{document}

\bibliographystyle{alpha3}

\maketitle

{\bf Abstract:} This paper presents a qualitative approach
to logical structure recognition of library references. The
system is driven by a generic model of a reference class 
and by an {\sc ocr} flow, given in {\sc sgml} format, that include {\sc
ascii} code of the characters and information about the typographic
style and the lexical affiliation of words. The approach used is
based on hypotheses production and verification about the existence of
sub-field limits in the reference area. At each step of the
analysis, the generated hypotheses are sorted on the basis of their
confidence scores and the most likely hypothesis is analyzed. The
result is a structured flow containing, in {\sc unimarc} format,
the list of different sub-fields recognized, accompanied with their
confidence score. 


{\bf Keywords}: Document Analysis, Low-level logical structure,
Qualitative analysis, {\sc oda} formalism, Library reference

\section{INTRODUCTION}

Document analysis has become, with the progress in {\sc ocr}
technology and electronic publishing, a helpful tool for document
input. Many attempts in this area have been made in the last
decade~\cite{den90,sri86,won82,che91}. The main approaches
tend to use a domain knowledge model to segment the document image
into homogeneous regions and to label them according to the model
description. An optical character reader is used to extract and
recognize the text components. The challenge of such systems is to
retrieve the document content in spite of the possibly bad quality of
images and the uncertainty of the generic model, and to incorporate
text reading into structure analysis. 

The key concept in document analysis is that of
structure~\cite{bro89,and88}. It gives the information to guide the
system's actions. Often, document analysis consists in finding the high
level structure in the document in terms of a hierarchy of physical
and logical objects. At this level, the layout components, dealing
more with the visual perception of the document, correspond to big 
regions such as {\it columns}, {\it text blocks}, {\it graphics} or
{\it photographs}. The {\it logical} components, more connected with
content interpretation, give for instance, {\it titles}, {\it
paragraphs} or {\it footnotes}. For this high level structure, the
strategy would need to be guided by the physical aspect
which is rich and allows the easy location of the different
components~\cite{che91,che92}.

There are many applications where it is necessary to pursue the
analysis across the content and to extract a finer structure. This
concerns the content architecture of physical blocks such as
{\it footnotes}, {\it figure captions}, {\it bibliography references},
etc. In these cases, the physical structure is generally limited to a
sequence of lines and words, not very much exploitable by the
analysis. The logical structure should be more informative. It
provides beyond field labels, a fine description of the content such
as the typographic style, the linguistic affiliation of words and
contextual information on successive sub-fields such as separators
and their location. Document analysis here resembles document
understanding. Several document image understanding systems 
have been proposed~\cite{sri87,che92} for documents such as 
letter addresses, forms or library references where the {\it logical} 
structure is more complete than {\it layout} structure.

This paper describes structure modeling for low-level
logical structure analysis of library references and its inherent
recognition strategy. The terminology is based on the {\sc oda}
international standard. Because of the uncertainty of the
{\sc ocr} data flow, we use a qualitative analysis based on hypothesis
evaluation. This allows to take into account what is important to
recognize and to evaluate the solution retained.

\section{LOW-LEVEL STRUCTURE DESCRIPTION}

\subsection{Reference description}

References are typed in several library catalogues and sorted by month and
year. Figure~\ref{reference} shows an example of a library reference.
The physical structure is partitioned into five areas. The first 
area, composed of the first line, contains on the right hand side, the
``{\sc cdu}'' code (Classification D\'ecimale Universelle) which
gives some information about the library classification of the
reference. The second area contains the reference body composed of a
series of fields describing the referred work in the reference such as~:
``{\it vedette}'' (author name or beginning of title), ``{\it title}'',
``{\it address}'', ``{\it collation}'' (material description of the
work~: location, editor, year, format, etc.). The body is often typed
in many lines. The third area contains the ``{\it Collection}'' field
(description of the series, volume, etc.). The fourth area contains
the ``{\it Note}'' field which gives information about, for example, the title
(abbreviated, complete, original, etc.). These last two areas are
optional and so are not always present in the references. The last
area, located on the last line of the reference, contains the ``{\it
Reference}'', on the left hand, and the ``{\it Order  number}'', on
the right hand.  

\begin{figure}[htbp]
\centerline{\psfig{figure=notice1.eps,width=13cm}}
\caption{\label{reference} Example of a library reference.} 
\end{figure}

\subsection{Structure modeling}

Knowing that the problem is to find the sub-fields within
reference areas, the model specification concentrated on the
description of sub-field properties, by the distinction of their
typographic styles, the existence of particular words or group of
words and their appearance in certain lexicons, and essentially their
limits (type of initials and finals such as capital letters,
particular words or type of punctuation separating the sub-fields). 

The {\sc oda} formalism was used to model the reference structure. The
model is given by a context-free grammar written in the {\sc ebnf}
formalism. The format of a production rule is as follows~: 

\[\begin{array}{l l l}
Term & ::= & Constructor ~subordinate\_Objects[Qualifier]|\\
     &     & Constant ~|~ Terminal \\
Constructor & ::= & seq\_td~ |~ seq\_lr~ |~ seq~ |~ aggr~ |~ cho~ |~ import
\end{array}\]

\subsubsection{Constructors and qualifiers}

A term, the left hand of a rule, can be simple (constant or
terminal) or composed of subordinate objects. In the last case, a
constructor describes the relationship between objects in the term
area. The constructor precises the order of the appearance of subordinate
objects such as {\sc sequence}~: top-down ({\it seq\_td}),
left-right ({\it seq\_lr}) or logical ({\it seq}), {\it
aggregate} ({\it aggr}) or {\it choice} ({\it cho}). A special
constructor ``{\it import}'' is used to inherit for the term some or
the total description of another existent and similar term.
Furthermore, to express the object occurrence in the term, each object
may be accompanied by a qualifier such as {\it optional} (?), {\it
repetitive} (+) or {\it optional-repetitive} (*).   

Here is an example~:

\begin{tabular}{|l l l|}
\hline
{\sc reference} & ::= & {\it seq\_td} {\sc cdu} {\sc global\_body} {\sc zref}\\
{\sc global\_body} & ::= & {\it seq\_td} {\sc body zcollect? znote*}\\
{\sc zref}        & ::= & {\it seq} {\sc ref} {\sc ordernumber}\\
...\\
\hline
\end{tabular}

The term ``{\sc global\_body}'' is described as a top-down sequence of
terms where ``{\sc zcollect}'' is optional and the note area ``{\sc
znote}'' is optional-repetitive. 


\subsection{Attributes}

Because of the weakness of the physical structure and the 
multitude of choices represented in the model, we add to the
previous description some attributes given by the library
specification to better precise the description of the reference
components. These attributes are associated to each rule
in the following format~:

\[Attribute\_name ~~~~ \{[-] value[weight]\}*\]

The minus sign indicates the negation of an attribute value. 

Several kinds of attributes have been defined, among them, {\it Type}
(string, line, word, char, etc.), {\it Mode} (capital, numeric,
alphabetic, punctuation, etc.), {\it Style} (bold, italic,
standard, etc.), {\it Position} (begining of line, inside, end),
{\it Lexicon} affiliation (author index, countries, towns, abbreviations,
articles, etc.), {\it Separator} between subordinate objects
(space, comma, hyphen, etc.), {\it Weight} which specifies the degree
of importance of subordinate objects, etc.

~~\\
{\bf Example} :

\begin{tabular}{|lll|}
\hline
{\sc title} &::=& {\it seq} {\sc propertitle restoftitle}\\
Style && -italic \\
Position && Begline\\
Sep && Comma\\
\hline
\end{tabular}
~~\\

This example describes the term ``{\sc title}'' as a logical sequence
of two objects~: ``{\sc propertitle}'' and ``{\sc restoftitle}'' 
where the style is not italic (may be bold or standard), which is
located at the beginning of the line and whose separator is a comma.


\subsection{Weights}

Given an uncertain {\sc ocr} flow and in order to obtain an evaluation
of the retained solution, weights are used. These weights are
specified in symbolic form, for example [A,G], and the actual numeric
values are determined from a base value specified by the user. In this
manner, the user can specify the importance that he attaches to each
subordinate object.

~~\\
{\bf Example}~:

\begin{tabular}{|lll|}
\hline
{\sc zpb} &::=&{\it seq} {\sc lcap rp particule?}\\
Weight&& {\sc particule} A {\sc lcap} G\\
\hline
\end{tabular}

The optional object ``{\sc particule}'' (A) is more important than
``{\sc lcap}'' (G). This specification is logical since an optional
object normally helps in reinforcing the possible presence of a term
more than an object that is always present.

\subsection{Remedial actions}

The processing of a rule needs sometimes a check procedure before or
after its processing, either to prepare the analysis of the rule, to
recover from failure of the analysis, or to post-process the
result. For example, if the analyzer is expecting only
numeric values in a 
region being analyzed but fails to find them, if there is a remedial
user function attached, it is called (usually this function should 
check for {\sc ocr} substitution errors, ex~: ``l'' for ``1'',  ``O''
for ``0''). 

~~\\
{\bf Example} : 

\begin{tabular}{|lll|}
\hline
{\sc fip}&::=& {\it cho} {\sc fip1 ipa} \\
Clex && -Abn\\
Style && italic\\
Action && +VerifyStringInField(fr.,false) Restitute(215,bb)\\
\hline
\end{tabular}

This production rule describes a choice between two terms neither of
which should contain any of the strings in the lexicon Abn
(expressed by the attribute Clex). There are two actions. The first one
indicates to verify before the rule analysis that the search zone does
not contain the string ``fr.''. In the event of the hypothesis being 
verified, the second function is executed to create a {\sc unimarc}
tag before restituting the result in the required format.

\section{STRUCTURE ANALYSIS : THE PROBLEM DATA}

Several problems arise while trying to extract the logical structure
from a document. The major one is that the image represents the
physical structure, while the recognition objective is to get
out the logical components. For this, we have to resolve two sub-problems~:
\begin{itemize}
\item find the physical structure, i.e. to cut the document image
into homogeneous and structural entities~: blocks, lines, words, etc.
\item convert the physical structure into a logical one, i.e.
to retrieve the document ``semantics''. 
\end{itemize}

Because of the finesse of the reference structures, the solution to
these two problems is searched for with a lot of precaution. The 
reference sub-fields are characterized by very unstable and fragile
indications. For example, the typographic style such as bold or italic
which is capital for the location of the author name and the title, is
often difficult to determine by {\sc ocr}. The style either overflows
into several sub-fields or fall short of the entire sub-field area.
Punctuations which mark the limit between sub-fields can sometimes
disappear or be substituted with something else. Word
recognition does not always succeed, which leads to lexical
affiliation errors. Furthermore, a lot of the sub-fields are optional,
and as such complicate the system's actions because it has to take
into account all the possibilities. 

An approach to this kind of data analysis consists in constructing all
possible segmentation hypotheses of sub-fields from all the possible
separators and to evaluate them in order to find the most likely
combination and order of sub-fields. This is to reduce the system
errors and ambiguities.

\section{SYSTEM OVERVIEW}

Figure~\ref{figure1} shows the major components of the developed system.

The {\it Input} is given by tagged {\sc ocr} output references. 

The {\it Domain knowledge} contains the generic structure of the
references (model) and also the data flow to recognize. The flow
is given in {\sc sgml} formalism. The model is compiled and the
flow is filtered to extract interesting information for the
analysis. 

The {\it Databases} contain all lexicons used for term
verification (index of author names and titles, towns, countries,
expressions, etc.). These indexes were recognized in a previous step in the
same manner, that is, with rules and tagged {\sc ocr} output. What follows
describes only the reference analysis.  

The {\it Structural analysis} is the main module of the
system. The system control acts on the hypotheses management process
to produce and verify hypotheses on the specific structure. The
specific structure is represented by a tree of terms. Hypotheses
are produced for each node of the tree and construction is pursued
first for the node which looks most likely (has the highest
score). 

The {\it Output}, tagged in {\sc unimarc}, contains the specific
structure identified by the system.

\begin{figure}[htbp]
%\centerline{\psfig{figure=figure1.eps,width=13cm}}
\caption{\label{figure1} System Overview.} 
\end{figure}

\section{INPUT DATA}

The data flow is obtained from a layout analysis of the
catalogue page images and a reading text process. 

The result of these tasks is a data flow containing the
reference text coded in {\sc sgml}. The tags separate the
lines and different information such as style or lexical class
corresponding to each word (token). Figure~\ref{flowreference} shows
the flow corresponding to the reference of figure~\ref{reference}. 

\begin{figure}[htbp]
\small{
\begin{verbatim}
<DOC TY=N PROV=ENRLEX EG=OK NPN=2085 NDN=2114 IMA=users/brb/juin73/images>
<PAG NP=1 NOM=0008.ima> <COL XHG=63 YHG=1900 XBD=1027 YBD=2912>
<NOT NON=2108> 159.962 <LEX L=AFR><B>Liger-Belair <LEX L=GNL,AFR><RED 
F=253>(Gérard).</B> <LEX L=GFR,GNL>Je <LEX L=GFR>suis <LEX
L=GFR>fakir. <LEX L=GFR,GNL>([Par] Gérard <LEX
L=AFR>Liger-Belair). <I>(Verviers, <RED F=253>Editions <LEX
L=GNL,AFR><RED F=253>Gérard &</I> <LEX L=GFR,GNL>C, 1973),
32 <LEX L=GFR,GNL,AFR><I>carré, <RED F=253>couv., <LEX
L=GFR,GNL>i11.,</I> 158 <LEX L=GFR,GNL><RED F=253>p. (30 <LEX
L=GNL><RED F=253>fr.). <LEX L=GFR,GNL>(Marabout-flash, 352). <LEX
L=GFR>[Titre <LEX L=GFR>introductif: <LEX L=GFR>Souvenirs, <LEX
L=GFR>révélations, <LEX L=GFR,GNL>conseils]. <LEX
L=GFR,GNL><RED F=253>B.D. 14.814 352 <S N=14><I>73-2108</I>
</NOT>
</DOC>
\end{verbatim}}
\normalsize
\caption{\label{flowreference} Flow of the given reference.}
\end{figure}

Each reference is located in this flow between two successive
tags ``$<$NOT'' and ``$<$/NOT$>$''. Useful tags for the document
analysis are ``LEX'' which gives the lexicon affiliations of words,
``I'' for italic style, ``B'' for bold style, and ``S'' for the number
of spaces. The defaults style is standard and as such not tagged.

\section{DOMAIN KNOWLEDGE}

The information given by the model and the data flow are reorganized
to be used by the analysis process. 

\subsection{Model compilation}

Grammar text is converted by a syntax analyzer and code generator
into a working structure. The working structure is a dynamic table of
terms where the entries correspond to term codes. Each term is given
by a list of characteristics gathered in a characteristic table. This
allows the system to read rapidly the characteristics of each term
analyzed. 

\subsection{Data filtering}

The filtering task consists in extracting the useful information
for structural analysis. In order to do this, the system generates
two structures~: 

\begin{itemize} 
\item a buffer containing only the text (without the tags),
\item a table which contains useful tokens extracted from the
flow such as style, token size, etc., and a pointer to the buffer.
\end{itemize}

\section{STRUCTURAL ANALYSIS}

\subsection{Principle}

The objective of our approach is to introduce qualitative
``reasoning'' as a function of the recognition evaluation. This
evaluation allows~: 
\begin{itemize}
\item the reduction of errors and ambiguities dues to faulty data
({\sc ocr} errors, data not fitting the model specification, etc.),
\item taking into account what is important to recognize,
\item the qualitative evaluation of  the obtained solutions,
\item the isolation and separation of doubtful areas.
\end{itemize}

To achieve this objective, weights are first assigned by the user
to the terms and attributes according to the degree of importance he
attaches to them. Objects for which weights are not 
specified are automatically assigned weights as a function of the
number of objects present for this term as well as the symbolic
weights already assigned to the other objects by the user.

For example, the ``{\sc cdu}'' is of type ``line'' as it always fits
into a single line (this automatically means that the analyzer will
conclude that it must end with a carriage return), alignment
``right'', mode ``printable'' as any character can be in this zone. The
style is standard (default style and so need not be specified). Weights
are attached to attributes that the user feels are important
for the good recognition of the field or object (left-hand term). To
stop an attribute from playing any role, the user attaches a weight of
zero. 

The expressive power of our grammar is such that an object can
have several values of the same attribute. For example, if all the user
has as information about the field is that it is non numeric and does not
contain punctuations, this translates into something like~: 

\begin{center}
Mode $~~~~$ -num 5 -punct 3
\end{center}
~~\\
where 5 and 3 are relative weights attached to non numeric and non
punctuation respectively. These weights, just like for subordinate
objects, are optional.

The specific structure is a tree of nodes corresponding to the terms
analyzed. At each step, the system further decomposes terms stacked in
an agenda. This stack is sorted by decreasing order of {\it 
a priori} scores. Since the agenda is always sorted in decreasing
order of hypothesis scores, the analyzer is said to function in an
opportunistic mode. That is, it always first selects the term that
looks most promising. Thus, it can move from one branch of the
hypotheses tree to another in no ``apparent'' order. Terms that are no
longer decomposable (i.e. leaves) are directly verified and as such
either pass or fail. If the analysis fails and a recovery function is
present it is first executed before the next item on the agenda is
selected and processed. This process continues until the agenda is
empty. The result and evaluation scores for the different nodes in the
hyotheses tree traversed to produce the output data for the fields
that need to be restituted. For example, in the references we treated,
names are transformed from (Surname Firstname(s)) to (Firstname(s)
Surname) while addresses are not restored.

The different analysis steps are detailed below.

\subsection{Initialization}

\begin{enumerate}
\item In the beginning, the agenda is initialized to the
model axiom.

\begin{center}
(Code for {\sc reference}, 100)
\end{center}

\item The specific structure is then created by initializing it with
the one current hypothesis (see fig.~\ref{figure4})

\begin{figure}[htbp]
%\centerline{\psfig{figure=figure4.eps,width=13cm}}
\caption{\label{figure4} Schema of the Specific Structure.}
\end{figure}

\underline{Status}~:

\begin{tabular}{l l}
wait &: hypothesis not yet verified\\
passed &: hypothesis verified with success\\
failed &: hypothesis failed
\end{tabular}

\underline{Score}~: {\it a priori} hypothesis score based on the
verification or not of the attributes, the initials and finals of the
generic term being verified.

\underline{Term}~: pointer to the generic term.

\underline{Father} : pointer to the generator of
this hypothesis (null for the root).

\underline{Weight} : the more an object score is important, the more
its evaluation will  have an influence on the final score. Weights
should be big when we approach the root. Inversely, the more we go
down in the tree, the more weights become less and less important.  

The weight is automatically computed during the analysis. It depends
on the depth of the father node (in the specific structure) and on the
symbolic weight given by the user as well as the scores of the
attributes verified. 

Let the rule be~:

\[O_{p} ::= seq~ O_1~O_2*~O_3? \ldots O_N\]

~~\\
where $O_i \in \{ O_1, O_2,\ldots, O_N \}$ is a subordinate object and
$N$ is the number of subordinate objects for the term $O_p$.

The evaluation function $E$ is given as~:

\[E(O_{p}) = \displaystyle \frac{\displaystyle \sum_{i=1}^{N}
P_{_{O_i}} \times E(O_i) \times L(O_i)}{\displaystyle \sum_{i=1}^{N}
P_{_{O_i}} \times L(O_i)}\] 

~~\\
where $P_{_{O_i}}$ is the weight of $O_i$, $L(O_i)$ is the number of
characters that make up subordinate object $O_i$, and $N$ is the
number of subordinate objects that compose the term. $P_{_{O_i}}$ is
defined as~: 

\[P_{_{O_i}} = p_{_{O_i}} \times \displaystyle \frac{D}{d}\]

~~\\
where~: 
\begin{quote}
$d$ = depth of $O_i$ in the tree,\\
$D$ = maximum depth in the model (21 in the present case),\\
$p_{_{O_i}}$ = weight deduced from the symbolic value given by the
user or computed as a function of the number of brothers.
\end{quote}

In this manner, the contribution of a son to the final score of
its father is also a function of the proportion of the area it occupies
in the zone assigned for its father. Thus, correctly recognizing a
subordinate object that is 20 characters wide in a zone of 25
characters (for the left-hand term, i.e. the father) has its importance. 
\end{enumerate}

\subsection{Iteration}

The analysis task is repeated while there are hypotheses to verify.
The constraint imposed on the system is to find all solutions (not
just the first, even if this sometimes leads to ambiguities). The
procedure is as follows~:

\begin{description}

\item a) pop off the most likely hypothesis from the list of goals
(agenda);
\item b) see if the hypothesis has already been processed in another
context, in which case, the result is directly inherited from the
solution tree;
\item c) else, see if actions have to be verified before. If yes,
perform them (there are actions that give directives to follow);
\item d) else (general case) analyze the constructor~:
\begin{description}
\item d.1) \underline{{\sc choice}}

- the search area is the same as that of the father, in this case it
is easy to search for frontiers;

- each of the choices inherits the {\it a priori} score of the
left-hand term (father).

- if the confidence score is acceptable, we put in the agenda the
corresponding subordinate object (the user can modify the cut-off score). 

\item d.2) \underline{{\sc sequence}}, ex: Seq A B C\\

- find in the search area (zone of the left-hand term) all the
initials and finals of the objects A, B and C. The initials and finals
are terminals given by the model (characters, words, etc.);

- construct  all the potential zones in the buffer
corresponding to the combination of initials and finals; that is, for
each possible final of A, find an initial of B that is immediately to
its right. For this combination, choose a final of B and find an
initial of C that corresponds, etc.

- these potentials combination  will be considered as hypotheses and stored
in the specific structure. Each of the objects that is part of a
hypothesis but is not a terminal is also pushed onto the agenda so as
to be analyzed in its own turn.

\item d.3) \underline{{\sc aggregate}}

-  is simply a choice of all possible combinations of the subordinate
objects. That is, all possible sequences (d.2) of the subordinate objects
are constructed and treated as choices (d.1)
\end{description}

\item e) sort the agenda by score and return to b)
\end{description}

\section{EXPERIMENTAL RESULTS}

Figure~\ref{resreference} gives the analysis result of the reference
given in figure~\ref{reference}. All the sub-fields were correctly
localized. They are coded and tagged in {\sc unimarc}. ``QSTR''
indicates the evaluation score (maximum 10 000).

\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} Structural Analysis Result of the Given
Reference.}
\end{figure}

The method has been tested on about 370 references. The average
analysis time on a {\sc sparc} 10 is 20'' with a minimum of 3'' and a
high of 3' depending on the complexity of the reference. This is the
case when the reference does not fit into the definition of the model
or the {\sc ocr} made mistakes as regards, for example, style (which
sometimes is the only information that can help identify a zone) or
completely misrecognized characters or punctuations. Before the
analyzer will give up on a reference, it is forced to explore all
hypotheses it generated. Since the goal is to find all possible
solutions, the fact that it encountered errors in critical areas does
not mean that there are no solutions in other branches of the solution
tree. 

In the event of errors, the system generates a fictive {\sc unimarc}
code 903 which it uses to demarcate the zone it should have recognized
for a field but which does not quite fit the characteristics as
specified by the user. This helps in modifying the model to take care
of exceptional cases or to really determine that the reference
was badly formed as a result of {\sc ocr} errors, the printers devil or
outright bad transcription of the reference. 

When the system finds more than one solution for a given zone, it
equally generates a fictive {\sc unimarc} code 902 that it puts
around each of the possible solutions which are then presented to an
operator who has to make a choice.

\section{CONCLUSION}

The system presented here gave good results on tested library
references. The errors encountered were due to incomplete specification
(reference not falling into any of the categories we were provided
information on) or {\sc ocr} errors. The ambiguities encountred were
partly due to a combination of incoherence in the specification (which
allows different legal segmentations) as well as {\sc ocr}
substitution errors. The evaluation allows the observation of the
quality of each reference and each field in the reference and
allows the user to intervene or not for manual correction. 

\begin{thebibliography}{99}
\bibitem{bel92} Bela\"{\i}d A. and Tombre K. {\it
Analyze de documents~: de l'image \`a la s\'emantique}. Colloque
National sur l'Ecrit et le Document, Nancy, 6-7 juillet 1992, pp.
3--29. 
\bibitem{che91} Chenevoy Y. and Bela\"{\i}d A. {\em
Hypothesis Management for Structured Document Recognition}.
International Conference on Document Analysis and Recognition, vol. 1, 
St-Malo, september 30 - october 2, 1991.
\bibitem{and88} Andr\'e J., Furuta R. and Quint V. {\it
Structured Documents}. Cambridge University Press, 1988.
\bibitem{che92} Chenevoy Y. {\em Reconnaissance
structurelle de documents imprim\'es : \'etudes et r\'ealisations.}
Th\`ese de Doctorat de l'INPL, d\'ecembre 1992.
\bibitem{bro89} Brown B. {\it Standards for Structured
Documents}. The computer Journal, n. 6, vol. 32, 1989.
\bibitem{den90} Dengel A. {\em Document Image Analysis}.
In Proc. of IAPR Workshops on Syntactic and Structural Pattern
Recognition, pp 78--87, 1990.
\bibitem{kre88} Kreich J., Luhn A. and Maderlechner G.
{\em Knowledge-Based Interpretation of Scanned Business Letters.} IAPR 
Workshop on CV-Special Hardware and Industrial Application, Tokyo,
Oct. 12-14, 1988.
\bibitem{sri86} Srihari S. N. and Zack G. W. {\em Document Image
Analysis}. Proceedings of the Eight Int. Conf. on Pattern Recognition,
Paris, pp. 434--436, 1986.
\bibitem{sri87} Srihari S. N., Wang C. H., Palumbo P. W.
and Hall J. J. {\em Recognizing Address Blocks on Mail Pieces~:
Specialized Tools}. AI magazine,n.  pp. 25--40, 1987.
\bibitem{won82} Wong K. Y., Casey R. G. and Wahl F. M. {\em
Document Analysis System}. IBM Journal Research Development 26, pp.
647--655, 1982. 
\end{thebibliography}

\end{document}
