\documentclass[a4paper,12pt]{article}
\usepackage[latin1]{inputenc}

%%% avec french, prendre le nouveau codage T1
%%% pour permettre la coupure des mots avec accents
%%% et rendre MlTeX inutile, assurant du meme coup
%%% une plus grande portabilite a ce source LaTeX
\usepackage{t1enc,french}

%%% Les marges
\usepackage{vmargin}
\setpapersize{A4}
%%% Signification des parametres :
%%% \setmargins{leftmargin}{topmargin}{textwidth}{textheight}%
%%%    {headheight}{headsep}{footheight}{footskip}
%%% Ici les 4 derniers parametres sont par defaut a 0
%%% Mais vous pouvez très bien leur donner une valeur non nulle
\setmargins{30mm}{33.5mm}{155mm}{230mm}{0pt}{0mm}{0pt}{0mm}
\pagestyle{empty}

\usepackage{cifed98}

\title{\bf Reconnaissance de l'écriture manuscrite hors-ligne par une
approche markovienne planaire à base de champs aléatoires}

\author{\bf George Saon et Abdel Belaïd\\[5mm]
        {\normalsize\it Laboratoire Lorrain de Recherche en Informatique et ses
        Applications (LORIA)}\\[-1mm]
        {\normalsize\it Bât. Loria, Campus scientifique, BP 239, 54506 Vand{\oe}uvre-Lès-Nancy, FRANCE}\\[-1mm]
        {\normalsize\it e-mail~: saon@loria.fr}
}
\date{}
\pagestyle{empty}
\begin{document}
\maketitle
\thispagestyle{empty}
~~\\
{\bf Résumé}

Dans ce papier, nous décrivons un modèle stochastique markovien
combinant les modèles planaires et les champs aléatoires de Markov
causaux en vue de la reconnaissance de l'écriture manuscrite
hors-ligne (chiffres et mots dans un vocabulaire réduit). Dans ce
modèle, la structure d'appariement est de type chaînes de Markov
emboîtées et l'estimateur est l'état local d'un champ de Markov
causal. Afin de réaliser une reconnaissance Maximum A Posteriori ({\sc
map}), nous avons adapté un apprentissage par maximum de vraisemblance
({\sc mle}) par ré-estimation itérative des paramètres du modèle. Les
résultats obtenus sur une base de 14~000 chiffres manuscrits
hors-ligne sont de 96.36\%. Les résultats au niveau des mots sont de
84.42\% sur une base de 15~892 mots multi-scripteurs.

~~\\
{\bf Mots-clés~:} Reconnaissance de l'écriture hors-ligne, modèle de
Markov planaire, champ aléatoire causal, apprentissage par maximum de vraisemblance

~~\\
{\large\bf 1. Introduction}

L'utilisation des {\sc hmm}s en reconnaissance automatique de l'écrit
a permis d'obtenir des résultats intéressants pour certaines
applications. Mais la nature 2D de l'écriture (différence importante
avec la parole) permet de penser que des améliorations plus
importantes peuvent être apportées en étendant les {\sc hmm}s à deux
dimensions. Cependant, il a été démontré~\cite{levin92a} qu'une
extension directe de l'algorithme {\sc dtw}, appelée {\sc dpw}
(dynamic plane warping), conduit à un problème {\sc np}
complet. En appliquant certaines contraintes à
l'appariement, on peut ramener le problème à une complexité
polynômiale. Le modèle résultant, appelé {\sc phmm} (comme pseudo-{\sc
hmm})~\cite{agazzi93a}, tout en étant simple à mettre en
{\oe}uvre, connaît certaines limites dues à l'hypothèse d'indépendance statistique des lignes de
l'image. Cette hypothèse le fait échouer face à la variabilité du
manuscrit non-contraint comme cela a été constaté dans~\cite{gilloux94a}. 

