% -*- Document-Type: LaTeX; Master-File: cms.tex -*- 
% les cesures
	\documentstyle[12pt]{article}
% format standard, centre'
	\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{Off-line Handwriting Recognition\\
       by Statistical Correlation}

\author{G. Saon, A. Belaïd and Y. Gong\\[5mm]
	{\sc Crin-Cnrs /Inria-Lorraine}\\
	Bât Loria, Campus scientifique, {\sc B.P.} 239\\
	54506 Vand{\oe}uvre-Lès-Nancy Cedex\\
	FRANCE\\
	Email~: {saonandy,abelaid,gong}@loria.fr\\
}
\date{}


\begin{document}

	\maketitle
\newcommand{\symset}{I\!\!L}
\newcommand{\rset}{I\!\!R}
\vspace{5mm}
\bibliographystyle{plain}

~~\\
{\bf Contact}: A. Belaïd, Tel: (33) 83 59 20 82, Fax: (33) 83 41 30 79\\ 
{\bf Original contribution}: Recognition without pre-segmentation,
incorporating context, use of bidimensional stochastic models.\\
{\bf Importance}: able to be adapted on any kind of parameterized
signal (speech, on-line handwriting).

\section{Introduction}
In this paper, we present a new approach to unconstrained, off-line
handwriting recognition ({\sc hwr}). It is based on the global plausibility
estimation of a word knowing the local probability of each individual
character. Having a set of character models issued from a training
step and an input word pattern, we try to maximize for each word of
the lexicon the sum of plausibilities of its component characters.
This maximisation is made in terms of observation quality and extent
of a symbol within the pattern. The proposed method operates in a
top-down manner by giving segmentation hypotheses which induce local
symbol extents for a given word of the lexicon against which the
pattern is matched. The word which obtains the highest average
plausibility per character is labeled as the recognized one. This
method was applied with success on continuous speech recognition
by~\cite{gong94a}.

\section{Method Description}

In the following formalism, we assume that a pattern can be described
as an observation sequence of $\rset ^P$-parameterized features along one
axis (i.e. contours on horizontal axis for handwriting). 

Let ${\bf X} = x_0 x_1 \ldots x_N$ be an observation sequence of a signal
where $x_i \in \rset^{P}$. We call duration the length of the sequence
in terms of the number of its vectors. Given a duration $d$ and a
centred sequence $X_i$ at instant $i$, we define a $Q$-state
observation matrix, $M_{X_i}(d) \in \rset^{Q \times P}$, $M_{X_i}(d) =
col(x_{i+\frac{d}{Q}j}^{t})_{-\frac{Q}{2} \le j < \frac{Q}{2}}$. The
idea of such a matrix relies on a linear sampling of a subsequence in
order to reduce the observation to a constant number of states $Q$. In 
this manner, a local observation is well parameterized by such a
matrix and its corresponding duration.

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
conditional probability of $\omega$ given observation ${\bf X}$ is:

\begin{equation}
P(\omega/{\bf X}) = \displaystyle \max_{0=t_0 <t_1< \ldots <
t_{L(\omega)-1} < t_{L(\omega)} = N} (\prod_{i=0}^{L(\omega)-1} 
P(s_i/X_{\frac{t_i+t_{i+1}}{2}},t_{i+1}-t_i+1))^{\frac{1}{L(\omega)}}
\label{lab20}
\end{equation}
~~\\
where $\{t_i\}_{0\le i \le L(\omega)}$ represents a set of letter
segmentation hypotheses. $t_{i+1}-t_i+1$ would be
therefore the local duration of character $s_i$. Formula (\ref{lab20})
reflects the conditional probability of a word as being the
geometrical average of symbol probabilities. The most plausible word
is the one which satisfies: $\omega^{*} =  \displaystyle
arg\max_{\omega \in \symset^{*}}P(\omega/{\bf
X})$, thus:

\begin{equation}
\omega^{*} = \displaystyle
arg\max_{\omega \in \symset^{*}} \frac{1}{L(\omega)} \displaystyle
\max_{t_i} \sum_{i=0}^{L(\omega)-1} \log P(s_i/X_{\frac{t_i+t_{i+1}}{2}},t_{i+1}-t_i+1)
\label{omegaetoile}
\end{equation}

The probability in~(\ref{omegaetoile}) can be expressed as: $P(s/X_i,d)  =
\frac{P(s,X_i,d)}{P(X_i,d)}$ with $P(X_i,d)$ being constant during
recognition therefore discardable. In the context of multi-models the
marginal probability density function (pdf) $P(s,X_i,d)$  can be
obtained by summing up on the set $K$ of all character models, ${\cal
M}_k$, as follows:    

\begin{equation}
P(s,X_ i,d)  =  \displaystyle \sum_{k \in K}P(X_i,{\cal M}_k,d,s)
\label{paxid}
\end{equation} 
~~\\
where $P(X_i,{\cal M}_k,d,s)$ is the joint pdf of vector sequence
$X_i$, character model ${\cal M}_k$, duration $d$ and symbol $s$. 

\begin{equation}
P(X_i,{\cal M}_k,d,s) = P(X_i/{\cal M}_k,d)P(d/{\cal M}_k)P({\cal M}_k/s)P(s) \
\end{equation}


\begin{itemize}

\item {\it Calculus of} $P(X_i/{\cal M}_k,d)$. Since features are
continuous, one naturally assumes that their 
corresponding quantified vectors belonging to a cluster follow a
multi-variate Gaussian pdf with mean observation
matrix $\overline{M}_k$ and state covariance matrix $\Sigma_k$ related
to model ${\cal M}_k$.

