2.1 – Prétraitement et normalisation des images

9Les premières étapes d’un système de reconnaissance d’écriture manuscrite consistent à préparer les données : normaliser les images en entrée, et en extraire les caractéristiques qui permettront de calculer les modèles. Nous limitons l’étape de la normalisation à la correction de l’inclinaison des caractères au niveau du mot. Les images ne sont pas normalisées en taille car les caractéristiques extraites par la suite sont indépendantes de la hauteur de l’image, et la modélisation HMM est robuste à un nombre variable de vecteurs de caractéristiques correspondant à un même modèle.

10Afin de calculer des caractéristiques propres aux ascendants et descendants, les lignes de base des mots sont calculées. Nous nous sommes inspirés du travail de (Vinciarelli et al., 2001) pour notre correction d’inclinaison et notre calcul de lignes de base. Nous avons adapté leur algorithme pour images binaires à des images en niveau de gris. Les lignes calculées sont fixes, comme illustré sur la figure 2 (les lignes de base haute et basse sont les deux lignes horizontales). Le calcul de l’angle d’inclinaison se fait par maximisation de l’entropie du profil de la projection horizontale des pixels de l’image.

Figure 2

Illustration de l’extraction de caractéristiques géométriques par fenêtre glissante

Illustration de l’extraction de caractéristiques géométriques par fenêtre glissante

2.2 – Extraction de caractéristiques

11L’extraction de caractéristiques s’inspire des travaux de (El-Hajj et al., 2005 ; El-Hajj et al., 2009) et utilise des fenêtres glissantes parcourant l’image de gauche à droite, comme illustré sur la figure 2. Les fenêtres sont divisées verticalement en un nombre fixe de cellules n_cells et sont de largeur w pixels. Dans chaque fenêtre sont extraites w + 20 caractéristiques : 2 sont reliées au nombre de transitions caractère/arrière-plan, 12 aux configurations de pixels (calcul de concavités), 2 à la position du centre de gravité, dont une dérivative (différence des positions verticales), et les autres sont reliées aux densités de pixels. Certaines de ces caractéristiques dépendent de la position des lignes de base. Les images en niveau de gris sont binarisées avec la méthode de (Otsu, 1979) afin de calculer les caractéristiques de transition caractère/arrière-plan ainsi que celles de configuration de pixels.

12Nous avons optimisé la largeur w des fenêtres glissantes, le décalage ? entre deux fenêtres consécutives et le nombre de cellules n_cells dans chaque fenêtre (comme illustré sur la figure 2) sur une base de validation indépendante. Le choix des paramètres est discuté dans la section 4.

2.3 – Caractéristiques dynamiques

13Afin d’ajouter de l’information sur l’environnement d’un caractère, nous avons choisi dans un premier temps d’agir au niveau des caractéristiques. Avec une dérivation, la dynamique des fenêtres glissantes entourant la fenêtre courante est prise en compte. Si p est l’abscisse en pixels de la fenêtre courante, alors la dérivation prendra en compte les fenêtres situées aux positions p ? ? ? i et p + ? ? i, pour 1 ? i ? K. ? est le décalage entre deux fenêtres consécutives et K le nombre de fenêtres participant au calcul des caractéristiques dérivées. La dérivation est calculée par une régression, donc K représente aussi la profondeur de la régression. En reconnaissance de la parole, les régressions du premier et second ordre sont connues respectivement comme les coefficients delta et delta-delta des caractéristiques cepstrales.

14Soit o_k le vecteur de caractéristiques de la fenêtre courante (à la position p), et o_k+i (resp. o_k?i) celui de la fenêtre décalée de i ? ? (resp. ?i ? ?) pixels, située à l’abscisse p + i ? ? (resp. p ? i ? ?). La régression du premier ordre du vecteur de caractéristiques o_k s’écrit :

15

162 ? K vecteurs o_j sont donc pris en compte pour le calcul des caractéristiques dynamiques.

17Le vecteur de caractéristiques final, en entrée du système, est alors la concaténation du vecteur initial o_k et de sa régression au premier ordre ?o_k. Nous montrons dans la section 4 que cet ajout permet d’améliorer les performances de notre système de reconnaissance d’écriture manuscrite.

2.4 – Modélisation de caractères indépendamment de leur contexte