Pour remédier à ce défaut, nous proposons une architecture de {\sc
phmm} consolidée par un estimateur local qui, en faisant une
observation dans un voisinage bidimensionnel, élimine {\it de facto}
cette hypothèse d'indépendance. En effet, l'observation dans une
position donnée se trouve répartie sur plusieurs lignes et colonnes de
l'image et conduit de ce fait à leur regroupement dans les super-états.
L'estimateur, donné par l'état local
d'un champ aléatoire à demi-plan non-symétrique, a été utilisé avec
succès dans d'autres systèmes à base de {\sc hmm}, sur des chiffres et
sur des mots dans un vocabulaire restreint~\cite{saon96c,saon97a}.

Nous décrirons d'abord l'architecture de ce modèle
(section~2), puis nous montrons comment s'effectue le
calcul de la vraisemblance d'une image et l'apprentissage {\sc mle} du
modèle (section~3), enfin nous présenterons les
résultats obtenus sur des bases de chiffres et de mots
(section~4). 

~~\\
{\large\bf 2. Description du modèle {\sc nshp-phmm}}

L'architecture du modèle est indiquée dans la
figure~\ref{nshp-phmm-arch}. Elle comprend un modèle vertical composé
de super-états et des modèles secondaires associés aux super-états. La
différence avec un {\sc phmm} classique réside dans l'observation
locale qui est conditionnée par un voisinage causal relatif au champ
aléatoire {\sc nshp}. 

\begin{figure}[htbp]
\centerline{\psfig{figure=../PHD/phmm2D.eps,width=8cm,height=7cm}}
\caption{\label{nshp-phmm-arch} Architecture de {\sc nshp-phmm}
d'ordre 3.} 
\end{figure}

Nous allons d'abord définir le champ {\sc nshp} utilisé puis nous
donnerons les éléments afférents au modèle complet.

~~\\
{\it 2.1 Définition du champ aléatoire {\sc nshp}}

Un champ aléatoire à demi-plan non-symétrique ({\sc nshp}) ${\bf X}$
est défini sur une lattice $L$ de dimensions $m\times n$ de la manière suivante~:

\[P(X_{ij}|{\bf X}_{\Sigma_{ij}})=P(X_{ij}|{\bf
X}_{\Theta_{ij}}),\forall (i,j)\in L\]
~~\\
où $\Sigma_{ij}=\{(k,l)\in L|l<j~\mbox{ou}~(l=j,~k<i)\}$ représente le
"passé" du pixel courant (le demi-plan gauche) et
$\Theta_{ij}\subset\Sigma_{ij}$ un sous-ensemble de ce demi-plan
appelé support. La figure~\ref{umrf} illustre ces deux types
d'ensembles. On appelle l'état local du champ {\sc nshp} la quantité
$P(X_{ij}|{\bf X}_{\Theta_{ij}})$.

\begin{figure}[htbp]
\centerline{\psfig{figure=UMRF.eps,width=7cm}}
\caption{\label{umrf} Ensemble de sites associés à un {\sc nshp}.}
\end{figure}

L'ordre du champ est donné par le nombre de pixels du voisinage et
l'on opte généralement pour des voisinages de mêmes dimension et forme
(avec des conditions frontalières adéquates).

L'intérêt de ce type de champ vient du fait qu'il est causalement
constructible dans le sens où les réalisations de ${\bf X}$ peuvent
être générées en partant du coin supérieur gauche et en effectuant un
balayage vertical (ou horizontal) de l'image.

De plus, il permet l'emploi de procédures de calcul récursives pour la
probabilité de masse $P({\bf X})$. En effet, elle se calcule par un
double produit le long des colonnes et des lignes de l'image des états
locaux~:

\begin{equation}
P({\bf X})=\displaystyle\prod_{(i,j)\in
L}P(X_{ij}|X_{\Theta_{ij}})=\prod_{j=1}^n\prod_{i=1}^m P(X_{ij}|X_{\Theta_{ij}})
\end{equation}

~~\\
{\it 2.2 Eléments du modèle {\sc nshp-phmm}}

Un {\sc nshp-phmm} d'ordre $P$ est défini par
$\eta=(\Theta,A,\pi,\Lambda)$, avec~:

\begin{description}
\item $V=\{0,1\}$ le vocabulaire. Nous notons une réalisation du pixel
$X_{ij}$ par $x_{ij}\in V$.
\item $\Theta=\{\Theta_{ij}\}_{(i,j)\in L}$,
$\Theta_{ij}=\{(i-i_k,j-j_k)|1\le k\le
P,j_k>0\mbox{ ou }(j_k=0,i_k>0)\}\cap L$, où $P$ représente le nombre
de pixels voisins. $\Theta$ est appelé l'ensemble des voisinages et
$P$ l'ordre du modèle (qui est identique à l'ordre du {\sc nshp}).
\item $S=\{s_1,s_2,\ldots,s_N\}$,
l'ensemble des $N$ super-états du modèle. 
On désigne un super-état pour la colonne $j$ par $q_j\in S$.
\item $A=\{a_{kl}\}_{1 \le k,l \le N}$, où
$a_{kl}=P(q_{j+1}=s_l|q_j=s_k)$, la matrice de
transition entre super-états.

