%template for producing IEEE-format articles using LaTeX.
%written by Matthew Ward, CS Department, Worcester Polytechnic Institute.
%use at your own risk.  Complaints to /dev/null.
%make two column with no page numbering, default is 10 point
\documentstyle[twocolumn]{article}
\pagestyle{empty}

%set dimensions of columns, gap between columns, and space between paragraphs
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}
\input{psfig}

%I copied stuff out of art10.sty and modified them to conform to IEEE format

\makeatletter
%as Latex considers descenders in its calculation of interline spacing,
%to get 12 point spacing for normalsize text, must set it to 10 points
\def\@normalsize{\@setsize\normalsize{12pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip 6pt plus3pt
minus3pt\let\@listi\@listI} 

%need an 11 pt font size for subsection and abstract headings
\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}

%make section titles bold and 12 point, 2 blank lines before, 1 after
\def\section{\@startsection {section}{1}{\z@}{24pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\large\bf}}

%make subsection titles bold and 11 point, 1 blank line before, 1 after
\def\subsection{\@startsection {subsection}{2}{\z@}{12pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\subsize\bf}}
\makeatother

\begin{document}

%don't want date printed
\date{}

%make title bold and 14 pt font (Latex default is non-bold, 16 pt)
\title{\Large\bf Stochastic Trajectory Modeling for Recognition\\
       of Unconstrained Handwritten Words}

\author{G. Saon, A. Bela\"{\i}d and Y. Gong\\
\begin{tabular}{c r l}
{\sc Crin-Cnrs /Inria-Lorraine} & Phone: & (33) 83 59 20 82\\
Bât. LORIA - Campus Scientifique - B.P. 239  & Fax: & (33) 83 41 30 79\\
F-54506 Vand{\oe}uvre-Lès-Nancy (France) & E-mail: & \{saon,abelaid,gong\}@loria.fr  
\end{tabular}}

\date{}

\maketitle
\newcommand{\symset}{I\!\!L}
\newcommand{\rset}{I\!\!R}
\def\argmax{\mathop{\rm argmax}}
\bibliographystyle{plain}
\maketitle

%I don't know why I have to reset thispagesyle, but otherwise get page numbers
\thispagestyle{empty}

\subsection*{\centering Abstract}
%IEEE allows italicized abstract
{\em
In this paper we describe an off-line handwritten word recognition
({\sc hwr}) system applied to the identification of literal french
check amounts. It consists of three successive levels denoted as
character, word and phrase level, each of them being related to the
previous ones via conditional probability distributions. Training is
done on character samples extracted from amount images which are
modeled as trajectories in some feature space. At word level, guided by a
dictionary, an internal character segmentation algorithm is used in
order to maximize a global word probability measure. A stochastic
grammar for a priori grammar generation probability of a phrase is
proposed at the last level. Results obtained on a 1779 amounts data
base provided by the {\sc SRTP}\footnote{Service de Recherche
Technique de la Poste (France)} are encouraging, showing our system
open to further improvements.   
}

%{\bf Keywords:} handwriting recognition, conditional probabilities, \\
% Gaussian distribution, clustering, stochastic grammars

\section{Introduction}
Because of the large variety of handwriting styles, the recognition is
very difficult. Different categories of styles (handprinted, pure
cursive) may involve different approaches in the recognition task, the
variety of handwriting styles being a criterion for recognition
systems known as scriptor dependence. Besides scriptor dependence, in
cursive handwriting characters may present various ligatures
according to preceeding and succeeding characters in a
word. We propose to study ligatures as being integral parts of a character. 

When developing our system we were inspired by analogous phenomena
present in continuous speech recognition. For example, characters in a
cursive handwritten word may suffer alterations due to left or right
character context just as phonemes in a continuously spoken
utterance. Starting from this consideration, {\sc hwr} techniques can
be borrowed from speech domain which is already the case with hidden
Markov models. Our word recognition scheme
falls in the framework of a method based on the stochastic trajectory
modeling ({\sc stm}) by Y. Gong {\em and al.}~\cite{gong94a}. The main
idea behind is the following:  

In some parametric space (i.e. cepstral) speech is represented by a
moving point as articulatory configuration changes. Thus, the acoustic
images of phonemes may be viewed as trajectory clusters presenting accumulation
points. Analogy with speech appears if in {\sc hwr} we consider 
continuous features like various word profiles along the horizontal
writing axis. Characters in a handwritten word will constitute
fragments of a trajectory in the feature space
considered. Figure~\ref{figure2} illustrates the trajectory principle
on {\em i}-shapes in contexts like "o-i-s", "v-i-n" and "e-i-z". 