18Le premier système présenté dans cet article est le système générique qui ne prend pas en compte les contextes des caractères. Il utilise une stratégie analytique et procède sans segmentation. Un mot est modélisé par la concaténation des caractères le composant, comme illustré sur la figure 3. Tous les modèles de caractères suivent la topologie de Bakis avec S états émetteurs (transitions gauche-droite et saut d’état autorisé). La densité de probabilité des observations est un mélange de N_G distributions Gaussiennes. Le mélange est obtenu par incrémentations successives du nombre de Gaussiennes suivies à chaque étape de ré-apprentissage avec l’algorithme Baum-Welch. Le passage de m à m +1 Gaussiennes se fait en clonant la Gaussienne de poids le plus fort dans une nouvelle Gaussienne. Chacune reçoit comme nouveau poids la moitié du poids de la Gaussienne initiale, et est décalée par l’addition (soustraction) d’une distribution normale de faible variance (?_split par défaut vaut 0.2). Le nombre optimal N_G de gaussiennes dans les mélanges est obtenu par des tests sur une base de validation.

Figure 3

Modélisation d’un mot par la concaténation des caractères le composant

Modélisation d’un mot par la concaténation des caractères le composant

19Etant donné que les modèles de notre système de base sont indépendants des contextes, chaque caractère a un unique modèle lui correspondant. Nous appelons ces modèles des ’monographes’. Notre système étant testé sur du français (cf. figure 1), nous prenons en compte les accents, car l’accentuation d’une lettre peut changer la signification d’un mot (’du’/’dû’ par exemple). Ainsi nous définissons un total de 78 monographes différents, comprenant des chiffres, des caractères accentués ou non, en majuscule ou minuscule, et des symboles (apostrophe, pourcentage, trait d’union). Dans notre système, a est donc différent de A et é est différent de e.

20Le décodage se fait avec l’algorithme Viterbi. Il n’y a aucune connaissance a priori de la vraisemblance des mots du vocabulaire, donc les mots du test ont tous la même probabilité. Nous utilisons le Hidden Markov Model Toolkit (HTK) (Young et al., 2006) pour l’apprentissage et le décodage.

3.1 – Introduction

21Nous avons vu dans la section 2.3 comment introduire une notion de contexte au niveau des caractéristiques avec une régression. Nous souhaitons maintenant exploiter l’observation présentée sur la figure 4 : un caractère a une forme variable suivant sa position dans un mot et les lettres qui l’entourent. Le système présenté ici prend en compte cette idée en modélisant un caractère en fonction de son contexte gauche et droit : un trigraphe.

Figure 4

Illustration des différentes formes que peut prendre un caractère selon son contexte : "i" et "n" ont une forme différente pour chaque apparition dans les mots ci-dessus

Illustration des différentes formes que peut prendre un caractère selon son contexte : "i" et "n" ont une forme différente pour chaque apparition dans les mots ci-dessus

22Une telle modélisation est utilisée en parole pour simuler l’effet de co-articulation, et les modèles sont nommés triphones (Lee, 1990). Mais, comme nous l’avons mentionné dans l’introduction (section 1), très peu de travaux de reconnaissance de l’écriture abordent les modèles en contexte et explorent leurs avantages. Il est vrai que l’inconvénient majeur de la modélisation des caractères en fonction de leur contexte est que le nombre de paramètres des HMM de tous les trigraphes possibles à modéliser est très élevé, et que pour un vocabulaire de taille moyenne (4 000 mots), le manque de données pour l’apprentissage devient un problème récurrent. Il existe pourtant des méthodes pour réduire ce nombre, basées sur le partage des paramètres entre modèles, ou entre états par exemple. Nous avons choisi d’utiliser une méthode de clustering sur les positions d’états afin de pallier ce problème et d’inclure efficacement des trigraphes dans notre système.

23Le prétraitement des images en entrée et l’extraction des caractéristiques (géométriques et dynamiques) sont identiques à ce qui est fait dans le système générique et décrit dans les sections 2.1, 2.2 et 2.3. L’apport majeur de notre système, outre la modélisation de caractères en fonction de leur contexte, est l’usage d’un processus de partage de paramètres utilisant un clustering d’états basé sur des arbres de décision binaires (voir section 3.3). Ces derniers sont construits à partir de questions originales que nous avons définies après observation de la morphologie des caractères présents dans le lexique (voir section 3.3.2).

3.2 – Modélisation de caractères en contexte

24Le principe de modélisation de caractères en fonction de leur contexte est assez naturel, car il nous paraît logique que la forme d’un caractère varie en fonction des lettres qui l’entourent. Ceci est illustré pour les caractères n et i dans la figure 4. De plus, étant donné que les deux mots de cette figure on été écrits par le même scripteur, on peut imaginer la variabilité des contextes qui peut exister dans une base de données multiscripteur de grande taille, telle que la base Rimes.