\item $\pi=\{\pi_k\}_{1 \le k \le N}$, où $\pi_k=P(q_1=s_k)$ est la
probabilité initiale du super-état $s_k$.

\item $\Lambda=\{\lambda^{k}\}_{1\le k\le N}$, l'ensemble des modèles
secondaires associés aux
super-états. $\lambda^{k}=(\Theta,A^{k},B^{k},\pi^{k})$, 
où~: 
\begin{description}

\item $S^{k}=\{s^{k}_1,s^{k}_2,\ldots,s^{k}_{N^{k}}\}$,
l'ensemble des $N^{k}$ états du modèle, l'état localisé en $(i,j)$
étant noté par $q_{ij}\in S^k$.
\item $A^{k}=\{a^{k}_{mn}\}_{1 \le m,n \le N^{k}}$, où
$a^{k}_{mn}=P(q_{i+1j}=s^{k}_n|q_{ij}=s^{k}_m)$, la matrice de
transition entre états.
\item $B^{k}=\{b^{k}_m(x,{\bf x})\}_{1\le m\le N^k}$,
$x\in\{0,1\},{\bf x}\in\{0,1\}^P$, $b^{k}_m(x,{\bf
x})=P(X_{ij}=x|{\bf X}_{\Theta_{ij}}={\bf x},q_{ij}=s^{k}_m)$, les
probabilités conditionnelles d'observation de pixels.
\item $\pi^{k}=\{\pi^{k}_m\}_{1 \le m \le N^{k}}$, où
$\pi^{k}_m=P(q_{i1}=s^{k}_m)$.
\end{description}
\end{description}

Cette définition correspond à un modèle dont les super-états sont
disposés horizontalement et les {\sc nshp-hmm}s secondaires orientés
verticalement. La figure~\ref{nshp-phmm-arch} illustre une
architecture de {\sc nshp-phmm} disposée à l'envers. 

Notons le fait que les
probabilités conditionnelles de pixels dépendent de deux états
(super-état et état secondaire). Ceci a l'avantage que les états
locaux du champ {\sc nshp} seront "transportés" par ces états et positionnés dynamiquement sur les
parties informantes des images. La question qui mérite d'être posée
concerne le risque de cassure des propagations locales des influences
de pixels voisins. En effet, en passant d'un état secondaire à un
autre, l'état local du {\sc nshp} change et il peut y avoir une perte
de propagation qui risque de diminuer la sensibilité du champ à
la continuité des primitives dans l'image. La pratique montre qu'il
faut choisir un grand nombre d'états secondaires par super-état pour
permettre des transitions fines entre les états locaux du champ {\sc nshp}. 

~~\\
{\large\bf 3. Apprentissage et reconnaissance}