The most common way for {\sc hwr} systems dedicated to specific
applications is to use context for limiting possible intra- and
inter-word relationships. For example, in literal check amount
identification~\cite{gilloux93a}, word context is given by
reduced vocabulary size and amount grammar. Thus, syntax can be used
to decrease ambiguity during recognition. 

The paper is organized as follows. We describe in more detail
some elements concerning trajectory representation
(section~\ref{method}), the character level (section~\ref{characters}) and
the word level (section~\ref{words}) which are the key points of our 
framework. A stochastic grammar for literal french check
amounts gives the phrase level in section~\ref{phrases}. Experiments
performed and results obtained will be discussed in
section~\ref{experiments}.   

\begin{figure}[htbp]
\centerline{\psfig{figure=trajectory.eps,height=5cm}}
\caption{\label{figure2} Illustration of the trajectory principle for
{\em i}.}  
\end{figure}

\section{Trajectory representation}
\label{method}

In the following formalism, we assume that a pattern can be described
as an observation sequence of $\rset ^P$-parameterized features along one
axis (for example, the evolution of upper and lower word image
subprofiles along 
the writing axis). Furthermore, this sequence can be regarded as a
concatenation of subsequences corresponding to elementary patterns, as
example handwritten words as a series of graphems or characters. 

Let ${\bf X} = x_0~ x_1~ \ldots ~x_{N-1}$ be an {\it observation sequence} of a
signal where $x_i \in \rset^{P}$, the parameterized feature space,
represents an {\it observation state} at instant $i$. The sequence
${\bf X}$ is said to be {\it centred} at instant $i$ (denoted $X_i$) if $X_i =
x_{i-\frac{N}{2}}~x_{i-\frac{N}{2}+1}~ \ldots~ x_i~
\ldots~x_{i+\frac{N}{2}-1}$. We call $N$ the {\it duration} of such a
sequence.   

Given a duration $d$ and a centred sequence $X_i$ at instant $i$, we
define a $Q$-state {\it observation matrix}, $M_{X_i}(d) \in \rset^{Q \times
P}$. The idea of such a matrix relies on a linear sampling of a
subsequence in order to map the $d$ observations to a constant number of
states $Q$. In this manner, a local observation is parameterized by such a
matrix and its corresponding duration. 
\begin{equation}
M_{X_i}(d) = col(x_{i+\frac{d}{Q}j}^{t})_{-\frac{Q}{2} \le j < \frac{Q}{2}}
\end{equation} 
Figure~\ref{mapping} shows the mapping of a character trajectory to a
4-state observation matrix.
\begin{figure}[htbp]
\centerline{\psfig{figure=mapping.eps,width=8cm}}
\caption{\label{figure3} Representation of trajectories.} 
\label{mapping}
\end{figure}

\section{Character level}
\label{characters}

Since features chosen vary continuously, one naturally assumes that 
parameter vectors corresponding to character samples belonging to a
cluster follow a multi-variate Gaussian pdf. Moreover, character
duration within a cluster is supposed to be normally distributed. Let
us consider character models as the parameters needed to estimate
the above mentioned Gaussian distributions.
A character model ${\cal M}_k$ is defined by the
quadruplet $(\overline{M}_k,\Sigma_k,\overline{d}_k,\sigma_k)$  
where $\overline{M}_k\in\rset^{Q\times P}$ represents mean observation
matrix, $\Sigma_k\in\rset^{Q\times Q}$ state
covariance matrix, $\overline{d}_k$ mean duration and $\sigma_k$
standard deviation for duration. An element $\sigma_{ij}$ of
$\Sigma_k$ indicates the covariance between the state $i$ and $j$
averaged over all feature parameters which explains the fact that
$\Sigma_k\in\rset^{Q\times Q}$. Details concerning estimation of these
quantities can be found in~\cite{saon94a}. Note
that models are character related and that a character may have several models.

We are interested in computing the conditional probability of a
character (symbol) $s$ knowing a centred observation sequence $X_i$ at
instant $i$ and a duration $d$.
\begin{equation}
P(s/X_i,d)  = \frac{P(s,X_i,d)}{P(X_i,d)} \label{lab7}
\end{equation}
~~\\
with $P(s,X_i,d)$ being the joint probability of symbol $s$, sequence
$X_i$ and duration $d$ (note that $P(X_i,d)$ is constant during
recognition). $P(s,X_i,d)$ is expressed by introducing $K$ character
models ${\cal M}_k$, $1\le k\le K$:
\begin{equation}
P(s,X_i,d)  =  \displaystyle \sum_{k=1}^{K}P(X_i,{\cal M}_k,d,s)
\end{equation} 
~~\\
For computational efficiency we approximate the sum by maximum. We
then obtain:
\begin{equation}
\begin{array}{l}
\log P(s,X_i,d)=\log\displaystyle \max_{1\le k \le K}P(X_i,{\cal
M}_k,d,s)=\\
=\displaystyle \max_{1\le k \le K}\log P(X_i,{\cal M}_k,d,s)
\end{array}
\label{lab8}
\end{equation} 
~~\\
Following the chain decomposition rule of conditional probabilities~:
\begin{equation}
\begin{array}{l}
P(X_i,{\cal M}_k,d,s)=P(X_i/{\cal M}_k,d,s)P(d/{\cal M}_k,s)P(s)\cdot\\
\cdot P({\cal M}_k/s)=P(X_i/{\cal M}_k,d)P(d/{\cal M}_k)P({\cal M}_k/s)P(s)  
\end{array}
\label{lab9}
\end{equation}
~~\\
since quantities $P(X_i/{\cal M}_k,d,s)$ and $P(d/{\cal
M}_k,s)$ do not depend on $s$ as they already depend on ${\cal M}_k$.