25Cette modélisation consiste à définir un mot non pas comme une succession de caractères, mais comme une succession de caractères avec leur contexte. Les monographes de la section 2.4 sont remplacés par des trigraphes, où le caractère central est influencé par le caractère à sa gauche (contexte gauche) et celui à sa droite (contexte droit). D’un point de vue syntaxique, nous définissons un contexte gauche avec un signe moins ’-’, et un contexte droit avec un signe plus ’+’. Ainsi, le monographe i de la figure 4.a, entouré d’un s et d’un e, devient, en contexte, le trigraphe s ? i + e. De même sur la figure 4.b, la lettre d entourée par un espace et un i se définit comme le trigraphe ?? d + i.

26Une fois que l’ensemble des trigraphes à apprendre est déterminé, l’étape suivante est le processus d’apprentissage. Celui-ci pourrait être effectué directement à partir des trigraphes précédemment définis, mais certains d’entre eux ont trop peu d’exemples dans la base d’apprentissage. De plus, le nombre de paramètres à calculer croit lorsque le nombre de Gaussiennes dans les mélanges des densités de probabilités augmente. Ainsi, pour les 4 500 différents trigraphes présents dans la base d’apprentissage et une topologie de modèles avec S états émetteurs et N_G Gaussiennes dans chaque mélange, si S et N_G sont de l’ordre de 10, le nombre de paramètres à calculer monte à presque un demi-million, ce qui est tout à fait prohibitif étant donné la quantité de données disponibles. C’est pourquoi nous considérons à présent le partage de paramètres par un clustering d’états, afin de pallier le problème du manque de données d’apprentissage ainsi que celui du trop grand nombre de modèles à calculer.

3.3 – Apprentissage des trigraphes et partage des paramètres HMM

3.3.1 – Présentation générale

27Dans cette section, nous présentons en détail notre système paramétrant les HMM de caractères en fonction de leur contexte, schématisé sur la figure 5. Nous détaillons les étapes de mise en place du partage des paramètres entre trigraphes précédant le processus final d’apprentissage.

Figure 5

Présentation générale du système à base de HMM de caractères en contexte

Présentation générale du système à base de HMM de caractères en contexte

28Le premier apprentissage est celui des monographes du lexique d’apprentissage. Les monographes sont initialisés avec une seule distribution Gaussienne associée à chaque état, puis plusieurs ré-estimations sont effectuées avec l’algorithme Baum-Welch. Les trigraphes sont alors eux-mêmes initialisés en copiant les modèles appris des monographes : pour un monographe donné, tous les trigraphes de la base d’apprentissage centrés sur ce caractère sont listés, et le HMM du monographe est copié pour correspondre au modèle initial de chacun des trigraphes. Ensuite, une première ré-estimation (avec 2 itérations) Baum-Welch de tous les trigraphes est effectuée. Durant cette étape, nous avons choisi de partager les matrices de transition entre trigraphes avec le même caractère central. Nous avons en effet observé qu’une fois la topologie d’un modèle choisi, des modifications sur les coefficients de la matrice de transition ont une très faible influence sur la phase de reconnaissance. Considérant cette information, nous avons alors imposé que les trigraphes ayant la même racine (tous les ? ? a + ?, puis tous les ? ? b + ?, etc.) partagent leur matrice de transition. Ainsi, le nombre de matrices à calculer se réduit au nombre initial de monographes.

29La seconde étape de notre système est le clustering d’états appliqué aux trigraphes. Le principe du clustering état par état est que, pour les trigraphes associés à une lettre centrale donnée, tous les états correspondant à une même position dans le modèle HMM sont soumis à un clustering. Cette étape est illustrée plus en détails sur la figure 6. Soit c le caractère central considéré. N_c différents trigraphes existent dans la base d’apprentissage, centrés sur c. Donc pour chaque position d’état i des trigraphes ? ? c + ?, 1 ? i ? S, N_c différents états devraient être calculés. L’utilisation de clusters d’états permet la réduction du nombre de modèles à calculer. Ainsi pour la position d’état numéro i, n_i ? N_c clusters sont sélectionnés pour représenter tous les états de la position i, définissant n_i différents modèles d’états s_i,j, 1 ? j ? n_i. Un état en position i prend alors sa valeur dans l’un des s_i,j modèles. Nous rappelons que pour des raisons de complexité, un modèle d’état est représenté par une seule distribution Gaussienne durant la phase d’initialisation des trigraphes et des clusters d’états.

Figure 6

Illustration du clustering d’états pour les trigraphes centrés sur la lettre b

Illustration du clustering d’états pour les trigraphes centrés sur la lettre b

30(Fink et al., 2007 ; Natarajan et al., 2006) ont montré l’efficacité de ce type de groupement. Nous différons de ce qu’ils proposent dans l’utilisation d’arbres de décision pour calculer nos clusters. Nous expliquons en détail notre méthode de calcul en section 3.3.2. Cette étape nous a permis de réduire le nombre de paramètres d’un facteur 10.