~~\\
{\it 3.1 Calcul de la vraisemblance}

Dans ce modèle, la vraisemblance d'une image s'obtient en faisant une
double somme sur les chemins de super-états et d'états de probabilités
conjointes qui seront factorisées suivant un schéma markovien bien
connu~:

\begin{equation}
P({\bf X}|\eta) = \displaystyle\sum_{{\bf Q}}
P({\bf X},{\bf Q}|\eta)=\displaystyle\sum_{{\bf Q}}
P({\bf X}|{\bf Q},\eta)P({\bf Q}|\eta)
\end{equation}
~~\\
ce qui donne, après décomposition et sous l'hypothèse {\sc nshp} de la
réalisation d'image~:

\begin{equation}
P({\bf X}|\eta)=\displaystyle\sum_{{\bf Q}}
\prod_{j=1}^n P(q_j|q_{j-1})\sum_{\{q_{ij}\}}\prod_{i=1}^m P(q_{ij}|q_{i-1j})
P(X_{ij}|{\bf X}_{\Theta_{ij}},q_{ij},\lambda^{q_j})
\end{equation}
~~\\
où tous les termes qui interviennent représentent des probabilités de
transition entre super-états et entre états secondaires et des probabilités
conditionnelles d'observation de pixels~:
\begin{eqnarray*}
P({\bf X}|\eta)&=&\displaystyle\sum_{q_1}\pi_{q_1}\sum_{\{q_{i1}\}}\pi_{q_{11}}^{q_1}b_{q_{11}}^{q_1}(X_{11}|{\bf
X}_{\Theta_{11}})a_{q_{11}q_{21}}^{q_1}\cdot\ldots\cdot
a_{q_{m-11}q_{m1}}^{q_1}b_{q_{m1}}^{q_1}(X_{m1}|{\bf X}_{\Theta_{m1}})\cdot\\
\nonumber &&\displaystyle\sum_{q_2}a_{q_1
q_2}\sum_{\{q_{i2}\}}\pi_{q_{12}}^{q_2}b_{q_{12}}^{q_2}(X_{12}|{\bf X}_{\Theta_{12}})a_{q_{12}q_{22}}^{q_2}\cdot\ldots\cdot
a_{q_{m-12}q_{m2}}^{q_2}b_{q_{m2}}^{q_2}(X_{m2}|{\bf X}_{\Theta_{m2}})\cdot\\
\nonumber &&\ldots\\
 &&\displaystyle\sum_{q_n}a_{q_{n-1}
q_n}\sum_{\{q_{in}\}}\pi_{q_{1n}}^{q_n}b_{q_{1n}}^{q_n}(X_{1n}|{\bf X}_{\Theta_{1n}})a_{q_{1n}q_{2n}}^{q_n}\cdot\ldots\cdot
a_{q_{m-1n}q_{mn}}^{q_n}b_{q_{mn}}^{q_n}(X_{mn}|{\bf X}_{\Theta_{mn}})
\end{eqnarray*}

Comme pour les {\sc phmm}s, ce calcul se prête tout
naturellement à une formulation récursive à l'aide de fonctions {\it
Forward-Backward} $\alpha-\beta$ à la fois pour le modèle principal et
pour les modèles secondaires dont le calcul ne sera pas détaillé ici.  