\begin{equation}
P(X_i/{\cal M}_k,d) =
\frac{1}{\sqrt{(2\pi)^{Q}|\Sigma_k|}}\exp^{-\frac{1}{2}tr((M_{X_i}(d)-\overline{M}_k)^{t}\Sigma_{k}^{-1}(M_{X_i}(d)-\overline{M}_k))}
\end{equation} 

\item {\it Calculus of} $P(d/{\cal M}_k)$.
Experience showed that duration is normally distributed within model
${\cal M}_k$ with mean value $\overline{d}_k$ and standard deviation
$\sigma_{k}$. 

\begin{equation}
P(d/{\cal M}_k) =
\frac{1}{\sqrt{2\pi \sigma_{k}^{2}}}\exp^{-\frac{(d-\overline{d}_k)^{2}}{
2 \sigma_{k}^{2}}}
\label{duration}
\end{equation}

\item {\em Calculus of} $P({\cal M}_k/s)$ and $P(s)$. They represent
the {\it a priori} probability of respectively the 
model ${\cal M}_k$ knowing $s$ and of $s$.
\end{itemize}

\subsection{Training Process}

It consists of defining the set of models ${\cal M}_k$, $k \in K$, from
a training corpus $S$. Each character sample $i \in S$ is given by an
observation matrix $M_i$ and duration $d_i$. Formally, a model ${\cal
M}_k$, $k \in K$ is defined as: ${\cal M}_k =
(\overline{M}_k,\Sigma_k,\overline{d}_k,\sigma_k)$.

The state covariance matrix is equal to: 
\begin{equation}
\Sigma_k = (a_{ij}^{k})_{1 \le i,j \le Q}~~~~~~~
a_{ij}^k = \frac{1}{|N_{k}^{s}|} \displaystyle \sum_{l \in N_{k}^{s}}
(M_{l}^i -\overline{M}_{k}^{i})^{t}(M_{l}^j -\overline{M}_{k}^{j})
\label{sigma}
\end{equation}

~~\\where $N_{k}^{s}$ is the set of samples of $s$ related to model
${\cal M}_k$. Linear sampling of each character subsequence leads us to
an observation matrix. These matrixes are grouped into classes using a
variation of the {\sc lbg} clustering algorithm~\cite{lin80}.
We used variable distances at each iteration:
$d(X,Y)=\sqrt{tr((X-Y)^t\Sigma^{-1}(X-Y))}$, with $X,Y\in
\rset^{Q\times P}$ and covariance matrix $\Sigma$ positively defined. 

\subsection{Recognition}

We need to maximize the sum of local duration probabilities. Applying
$log$ to equation (\ref{duration}) results, modulo a constant
term, in~:
 
\begin{equation}
f(t_0,t_1, \ldots, t_{L(\omega)}) = \displaystyle
\sum_{i=0}^{L(\omega)-1}-\frac{(t_{i+1}-t_i-\overline{d}_i)^{2}}{2
\sigma_{i}^{2}}
\end{equation}
~~\\
with the constraints $t_{0}=0$, $t_{L(\omega)}=N$, $t_{i}\le t_{i+1}$.
Following {\it Lagrange multiplicators theory} we deduce: $t_0=0,~~t_{i+1}  =  t_i+\overline{d}_i -\sigma_{i}^{2} \frac{(\displaystyle
\sum_{j=0}^{L(\omega) -1} \overline{d}_j - N)}{\displaystyle
\sum_{j=0}^{L(\omega) -1} \sigma_{j}^{2}},~~0\le i <L(\omega)$
~~\\
$\overline{d}_i$, $\sigma_{i}$  representing, respectively, global mean
duration and standard deviation for symbol $s_i$. In practice, we may
deplace the $t_i$'s around these values within a centred interval of
variation assuring always $|t_{i+1}-t_{i}-\overline{d_i}| < 2
\sigma_i$ in order to maximize also the observation quality. This
method has the advantage of a global view on the initial segmentation
hypotheses $\{t_i\}_i$ and afterwards it reinforces also the maximum
calculus in (\ref{omegaetoile}).


\section{Experiments and Results}
\label{results}

The corpus contains about 500 words written by 30 scriptors without
constraints but with a limited vocabulary (28, corresponding to
the French bank check wording words). Characters in each word were
manually segmented (about 2000 characters from the corpus, varying
from 15 to 400 samples per character). For character recognition, the
average rate is 90.63\% for the third choice. For word recognition,
the average rate is between 84.74\% (1$^{st}$ choice) and 95.90\%
(3$^{rd}$ choice).
  
\section{Conclusion}
We developed a theoretical framework and a system prototype for {\sc
hwr} by stochastic modeling with a close relation with similar
researches in continuous speech recognition. Problems encountered are
analogous but {\sc hwr} has particularities due to its bidimensional
aspect. Despite modest recognition scores, the method remains
promising and is open to improvements concerning feature analysis and
context modeling. Further developments should cope with more
discriminant continuous features taking into account geometrical and
topological properties inherent to writing. Convolution masks for
finding basic components such as strokes, cavities, peaks and curves
are actually in study. Future extensions dealing with grammar
constraints for search space limitation (context at syntactic level)
should be foreseen. 
 
\bibliography{/loria/ecriture/biblio/biblio}

\end{document}