31Finalement, étant donné que le clustering d’états entraîne une réduction importante du nombre d’états différents, certains trigraphes se retrouvent partager exactement les mêmes états, et donc être identiques. Nous groupons donc dans une dernière étape les trigraphes identiques, ce qui permet de réduire encore le nombre de modèles, le divisant par trois.

32Une fois le calcul et la mise en place des clusters d’états terminés, le système est prêt à finir d’apprendre les modèles des caractères en contexte. En utilisant l’algorithme Baum-Welch pour les étapes de ré-estimation des paramètres des HMM, nous augmentons de manière incrémentale le nombre de Gaussiennes dans chaque mélange, en utilisant la même procédure que celle décrite dans la section 2.4 pour les monographes. Ainsi, chaque trigraphe atteint une topologie identique à celle des monographes du système générique, c’est-à-dire S états émetteurs et N_G distributions Gaussiennes par état. Cela nous permet de comparer directement les deux approches, contextuelle et non contextuelle.

3.3.2 – Arbres de décision pour clustering d’états de trigraphes

33Le clustering par arbres de décision est une alternative au clustering guidé par les données. Il se base sur une mesure de distance entre modèles utilisant la maximisation de la vraisemblance, et permet une découpe de clusters contrôlée. Ce type de clustering a d’abord été proposé pour la parole (Young et al., 1994) où il donne des résultats au niveau de l’état de l’art avec un système moins complexe que d’autres systèmes avec modèles en contexte. Le regroupement et la séparation de clusters d’états sont conduits par un arbre binaire dont chaque nœud correspond à une question rhétorique sur les contextes des modèles. Dans notre cas, les questions sont définies sur les caractéristiques morphologiques des contextes gauche et droit des caractères. Un arbre est construit pour chaque position d’état de tous les trigraphes correspondant à une même lettre centrale. Nous définissons ainsi 78 lettres centrales ? S états par caractère arbres différents.

34Pour construire un arbre, tous les états correspondant à une même position pour une lettre centrale donnée sont d’abord regroupés au nœud racine. Ensuite, la question binaire qui sépare le groupe en deux sous-groupes de vraisemblance maximale est choisie, et la séparation est effectuée, créant deux nouveaux nœuds. Il en va ainsi de la scission de chaque nœud jusqu’à ce que l’augmentation de la vraisemblance descende sous un seuil, ou bien jusqu’à ce que plus aucune question ne soit disponible qui puisse créer deux sous-groupes avec un taux d’occupation d’états suffisant.

35On peut formuler mathématiquement le clustering par arbres de décision. Soit P l’ensemble d’états présents dans le nœud courant. P est associé au sous-ensemble F d’observations (vecteurs de caractéristiques) {o_f}_f?F. Par définition, tous les états présents dans P sont les membres d’un même cluster, ils partagent donc les mêmes moyenne ?(P) et variance ?(P). Par suite, la vraisemblance de P générant l’ensemble des {o_f}_f?F s’écrit :

36

37Pour plus de clarté, nous simplifierons désormais L({o_f}_f?F ; P) en L(P). Dans l’équation [2], ?_s(o_f) est la probabilité a posteriori que le vecteur de caractéristiques o_f soit généré par l’état s ? P. En supposant que la densité de probabilité représentée par (?(P), ?(P)) est une Gaussienne et de matrice de covariance diagonale, on peut l’estimer à partir des échantillons {o_f}_f?F, et L(P) peut être reformulé par (Young et al., 1994) :

38

39n est la dimension des vecteurs o_f et ?(P) est le taux d’occupation d’états cumulé du nœud courant :

40

41La séparation de P en deux sous-groupes P_q+ et P_q? est alors faite par la question q^? qui maximise ?L_q, défini par :

42

43La scission se fait à condition que ?(P_q+) et ?(P_q?) soient au-dessus du taux minimal d’occupation N_P, et que ?L_q soit plus grand que le seuil minimal de croissance de variance ?L_R. Le choix des paramètres N_P et ?L_R est effectué sur une base de validation (voir section 4.2.3).

44La minimisation de l’équation [5] peut être reformulée (Zen et al., 2003) :

45

46Les questions q définissant les arbres de décision pour la reconnaissance de la parole on été réalisées par des experts (Odell, 1992). A notre connaissance, personne n’utilise de tels arbres pour l’écrit. Nous avons donc proposé des questions en rassemblant des caractères semblables dans différents contextes. L’ensemble des questions que nous avons créées contient des questions générales, pour permettre des clusters de grande taille, mais aussi des questions précises, au cas où des clusters plus petits doivent être créés, et des questions intermédiaires. Les questions sont uniquement fonctions des contextes (gauche et droit). Par exemple :