The parameters of~(\ref{lab9}) can be estimated using the EM
algorithm. Here we utilize a modified version of the LBG vector quantization
technique~\cite{linde80a}. A character sample $(X_{i},d)$ is
defined by a centred observation sequence and its corresponding
duration A point $(X_{i},d)$ is affected to the 
cluster $k$ if:
\begin{equation}
\begin{array}{l}
D((X_{i},d),{\cal M}_k)=-\log(P(X_{i}/{\cal
M}_k,d)P(d/{\cal M}_k))=\\
=\displaystyle\min_{1\le l\le K}D((X_{i},d),{\cal M}_l)
\end{array}
\label{distance}
\end{equation}

\section{Word level}
\label{words}

Since a handwritten word is composed of individual
characters, the recognition is based on evaluation of the probability of
these characters. 

Let $\symset = \{s_0,s_1, \ldots s_l\}$ be the set of characters and a
word $\omega \in \symset^{+}$ of length $L(\omega)$,
$\omega=s_0~s_1~\ldots~ s_{L(\omega)-1}$. The probability
of $\omega$ given observation sequence \\
${\bf X}=x_0\ldots x_{N-1}$, $x_i\in\rset^P$ is defined as: 
\begin{equation}
P(\omega/{\bf X}) = \displaystyle
\max_{\{t_{i}\}}\left\{\prod_{i=0}^{L(\omega)-1}P(s_i/X_{\frac{t_i+t_{i+1}}{2}},t_{i+1}-t_i)\right\}^{1\over
{L(\omega)}}
\label{lab20}
\end{equation}
~~\\
where $0=t_0<\ldots<t_i<t_{i+1}<\ldots<t_{L(\omega)}=N-1$
represents a set of character 
segmentation hypotheses. $t_{i+1}-t_i$ would be
therefore the hypothesized duration of character $s_i$. Formula (\ref{lab20})
reflects the conditional probability of a word as being the
geometrical average of symbol probabilities. We assume implicitly that
local observations are made independently, thus $P(\omega/{\bf X})$
can be factorized. In practice, one performs the natural logarithm of
the above given probability. The recognized word is the one which
satisfies: 
\begin{equation}
\omega^{*}=\displaystyle \argmax_{\omega \in \symset^{+}}
P(\omega/{\bf X}) = \displaystyle \argmax_{\omega \in \symset^{+}} \log
          P(\omega/{\bf X})
\label{lab6}
\end{equation}

\section{Phrase level}
\label{phrases}
Literal amounts obey precise syntactical and semantical rules. For
example, in French each amount must end in "francs" or "centimes" or
the corresponding abbreviations. Furthermore, one may observe that
some amounts are more frequent, thus more probable, than others. Based
on these observations, we added a phrase level to our recognition
system. We use stochastic grammars for combining syntax correctness and
grammar generation probability of a phrase.

Let $G=(N,V_{T},P,Q,S)$ be a stochastic grammar with $Q=\{p_{i}\}_{i}$
representing the set of probabilities of applying production rule
$r_{i}\in P$ during a reduction. We limit us to context-free
unambiguous grammars which means that each terminal phrase has a
unique derivation. For $\alpha\in V_{T}^{*}$, let this derivation be $S\Rightarrow_{r_{1}}\alpha_{1}\ldots\Rightarrow_{r_{i}}\alpha_{i}\ldots
\Rightarrow_{r_{n}}\alpha$, where $\Rightarrow_{r_{i}}$ denotes the
application of rule $r_{i}$ in the current derivation step. Grammar
generation  probability of $\alpha$ becomes: 
\begin{equation}
P(\alpha)=\displaystyle\prod_{i=1}^{n}P(r_{i}/r_{1},r_{2},\ldots,r_{i-1})
\label{proba}
\end{equation}
To have reliable estimations of these probabilities, large quantity of
phrase data would be required. For trainability reasons the grammar is
considered unrestricted, i.e.:  
\begin{equation}
P(r_{i}/r_{1},r_{2},\ldots,r_{i-1})=P(r_{i})=p_{i}
\label{unrestricted}
\end{equation} 
For french check literal amounts we built a stochastic grammar which
accepts 96.11\% of the phrases constituting labels in our data base. Each
phrase is parsed and production application frequencies are updated. The set of
terminals $V_{T}$ contains words used for literal numbers plus
"francs", "et", "centimes".  
It is important to point out that during recognition word segmentation
limits within the amount image are supposed to be known. Therefore,
the precise length $l$ of the phrase to be recognized is given
beforehand. 