~~\\
{\it 3.2 Eléments d'apprentissage}

Le critère d'estimation retenu pendant l'apprentissage est le {\sc
mle}. Le choix de ce critère se justifie par le lien direct qui existe entre
la maximisation de la vraisemblance des échantillons et
l'aboutissement à un classifieur à taux d'erreur minimum sous réserve
que le modèle respecte la réalité des données. 

Nous avons opté pour une estimation itérative des paramètres de type
{\it Baum-Welch}. Etant données les fonctions $\alpha-\beta$ calculées
pour chaque image échantillon ${\bf X}^{r}$, les formules de
ré-estimation des probabilités de transition des super-états sont
analogues à celles employées pour un {\sc hmm} classique. Pour les
transitions entre états secondaires il y a une double contribution
dans les poids du comptage {\sc mle}. La formule de ré-estimation pour
les transitions secondaires est~:
\begin{eqnarray*}
\overline{a}_{uv}^k&=&\frac{\displaystyle\sum_{r=1}^R
\frac{1}{P_r} \sum_{j=1}^{n_r}
\frac{\gamma_j^r(k)}{P_k({\bf X}_j^r)}\sum_{i=1}^{m_r-1}\alpha_{ij}^{k(r)}(u)a_{uv}^k
b_v^k(X_{i+1j}^r,{\bf X}_{\Theta_{i+1j}}^r)\beta_{i+1j}^{k(r)}(v)}{\displaystyle\sum_{r=1}^R
\frac{1}{P_r} \sum_{j=1}^{n_r}
\frac{\gamma_j^r(u)}{P_k({\bf X}_j^r)}\sum_{i=1}^{m_r-1}\gamma_{ij}^{k(r)}(u)},~1\le u,v\le N^k
\end{eqnarray*}
~\\
où~:
\begin{itemize}
\item $m_r,n_r$ sont respectivement, les lignes et les colonnes de l'image ${\bf X}^{r}$,
\item $P_r\stackrel{\rm{not}}{=}P({\bf X}^r|\eta)$ représente la
probabilité d'émission de l'échantillon ${\bf X}^{r}$,
\item $P_k({\bf X}_j^r)$ est la probabilité d'émission de la colonne
${\bf X}_j^r$ de l'échantillon ${\bf X}^{r}$ par le modèle secondaire associé
au super-état $s_k$,
\item $\gamma_j^r(k)\stackrel{\rm{not}}{=}\alpha_j^r(k)\beta_j^r(k)$
représente la probabilité de se trouver dans le super-état $s_k$ pour la
colonne $j$,
\item
$\gamma_{ij}^{k(r)}(u)\stackrel{\rm{not}}{=}\alpha_{ij}^{k(r)}(u)\beta_{ij}^{k(r)}(u)$
est la probabilité de se trouver dans l'état secondaire $s^k_u$ du
modèle associé au super-état $s_k$ à la position $(i,j)$.
\end{itemize}

L'originalité du modèle réside dans la manière de ré-estimer les
probabilités conditionnelles d'observation de pixels. En effet, il
s'agit de trouver une estimation des distributions du champ {\sc nshp}
dans les états secondaires tout en répondant aux contraintes imposées
par le critère {\sc mle}. L'inférence des distributions {\sc nshp}
consiste principalement à effectuer des comptages de configurations de
pixels (pixel courant et son voisinage) à partir des images binaires
des échantillons. Les contraintes {\sc mle} reviennent à attribuer des
poids à la présence de ces configurations qui dépendent de trois
facteurs~:
\begin{itemize}
\item Globalement, de la probabilité d'émission de l'image par le
modèle (ou vraisemblance).
\item De la probabilité de se trouver dans le super-état pour un
indice de colonne donné ainsi que de la probabilité d'émission de
cette colonne par le modèle secondaire associé au super-état.
\item Enfin, de la probabilité de se trouver dans l'état secondaire
qui porte la distribution {\sc nshp} à estimer.
\end{itemize}

Ainsi, la formule de ré-estimation est comme suit~:

\begin{equation}
\overline{b}_u^k(x,{\bf x})=
\frac{\displaystyle\sum_{r=1}^R\frac{1}{P({\bf
X}^r|\eta)}\sum_{j=1}^{n_r}\frac{P(q_j=s_k,{\bf X}^r|\eta)}{P({\bf X}_j^r|\lambda^k)}\sum_{
\begin{array}{c}
~~~i=1~t.q.\\
X_{ij}^{r}=x~et~{\bf X}_{\Theta_{ij}}^{r}={\bf x}
\end{array}}^{m_r}P(q_{ij}=s_u^k,{\bf X}_j^r|\lambda^k)}
     {\displaystyle\sum_{r=1}^R\frac{1}{P({\bf
X}^r|\eta)}\sum_{j=1}^{n_r}\frac{P(q_j=s_k,{\bf X}^r|\eta)}{P({\bf X}_j^r|\lambda^k)}\sum_{
\begin{array}{c}
~~i=1~t.q.\\
{\bf X}_{\Theta_{ij}}^{r}={\bf x}
\end{array}}^{m_r}P(q_{ij}=s_u^k,{\bf X}_j^r|\lambda^k)}
\label{pixelprob2}
\end{equation}

~~\\
{\it 3.3 Reconnaissance}

La reconnaissance revient à calculer pour une image entrante les
probabilités d'émission par tous les modèles {\sc nshp-phmm} en
compétition puis à étiqueter cette image selon la règle de Bayes qui
fait intervenir la probabilité {\it a priori} des modèles.

~~\\
{\large\bf 4. Expérimentations et résultats}

~~\\
{\it 4.1 Reconnaissance de chiffres manuscrits}

Les expérimentations sur les chiffres manuscrits ont porté sur la base
{\sc unipen} comprenant 14000 échantillons multi-scripteurs écrits
en-ligne et transformés en imagettes binaires $16\times 16$. 1260
échantillons par chiffre ont été utilisés pour l'apprentissage des
modèles et 1400 pour le test (1/10 de la base). Chaque modèle comporte
8 super-états et 8 états par super-état. Le nombre de pixels du
voisinage (ou l'ordre) est 3 correspondant au voisinage indiqué dans
la figure~\ref{nshp-phmm-arch} et l'architecture est de type
gauche-droite stricte à la fois pour le modèle principal et pour les
modèles secondaires. L'initialisation des paramètres est uniforme pour
les transitions et se fait par comptage de configurations dans des
zones issues de décompositions régulières $8\times 8$ pour les
probabilités de pixels.

L'apprentissage de base consiste en 10 itérations {\sc mle}. Ensuite,
un apprentissage correctif~\cite{bahl88a} sur les échantillons
mal-reconnus a été effectué. La synthèse de prototypes de chiffres par
les {\sc nshp-phmm}s suite à cet apprentissage est illustrée dans la
figure~\ref{proto}. 

\begin{figure}[htbp]
\centerline{\psfig{figure=../PHD/proto-phmm.eps,width=16cm}}
\caption{\label{proto} Synthèse de prototypes de chiffres par des
{\sc nshp-phmm}s à nombre de super-états et d'états variable~: $2\times 2$
(a), $4\times 4$ (b), $8\times 4$ (c) et $8\times 8$ (d).} 
\end{figure}

Les résultats de reconnaissance du modèle de base (sans
apprentissage correctif) et avec apprentissage correctif sont résumés dans le
tableau~\ref{tab-digits3} et la matrice de confusion associée au
meilleur score global est indiquée dans~\ref{conf-digits3}. 

\begin{table}[htpb]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|c|}\hline
Apprentissage/Système & Top 1 & Top 2 & Top 3 & Top 4 & Top 5 & N1/Ntot\\\hline
{\sc mle} & 94.43\%&  98.64\%&  99.64\%&  99.86\%&  99.86\%& 1322/1400\\\hline
{\sc mle}+{\sc ct} 3 passes & 95.21\%&  98.79\%&  99.64\%&  99.86\%& 99.86\%&1333/1400\\\hline
{\sc mle}+{\sc ct} 6 passes & 96.36\%&  98.86\%&  99.71\%&  99.86\%&
99.86\%& 1349/1400\\\hline\hline
{\sc nshp-hmm} & 96.07\%&  98.93\%&  99.57\%&  99.79\%&  99.86\%& 1345/1400\\ \hline
\end{tabular}
\caption{\label{tab-digits3}Scores de reconnaissance de chiffres
pour des {\sc nshp-phmm}s d'ordre 3 sans et avec apprentissage
correctif ({\sc ct}) et pour des {\sc nshp-hmm}s d'ordre 3 avec {\sc ct}.}
\end{center}
\end{table}

\begin{table}[htpb]
\begin{center}
\begin{tabular}{r|rrrrrrrrrr|r}
    &  0 &  1 &  2 &  3 &  4 &  5 &  6 &  7 &  8 &  9 & \%\\ \hline 
  0 &138 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 98.57\\ 
  1 & 0 &139 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 99.29\\ 
  2 & 2 & 0 &135 & 0 & 1 & 0 & 0 & 0 & 2 & 0 & 96.43\\ 
  3 & 3 & 0 & 0 &132 & 0 & 3 & 0 & 1 & 1 & 0 & 94.29\\ 
  4 & 0 & 1 & 0 & 0 &133 & 0 & 1 & 2 & 0 & 3 & 95.00\\ 
  5 & 0 & 0 & 0 & {\bf 8} & 0 &132 & 0 & 0 & 0 & 0 & 94.29\\ 
  6 & 0 & 1 & 0 & 0 & 0 & 1 &138 & 0 & 0 & 0 & 98.57\\ 
  7 & 0 & 1 & 4 & 0 & 2 & 0 & 0 &133 & 0 & 0 & 95.00\\ 
  8 & 3 & 0 & 2 & 0 & 1 & 0 & 0 & 0 &133 & 1 & 95.00\\ 
  9 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 3 &136 & 97.14\\ 
\end{tabular}
\end{center}
\caption{\label{conf-digits3}Matrice de confusion pour le premier choix.}
\end{table}

Une comparaison de ce modèle avec un {\sc phmm} classique (sans
voisinage ou, ce qui est équivalent, d'ordre 0) d'architecture
identique et appris dans les mêmes conditions indique une
augmentation du score de 5\% en faveur du {\sc nshp-phmm} d'ordre 3.  

~~\\
{\it 4.2 Reconnaissance de mots manuscrits}

Pour les expérimentations sur les mots manuscrits, nous avons choisi
la base {\sc lix} (15892 images de mots multi-scripteurs) dont la taille du vocabulaire à reconnaître est de
26. Les seuls pré-traitements effectués sur les images de mots sont la
correction de la pente, la normalisation en hauteur à 20
lignes et la réflexion de l'image~\cite{saon97a}. Ces pré-traitements
sont résumés dans la figure~\ref{preprocessing}.

\begin{figure}[htbp]
\centerline{\psfig{figure=../PHD/preprocessing.eps,width=16cm}}
\caption{\label{preprocessing} Etapes de pré-traitement des mots.}
\end{figure}
   
L'apprentissage a été fait sur 1800 échantillons
par modèle exceptés les mots moins fréquents (9/10 de toute la
base). Le test a porté sur le 1/10 restant des échantillons pour
chaque modèle et plus précisément sur 1598 images. L'architecture des
modèles est comme suit~:
nombre de super-états égal à la longueur moyenne divisée par 2, nombre
d'états égal à 10, transitions autorisées uniquement vers
l'état/super-état courant ou suivant initialement
équiprobables. L'ordre des modèles est 3 et l'initialisation des
probabilités conditionnelles de pixel est faite par comptage de
configurations dans les zones issues des décompositions des
images. L'apprentissage de base consiste en 3 passes de ré-estimation
{\sc mle} et l'apprentissage correctif comporte également 3 passes de
ré-estimation. Le score de reconnaissance est de 84.42\% top 1 et de
95.37\% top 5 comme indiqué par le tableau~\ref{comparison}. 

\begin{table}[htpb]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|}\hline
Système & Top 1& Top 2 & Top 3& Top 4 & Top 5\\ \hline
{\sc nshp-phmm}  &  84.42\%&  91.77\%&  93.27\%&  94.76\%&  95.37\%\\
\hline
{\sc nshp-hmm} & 91.10\%&  95.77\%&  97.35\%&  98.10\%&  98.60\%\\ \hline 
\end{tabular}
\caption{\label{comparison} Scores de reconnaissance de mots sur la
base {\sc lix} avec apprentissage correctif.}
\end{center}
\end{table}

~~\\
{\large\bf 5. Conclusion}

Nous avons décrit une méthode de reconnaissance de l'écriture
manuscrite fondée sur l'utilisation d'un modèle {\sc phmm} dont
l'estimateur local dans les états secondaires est un champ aléatoire
causal. De part la nature de ce modèle, l'observation se fait
directement sur les pixels de l'image sans faire appel à une recherche
de primitives. L'apprentissage est réalisé dans le sens d'un critère
{\sc mle} et consiste au niveau des distributions {\sc nshp} à compter
des configurations de pixels dans les images d'échantillons. Alors que
les résultats obtenus pour la reconnaissance de chiffres montrent une
bonne robustesse de ces modèles, leur application sur des mots
manuscrits indique des faiblesses par rapport à des modèles où la
composante champ aléatoire est prédominante et la structure
d'appariement plus simple. En effet, des modèles de type {\sc
nshp-hmm}~\cite{saon97a} donnent pour la même application des
résultats nettement supérieurs tout en étant légèrement moins
performants que les {\sc nshp-phmm}s sur la reconnaissance de
chiffres. En conclusion, il semble que la définition des paramètres
architecturaux nécessite plus de soin dans le cas des mots
manuscrits. Il y a un risque de sur-paramétrisation par rapport aux
{\sc nshp-hmm}s qui peut expliquer la chute des performances pour
cette application. En outre, toutes les possibilités d'appariement
vertical n'ont pas été explorées car les images entrantes ont la même hauteur.

~~\\
\def\refname{{\large\bf 6. Références}}
\begin{thebibliography}{1}

\bibitem{agazzi93a}
O.~E. Agazzi and S.~Kuo.
\newblock {Hidden Markov Model Based Optical Character Recognition in the
  Presence of Deterministic Transformation}.
\newblock {\em Pattern Recognition}, 26(12):1813--1826, February 1993.

\bibitem{bahl88a}
L.~R. Bahl, P.~F. Brown, P.~V. de~Souza, and R.~L. Mercer.
\newblock {A New Algorithm for the Estimation of Hidden Markov Model
  Parameters}.
\newblock In {\em IEEE-ICASSP}, volume~1, pages 493--496, 1988.

\bibitem{gilloux94a}
M.~Gilloux.
\newblock {Reconnaissance de chiffres manuscrits par mod\`ele de Markov
  pseudo-2D}.
\newblock In {\em Actes du $3^{\grave{e}me}$ Colloque National sur l'\'{E}crit
  et le Document}, pages 11--17, Rouen, France, 1994.

\bibitem{levin92a}
E.~Levin and R.~Pieraccini.
\newblock {Dynamic Planar Warping for Optical Character Recognition}.
\newblock In {\em IEEE-ICASSP}, volume III, pages 149--152. IEEE, 1992.

\bibitem{saon96c}
G.~Saon and A.~Bela\"{\i}d.
\newblock {Binary Pattern Recognition Using Markov Random Fields and HMMs}.
\newblock In {\em International Conference on Acoustics Speech and Signal
  Processing (ICASSP'97)}, volume~5, pages 3725--3728, Munich, Germany, April
  1997.

\bibitem{saon97a}
G.~Saon and A.~Bela\"{\i}d.
\newblock {Off-line Handwritten Word Recognition Using A Mixed HMM-MRF
  Approach}.
\newblock In {\em Fourth International Conference on Document Analysis and
  Recognition (ICDAR'97)}, volume~1, pages 118--122, Ulm, Germany, Aug. 1997.

\end{thebibliography}

\end{document}