• (question générale) le contexte droit est-il une lettre majuscule ? minuscule ? Contient-il un ascendant ?
• (question intermédiaire) le contexte gauche contient-il une boucle ("o", "b", "d", etc.) ? Une barre verticale ("t", "p", etc.) ?
• (question précise) est-ce que le lien avec la lettre suivante (précédente) se situe sur la ligne de base basse ("a", "c", etc.) ? Sur la ligne de base haute ("v", "w", etc.) ?

Un exemple d’arbre de décision est donné en figure 7. Il représente l’arbre calculé pour la position d’état numéro deux des trigraphes centrés sur la lettre b.

3.3.3 – Reconnaissance de mots avec modèles de caractères en contexte

47Au-delà de l’apport original des arbres binaires pour le calcul des clusters, l’utilisation d’arbres de décision apporte une fonctionnalité supplémentaire très utile lors du décodage : elle permet de sélectionner les clusters qui serviront à modéliser les états des trigraphes non vus lors de l’apprentissage. En effet, nous utilisons pour nos tests des lexiques prédéterminés. Par exemple, pour la base Rimes 2009, deux lexiques ont été donnés pour le test, chacun contenant des mots non existants dans le lexique d’apprentissage. Ainsi, plusieurs nouveaux mots, et donc plusieurs nouveaux trigraphes apparaissent, qui n’ont pas été appris. Le clustering par arbres permet de les modéliser car il peut adapter les modèles appris à n’importe quel vocabulaire (basé sur les mêmes monographes de départ). Si nous avions calculé nos clusters par une distance entre les données (Kullback-Liebler) par exemple (data-driven clustering), cela n’aurait pas été possible. En effet, ne disposant pas de données étiquetées pour apprendre les nouveaux trigraphes, un calcul de distance aux clusters les plus proches n’est pas envisageable.

48La modélisation d’un trigraphe inconnu se fait de la manière suivante : chaque état du trigraphe est positionné à la racine de l’arbre correspondant au même numéro d’état et à la même lettre centrale. Ensuite, chaque état parcourt son arbre, répondant aux questions sur les contextes du nouveau trigraphe, jusqu’à atteindre un nœud où est positionné un cluster. Le modèle d’état représentant le cluster est alors le modèle assigné au numéro d’état considéré. Cette procédure est illustrée sur la figure 8 pour l’assignation d’un modèle à l’état numéro 2 du trigraphe inconnu m ? b + e. L’arbre de décision pour cette position d’état a été calculé lors de la phase d’apprentissage et est représenté sur la figure 7. Plaçons l’état numéro 2 de m ? b + e, non attribué, au nœud racine de l’arbre. La première question posée est : Le contexte gauche est-il en minuscule ? Etant donné que m est une minuscule, la réponse est oui, donc l’état descend vers le nœud correspondant à la réponse oui, où une nouvelle question est posée : Le lien avec le contexte gauche est-il sur la ligne de base basse ? Après avoir répondu à cette question, le processus est recommencé jusqu’à ce que l’état atteigne un cluster. Dans notre cas, les réponses successives mènent au cluster s2_1, qui est donc le modèle choisi pour l’état numéro 2 de notre trigraphe inconnu.

Figure 7

Exemple d’arbre de décision pour le clustering d’états : l’ordre des questions et les clusters sont associés à un état donné (ici l’état numéro 2) de tous les trigraphes ? ? b + ?

Exemple d’arbre de décision pour le clustering d’états : l’ordre des questions et les clusters sont associés à un état donné (ici l’état numéro 2) de tous les trigraphes ? ? b + ?

49La capacité des arbres de traiter des trigraphes non vus a été très utile pour nos expériences sur la base Rimes. Les lexiques d’apprentissage et de test étant différents, plusieurs centaines de nouveaux trigraphes devaient être modélisés.

Figure 8

Sélection de cluster pour l’état 2 du trigraphe de test m ? b + e non appris (absent du lexique d’apprentissage mais présent dans celui du test)

Sélection de cluster pour l’état 2 du trigraphe de test m ? b + e non appris (absent du lexique d’apprentissage mais présent dans celui du test)

4.1 – La base de données Rimes

50La base de données Rimes a été rendue disponible en 2006 (Augustin et al., 2006). Des exemples sont donnés sur la figure 1. Elle rassemble plus de 12 500 documents manuscrits écrits par environ 1 300 volontaires. Elle a été créée pour répondre au besoin récurrent de bases complètes d’images propres et de taille suffisante. Peu de contraintes ont été imposées aux scripteurs (papier blanc et thème principal) : les documents sont donc très variables, ce qui rend la base réaliste. A partir des documents collectés, il est possible d’évaluer des systèmes de reconnaissance de logo, d’analyse de structure de texte, et de reconnaissance de mot, caractère, ligne, ou paragraphe. Notre travail se concentre pour l’instant sur la reconnaissance de mots isolés.