We denote by ${\cal X}={\bf X}^{(1)}\ldots{\bf X}^{(i)}\ldots{\bf
X}^{(l)}$ the concatenation of all observation sequences corresponding
to the words of an input literal amount image and by $\alpha^{*}\in
L(G)$, $|\alpha^{*}|=l$ the most probable syntactically correct phrase
of length $l$. The output of our recognition system verifies: 
\begin{equation}
\begin{array}{l l}
\alpha^{*}&=\displaystyle \argmax_{\alpha\in
L(G),|\alpha|=l}P(\alpha/{\cal X})P(\alpha/G)=\\ 
&=\displaystyle \argmax_{\alpha\in
L(G),|\alpha|=l}P(\alpha)\prod_{i=1}^{l}P(\omega_{i}^{\alpha}/{\bf
X}^{(i)}) 
\end{array}
\end{equation}
where by $P(\alpha)$ we understand a priori grammar generation
probability of the phrase $\alpha$ in the sense of
equation~(\ref{proba}) under the assumption~(\ref{unrestricted}).
  
\section{Experiments and results}
\label{experiments}

The set of experiments was performed on the {\sc SRTP} data
base containing 1779 handwritten amount images (3796 words) each
amount being written by a different scriptor. Images are provided with
label file and word segmentation file. As mentioned before, the word
segmentation file is used during recognition. Labels are supposed to
be the exact transcription of the amount image and word recognition
rates are computed by direct comparison between label and recognition
output file. Each amount image was scanned at 300 dpi from real postal
checks. The literal amount zone was previously located and
isolated. Horizontal and diagonal bars have been removed and images were binary
thresholded. Several examples of images are presented at the end of
the paper. Amount word length varies between 2 and 11 with an average
length of 4. 

The purpose of the experiments reported was to validate a
new formalism in {\sc hwr} thus very simple features are used.
We considered normalized distances $\in [0,1]$ along
vertical axes between upper and lower word subprofiles and character
surrounding frames. By giving cut
points between characters, surrounding frames for each character are
determined. Distances are adjusted with respect to these rectangles in
order to code more accurately the character shapes.

Training was performed on 799 amount images. Each word was manually
segmented in characters and coded following the earlier mentioned
features. Character samples, represented by centred observation
sequences and durations, are clustered (section~\ref{characters}).

Recognition was done on 980 images distinct from the training
images. Following equation~(\ref{lab20}) cut points between characters
are proposed and coding is done as mentioned above. Average word
recognition results are resumed in table~\ref{results2} (Top i means
word recognition rate among the first i candidates). We show further
some difficult cases of amounts which were well recognized among the
first 3 choices.

\begin{table}
\begin{tabular}{|c|c|c|c|c|c|}\hline
Top & 1 & 2 & 3 & 4 & 5\\ \hline
Avg (\%) & 82.83 & 86.87 & 89.39 & 90.91 & 91.41\\ \hline
\end{tabular}
\caption{Average word recognition scores}
\label{results2}
\end{table}

\section{Conclusion}
\label{conclusion}

We developed a theoretical framework and a system prototype for {\sc
hwr} by stochastic modeling of character variations. The framework is
in relation with similar researches in speech
recognition. One major topic of our future research interest is writer
style conditioned recognition. We intend to group human writings in
classes by extracting several proximity measures between different
words composing a same amount which vary significantly for a same word
issued from different writing styles. We are convinced that
this conditioning may improve recognition accuracy. 

\bibliography{/users/ecriture/commun/biblio}

\centerline{\psfig{figure=Haa10003.eps,width=8cm}}
\centerline{\psfig{figure=Haa10003.lab.eps,width=8cm}}

\centerline{\psfig{figure=Haa10063.eps,width=8cm}}
\centerline{\psfig{figure=Haa10063.lab.eps,width=8cm}}

\centerline{\psfig{figure=Haa10090.eps,width=8cm}}
\centerline{\psfig{figure=Haa10090.lab.eps,width=8cm}}

\centerline{\psfig{figure=Haa10092.eps,width=8cm}}
\centerline{\psfig{figure=Haa10092.lab.eps,width=8cm}}

\end{document}