51Des campagnes d’évaluation ont eu lieu depuis 2007, ce qui nous permet de nous comparer à l’état de l’art. Nous utilisons dans cet article les données et la procédure de la campagne Rimes-ICDAR 2009 (Grosicki et al., 2009). L’ensemble d’apprentissage est composé de 44 196 images de mots isolés pour un lexique de 4 500 mots différents. Un ensemble de validation de 7 542 mots issus d’un lexique de taille 1 636 est donné. L’ensemble de test est quant à lui composé de 7 464 images de mots isolés pour un lexique de 1 612 mots. Plus de 300 mots du lexique de validation n’existent pas dans le lexique d’apprentissage, et plus de 300 autres sont ajoutés par le lexique de test par rapport à la concaténation des deux lexiques précédents. Des nouveaux mots signifient souvent des nouveaux trigraphes, ce qui nous ramène aux raisons mentionnées dans la section 3.3.3 sur le choix de l’utilisation d’arbres de décision pour la construction des clusters.

4.2 – Mise en place du protocole expérimental

4.2.1 – Extraction des caractéristiques

52Nous avons fait varier la largeur w des fenêtres glissantes, l’espace ? entre deux fenêtres consécutives, et le nombre de cellules n_cells utilisées pour l’extraction des caractéristiques afin de trouver les meilleurs paramètres pour nos expériences. Pour cela, nous avons utilisé un système générique où les caractères sont non seulement indépendants du contexte mais aussi modélisés sans prendre en compte leur casse ou leur accentuation. Ainsi, "a", "A" et "à" ont le même modèle. Ceci nous permet de faire des apprentissages et décodages rapides. Les modèles sont appris sur la base d’apprentissage de Rimes et évalués sur la base de validation et son lexique. Pour chaque ensemble de caractéristiques, nous avons fait varier le nombre d’états par HMM de caractère entre 5 et 15 afin d’évaluer les paramètres optimaux d’apprentissage. Le tableau 1 donne les taux de reconnaissance (calculés sans prendre en compte la casse ou les accents) des 4 meilleurs ensembles de caractéristiques testés, chacun avec son nombre optimal d’états par caractère, pour un nombre de gaussiennes variant de 10 à 40.

Tableau 1

Comparaison de différents paramètres pour l’extraction des caractéristiques, sur un système générique appris sur la base d’apprentissage de Rimes et testé sur la base de validation

nb. de Gaussiennes par état 10 15 20 30 40 paramètres d’extraction w=8 ?=4 ncells =20 nbétats =8 61, 61 65, 86 68, 42 69, 53 71, 82 w=10 ?=5 ncells =20 nbétats =8 59,20 63,67 65,38 66,0 67,89 w=10 ?=6 ncells =20 nbétats =6 53,92 58,51 61,08 61,58 64,76 w=14 ?=7 ncells =20 nbétats =6 50,53 57,11 59,15 60,08 62,70

Comparaison de différents paramètres pour l’extraction des caractéristiques, sur un système générique appris sur la base d’apprentissage de Rimes et testé sur la base de validation

53D’après les résultats obtenus, nous choisissons les paramètres w = 8 pixels, ? = w/2 = 4 pixels et n_cells = 20 cellules, donnant 28 caractéristiques différentes. Nous nommons par la suite cet ensemble de caractéristiques w8d4c20, pour lequel le nombre optimal d’états par caractère est S = 8. Enfin, nous choisissons pour la suite d’établir le nombre N_G de distributions Gaussiennes par état à N_G = 20, car cela correspond au meilleur compromis entre performance du reconnaisseur et temps de calcul : un décodage avec 40 gaussiennes nécessite 50 % de temps en plus qu’un décodage avec 20 gaussiennes (600 ms au lieu de 400 ms par mot) et un décodage avec 30 gaussiennes dans chaque mélange apporte peu d’améliorations par rapport à 20 gaussiennes.

4.2.3 – Paramètres des arbres de décision

56Nous avons présenté en section 3.3.2 la méthode de scission d’un nœud d’un arbre par la question q^? maximisant ?L(q). Pour le calcul des clusters, deux paramètres restent à établir, ?L_R et N_P :

• ?L_R est la valeur minimale que peut prendre ?L(q^?). Si, quelle que soit la question q, ?L(q) est inférieur à ?L_R, alors le nœud n’est pas scindé et devient un cluster.
• N_P est le taux d’occupation d’états minimal du nœud contenant l’ensemble d’états P partageant leurs paramètres. Ce seuil permet d’avoir des clusters de taille suffisante et donc des états correctement estimés. Mathématiquement, pour un état j ? P, N_j est la somme sur toutes les observations de la probabilité d’être dans l’état j, et N_P est la somme de tous les N_j pour j ? P.

Nous avons fixé ces paramètres sur la base de validation, et répété la procédure initialisation - duplication - clustering par position d’état - apprentissage et augmentation du nombre de distributions Gaussiennes (jusqu’à N_G = 10 pour plus de rapidité dans les calculs) comme décrit dans la section 3.3 pour plusieurs couples (?L_R, N_P). On vérifie que plus ?L_R ou N_P est élevé, moins le nombre total de clusters est grand, c’est-à-dire moins il y a d’états différents, et donc de calculs. La figure 9 montre l’influence du nombre d’états (fixé par le couple (?L_R, N_P)) sur le taux de reconnaissance du système avec modèles en contexte sur la base de validation. Chaque point représente un couple (?L_R, N_P) donné. On constate que plus le nombre de clusters d’états est faible, meilleur est le système.

57Comme indiqué sur la figure 9, nous avons choisi la paire (?L_R = 450, N_P = 450) pour notre système final. Ces paramètres représentent le meilleur équilibre entre le taux de reconnaissance (76, 13 % pour 10 Gaussiennes sur la base de validation), le temps de calcul des clusters, et celui pour le décodage. Graphiquement, il est le point le plus en haut à gauche de la figure 9. Le système choisi définit un total de 1 924 états différents. Au vu du faible nombre d’états différents par rapport aux trigraphes présents dans la base d’apprentissage, certains trigraphes se trouvent partager exactement les mêmes états. Le nombre de trigraphes différents diminue donc aussi. Pour notre système, ce nombre passe de 4 784 à 2 130 sur la base d’apprentissage.

Figure 9

Influence du nombre final d’états (clusters) différents sur le taux de reconnaissance (base de validation ; 8 états/trigraphe ; 10 distributions Gaussiennes/état)

Influence du nombre final d’états (clusters) différents sur le taux de reconnaissance (base de validation ; 8 états/trigraphe ; 10 distributions Gaussiennes/état)

4.3 – Résultats

58Une fois le protocole expérimental posé, nous pouvons évaluer les deux systèmes présentés dans cet article sur la base de test de Rimes-ICDAR 2009 (Grosicki et al., 2009). Deux expériences sont menées pour des dictionnaires de test de différente taille. Une première expérience utilise un dictionnaire contenant 5 334 mots différents. Une autre utilise le dictionnaire restreint contenant uniquement les mots du test, soit 1 612 mots. Les modèles sont appris en distinguant la casse et les accents. Le taux de reconnaissance est évalué sans prendre en compte la casse, mais en respectant les accents, conformément au protocole de la compétition Rimes-ICDAR 2009.

59Pour rappel, le premier système (CI) modélise les caractères indépendamment de leur contexte. Décrit dans la section 2.4, il présente une topologie de 8 états par caractère et 20 distributions Gaussiennes par état. Le second système (CD) est celui décrit dans la section 3, modélisant les caractères en fonction de leur contexte : les trigraphes. Nous avons compté 297 nouveaux trigraphes présents dans la base de test et non dans les bases d’apprentissage ou de validation. Les arbres de décision nous ont donc permis de leur allouer des modèles. Les paramètres du système CD sont fixés sur la base d’apprentissage (calcul et répartition des clusters). Pour l’apprentissage final des Gaussiennes (après l’étape de partage des paramètres et avant l’incrémentation du nombre de Gaussiennes dans chaque mélange), nous avons testé deux méthodes, l’une utilisant simplement les données de l’ensemble d’apprentissage, l’autre utilisant ces données plus celles de l’ensemble de validation.

60Les résultats sont donnés sur le tableau 2. Pour chaque système, nous montrons le taux de reconnaissance obtenu sur chacun des lexiques proposés pour le test avec un intervalle de confiance binomial.

Tableau 2

Comparaison des systèmes présentés, modélisant les caractères en fonction de leur contexte (CD) ou non (CI). Résultats sur la base de test de Rimes 2009 contenant 7 464 images

Ensemble d’apprentissage Lexique de test (1612 mots) Lexique complet (5334 mots) Système CI train (44197 images) 73, 04 % ±0, 01 66, 0 % ±0, 01 CI train+valid (51739 images) 75, 52 % ±0, 009 68, 57 % ±0, 01 CD train (44197 images) 79, 34 % ±0, 009 74, 33 % ±0, 01 CD train+valid (51739 images) 80, 35 % ±0, 009 75, 53 % ±0, 009

Comparaison des systèmes présentés, modélisant les caractères en fonction de leur contexte (CD) ou non (CI). Résultats sur la base de test de Rimes 2009 contenant 7 464 images

61Deux observations majeures peuvent être lues sur le tableau 2 :

• d’une part, l’augmentation du nombre de données pour l’apprentissage permet une amélioration des performance (plus de 2 % pour le système CI, et de 1 % pour le système CD). Cela nous motive à poursuivre des expériences sur l’ajout de données pour obtenir une meilleure modélisation.
• d’autre part, on remarque que la modélisation des caractères en fonction de leur contexte améliore considérablement les performances, quel que soit le lexique utilisé lors du décodage. Ainsi, pour un système appris sur le plus de données possible, l’amélioration est de 4,8 % pour le petit dictionnaire, et de près de 7 % pour le plus grand. Ainsi, même si les systèmes dits ’CD’ ont plus de paramètres à calculer (1 924 états, au lieu de 8 (états pas caractère) * 78 (monographes) = 624 états), ils obtiennent de meilleurs résultats. Ceci est dû à la plus grande précision dans la modélisation des caractères, mais aussi à la gestion de la taille des clusters d’états, correctement paramétrée grâce à une étape de validation (cf. figure 9).

4.4 – Comparaison avec l’état de l’art

62Le tableau 3 montre la performance de notre système par rapport aux systèmes à base de HMM uniquement, présents dans la compétition ICDAR.

Tableau 3

Comparaison avec l’état de l’art des systèmes à base de HMM uniquement sur la base de test Rimes 2009

système taux de reconnaissance Lexique de test Lexique complet système présenté 80, 35 % 75, 53 % IRISA LITIS 79,6 % 74,1 % 74,7 % 66,7 %

Comparaison avec l’état de l’art des systèmes à base de HMM uniquement sur la base de test Rimes 2009

63Le système proposé par l’Irisa (Guichard et al., 2010) est basé sur des HMM à densités continues. Le pré-traitement des images est standard, et les caractéristiques, décrites dans (Bazzi et al., 1999), sont extraites par des fenêtres glissantes et dépendent des lignes de base. Le nombre d’états par modèle de caractère varie.

64Le Litis quant à lui propose un système à base de HMM multiflux (Kessentini et al., 2008). Deux ensembles de caractéristiques sont extraits (l’un basé sur les contours, l’autre sur les densités de pixels) de deux fenêtres glissantes distinctes. Chaque ensemble permet la modélisation d’un système HMM, correspondant à un flux.

65Nous pouvons voir sur le tableau 3 que le résultat obtenu par notre système dépasse les performances des autres systèmes de la compétition basés uniquement sur des HMM. Ce résultat très positif nous permet de démontrer la capacité de la modélisation de caractères en contextes à être utilisée pour la reconnaissante d’écriture manuscrite hors-ligne. Avec un temps de décodage rapide, les performances obtenues dépassent celles de l’état de l’art des systèmes HMM.

66Il nous faut cependant compléter cette comparaison avec d’autres systèmes, présents lors de la compétition ICDAR 2009. Le système gagnant, à base de réseaux de neurones récurrents (RNN) (Graves et al., 2007 ; Graves et al., 2009), et présenté par TUM (Technische Universität München), donne un taux de reconnaissance remarquable, de 93,2 %. La principale différence entre les RNNs et les HMM est que l’un utilise un apprentissage discriminatif et l’autre génératif. Cependant, si les résultats des RNNs sont à leur avantage pour la reconnaissance de mots isolés, on peut se poser la question de la généralisation à la lecture de lignes ou de textes complets. Aussi, l’avantage des HMM est leur adaptation à n’importe quel vocabulaire de test, ce qui n’est pas valable pour les RNNs.

67Deux autres systèmes présentent aussi de bons résultats : le système présenté par l’UPV (Toselli, 2004), et celui présenté par Siemens (Caesar et al., 1993 ; Kaltenmeier et al., 1993 ; Schambach, 2003), donnant respectivement 86,1 % et 81,3 % de taux de reconnaissance. Ces deux systèmes, bien qu’utilisant en partie des HMM, ne sont pas cités ici car ils sont issus de combinaisons de plusieurs systèmes, et les performances des systèmes seuls n’étant pas fournies, leurs résultats ne sont pas comparables à ceux de notre reconnaisseur à base de modèles en contextes, présenté seul. La combinaison de systèmes est pourtant une solution intelligente à l’amélioration d’un système global, c’est pourquoi nous l’avons aussi envisagé (Kermorvant et al., 2010), mais cela ne rentre pas dans le cadre de cet article.