Source: http://patrice.dargenton.free.fr/publications/these.html
Timestamp: 2017-08-20 20:56:04+00:00

Document:
Contribution à la Segmentation et à la Reconnaissance de l'Ecriture Manuscrite
N° d'ordre 94 ISAL 0106 Année 1994
L'INSTITUT NATIONAL DES SCIENCES APPLIQUEES DE LYON
SPECIALITE : INGENIERIE INFORMATIQUE
DARGENTON Patrice
Contribution à la Segmentation
et à la Reconnaissance de l'Ecriture Manuscrite
Soutenue le 14 décembre 1994 devant la Commission d'Examen
Jury MM. C. BELLISSANT - Président
J.-P. CRETTEZ - Rapporteur
Y. LECOURTIER - Rapporteur
Mme N. VINCENT
TABLE DES MATIERES PRINCIPALES
CHAPITRE I. METHODES ET OUTILS ACTUELS DE LA RECONNAISSANCE DES TEXTES MANUSCRITS. 8
1. Les primitives, outils de la reconnaissance. 8
2. La méthode de reconnaissance. 27
3. La stratégie de reconnaissance. 37
CHAPITRE II. ETUDE DE LA SEGMENTATION.. 44
1. Segmentation globale de l'image par application de transformées mathématiques. 45
2. Segmentation par extraction de graphèmes. 86
CHAPITRE III. RECONNAISSANCE PAR APPARIEMENT DE GRAPHES STRUCTURELS 122
1. Construction d'un graphe structurel représentatif d'une forme. 122
2. Appariement des graphes structurels des lettres manuscrites. 149
3. Reconnaissance structurelle de lettres manuscrites. 172
Conclusion. 179
CHAPITRE IV. LES PERSPECTIVES POUR LA RECONNAISSANCE DES MOTS MANUSCRITS 182
1. Les perspectives à partir de la segmentation du mot en graphèmes. 183
2. Les perspectives à partir du graphe structurel du mot non segmenté. 191
3. Récapitulatif des méthodes et des perspectives pour la reconnaissance des mots manuscrits. 194
Les perspectives pour la reconnaissance des mots manuscrits. 195
1. Les perspectives à partir de la segmentation du mot en graphèmes. 195
2. Les perspectives à partir du graphe structurel du mot non segmenté. 197
4. Détermination de la stratégie de reconnaissance. 198
Conclusion. 205
CONCLUSION.. 206
REFERENCES BIBLIOGRAPHIQUES. 207
TABLE DES MATIERES. 220
TABLE DES MATIERES PRINCIPALES. 224
1.1. Les objectifs de l'extraction des primitives. 8
1.2. La problématique de l'extraction de l'information. 10
1.3. L'extraction des primitives. 11
1.3.1. Les approches de l'extraction des primitives. 11
1.3.2. Les catégories de primitives. 12
1.3.3. Les étapes de l'extraction des primitives. 13
1.4. Les techniques de changement de représentation. 16
1.4.1. Extraction des composantes connexes. 16
1.4.2. Représentation par le contour 21
1.4.3. Représentation par le squelette. 23
2.1. Etude bibliographique sur la modélisation des mots manuscrits. 27
2.1.1. Approximation du mot par des segments de droite. 27
2.1.2. Modélisation à partir de l'axe du mot 27
2.1.3. Modélisation du mot à l'aide des graphèmes. 27
2.2. Les catégories de méthodes. 29
2.2.1. Paramétrage du mot 30
2.2.2. Modélisation de la forme du mot indépendamment des lettres. 31
2.2.3. Modélisation de la forme du mot liée aux lettres. 32
2.2.4. Modélisation de la forme des lettres dans le mot 32
2.2.5. Modélisation des lettres. 33
2.2.6. Segmentation du mot en graphèmes. 34
2.2.7. Schéma récapitulatif des méthodes de reconnaissance. 35
3.1. Les approches ascendante et descendante. 37
3.2. Les recherches en largeur et en profondeur 37
3.3. La réduction du vocabulaire. 39
3.4. La stratégie combinatoire. 39
3.4.1. La méthode très combinatoire. 40
3.4.2. La méthode combinatoire par paliers. 40
3.5. La stratégie de confrontation. 40
3.6. La stratégie de coopération. 41
1.1. La transformée de Hough (TH) 45
1.1.1. Le principe d'utilisation. 45
1.1.1.1. Aspects théoriques de la TH.. 45
1.1.1.2. Localisation des segments de droite. 47
1.1.1.3. Critères de sélection des droites. 48
1.1.2. Application à l'analyse de l'écriture manuscrite. 50
1.1.2.1. Détection de l'inclinaison. 50
1.1.2.2. Détection de l'épaisseur moyenne du trait 51
1.1.3. Segmentation. 52
1.1.3.1. Détection du corps des mots. 52
1.1.3.2. Localisation des hampes et jambages. 53
1.1.4 Bilan et discussion. 54
1.2. La transformée de Fourier (TF) 55
1.2.1. Aspects théoriques de la TF. 55
1.2.1.1. TF d'un signal réel 55
1.2.1.2. TF discrète (TFD) et TF rapide (TFR) 57
1.2.1.3. TF bidimensionnelle (TF2D) 60
1.2.1.4. Propriétés de la TF. 61
1.2.2. Analyse spectrale de l'écriture. 63
1.2.2.1. Propriétés spectrales de l'écriture - Spectroscopie optique et numérique 63
1.2.2.2. Analyse de la répartition fréquentielle. 64
1.2.2.3. Analyse d'une raie caractéristique du spectre (détection des lignes d'écriture et de leur inclinaison) 66
1.2.2.4. Analyse de l'axe d'inertie du spectre. 68
1.2.3. Segmentation harmonique des mots manuscrits. 70
1.2.3.1. Segmentation harmonique 1D.. 70
1.2.3.2. Segmentation harmonique 2D.. 73
1.2.4. Reconnaissance harmonique. 78
1.2.4.1. Reconnaissance des caractères. 78
1.2.4.2. Reconnaissance harmonique des mots manuscrits. 81
1.2.4.3. Conclusion sur la reconnaissance par la TF. 83
1.3. Conclusion. 84
2.1. Segmentation du mot 86
2.1.1. Détermination de la zone médiane du mot 86
2.1.1.1. Analyse de l'histogramme horizontal 86
2.1.1.2. Analyse des graphèmes. 88
2.1.2. Segmentation du mot 91
2.1.2.1. Préclassification des graphèmes. 91
2.1.2.2. Traitement des graphèmes. 92
2.1.2.3. Exemples de segmentation de mots en graphèmes. 93
2.2. Classification des graphèmes. 95
2.2.1. Détection des boucles. 95
2.2.1.1. Remplissage. 95
2.2.1.2. Détermination de la classe des graphèmes. 96
2.2.2. Constitution d'un alphabet de transcription de graphèmes en lettres. 97
2.2.2.1. Table de coût 97
2.2.2.2. Combinaisons de deux ou trois graphèmes. 98
2.2.2.3. Graphèmes multiples. 100
2.2.2.4. Modulation des coûts en fonction des concavités. 100
2.2.2.5. Constitution de l'alphabet 102
2.3. Reconnaissance des mots à l'aide d'un dictionnaire. 109
2.3.1. Construction des séquences de graphèmes. 109
2.3.2. Procédure élémentaire de recherche. 109
2.3.3. Calcul d'une distance d'édition. 111
2.3.4. Résultats. 112
2.3.5. Classification des erreurs relevées. 117
2.4. Bilan et discussion. 118
1.1. Squelettisation de la forme. 124
1.1.1. Calcul de la distance minimale de chaque pixel de la forme à son contour 125
1.1.2. Détermination du noyau de la forme. 126
1.1.3. Amincissement du noyau en squelette. 126
1.1.3.1. Suivi de contour 126
1.1.3.2. Amincissement du noyau à l'aide de masques. 128
1.2. Construction du graphe structurel 131
1.2.1. Détection des arcs du squelette. 131
1.2.2. Traitement des arcs. 131
1.2.2.1. Détermination du voisinage des arcs. 131
1.2.2.2. Fragmentation des arcs. 132
1.2.2.3. Ebarbulage des petits arcs. 132
1.2.2.4. Fusion des fragments d' arcs. 132
1.2.3. Construction du graphe d'attribut - Approximation polygonale des arcs. 133
1.2.4. Modélisation informatique de la structure d'un graphe. 135
1.3. Résultats. 136
1.3.1. Comparaison entre le graphe structurel et la lettre originale. 138
1.3.2. Alphabet en caractères majuscules bâton. 139
1.3.3. Alphabet manuscrit en caractères minuscules. 142
1.3.4. Essais sur des mots manuscrits. 146
1.4. Discussion. 147
2.1. Appariement de deux graphes structurellement proches. 150
2.1.1. Superposition des deux graphes. 150
2.1.2. Appariement des noeuds de deux graphes. 151
2.1.3. Appariement des arcs des deux graphes en fonction des noeuds correspondants 154
2.1.4. Défauts rencontrés. 157
2.1.5. Conclusion. 157
2.2. Appariement de deux graphes structurels quelconques. 157
2.2.1. Recherche d'un isomorphisme optimal de graphe. 157
2.2.1.1. Appariement de l'ensemble des noeuds et points de contrôle. 157
2.2.1.2. Appariement de l'ensemble des segments. 160
2.2.1.3. Appariement simultané des noeuds et des arcs. 161
2.2.1.4. Propagation de contrainte par relaxation. 162
2.2.1.5. Synthèse. 163
2.2.2. Calcul de la distance d'édition entre les arcs. 164
2.2.3. Procédure d'appariement des arcs. 166
2.2.4. Recherche des similarités de sous-chaînes. 166
2.3. Détermination de la distance entre les deux graphes. 168
2.3.1. Distance entre les arcs appariés. 168
2.3.2. Distance entre les noeuds appariés. 169
2.3.3. Exemples de distances entre deux graphes. 169
2.3.4. Exemples de similarités détectées. 170
3.1. Plausibilité de reconnaissance. 172
3.2. Confrontation de plusieurs scores de reconnaissance. 172
3.3. Exemple de reconnaissance. 173
1.1. Reconnaissance des combinaisons de graphèmes. 183
1.1.1. Reconnaissance des lettres dans le mot 184
1.1.2. Reconnaissance des lettres indépendamment du mot 184
1.1.3. Reconnaissance classique et reconnaissance ciblée sur les lettres discriminantes 186
1.2. Reconnaissance structurelle des graphèmes isolés. 187
1.2.1. Reconnaissance des lettres dans le mot 187
1.2.2. Reconnaissance des lettres indépendamment du mot 188
1.2.3. Reconnaissance du mot modélisé par les graphèmes. 189
2.1. Reconnaissance des lettres dans le mot 191
2.2. Reconnaissance des lettres indépendamment du mot 192
2.3. Reconnaissance du mot indépendamment des lettres. 193
1.1. Reconnaissance des combinaisons de graphèmes. 195
1.1.1. Reconnaissance des lettres dans le mot 195
1.1.2. Reconnaissance des lettres indépendamment du mot 195
1.1.3. Reconnaissance classique et reconnaissance ciblée sur les lettres discriminantes 196
1.2. Reconnaissance structurelle des graphèmes isolés. 196
1.2.1. Reconnaissance des lettres dans le mot 196
1.2.2. Reconnaissance des lettres indépendamment du mot 196
1.2.3. Reconnaissance du mot modélisé par les graphèmes. 197
2.1. Reconnaissance des lettres dans le mot 197
2.2. Reconnaissance des lettres indépendamment du mot 197
2.3. Reconnaissance du mot indépendamment des lettres. 197
4.1. Similitude des approches à différents niveaux. 198
4.2. Analogie de stratégie dans des problèmes divers. 199
4.3. Les hypothèses et la connaissance a priori 200
4.4. Les hypothèses de primitives et la quantité d'information. 201
4.5. Minimisation de la prise de risque. 202
4.6. La stratégie humaine de la reconnaissance de l'écriture. 202
Je tiens à exprimer toute ma reconnaissance à :
Monsieur C. BELLISSANT, professeur à l'Université de Grenoble, qui me fait l'honneur de présider ce jury.
Monsieur H. EMPTOZ, professeur à l'INSA de Lyon, directeur du LISPI et de l'équipe Reconnaissance des Formes et Vision, pour m'avoir accueilli au sein de son équipe dynamique. C'est grâce à son soutien et ses encouragements que ce travail a vu le jour.
Madame N. VINCENT, maître de Conférences, agrégée à l'INSA de Lyon, pour avoir dirigé ce travail. Je tiens à la remercier pour l'aide précieuse qu'elle m'a apportée et pour le travail considérable qu'elle a consacré au suivi et à l'élaboration de la thèse.
Monsieur J.-P. CRETTEZ, de l'Ecole Nationale Supérieure Telecom Paris, pour avoir accepté d'être rapporteur de cette thèse, et pour les conseils qu'ils m'a donnés.
Monsieur Y. LECOURTIER, professeur à l'Université de Rouen, pour avoir accepté d'être rapporteur de cette thèse, et pour l'intérêt qu'il porte à mes travaux.
Monsieur Y. ROBERT, professeur à l'Ecole Normale Supérieure de Lyon, pour avoir accepté de faire partie de ce jury.
Je tiens également à remercier ici l'ensemble de l'équipe Reconnaissance des Formes et Vision du LISPI, parmi laquelle j'ai passé ces quatre années dans un cadre de travail agréable et très enrichissant. Cette ambiance conviviale et sympathique ainsi que les nombreux échanges d'idées ont été fructueux et ont contribué à cette synergie qui fait que l'équipe est plus que la somme individuelle de ses membres.
SEGMENTATION ET À LA RECONNAISSANCE DE L'ECRITURE MANUSCRITE
La reconnaissance de l'écriture manuscrite est le vieux rêve de tous ceux qui ont eu besoin d'entrer des données dans un ordinateur. Il remonte à plus d'une trentaine d'années. Aujourd'hui, il existe plusieurs domaines dans lesquels la reconnaissance de l'écriture manuscrite est attendue avec impatience, par exemple dans le tri automatique du courrier, le traitement automatique de dossiers administratifs, des formulaires d'enquêtes, ou encore l'enregistrement des chèques bancaires.
Ces applications montrent clairement les spécificités du domaine de la reconnaissance de l'écriture manuscrite par rapport à celui de la reconnaissance optique des caractères (OCR : Optical Character Recognition) qui concerne les caractères imprimés ou dactylographiés. Il est nécessaire de distinguer également la reconnaissance en ligne (on-line) de l'écriture manuscrite, qui relève plutôt de l'interfaçage entre l'homme et l'ordinateur (un stylo spécial est connecté à la machine et ne fonctionne que sur une tablette sensible), de la reconnaissance hors ligne (off-line). Seule la reconnaissance hors ligne sera considérée dans ce travail.
Quelques systèmes de reconnaissance de l'écriture manuscrite ont été réalisés et sont opérationnels à ce jour. Cependant, ils sont spécifiques à un domaine précis et sont encore limités. Par exemple, en ce qui concerne la poste, la reconnaissance de l'écriture manuscrite, contrairement à celle des caractères imprimés, se limite au code postal en chiffres ainsi qu'à la ville en caractères majuscules.
La reconnaissance universelle de l'écriture manuscrite par l'ordinateur est du domaine de la fiction pour quelques années encore. Tous les chercheurs sont confrontés à un problème difficile et incontournable, celui de la segmentation. La segmentation fait partie du processus de prétraitement et d'extraction de l'information, qui est un préalable à toute reconnaissance. Nous y avons consacré près de la moitié de notre travail.
Dans un premier chapitre, une analyse des méthodes et outils de la reconnaissance des textes manuscrits sera présentée. Ensuite, nos travaux de recherche, orientés en particulier sur l'utilisation des transformées, seront exposés dans le cadre d'une étude de la segmentation (chapitre II) suivant une approche globale.
Cette étude, si elle a ouvert de nouvelles voies de recherche, a cependant montré la nécessité de compléter les résultats obtenus par un approfondissement de la reconnaissance au niveau de la lettre. Nous proposerons donc dans le troisième chapitre une méthode de reconnaissance basée sur les graphes structurels.
Nous présenterons alors des perspectives que nous envisageons pour la reconnaissance des mots manuscrits (chapitre IV) avant notre conclusion.
METHODES ET OUTILS ACTUELS DE LA RECONNAISSANCE DES TEXTES MANUSCRITS
CHAPITRE I. METHODES ET OUTILS ACTUELS DE LA RECONNAISSANCE DES TEXTES MANUSCRITS
L'extraction de l'information est la première étape de la reconnaissance. Elle est réalisée à l'aide de l'extraction des primitives, qui sont des informations élémentaires. La primitive est l'outil de la reconnaissance.
Nous traiterons en premier lieu de l'extraction des primitives dans le cas général, c'est-à-dire quel qu'en soit le niveau (lettre, mot ou texte). Dans une seconde partie, nous nous concentrerons sur l'exploitation de ces primitives pour la reconnaissance des mots manuscrits. Nous présenterons une synthèse des méthodes de reconnaissance que nous avons élaborée à partir d'une étude bibliographique sur plusieurs systèmes de reconnaissance.
Dans la troisième partie, nous présenterons les différentes stratégies qui sont généralement mises en oeuvre pour exploiter les méthodes exposées précédemment.
1. Les primitives, outils de la reconnaissance
Il n'est pas dans nos intentions de reprendre une étude qui maintes fois a été faite mais seulement de rappeler certains outils, auxquels nous ferons souvent appel par la suite. Auparavant, nous préciserons les objectifs ainsi que la problématique de l'extraction de l'information.
1.1. Les objectifs de l'extraction des primitives
Au cours de l'extraction des primitives, plusieurs objectifs, qui précèdent la reconnaissance, peuvent être envisagés. Les principaux objectifs que nous définirons dans la perspective de la reconnaissance de l'écriture manuscrite sont : l'analyse, la segmentation, le paramétrage, la modélisation, le codage et la classification.
- L'Analyse, dont la définition littérale est "la décomposition d'un tout en ses parties", consiste généralement en l'extraction d'un ensemble d'attributs caractéristiques du texte. Concrètement, l'analyse d'un texte manuscrit consiste à recueillir des informations statistiques telles que la disposition des lignes d'écriture, leur orientation, leur régularité, l'espacement des mots et des lettres, la régularité et l'inclinaison des lettres, l'épaisseur du trait, ainsi que la ligature des lettres à l'intérieur des mots. L'objectif de l'analyse peut aboutir éventuellement à l'identification du scripteur, le signifiant [LORETTE 92], plutôt que directement à la reconnaissance du texte, le signifié.
- La Segmentation désigne la séparation de l'information en ses éléments constitutifs afin de les identifier isolément. La définition de la segmentation est donc assez proche du sens littéral du mot analyse. On parle de sur-segmentation lorsque l'élément constitutif est lui-même fragmenté, et de sous-segmentation lorsque plusieurs éléments constitutifs n'ont pas pu être isolés. Dans le cas de la reconnaissance des mots, les éléments constitutifs sont naturellement les lettres du mot. Il est nécessaire de distinguer la segmentation logique de la segmentation physique du document [LORETTE 92]. Les éléments logiques sont les éléments sémantiques composant le texte, c'est-à-dire les lettres ou les mots, ils ne correspondent pas toujours aux éléments physiques qui sont liés aux pixels de l'image. L'extraction des composantes connexes (cf. § 1.4.1.) est un exemple typique de segmentation physique.
- Le Paramétrage consiste à établir une liste d'attributs représentés par une variable binaire (attribut présent ou absent) ou multivaluée (proportionnelle à l'importance de l'attribut), qui ont été détectés et évalués dans l'image. A la différence de l'analyse, le paramétrage ne concerne qu'un mot ou qu'une lettre en vue de sa reconnaissance.
- La Modélisation est la construction d'une représentation approximative de la forme entière. A la différence du paramétrage, l'objectif est la réduction de l'information utile, au minimum nécessaire pour représenter complètement la forme, en particulier son aspect et sa structure. Si la modélisation est une description proche d'aspect de la forme originale, on parle alors d'une schématisation, avec une approximation plus ou moins importante. Sinon, il s'agit d'un codage de l'information. Dans ce cas, on ne se soucie pas de l'aspect de la modélisation, mais seulement de la pertinence de l'information qu'elle apporte à la reconnaissance. On remarque que, d'une façon générale, la schématisation par exemple d'un mot est une structure de données en deux dimensions (2D), tandis que le codage aboutit à une structure de données arborescentes (arbre de primitives 1D-2D), alors que le paramétrage se traduit par une liste ou bien un vecteur (1D).
- La classification peut être considérée comme une identification partielle de l'information. L'objectif de la classification est, lorsque l'on ne dispose pas de toute l'information nécessaire à l'identification complète de la forme (cas de la reconnaissance), de déterminer quand même une catégorie à laquelle elle appartient. Le principe est que moins d'information est nécessaire pour distinguer les caractères que pour les reconnaître.
Ces différents objectifs participent à la Segmentation, la Transformation (ou le Changement de Représentation) et la Réduction de l'information, qui sont les trois axes de la reconnaissance suivant lesquels nous présenterons au paragraphe 1.3.3. les différentes étapes de l'extraction de l'information.
1.2. La problématique de l'extraction de l'information
L'objectif de l'étape de l'extraction de l'information est la sélection de l'information pertinente qui se trouve noyée dans la masse de l'information brute acquise. La problématique de cette étape a pour origine le risque de perte d'information signifiante pour la reconnaissance. La minimisation de ce risque est conditionnée par deux dilemmes liés chacun à un paradoxe de causalité. Il s'agit du dilemme de la réduction et du dilemme de la segmentation.
Nous allons développer dans cette partie la nature de ces dilemmes en présentant les différentes origines de perte d'information lors du processus de la reconnaissance de l'écriture manuscrite.
La première étape du processus est l'acquisition de l'information. Il est évident que l'on ne peut pas extraire une information qui n'est pas présente dans le tracé. C'est pourquoi, avant de traiter de la perte d'information pendant la phase d'acquisition, nous considérerons la perte d'information pendant la phase de production de l'écriture.
- La perte d'information pendant la phase de production de l'écriture
Cette première origine de perte d'information, qui a lieu pendant l'écriture elle-même, est due au facteur humain. Cette question, qui s'écarte un peu de notre sujet, a cependant des conséquences déterminantes sur la reconnaissance.
Nous pensons que l'origine de la perte d'information est due à la projection dans un espace de dimension inférieure, du concept des mots lors de leur tracé linéaire dans le plan.
Le caractère subjectif de l'écriture tient au fait que le lecteur étant aussi le scripteur, il peut ne pas s’apercevoir que son écriture est illisible !
L’auteur a en outre la liberté de s’appliquer à ne bien tracer que les lettres permettant de distinguer les mots. Cette attitude a une conséquence importante sur la stratégie de lecture à adopter pour la reconnaissance. En effet, elle implique d’avoir la connaissance du vocabulaire parmi lequel l’auteur a estimé pouvoir distinguer les mots.
Cette perte d’information peut se manifester par une grande variation dans le tracé de l'écriture, par rapport au modèle scolaire ou à un tracé moyen, ou bien par une influence entre le tracé des lettres adjacentes dans le mot, qui augmentera ensuite la difficulté de les séparer.
La limite à considérer pour ce type de perte d'information est que si un humain ne peut pas lire un texte, un ordinateur ne le pourra probablement pas non plus. Cela fixe une borne inférieure à la qualité d'écriture admissible pour un système de reconnaissance.
- La perte d'information pendant la phase d'acquisition
L’objectif de cette étape est d’acquérir le maximum d'informations, afin d'obtenir des images numériques les plus précises. La perte d'information pendant l'acquisition est liée le plus souvent à la faiblesse des capteurs (scanner ou éventuellement caméra), ou aux conditions d'acquisition.
A ce niveau du processus, il reste à déterminer si l’information signifiante est accessible ou non parmi toute l’information acquise.
- La perte d'information pendant la phase de réduction
La phase de réduction consiste à extraire l’information signifiante qui est noyée dans le bruit.
Dans le cas de la classification, l’objectif est d’éliminer davantage de bruit que d’information afin de faciliter la discrimination.
Dans le cas de l'approximation, l'objectif est de modéliser en minimisant la perte d'information. Mais, plus précise est la modélisation, plus la procédure de reconnaissance est complexe et plus la représentation est sensible aux variations de tracé (fioritures non signifiantes pour la reconnaissance). Comment s'affranchir de cette forte variabilité du tracé grâce à l'approximation, sans perdre l'information signifiante nécessaire à la reconnaissance ?
Ce dilemme de la réduction repose sur le paradoxe que l'on ne peut savoir qu'une information est signifiante ou non tant que la forme n'est pas reconnue.
Il en résulte une certaine subjectivité de l'étape de réduction, ce qui implique un risque de perte d'information.
Nous verrons dans la première partie du chapitre II que le changement de représentation opéré grâce aux transformées mathématiques, en particulier celles de Fourier et Hough, peut apporter une aide précieuse dans ce cas.
Une autre perte d'information se produit également au cours de la phase de segmentation.
- La perte d'information pendant la phase de segmentation
A l'instar du dilemme de la réduction, le problème de la segmentation nous ramène une seconde fois au paradoxe de causalité.
Pour pouvoir segmenter le mot en lettres afin de les reconnaître isolément, il est nécessaire au préalable de les localiser, or comment localiser ces lettres sans les avoir reconnues auparavant?
C'est dans le chapitre II - Etude de la segmentation - que nous approfondirons cette question.
1.3. L'extraction des primitives
1.3.1. Les approches de l'extraction des primitives
En fonction de l'objectif fixé et de la méthode d'extraction choisie, l'approche de l'extraction des primitives peut être systématique ou heuristique.
- La modélisation et le codage conduisent à une approche systématique dans la mesure où l'objectif fixé est la détermination d'une représentation complète de la forme, même de façon approximative. Dans la modélisation, les primitives sont obtenues a posteriori, par le résultat de l'approximation, tandis que, en ce qui concerne le codage, les catégories de primitives sont définies a priori. Un test, qui est par exemple réalisé à l'aide d'une sonde, permet de valider la présence de chacune des primitives sur l'ensemble de la forme.
- Le paramétrage conduit plutôt à une approche heuristique. Dans ce cas, on ne cherche pas nécessairement une représentation complète mais seulement des indices significatifs. De même que dans le cas du codage, ces indices sont des primitives définies a priori.
Au-delà de cette classification un peu formelle, la différence entre les approches systématique et heuristique comme entre le caractère a priori ou a posteriori, s'avère plus nuancée dans la pratique.
1.3.2. Les catégories de primitives
Nous avons distingué quatre catégories principales de primitives : les primitives topologiques, statistiques, structurelles et globales.
Les primitives topologiques ou métriques
Le terme métrique désigne la mesure d'une distance. La topologie est "l'étude des propriétés de l'espace (et des ensembles) du seul point de vue qualitatif". Concrètement, la topologie consiste, à l'aide de sondes appliquées directement sur l'image "brute", à effectuer par exemple sur l'échantillon les mesures et les tests suivants :
- compter dans une forme le nombre de trous,
- évaluer les concavités,
- mesurer des pentes et autres paramètres de courbures et évaluer des orientations principales,
- mesurer la longueur et l'épaisseur des traits,
- détecter les croisements et les jonctions des traits,
- mesurer les surfaces, les périmètres,
- déterminer le rectangle délimitant l'échantillon, ou le polygone convexe,
- évaluer le rapport d'élongation (ou allongement) longueur/largeur, ...
- rendre compte de la disposition relative de ces primitives.
Les primitives structurelles
A la différence des primitives topologiques, les primitives structurelles sont généralement extraites non pas de l'image brute, mais à partir d'une représentation de la forme par le squelette (cf. § 1.4.3.) ou par le contour (cf. § 1.4.2.). Ainsi, on ne parle plus de trous, mais de boucles ou de cycles dans une représentation filiforme du caractère. Cependant, pour le reste, les primitives structurelles correspondent à peu près aux primitives topologiques, il s'agit principalement :
- des segments de droite,
- des arcs, boucles et concavités, des pentes,
- des angularités, points extremum et points terminaux, jonctions et croisements.
Les primitives statistiques
Elles véhiculent une information qui est distribuée sur toute l'image. L'histogramme, qui représente le nombre de pixels sur chaque ligne ou colonne de l'image, en est un exemple classique et simple à calculer. L'histogramme directionnel est plus long à calculer car il nécessite par exemple l'utilisation d'un algorithme de BRESENHAM [BRET 88] permettant de compter le nombre de pixels contenus sur une ligne de direction quelconque de l'image. L'histogramme des transitions, comme l'indique son nom, ne retient que le nombre des transitions 0-1 et 1-0.
Une application pratique des primitives statistiques de la sorte est réalisée grâce à l'intersection de la forme avec un réseau de droites pour la reconnaissance des chiffres manuscrits [AUTRET 91]. Dans ce cas, des histogrammes de transition sont construits seulement avec un échantillon de quelques droites au lieu de la totalité de celles-ci, ce qui permet une réduction a priori des données caractéristiques.
Pour s'affranchir du choix arbitraire de ces droites (espacement et orientation des droites du réseau) qui doit nécessairement être fixe entre l'apprentissage et la reconnaissance, on peut faire intervenir les probabilités en calculant la fréquence des intersections de la forme avec une série de droites aléatoires [HEUTTE 93].
On utilise aussi une autre primitive statistique basée sur un moyennage des pixels situés à l'intérieur d'un masque rectangulaire. La construction d'une matrice de masque recouvrant la totalité de la forme permet une représentation statistique à partir d'un nombre très réduit de valeurs correspondant à chaque masque (cf. Annexe A).
Les primitives globales
Elles sont naturellement basées sur une transformation globale de l'image. La caractéristique d'une primitive globale est de dépendre de la totalité des pixels d'une image. Nous en étudierons deux, les transformées de Hough et de Fourier, dans le second chapitre.
1.3.3. Les étapes de l'extraction des primitives
Il peut y avoir plusieurs étapes intermédiaires pour parvenir à l'objectif fixé. La première étape importante de la reconnaissance est le changement de représentation de l'information. A partir de l'image numérique brute, qui est la représentation originelle, on relève quatre autres représentations possibles de l'information, ce sont :
1°) L'extraction des composantes connexes
2°) L'extraction du contour
3°) La détermination du squelette (au sens large du terme)
4°) Les transformations mathématiques qui opèrent globalement sur l'image (cf. Chapitre II).
Ces techniques de changement de représentation de l'information seront détaillées au paragraphe 1.4. C'est à partir d'une de ces représentations qu'est ensuite réalisée l'étape d'extraction des primitives proprement dite.
On le voit, le vocabulaire lié à l'extraction des primitives est riche et varié. Aussi, afin d'ordonner toutes les étapes suivant la progression normale du traitement de l'information et en les situant les unes par rapport aux autres, nous avons regroupé sur un schéma l'ensemble de ces opérations suivant deux axes indépendants qui représentent la segmentation et la réduction de l'information. La réduction vise à l'élimination de l'information redondante ou du bruit. Son axe va dans le sens de la reconnaissance (l'identification est la réduction ultime de l'information), ce qui n'est pas le cas de la segmentation.
Si la visualisation du schéma en trois dimensions avait été aisée, nous aurions ajouté un troisième axe, indépendant des deux autres, intitulé la transformation (ou le changement de représentation) de l'information. En effet, cet acte n'est pas une segmentation et ne conduit pas obligatoirement à une réduction de l'information. Pratiquement, nous avons projeté cet axe dans le plan (segmentation, réduction).
Les objectifs et les étapes de l'extraction des primitives
L'ensemble des échantillons d'écriture traités dans notre travail est constitué par des images numériques de type binaire. Or, dans le cas où les échantillons sont numérisés avec une caméra CCD ou un scanner multiniveau, les images obtenues sont de type niveaux de gris, ce qui nécessite souvent une étape préliminaire de binarisation et n'est pas sans poser le problème du choix du seuil lorsque le fond de l'image a un niveau uniforme. Certaines études [PETIER 91] montrent alors l'intérêt de pratiquer l'étape d'extraction des primitives directement sur l'image en niveaux de gris.
En revanche, lorsque le fond de l'image est uniforme, la binarisation n'entraîne pas une perte d'information significative, à condition que la résolution soit suffisante.
D'autre part, nous devons mentionner un problème entraînant une étape supplémentaire de segmentation, que nous n'avons pas fait figurer dans notre schéma, lorsqu'une information non signifiante pour la reconnaissance est superposée au texte à décrypter. Cette information peut être par exemple les barres obliques dans le cas des chèques ou encore un bruit quelconque. Le traitement consiste alors à extraire l'information utile du reste de l'image.
1.4. Les techniques de changement de représentation
1.4.1. Extraction des composantes connexes
L'extraction des composantes connexes, procédure également appelée capture des connexités ou étiquetage des pixels, est largement utilisée en Reconnaissance des Formes (RdF) pour segmenter les images binaires. La technique consiste à regrouper les pixels voisins dans un ensemble appelé composante connexe. Chaque ensemble est disjoint des autres et peut ensuite être aisément isolé. La 4-connexité est distinguée de la 8-connexité suivant que le critère de voisinage comprend les 4 ou les 8 voisins d'un pixel.
Il existe deux principaux algorithmes pour accomplir cette tâche :
- le premier est basé sur une procédure de suivi de contour [LEROUX 91] : en parcourant le contour d'un objet et en revenant au point de départ, une composante connexe est délimitée, à l'exclusion cependant des contours intérieurs correspondant aux éventuels trous (cf. § 1.4.2.).
- le second algorithme procède par une propagation d'un étiquetage des pixels lorsque l'on effectue un balayage des lignes et des colonnes de l'image.
Nous avons élaboré un algorithme de ce type fonctionnant en une seule passe, suivant le critère de 4-connexité (cette méthode sera exploitée dans le chapitre II § 2.).
La propagation de l'étiquette des pixels suivant les colonnes (verticalement) est prioritaire sur la propagation suivant les lignes (horizontalement). On procède de la manière suivante :
En parcourant une ligne horizontale de gauche à droite, on associe un numéro (une étiquette) à chaque pixel de telle sorte que tous les pixels voisins portent le même numéro (le numéro zéro est réservé pour un pixel "vide"). Lorsque sur cette ligne, le voisinage est interrompu, puis reprend plus loin, le numéro est incrémenté de 1. Les étiquettes sont représentées par les lettres A, B et C sur la figure 1a.
Figure 1a : Propagation de l'étiquetage des pixels de gauche à droite sur une ligne horizontale
Lorsqu'une nouvelle ligne est commencée, on propage naturellement l'étiquetage de haut en bas en recopiant le numéro du pixel qui se trouve au-dessus du premier pixel de la nouvelle ligne. S'il n'y a pas de pixel au-dessus, un nouveau numéro est utilisé (fig. 1b).
Figure 1b : Propagation de l'étiquetage des pixels de haut en bas sur une colonne verticale
Lorsqu'un conflit se présente entre la propagation horizontale et la propagation verticale des étiquettes, deux cas se présentent alors (fig. 1c) :
Figure 1c : Conflit entre la propagation horizontale et verticale
1er cas : si le numéro des pixels horizontaux correspond à une nouvelle étiquette, alors il est facile de résoudre le conflit en remplaçant la nouvelle étiquette de tous les pixels à gauche du point de conflit par le numéro prioritaire du pixel de la ligne précédente (fig. 1d). La nouvelle étiquette est alors annulée ;
Figure 1d : Résolution du conflit correspondant au 1er cas
2e cas : Si le numéro des pixels horizontaux a déjà été propagé à partir de la ligne précédente, il serait trop long de remplacer tous les pixels correspondants. Aussi, on note dans un tableau que les deux étiquettes en conflit désignent une unique composante connexe (fig. 1e).
Figure 1e : Résolution du conflit correspondant au 2e cas
Cet algorithme, dont nous allons analyser les particularités, présente plusieurs avantages par rapport aux autres algorithmes que nous avons pu étudier (les procédures sont rarement explicitées dans les articles publiés concernant les systèmes qui les utilisent).
Le premier est la simplicité de la procédure de propagation de l'étiquetage obtenue en sacrifiant l'optimisation en mémoire. En effet, il y a beaucoup plus de numéros distincts d'étiquettes que de véritables composantes connexes. Or il est nécessaire de réserver pour chaque pixel de l'image un emplacement mémoire (1 ou 2 octets) suffisant pour mémoriser le codage du plus grand numéro utilisé pour l'étiquette d'un pixel, ce qui limite l'utilisation de cet algorithme à des images de petite taille. Si la mémoire pose un problème, une solution consisterait à étiqueter les pixels de façon cyclique, en repartant au numéro 1 après le numéro 65535 (216-1). Mais cela supposerait que le graphisme du texte ne s'étale pas sur trop de lignes à la fois, au risque de ne plus pouvoir différencier ensuite les pixels non connexes portant le même numéro.
Le second avantage de cet algorithme est de fournir systématiquement les minimums du contour supérieur. A un minimum correspond un changement d'étiquette à l'intérieur d'une même composante connexe. C'est le cas de la figure 1e. Au sein d'une composante connexe, deux étiquettes distinguent des fragments, ce que nous avons exploité en appliquant l'algorithme à la segmentation des mots manuscrits. Sur les figures 2 et 3, nous pouvons voir le résultat de cet étiquetage des pixels sur les mots "trois" et "dix", lorsque plusieurs sens de balayage différents sont utilisés (1 : Haut-Bas / Gauche-Droite, 2 : BHGD, 3 : GDHB, 4 : DGHB).
Les paramètres que l'on peut calculer sur les composantes connexes sont principalement l'aire, la longueur du contour, la largeur mais également la délimitation du rectangle englobant la composante connexe. Ces calculs sont facilités par l'étiquetage des pixels.
Le plus souvent, l'extraction des composantes connexes est utilisée comme traitement préalable aux autres types de représentation des données, afin de procéder à une segmentation initiale de l'image et sans tenir compte de l'étiquetage. Ainsi l'étape suivante peut être :
- le retour à l'image brute (mais segmentée) sur laquelle on pourra alors extraire les primitives statistiques et employer les sondes topologiques pour compléter le paramétrage de la composante connexe ;
- la détermination du squelette [LEROUX 91ab], [POTIER 91] (cf. § 1.4.3.) ;
- l'extraction et l'analyse du contour pour la segmentation du mot en graphèmes, par exemple [MOREAU 91].
1.4.2. Représentation par le contour
L’exploitation du contour est fréquente, tant en reconnaissance de l'écriture qu'en RdF en général, étant donné la facilité de l'extraction.
Le contour est également utilisé comme étape préalable à un changement de représentation de l'information, en tant qu'empreinte des formes contenant une quantité réduite de données.
Extraction du contour
Dans les images à niveaux de gris, il est intéressant d'extraire le contour à l'aide d'un calcul de gradient. Ce contour est alors d'autant plus marqué que le niveau des pixels résultant du gradient est élevé. En revanche, dans les images binaires, il est plus avantageux d'utiliser un algorithme de suivi de contour car il fournit directement une liste ordonnée de points. Un exemple simple d'algorithme est détaillé dans le chapitre III. Nous ne nous étendrons pas sur ce sujet car le suivi du contour ne présente pas de difficultés en soi ; seule l'approximation de ce contour peut ensuite conduire à des résultats plus ou moins variables.
Nous préciserons maintenant quelles sont les différentes représentations possibles auxquelles on peut aboutir à partir du contour.
L'analyse du contour est souvent utilisée en reconnaissance des textes manuscrits pour la segmentation des mots en lettres. Elle sera détaillée dans le paragraphe 2.1.3.
Le changement de représentation le plus simple est la vectorisation : il permet d'obtenir l'invariance par translation, c'est-à-dire, l'invariance à la position de la forme. Pour cela la quantité d'information contenue dans la liste des pixels du contour est avantageusement réduite à l'aide du code de FREEMAN en une liste de vecteurs unitaires. Le principe est de mémoriser seulement la position de chaque pixel par rapport au pixel précédent (4 ou 8 directions en fonction de la continuité du contour) au lieu des deux coordonnées de tous les pixels dans le plan.
La transformation globale du contour
A partir de cette liste de vecteurs, l'objectif de la transformation globale du contour est d'intégrer à la reconnaissance, des propriétés d'invariance à certaines déformations ou transformations que peut subir la forme, telles que :
- la rotation,
- le changement de taille ou d'échelle,
- le cisaillement, l'homothétie ou une autre transformation affine,
- une transformation non linéaire (torsion, distorsion, ...).
Lorsque l'on compare une forme test avec une forme apprise, il est nécessaire de tenir compte d'autres variables telles que, par exemple, le point de départ du contour dans la chaîne, ou la résolution du contour (nombre de vecteurs pour le décrire, quelle que soit sa taille).
Les principales transformations globales du contour sont les suivantes :
- descripteurs de Fourier
- calcul des moments
- transcodage du contour : par exemple, par rapport au centre de gravité de la forme, la mémorisation du plus grand rayon en fonction de chaque direction échantillonnée.
Ces transformations sont adaptées à des problèmes généraux de reconnaissance des formes, tels ceux rencontrés dans le domaine de l'analyse de scène en robotique, où les formes quelconques peuvent être vues dans toutes les directions, en perspective, avec des parties cachées et souvent du bruit, et aussi en trois dimensions. Dans le domaine de la reconnaissance de l'écriture, les caractères ne sont pas des formes quelconques, elles sont toujours vues à plat, et on ne cherche jamais à les reconnaître à l'envers, dans un miroir, déformées ou partiellement occultées. Il reste cependant des déformations simples qui sont effectivement rencontrées. Par exemple en OCR, le style italique est une déformation modélisable par un cisaillement, qui est d'ailleurs créé de la sorte dans les logiciels de traitement de texte à partir des modèles vectoriels des caractères droits. Pour l'écriture manuscrite, les déformations sont plus importantes que dans le simple style italique et plus variées.
Autres représentations obtenues à partir du contour
L'extraction du contour peut servir d'étape préliminaire aux deux autres changements de représentation que sont l'extraction des composantes connexes, comme nous l'avons vu au paragraphe 1.4.1, et la construction du squelette, comme nous le préciserons au paragraphe 1.4.3.
L'approximation du contour
L'objectif de l'approximation du contour est également la reconnaissance, mais la représentation est proche d'aspect de l'original. La reconnaissance est basée sur l'appariement (cf. Chapitre III § 3.4.). Un algorithme d'approximation polygonale est détaillé dans le chapitre III § 1.2.3.
Lorsque l'on apparie ainsi les formes par leur contour, il est intéressant de distinguer les contours intérieurs des contours extérieurs afin de conserver la cohérence de l'appariement.
Une autre approche, plutôt que d'utiliser la modélisation directe en 2D, consiste à procéder d'abord à un codage du contour, pour n'apparier que le code des contours, ce qui simplifie la procédure : on utilise pour cela une grammaire d'attribut, et la reconnaissance consiste à vérifier que le code de la forme appartient à la syntaxe autorisée de la grammaire [BELAID 92].
1.4.3. Représentation par le squelette
L'extraction du squelette désigne, au sens large du terme, un ensemble de techniques visant à représenter les formes à l'aide d'une structure fine continue qui passe à égale distance des contours. La squelettisation est une opération souvent utilisée en modélisation ou en représentation de l'écriture manuscrite, car l'écriture est assimilable à un long ruban replié sur lui-même et d'épaisseur constante. Le modèle à l'origine de la production de l'écriture est un modèle linéaire sans épaisseur, de sorte que la représentation par le squelette est naturelle et d'aspect proche de l'écriture. En ce sens, elle est proche de la représentation "en-ligne" ("on-line"), sauf en ce qui concerne l'ordre temporel du tracé ainsi que les "barbules" qui ne sont pas significatives du tracé.
Extraction du squelette
L'opération de squelettisation consiste donc, dans le cas particulier de l'écriture, à éliminer l'épaisseur du trait ou plutôt à l'amincir jusqu'à l'épaisseur minimale d'un pixel. Les multiples méthodes de squelettisation peuvent se grouper en trois catégories :
* L'amincissement
Les termes érosion ou éclaircissage ont un sens assez semblable à celui de amincissement employé en morphologie mathématique et qui est contenu dans le terme anglais "thinning". Cette technique consiste à appliquer un élément structurant d'une transformation de tout ou rien dans laquelle le pixel central noir est remplacé par un pixel blanc en fonction de la configuration des pixels voisins. Il existe trois stratégies sur la manière d'appliquer ce masque à l'ensemble des pixels de l'image. Dans la première, un balayage horizontal et vertical de toute l'image est effectué en plusieurs passes jusqu'à ce qu'il ne reste plus de pixels à éroder, ou encore en une seule passe avec une érosion directe des pixels à chaque translation du masque. La troisième stratégie consiste en un suivi de contour appliqué successivement d'une manière analogue à une érosion "naturelle".
A l'intérieur de chacune de ces stratégies, on rencontre de nombreuses variantes qui conduisent à des améliorations portant sur les imperfections classiques du squelette telles que les "barbules" ou le décalage entre le squelette et la forme. Les améliorations concernent également l'optimisation de la procédure, comme par exemple l'ébarbulage simultané à l'amincissement.
* Le "gradient"
Dans cette technique, qui s'adapte également aux images à niveaux de gris, on procède à un balayage de l'image avec un masque comme pour l'amincissement, mais la configuration des pixels n'est plus prise en compte. En effet, seuls les niveaux minimum et maximum des pixels à l'intérieur du masque sont considérés. Trois étapes sont nécessaires pour aboutir au squelette.
Elles sont détaillées au chapitre III § 1.1. Ce sont :
1) le calcul de la distance minimale de chaque pixel de la forme au contour
2) la détermination du noyau de la forme
3) l'amincissement du noyau en squelette.
Dans la méthode que nous allons proposer, le noyau a une épaisseur de un ou deux pixels suivant que l'épaisseur du trait comporte un nombre de pixels pair ou impair. Le squelette possède toujours une épaisseur de un pixel grâce à la troisième étape, mais a le défaut de ne pas respecter les connexités. On montrera comment ce défaut peut être supprimé en définissant un voisinage en chaque point.
A la différence des autres techniques, la transformation aboutissant au noyau est parfaitement réversible. Il n'y a pas de perte d'information. En ce sens, la squelettisation obtenue par cet algorithme est plus proche de la définition de l'opération de morphologie mathématique d'extraction du squelette. Pourtant, cette technique est peu utilisée, sans doute en raison de la discontinuité du squelette. L’étude de d’Acierno [d'ACIERNO 91] est le seul exemple de système comportant une étape de squelettisation qui utilise cette technique.
* Le suivi de trait
Cette technique consiste à trouver un chemin à l'intérieur et au milieu du trait et qui parcourt l'ensemble du tracé [PAQUET 90, 91b] [PETTIER 91]. La réunion des chemins forme un graphe qui s'apparente au squelette. L'avantage de cette technique est qu’elle indiquela présence des liaisons entre tous les points du graphe, elle ne nécessite donc pas le traitement de chaînage des pixels isolés (cf. § suivant) qui incombe aux autres techniques.
Il existe encore d'autres techniques visant à extraire un squelette ou pseudo-squelette telle que celle basée par exemple sur la mise en correspondance des deux versants du contour.
On peut relever quelques critères permettant de récapituler les différences caractérisant chacune des différentes techniques :
- présence et importance des barbules,
- épaisseur de 1 ou de 2 pixels,
- continuité du squelette, prise en compte du critère de 4 ou 8-connexité,
- facilité du chaînage des pixels du squelette,
- centrage du squelette au milieu de la forme.
On consultera une synthèse [HU 91] de ces techniques, comportant notamment les liens entre les squelettes et les diagrammes de Voronoï, ainsi que des études de comparaisons méthodiques et automatiques entre les différents squelettes qui pourront compléter notre brève présentation.
La squelettisation est une opération qui nécessite un traitement de l'information avant la reconnaissance. En effet, le squelette est une structure de données brutes que l'on ne peut pas exploiter directement. Elle nécessite une certaine interprétation dont l'objectif est de normaliser l'ensemble des données en un tout cohérent, ceci indépendamment de l'étape de reconnaissance. Afin de préciser la nature des divers traitements qu'elle comporte, nous nous référons à l'exemple typique de ce qui est appliqué pour la squelettisation "gradient" (cf. chapitre III § 1.1.)
La 1ère étape est le Chaînage des pixels (détection des arcs du squelette) qui est basé sur la détection des pixels voisins du squelette (qui est discontinu) ;
La 2ème étape est la Détermination du voisinage des arcs;
La 3ème étape est la Fragmentation (ou la segmentation) des arcs aux points de jonction ou croisements ;
La 4ème étape est l'Ebarbulage des petits arcs ;
La 5ème étape est la Fusion des fragments d'arc ;
La 6ème étape est une Approximation polygonale des arcs ;
La 7ème et dernière étape est la correction des arcs et la Construction du graphe.
Ces étapes peuvent se regrouper en trois opérations principales :
- Réduction : l'extraction du squelette ;
- Changement de représentation : 1, 2 et 3 ;
- Interprétation : 4, 5, 6 et 7.
La brève présentation des techniques de changement de représentation étant achevée, nous allons maintenant étudier dans une deuxième section comment exploiter les primitives extraites pour la reconnaissance des mots manuscrits.
2. La méthode de reconnaissance
Le point critique de la reconnaissance de l'écriture manuscrite est la modélisation du mot à l'aide des primitives que nous avons extraites (cf. § 1.). En effet, du fait de la difficulté que pose la segmentation en lettres dans l'écriture manuscrite (cf. chapitre II - étude de la segmentation), le mot devient l'entité sémantique minimale. Nous allons donc étudier comment exploiter ces primitives extraites en précisant le but intermédiaire qui est visé, et quelle influence le type de primitive a sur la modélisation des mots, en particulier sur le niveau de description du mot qui est atteint.
Il est utile de souligner que les conditions exactes de l'application considérée (en particulier l'étendue du vocabulaire) ont une influence sur l'objectif de la reconnaissance et donc sur l'extraction des primitives. Suivant ces conditions, on optera plutôt pour une modélisation, une classification ou une segmentation des mots. Ainsi suivant chaque objectif, une méthode de reconnaissance sera plus appropriée (cf. § 2.2.).
2.1. Etude bibliographique sur la modélisation des mots manuscrits
L'objectif visé dans ce paragraphe est la modélisation, c'est-à-dire la représentation approximative mais complète du mot par un ensemble de primitives.
L'étude bibliographique que nous avons menée dans le cadre de la reconnaissance omniscripteur hors-ligne des mots manuscrits, a conduit à la classification suivante qui regroupe les principales approches rencontrées pour la modélisation des mots manuscrits.
2.1.1. Approximation du mot par des segments de droite
- Segments de droite [LECOLINET 93a] et [LERY 89] ;
- Approximation polygonale du squelette [LEROUX 91ab] ;
- Modélisation des hampes et jambages ainsi que des concavités par des segments horizontaux et verticaux [LECOLINET 91] ;
- Détection des lettres clefs du mot [CHERIET 93] (principalement les hampes et jambages).
2.1.2. Modélisation à partir de l'axe du mot
- Intersection avec l'axe rectiligne du mot [PAQUET 91b] et [OLIVIER 93] ;
- Axe curviligne du mot [SIMON 89] et [DELEDICQ 93] ;
2.1.3. Modélisation du mot à l'aide des graphèmes
Les graphèmes sont des éléments qui conduisent, par leur combinaison, à des hypothèses de lettres. Ils sont déterminés en fonction des primitives suivantes :
- Arcs, boucles, points de rebroussement [AOKI 86] ;
- Boucles, concavités, classification avec les zones des hampes et jambages [BOZINOVIC 84], étude des composantes connexes [MOREAU 91] et [LEROUX 91ab].
Les études dans le domaine de la segmentation du mot en graphèmes sont principalement basées sur l'analyse du contour (cf. § 1.4.2.). Les critères de segmentation que nous avons répertoriés sont liés à la détection des minimums du contour supérieur du mot [BOZINOVIC 84] [MAIER 86] [LEROUX 91]. Les hypothèses de base sont les suivantes :
- les caractères composant le mot ne sont reliés que par un seul trait ;
- la segmentation peut être effectuée par une coupure verticale située au minimum local du trait de connexion.
La détection de ce minimum local est obtenue par le calcul de la dérivée du contour, c'est-à-dire, dans l'espace discrétisé, de la différence des ordonnées de deux points d'abscisses consécutives. Puis le minimum est validé en fonction des critères d'unicité du trait de connexion et de son épaisseur, afin de ne pas couper un caractère comportant un minimum local à l'intérieur de son tracé. Lorsque le critère d'unicité du trait ne peut être vérifié à l'aplomb d'un minimum local, une coupure oblique (angle soit fixé soit variable) peut améliorer la méthode [DARGENTON 90].
Afin de renforcer les hypothèses de base, plusieurs autres critères ont été proposés dans différentes études incluant la segmentation des mots manuscrits :
- la proximité entre deux coupures
Deux coupures successives ne peuvent survenir à une distance inférieure à la largeur minimum d'une lettre.
- la zone centrale du mot
La zone centrale du mot, qui doit être détectée au préalable (cf. Chapitre 2 § 2.1.1.), est la zone où se situent la plupart des ligatures entre les lettres.
- le sens de parcours du contour
Le sens positif ou négatif par rapport au sens trigonométrique est pris en compte pour générer des hypothèses de segmentation [BADIE 82] [HOLT 92].
- le profil supérieur et les concavités latérales
Le profil supérieur est obtenu par le maximum du contour à chaque abscisse. Le profil supérieur est une fonction de l'abscisse tandis que le contour est multiforme, d'où la simplification de la détection des minimums.
Les concavités latérales sont des zones dans lesquelles la segmentation est improbable. Elles sont donc utilisées pour délimiter les zones de segmentation potentielle, ou points d'ancrage, à partir du profil supérieur [LECOLINET 90].
- les crêtes du profil supérieur
Deux crêtes du profil supérieur détectées de part et d'autre du point d'ancrage renforcent l'hypothèse de segmentation.
- la confrontation des hypothèses du contour supérieur et du contour inférieur
Les minimums du contour supérieur sont mis en relation avec les maximums du contour inférieur [MOREAU 91] [HOLT 92] (cf. Détection des extremums basée sur l'étiquetage). Dans le cas d'un trait de liaison simple entre deux lettres, ce critère est équivalent à celui utilisant les crêtes du profil supérieur.
Les critères de segmentation à partir du contour que nous avons présentés sont valables pour la grande majorité des traits de liaison entre les lettres des mots. Cependant, de même que la segmentation basée sur l'étiquetage des connexités (cf. § 1.4.1.), la segmentation basée sur l'analyse du contour, qui est plus classique, conduit inévitablement à la sur-segmentation des lettres présentant un minimum local, tel qu'une liaison intra-lettre dans le cas 'u' ou 'v', par exemple, ou bien à la suite d'une boucle ouverte, ce qui est fréquemment le cas des lettres 'a' ou 'o'. Elle conduit également à la sous-segmentation, en cas d'absence de minimum local entre deux lettres, ce qui peut survenir pour les lettres collées, ou bien lorsque la liaison inter-lettres correspond à un maximum du contour inférieur.
On notera cependant que la segmentation basée sur l'étiquetage, qui est plus systématique, conduit à des coupures à chaque minimum local du contour supérieur, quelle que soit sa position verticale. La sur-segmentation qui en résulte nécessite donc une étape renforcée de recomposition en lettres, comme nous le verrons dans le chapitre II § 2.1.2.
2.2. Les catégories de méthodes
L'objectif de la reconnaissance est de retrouver l'information manquante, qu'elle soit non présente, perdue ou non directement accessible, à partir des informations que l'on a extraites, en s'aidant éventuellement du contexte environnant (principalement des contextes lexical et syntaxique).
Nous allons présenter six catégories de méthodes que nous avons répertoriées, à partir de l'étude de plusieurs systèmes de reconnaissance. Il s'agit des méthodes de :
1. Paramétrage du mot
2. Modélisation de la forme du mot indépendamment des lettres
3. Modélisation de la forme du mot liée aux lettres
4. Modélisation de la forme des lettres dans le mot
5. Modélisation des lettres
6. Segmentation du mot en graphèmes
Auparavant, il est nécessaire de préciser la terminologie que nous avons souvent utilisée dans cette analyse autour du mot "Matching". Nous avons utilisé ce terme pour désigner d'une façon générique la mise en correspondance, l'appariement ou la distance d'édition :
- La mise en correspondance traduit l'action du matching, sans préciser la méthode de comparaison, la nature de la distance ou du coût utilisé. Par exemple, un mot (ou une lettre) "match" avec un (ou une) autre s'ils se correspondent plus ou moins.
- L'appariement est le terme choisi pour la mise en paire de deux graphes structurels, il est proche de la mise en correspondance, mais précise la méthode de comparaison. L'appariement des graphes structurels utilise une distance d'édition sur chacun des couples d'arcs des deux graphes (cf. Chapitre III).
- La distance d'édition est un algorithme classique de mise en correspondance de deux chaînes linéaires, chaque élément de la chaîne peut représenter un symbole, un caractère, un segment...
Le terme de matching implique une comparaison systématique, c'est une méthode descendante comme nous le préciserons plus loin (cf. § 3.1.).
2.2.1. Paramétrage du mot
Le paramétrage du mot a pour but la sélection d'un nombre restreint de mots parmi un grand lexique. La méthode de reconnaissance est basée sur une description approximative du mot entier. Elle est peu sensible et donc très tolérante aux fluctuations du tracé. Cette méthode n'est que la première étape de la reconnaissance et doit donc être utilisée conjointement avec d'autres méthodes de reconnaissance plus fines.
L'approche peut être ascendante ou descendante suivant la procédure utilisée :
- Une classification des mots constitue une approche purement ascendante. Nous appellerons cette première méthode M1. La classification peut par exemple être basée sur l'utilisation d'une table de correspondance pré-calculée telle qu'une table de longueur moyenne des mots, ou bien elle peut être programmée de façon arborescente suivant une liste d'attributs. Toutefois, cette dernière méthode est envisageable seulement au niveau de la reconnaissance de lettres. Une classification par un réseau neuromimétique constituerait un autre exemple de reconnaissance purement ascendante.
M1 : Classification du mot
- En revanche, le calcul d'une distance, effectué entre tous les mots paramétrés d'un dictionnaire de caractéristiques de mots, conduit à une approche purement descendante. La reconnaissance grâce aux coefficients de Fourier que nous présenterons dans le chapitre II (cf. § 1.2.4.2.) est un exemple typique d'approche descendante de la reconnaissance de mots entiers paramétrés. Cette dernière méthode s'apparente à celle basée sur la modélisation de la forme du mot (cf. § 2.2.2.), à la différence que le codage doit être interprété pour obtenir la représentation visuelle des mots.
2.2.2. Modélisation de la forme du mot indépendamment des lettres
Les méthodes basées sur la modélisation de la forme des mots suivent deux tendances principales concernant le niveau de description utilisé :
- Une description approximative conduit à des méthodes similaires à M1 de réduction du lexique, c'est-à-dire de génération d'hypothèses de mots proches. C'est le cas de [CHERIET 93] qui décrit une méthode de reconnaissance globale basée sur les lettres clefs du mot. Dans ce type de méthode, on exploite des indices visuels globaux sur le mot, le plus souvent tels que les hampes et jambages [LEROUX 91ab] mais aussi les contours haut et bas [PARISSE 92]. Cependant, ce dernier cas sort du domaine de la reconnaissance omniscripteur car la réduction du lexique de 50 000 à 200 mots est basée sur un apprentissage monoscripteur.
- Une description plus précise conduit à des méthodes de matching global du mot indépendamment des lettres (M2), telles que la méthode de [MOREAU 91] basée sur les hampes et jambages, celle de [LECOLINET 93b] ainsi que de l'appariement de graphe structurel de mot (cf. Perspectives Chapitre 4 § 2.3.) dans lequel la description est plus précise. Elles permettent la reconnaissance fine du mot dans le cas d'un petit lexique ou bien dans le cas d'un grand lexique ayant préalablement été réduit. Dans les deux cas, la reconnaissance est tributaire de la liste des mots. Un mot n'y figurant pas ne pourra naturellement pas être reconnu (cas d'un mot nouveau ou non sélectionné dans le grand lexique). Les méthodes de type M2 sont les méthodes de recherche descendante en largeur du mot :
M2 : Matching global du mot indépendamment des lettres :
La méthode M2 est à la fois sensible et tolérante aux variations du tracé et son caractère global assure sa robustesse, ce qui en fait une méthode adaptée à l'écriture de moyenne ou faible qualité. C'est la nature fortement combinatoire de la procédure de matching qui limite ce genre d'approche à un petit lexique.
Le point critique de la méthode est l'utilisation d'un dictionnaire de formes de mots, dans la mesure où plus la description est précise, plus l'apprentissage est délicat. En effet, la précision limitant la représentativité des mots, il y a un compromis entre la généricité (unicité de la forme apprise) et l'adéquation (apprentissage des formes variantes ou spécialisées).
2.2.3. Modélisation de la forme du mot liée aux lettres
Nous avons regroupé dans cette catégorie (M3) les méthodes basées sur les primitives obtenues par l'intersection du mot avec un axe rectiligne [PAQUET 91b] [OLIVIER 93] [TACONET 92], ainsi que la méthode utilisant l'axe curviligne du mot [SIMON 89, 92] [DELEDICQ 93]. De manière analogue à M2, ces méthodes utilisent un dictionnaire de formes de mots, et héritent donc des caractéristiques principales de M2, c'est-à-dire une reconnaissance robuste mais tributaire du mot, avec le problème de l'apprentissage.
La forme des mots est cette fois davantage liée aux lettres, cependant le codage des lettres n'est pas dissociable du mot. La représentation de deux lettres identiques sur des mots distincts est indépendante.
Les mots du dictionnaire sont représentés par une chaîne de description liée à l'axe du mot, par exemple les formes régulières et singulières liées à l'axe curviligne. Un calcul de distance d'édition est effectué entre cette chaîne et la chaîne des primitives qui ont été segmentées sur le mot, en utilisant éventuellement des règles de réécriture.
Contrairement à M2 qui ne possède pas l'objectif intermédiaire de reconnaissance des lettres, cette méthode aboutit à des hypothèses de lettres générées seulement pendant le matching avec le mot (méthode de recomposition en lettres). On dit alors qu'il y a segmentation implicite du mot en lettres (implicite car dépendante et guidée par le mot), cependant il y a segmentation explicite du mot en primitives de niveau inférieur à la lettre (par exemple des points d'ancrage explicites indépendants du mot).
M3 : Matching sur le mot lié aux lettres
2.2.4. Modélisation de la forme des lettres dans le mot
Le critère principal de cette méthode (M4) est l'utilisation d'un lexique dans lequel chaque mot est représenté par des lettres ASCII, comme dans un dictionnaire ordinaire, au lieu d'une base de formes de mots (par convention dans la suite, ASCII désigne les caractères par opposition à leur forme). Chaque lettre possède un codage [LECOLINET 93a] [DELEDICQ 93] ou une modélisation individuel et indépendant des mots. Le principe de la reconnaissance repose sur le calcul d'une distance d'édition entre la description symbolique de la lettre (S.F.D. : Symbolic Features Descriptor [LECOLINET 93a]) et les primitives (V.I. : Visual Indexes) extraites sur chaque lettre du mot à reconnaître.
Cette méthode est également une méthode de segmentation implicite du mot en lettres (les hypothèses de lettres dépendent du mot). La modélisation individuelle de chaque lettre pose le problème de la modélisation des liaisons entre les lettres du mot ainsi que de l'influence du tracé de chaque lettre, ce qui complique l'apprentissage (apprentissage au niveau lettre, apprentissage des n-grammes).
Cette méthode nécessite une optimisation (compression du dictionnaire en un réseau de pétri [VASQUEZ 90]) pour ne pas avoir à reconnaître plusieurs fois les mêmes lettres. Il est en effet superflu de recommencer le matching d'une lettre commune et à la même position dans plusieurs mots distincts, avec les mêmes primitives.
M4 est potentiellement plus adapté à un grand dictionnaire que M3 du fait du codage individuel des lettres.
M4 : Matching des lettres dans le mot ASCII
2.2.5. Modélisation des lettres
Les méthodes de reconnaissance de lettres basées sur la modélisation des lettres (M5) utilisent un matching avec des primitives de bas niveau, de manière analogue aux méthodes de type M4. Par exemple, une distance d'édition est calculée entre les segments de la lettre modélisée dans la base de données et ceux extraits dans l'image de la lettre.
M5 : Matching de la lettre avec les primitives de bas niveau :
La modélisation que nous proposerons dans le chapitre III est une structure d'arcs composés de segments de droites, et organisée en un graphe de liaison pour chaque lettre (M5.2 : Appariement des graphes structurels des lettres).
Le but de la modélisation des lettres est d'exploiter le maximum d'information lorsque les lettres sont bien écrites, en particulier pour reconnaître précisément les lettres discriminantes dans les mots. L'utilisation du matching de lettres s'inscrit dans deux stratégies opposées :
- La première est la reconnaissance des lettres dépendantes du mot, ce qui rejoint la méthode M4 ;
- La seconde est la génération d'hypothèses de lettres indépendantes du mot (cf. § 3. et Chapitre 4).
2.2.6. Segmentation du mot en graphèmes
Nous avons regroupé dans cette catégorie (M6) les méthodes de segmentation explicite du mot (segmentation indépendante d'une hypothèse a priori sur le mot) par des coupures verticales seulement. Les différentes techniques de segmentation en graphèmes que nous avons rencontrées sont basées sur l'analyse du contour (cf. § 2.1.3.).
Les techniques classiques de segmentation du mot [MOREAU 91] [HOLT 92] conduisent naturellement au paramétrage des graphèmes en vue de leur classification (M7 : Classification des graphèmes), qui est une approche ascendante de la reconnaissance. Par exemple, dans le système de Moreau, le paramétrage aboutit à un vecteur de 138 caractéristiques par graphème.
La reconnaissance est ensuite effectuée grâce à un matching de la séquence des graphèmes avec chaque mot d'un dictionnaire, les mots étant codés en graphèmes. Suivant cette approche, il n'y a donc pas d'hypothèses de lettres générées, car les graphèmes assument le rôle des lettres dans le dictionnaire.
L'originalité de l'approche du système que nous proposerons (cf. Chapitre II § 2.) tient à l'utilisation d'un dictionnaire ordinaire de mots codés en lettres. La reconnaissance est alors basée sur un matching des séquences de combinaison de graphèmes avec les lettres de chaque mot (M8). Pour réaliser la correspondance des graphèmes avec les lettres, nous avons utilisé une table de substitution qui prévoit l'ensemble des combinaisons de graphèmes valides avec un coût de substitution en lettres pour chacune.
M8 : Matching des séquences de graphèmes avec les lettres dans le mot
Lorsque le niveau de segmentation conduit à des primitives de plus bas niveau, la segmentation n'est plus seulement verticale, mais également horizontale. L'approximation polygonale du squelette du mot, qui est réalisée dans le système de [LEROUX 91ab], est un exemple de segmentation à un plus bas niveau. Dans cette approche, la détection et la classification des graphèmes nécessitent un matching au niveau de la lettre, ce qui en fait une approche hybride avec M5 (Méthode de matching de la lettre avec les primitives de bas niveau).
Le système de [DELEDICQ 93], qui est basé sur plusieurs niveaux de description coexistants, utilise également un matching de lettres pour aboutir aux graphèmes.
La tendance opposée consistant à la représentation du mot par des graphèmes approximatifs a également été étudiée [LECOLINET 91]. Elle conduit à une approche intermédiaire avec la méthode M4, sauf que dans ce cas, on se limite à la pré-reconnaissance des graphèmes, c'est-à-dire à la génération d'hypothèses de présence seulement des lettres dépendantes des mots du dictionnaire.
Lorsque l'on considère la segmentation du mot à différents niveaux, il en ressort une confusion entre les approches, et il devient délicat de discerner exactement le type de méthode employée. Aussi nous estimons que la segmentation exclusivement accomplie par une coupure verticale du tracé du mot est un critère satisfaisant pour déterminer l'ensemble des méthodes purement basées sur la segmentation explicite du mot en graphèmes.
2.2.7. Schéma récapitulatif des méthodes de reconnaissance
Nous avons récapitulé dans le schéma suivant les catégories de méthodes de reconnaissance que nous avons étudiées. Celles-ci sont organisées en fonction de la proximité de leur principe de matching.
La méthode M9 figurant sur ce schéma est une méthode de reconnaissance ascendante du mot à partir de ses lettres plus ou moins reconnues. Elle sera détaillée dans le chapitre 4.
3. La stratégie de reconnaissance
Après avoir présenté les catégories de méthodes d'exploitation de l'information, nous allons maintenant proposer une analyse des stratégies utilisées pour exploiter ces méthodes dans un système de reconnaissance. Nous avons choisi de présenter les stratégies dans une partie séparée des méthodes car une même stratégie peut exploiter plusieurs méthodes complémentaires ou bien une seule méthode avec une variante ou une tendance vers une autre méthode. Dans un système de reconnaissance, la conséquence est l'existence d'une "procédure spéciale" remettant plus ou moins en cause la stratégie initiale, un flou entoure alors les conditions réelles de fonctionnement de cette procédure.
Les deux objectifs principaux de la stratégie que nous avons retenus sont naturellement la diminution du risque d'erreur d'une façon générale, et l'optimisation, en particulier la réduction du temps de reconnaissance. Les moyens mis en oeuvre pour cela sont essentiellement la réduction du domaine de recherche, l'exploitation et la confrontation des informations complémentaires et également le choix de la méthode appropriée en fonction du contexte.
3.1. Les approches ascendante et descendante
Chaque système comporte une étape initiale minimale d'extraction de l'information. Il s'agit de l'étape d'extraction des primitives (cf. § 1), qui est une phase ascendante de la reconnaissance, la phase descendante étant la procédure de vérification de la concordance de chaque mot avec ces primitives extraites. En considérant que toute extraction de primitives est une forme de segmentation explicite (comme les méthodes de segmentation explicite du mot en lettres), on réduit l'ensemble des systèmes de reconnaissance à une structure comprenant une phase ascendante ainsi qu'une phase descendante. L'approche stratégique résulte alors d'un compromis sur l'importance de chacune de ces deux phases.
Cette approche stratégique dépend essentiellement du niveau de segmentation (segmentation en graphèmes ou segmentation en primitives de bas niveau) ainsi que du niveau de description qui est visé à partir de ces primitives.
Le choix de ces deux niveaux détermine largement la méthode de "matching" (mise en correspondance) qui sera utilisée, et partant, la stratégie permettant d'exploiter cette méthode. En effet, le choix de ces primitives oriente la recherche plutôt en largeur ou plutôt en profondeur.
3.2. Les recherches en largeur et en profondeur
La méthode de reconnaissance analytique basée sur la segmentation en graphèmes comporte une première phase ascendante de classification des graphèmes, puis une phase descendante de vérification de la concordance des graphèmes avec les lettres de chaque mot. Ainsi, le niveau de segmentation fixe la limite supérieure de la phase ascendante, cette limite étant élevée dans ce cas. En effet, pendant la phase descendante de matching avec le mot, seules des primitives de haut niveau (niveau logique) sont utilisées, de sorte que cette approche correspond à une recherche plutôt en profondeur.
- M6 : Segmentation du mot en graphèmes
- M7 : Classification des graphèmes
- M8 : Matching des séquences de graphèmes avec les lettres dans le mot
A l'inverse, une limite supérieure peu élevée du niveau de segmentation conduit à l'utilisation de primitives de bas niveau (P.B.N.). Ce niveau peu élevé de la phase ascendante caractérise une recherche plutôt en largeur. A partir de ces primitives de bas niveau, le niveau de description visé (modélisation au niveau du mot, ou au niveau de la lettre) détermine alors l'importance de l'aspect combinatoire.
- La modélisation au niveau du mot entier conduit à une méthode descendante très combinatoire, et nécessite un dictionnaire de formes de mots :
M2 : Matching global sur le mot, indé-pendamment des lettres
- La modélisation au niveau de la lettre dans le mot conduit à une méthode descendante combinatoire par palier. Elle comporte deux phases descendantes imbriquées, la recherche s'étend donc un peu en profondeur.
M4 : Matching des lettres dans le mot appartenant à un dictionnaire ASCII. L'utilisation d'un dictionnaire de codage de lettres à partir des primitives de bas niveau est le critère déterminant qui distingue cette méthode de la précédente.
3.3. La réduction du vocabulaire
La plupart des stratégies de reconnaissance sont basées sur une recherche en largeur sur un petit lexique de mots (par exemple, le vocabulaire des chèques). Lorsque les spécifications du système de reconnaissance concernent un grand lexique de mots (dictionnaire spécialisé ou général), une étape de sélection d'une liste réduite de mots candidats à la reconnaissance est effectuée au préalable. Cette réduction du vocabulaire se fait principalement par une méthode de reconnaissance globale (M2) utilisant un jeu de primitives de faible niveau de description, c'est-à-dire aboutissant à une description approximative mais très souple du mot. Par exemple, [CHERIET 93] utilise les lettres clefs du mot et [LECOLINET 93a] analyse la forme globale du mot en respectant des contraintes syntaxiques et sémantiques.
Le seul système rencontré dont la reconnaissance est basée directement sur un grand vocabulaire est celui de [DELEDICQ 93]. Il utilise plusieurs niveaux de description en vue de réaliser un apprentissage analytique. La technique choisie, qui semble être la seule envisageable dans le cas d'un grand vocabulaire, est basée sur un dictionnaire de codage des lettres de l'alphabet et un dictionnaire de mots ASCII. L'utilisation de plusieurs niveaux de description conduit nécessairement à plusieurs méthodes de reconnaissance distinctes (segmentation en graphèmes : M6, axe curviligne du mot : M3, dictionnaire de codage des lettres : M5, segmentation en lettres dépendantes du mot ASCII : M4). Ces méthodes et la stratégie n'ont pas encore été fixées et seul l'apprentissage analytique est traité dans l'article.
En fonction du lexique, la réduction du vocabulaire peut aboutir à la reconnaissance lorsqu'un seul mot satisfait aux contraintes syntaxiques et sémantiques parmi l'ensemble des mots sélectionnés. Cependant, dans le cas général, on dispose d'une liste réduite de mots candidats à la reconnaissance à l'issue de cette première étape, une recherche en largeur est alors envisageable suivant des stratégies diverses.
3.4. La stratégie combinatoire
La stratégie combinatoire est une approche typiquement descendante, c'est-à-dire que la segmentation en lettres est guidée par chacun des mots du vocabulaire réduit, donc implicite. L'extraction de primitives de bas niveau (niveau inférieur à celui de la lettre), est la seule étape ascendante de cette stratégie.
Ensuite, nous distinguons les méthodes très combinatoires et combinatoires par paliers suivant le lien entre le codage des lettres et celui du mot.
3.4.1. La méthode très combinatoire
La méthode de reconnaissance basée sur la modélisation de la forme du mot liée aux lettres (M3) constitue une méthode très combinatoire. En effet, l'absence de codage des lettres indépendamment du mot implique un matching global du mot.
Nous citons par exemple les méthodes basées sur l'axe rectiligne du mot [PAQUET 91b] [OLIVIER 93] ainsi que celles basées sur l'axe curviligne [DELEDICQ 93] [SIMON 89, 92].
On remarque la tendance vers la méthode combinatoire par paliers du système de Paquet, qui comporte une recherche de pseudo-lettres dans la phase de substitution, afin de diminuer la complexité du matching du mot.
3.4.2. La méthode combinatoire par paliers
La méthode combinatoire par paliers correspond à la méthode de reconnaissance basée sur la modélisation de la forme des lettres dans le mot (M4). Chaque matching des lettres avec les primitives de bas niveau contribue à limiter la combinatoire sur l'ensemble du mot à des paliers correspondant à la largeur moyenne des lettres.
Le système de [LECOLINET 93a] est un exemple de système mettant en oeuvre la stratégie de la méthode M4. L'intérêt de cette méthode est son ouverture vers des astuces stratégiques permettant d'optimiser le temps de reconnaissance. Ainsi dans ce système, les lettres des mots du dictionnaire sont ordonnées par signification ou visibilité décroissante, ce qui offre une reconnaissance plus efficace et intelligente.
Cependant, la tendance vers une stratégie itérative est adoptée par le système lorsque la description symbolique d'une lettre ne correspond pas avec les indices visuels (cf. 2.2.4.). Une procédure appelée "démon", sans doute car elle va à l'encontre de la stratégie initiale, est chargée de vérifier la présence d'une information qui n'avait pas été observée ou retenue au départ.
L'aspect itératif de cette variante dans la stratégie est dû au fait que l'étape d'extraction de l'information peut être réitérée tant que le mot n'est pas reconnu, avec une recherche différente ou plus poussée. L'intérêt est de commencer par extraire l'information minimale nécessaire à la reconnaissance dans la plupart des cas afin d'éviter des recherches inutiles. La stratégie itérative peut ainsi améliorer l'efficacité de la reconnaissance.
3.5. La stratégie de confrontation
Suivant cette stratégie, les résultats de deux méthodes indépendantes sont confrontés pour fournir la décision finale de la reconnaissance. Le système de [MOREAU 91] est un exemple de mise en oeuvre de cette stratégie, en basant les deux méthodes sur les mêmes primitives, toujours sur le vocabulaire réduit des chèques.
La première est une méthode de reconnaissance analytique basée sur la segmentation explicite du mot en graphèmes (M6, cf. § 2.2.6.).
La seconde est une méthode de reconnaissance globale du mot basée sur les hampes et jambages mais indépendamment des lettres (un dictionnaire de mots codés en graphèmes est probablement utilisé) (cf. § 2.2.2.).
L'indépendance des deux méthodes contribue à la complémentarité des résultats et conforte leur fiabilité. Cette synergie de reconnaissance sera exploitée au niveau de la reconnaissance des lettres dans le chapitre III : grâce à l'utilisation de plusieurs coûts indépendants concourant à la désignation des lettres de l'alphabet, nous montrerons comment réduire sensiblement le nombre d'erreurs de reconnaissance, même si un des coûts est statistiquement plus fiable que les autres. L'intérêt de la stratégie de confrontation réside dans l'adaptation automatique de l'importance de chaque contribution au coût global en fonction des résultats obtenus (cf. Chapitre III § 3.4.).
3.6. La stratégie de coopération
Le système de [LEROUX 91] est un exemple mettant en oeuvre une stratégie de coopération, c'est-à-dire opportuniste, car le choix de la méthode est contrôlé par la qualité de l'écriture grâce à l'utilisation d'un "blackboard". C'est un système expert dans lequel plusieurs modules, organisés dans un "tableau noir", participent à la décision.
Lorsqu’une écriture de bonne qualité a été détectée, le système décide d'entreprendre une reconnaissance analytique basée sur des primitives de bas niveau obtenue par l'approximation polygonale du squelette. Puis, une détection et une classification des graphèmes est effectuée à partir de ces primitives.
Sinon, lorsque la qualité détectée est faible, le système opte pour une reconnaissance globale du mot (M2) avec un codage des mots du dictionnaire par les hampes et jambages.
Ce système, qui fonctionne avec le vocabulaire réduit des chèques, est le seul exemple rencontré réalisant un matching des lettres indépendamment du mot (M5) dans la procédure de reconnaissance analytique, et le seul exemple de stratégie de coopération opportuniste guidée par une structure de contrôle.
Gr. : Graphèmes
P.B.N. : Primitives de Bas Niveau
Prim. Glob. : Primitives Globales
Lors de l'extraction des primitives, l'objectif est de sélectionner l'information pertinente qui se trouvait noyée dans la masse de l'information brute acquise. Il s'agit d'éliminer plus de bruit que d'information signifiante afin d'augmenter la discrimination. Autrement dit, la question qui se pose est comment réduire sans être réducteur ?
Le dilemme qui se présente est alors le suivant : une trop grande approximation entraîne une perte d'information. En effet, certaines lettres étant plus informantes que d'autres, il est nécessaire de conserver une description précise du mot. Or, la complexité du système de reconnaissance augmente avec le niveau descriptif des primitives.
Pour résoudre ce problème de complexité, la segmentation du mot en lettres semble la seule issue qui nous permette d'utiliser des primitives évoluées. Il est inutile de rappeler la difficulté de segmenter les mots du fait de l'interdépendance du tracé des lettres.
D'une façon plus générale, le résultat de chaque extraction de primitives peut être considéré comme une forme particulière de segmentation ou de réduction de l'information. La segmentation implique toujours le risque de fragmentation d'une unité d'information, qu'il s'agisse de la segmentation du mot en lettres ou bien de l'extraction de primitives sur la lettre. D'autre part, la réduction occasionnée par l'approximation constitue une sélection souvent arbitraire de l'information. Dans ces deux cas, il y a donc inévitablement un risque de perte d'information. Notre objectif dans le prochain chapitre va consister à réduire ce risque dans une étude approfondie de la segmentation.
CHAPITRE II. ETUDE DE LA SEGMENTATION
Après avoir établi un bilan des principaux outils et des méthodes dont nous disposions pour la reconnaissance des textes manuscrits, il nous faut en venir à l'obstacle auquel se sont affrontés tous les chercheurs : la segmentation. Segmentation des lignes en mots, segmentation des mots en lettres, la segmentation, cette opération si facilement réalisée par le lecteur qu'elle en est devenue inconsciente, il nous a semblé nécessaire de l'aborder sous un angle différent, celui du mot, des groupes de lettres ou des fragments de lettres plutôt que celui des caractères, avec une autre stratégie faisant appel à l'aide des mathématiques, notamment aux transformées.
Lors de l'étude de la modélisation des mots manuscrits, il est apparu que le résultat de l'extraction de chaque primitive pouvait être considéré comme une forme particulière de segmentation ou de réduction de l'information. Dans ces deux cas, il y a un risque de perte d'information.
L'idée qui est à l'origine de la première partie de ce chapitre, est que ce risque de perte d'information peut être minimisé en remplaçant l'approche locale de la segmentation et de la réduction par une approche globale, ceci grâce à l'utilisation de transformées mathématiques. En effet, les transformations globales comme la transformation de Fourier constituent un changement de représentation réversible (les transformations étudiées sont orthogonales) donc sans perte d'information. Ce changement a pour but la concentration d'une information qui est noyée dans le bruit ou parmi d'autres données redondantes ou non significatives.
L'objectif est de construire, à partir de la segmentation globale et de la réduction globale appliquées à une image transformée, des primitives qui dépendent encore de la totalité des pixels de l'image (primitives globales), afin d'extraire des informations réparties (non localisées) auxquelles l'oeil humain pourrait avoir naturellement accès. Quelle est la nature de ces informations ? Elle dépend de la transformation mathématique que l'on utilise. Nous nous sommes principalement intéressé aux transformées de Hough et de Fourier, car nous avons axé notre recherche sur l'analyse et la segmentation de l'écriture plutôt que sur la reconnaissance ou la classification, objectifs pour lesquels d'autres transformées sont plus appropriées.
Les études s'appliquant à l'extraction de primitives globales de l'écriture manuscrite sont bien moins nombreuses que les études, devenues classiques, relatives aux primitives locales, c'est pourquoi, aujourd'hui où des moyens de calcul importants nous ouvrent de nouvelles perspectives avons-nous voulu, pour répondre à la question sur la nature des informations globales, procèder à une recherche méthodique, théorique puis expérimentale, recherche que nous ferons suivre de quelques applications.
Dans la deuxième partie de ce chapitre, nous mènerons une étude complémentaire de la segmentation - la segmentation par l'extraction de graphèmes - qui constitue une approche plus classique mais aussi qui conduit à des résultats plus pratiques. Nous montrerons que la segmentation en graphèmes nécessite la connaissance de plusieurs informations sur l'écriture, informations qui peuvent être obtenues à partir de l'approche globale de la segmentation étudiée dans la première partie.
1. Segmentation globale de l'image par application de transformées mathématiques
Notre étude portera principalement sur l'apport des transformées de Hough et de Fourier.
1.1. La transformée de Hough (TH)
1.1.1. Le principe d'utilisation
1.1.1.1. Aspects théoriques de la TH
La TH fut à l'origine conçue comme un moyen de détection des lignes droites [HOUGH 62]. Habituellement, on regroupe sous le terme générique TH, des transformations qui permettent de détecter et de localiser dans les images, des courbes paramétriques appartenant à une même famille. Limitons-nous à une famille de droites.
Toute droite (D) du plan (fig. 1) peut être caractérisée par une représentation polaire, de paramètres r et q, de la manière suivante :
un point M(x,y) appartient à D(r, q) si ses coordonnées vérifient la relation [BESANÇON 88] :
x cos(q) + y sin(q) = r (1)
L'intérêt de cette modélisation est de permettre une représentation des droites horizontales et verticales (fig. 2).
Deux types de transformations sont distingués suivant le principe de calcul :
- la transformation "Many to One", ou communément "m à 1", fait correspondre à une droite passant par n points un et un seul point dans l'espace de Hough (fig. 3) ;
- la transformation "One to Many", ou "1 à m", associe à chaque point de l'image la totalité des droites passant par ce point. Dans l'espace transformé, on obtient alors une sinusoïde (fig. 4).
La TH de 1 à m est la plus couramment employée car son coût de calcul est moins important que celui de la TH de m à 1. Ainsi, seule la TH de 1 à m sera considérée par la suite.
On montre que pour les droites D(r,q) la définition de l'angle q entre 0 et avec r prenant des valeurs positives ou négatives est équivalente, tant en coût de calcul qu'en taille mémoire, à une définition de l'angle q entre 0 et 2 avec r ne prenant que des valeurs positives [TIMOUNI 85]. Des deux options, c'est la première qui est choisie afin de faciliter le choix des directions. L'origine du plan de l'image initiale est donc placée au centre de l'image et le secteur angulaire maximal est .
Le traitement des images par ordinateur suppose évidemment que les plans soient discrétisés, aussi bien le plan de l'image que le plan transformé. Tout point M de l'image est caractérisé par ses coordonnées x et y qui sont entières. Les points de l'espace transformé auront pour coordonnées (r,q,n(r,q)), n(r,q) désignant le nombre de points de l'image initiale appartenant à la droite d'équation
x cosq + y sinq = r
La taille de l'accumulateur que nous avons choisi est de 16 directions pour les angles et d'une amplitude des rayons égale à la diagonale de l'image, ceci quel que soit le domaine de variation des directions des droites considérées.
L'algorithme peut être formulé ainsi [MAITRE 85] :
Pour tout point M(x,y) de l'image, incrémenter tout élément de l'accumulateur d'indice (r,q) tel que le point M appartienne à la droite D(r,q).
Sur les quatre boucles imbriquées que comporte cet algorithme (x et y puis r et q), une économie de calcul substantielle est obtenue en déterminant la valeur de r en fonction de q, x et y, plutôt que de tester systématiquement si chaque couple (r,q) vérifie la relation (1).
On peut noter que, comme pour toute courbe représentée dans un espace discret, il est alors nécessaire de rendre connexe le tracé entre chaque point (q, r(q,x,y)) et (q+1, r(q+1,x,y)) de l'accumulateur.
1.1.1.2. Localisation des segments de droite
Le principe de la détection des droites à l'aide de la TH est le suivant :
Deux points M1 et M2 de l'image définissent nécessairement une droite D représentée dans l'accumulateur, car la définition de r et q couvre tout le plan. Pour la détecter, il suffit de retrouver le couple (r,q) pour lequel l'accumulateur vaut deux (fig. 5). Cependant, pour localiser le segment [M1, M2], et d'une façon générale, les deux points extrêmes M1 et M2 sur une droite D détectée passant par n points de l'image, les coordonnées extrêmes (x,y) des points du segment doivent être mémorisées et actualisées au fur et à mesure du calcul de la TH. On utilise pour cela quatre tableaux minx, maxx, miny et maxy indicés par les coordonnées (r,q) :
Si x<minx[r,q] alors minx[r,q]=x et miny[r,q]=y ;
Si x>maxx[r,q] alors maxx[r,q]=x et maxy[r,q]=y ;
Si x=minx[r,q]=maxx[r,q] alors
miny[r,q]=min(miny[r,q],y) et maxx[r,q]=max(maxx[r,q],x).
L'algorithme opérationnel s'écrit alors :
Pour tout point M(x,y) de la forme :
pour q = qmin jusqu'à qmax :
r = x cos(q) + y sin(q) ;
si r >= rmin et r < rmax alors :
Pour tout ri compris entre r et la valeur précédente
de r obtenue pour l'angle q-1 :
incrémenter(acc[ri,q]) et
si le point M(x,y) définit un point extrême du
segment de la droite D(ri,q), alors mémoriser
1.1.1.3. Critères de sélection des droites
La TH ainsi définie permet de détecter les droites ayant au moins un point commun avec l'image. Ces droites sont évidemment en trop grand nombre pour permettre de résoudre un quelconque problème. Aussi allons-nous définir différents critères de sélection de certaines de ces droites.
La valeur de l'accumulateur indique, pour chaque droite D(r,q), le nombre de pixels appartenant, au sens discret, à cette droite. Cette valeur constitue donc un premier critère de sélection des droites. Dans le domaine de l'analyse d'image, ce critère est habituellement utilisé pour la détection de droites grâce à la TH dans des images bruitées.
L'orientation des droites est un second critère de sélection directement utilisable. En effet, à l'issue du calcul de la TH, les droites sont triées par leurs orientations q dans l'accumulateur. En revanche, le tri par le rayon r (distance de la droite au centre de l'image - ou moment de la droite - cf. fig. 1) n'a pas d'intérêt particulier dans le cas des images de mots.
Le troisième critère que nous utiliserons est le type d'intersection du segment avec l'image du mot. Ce critère n'est accessible que par l'examen, pixel par pixel, de chaque segment. Trois types de segments de droite sont ainsi distingués sur les figures 6abc :
1°) type I : Les segments comportant de nombreuses interruptions (fig. 6a) ;
2°) type II : Les segments sans interruption (fig. 6b) ;
3°) type III : Le reste est constitué par des segments reliant deux points quelconques de l'image. Ces derniers segments sont caractérisés par une valeur faible de l'accumulateur (de 2 jusqu'à deux fois l'épaisseur moyenne du trait de l'écriture). Ils ne présentent que peu d'intérêt, sauf par le fait que leur ensemble délimite approximativement l'enveloppe convexe du mot (fig. 6c).
Ces critères seront utilisés afin de sélectionner des droites particulières sur des échantillons. L'analyse de ces droites permettra d'évaluer certains paramètres caractéristiques de l'écriture, tels que l'inclinaison et l'épaisseur moyenne du trait et aussi de détecter et de localiser les hampes et les jambages.
1.1.2. Application à l'analyse de l'écriture manuscrite
1.1.2.1. Détection de l'inclinaison
Deux sortes d'inclinaisons sont distinguées dans les images de mots. La première est l'inclinaison globale du mot par rapport au cadre de l'image, que l'on représente par l'axe moyen du mot. La seconde est l'inclinaison des lettres par rapport à cet axe. Ces deux sortes d'inclinaisons seront examinées successivement.
En limitant l'orientation possible de l'axe des mots à ±45°, nous avons d'abord détecté le segment continu le plus long (segment de type II) compris dans le secteur [45°, 135°] de l'image ; ce segment S0 est représentatif de l'inclinaison des lettres du mot ; il correspond à une hampe ou à un jambage, ou bien à un tronçon voisin de la verticale dans une lettre médiane (lettre sans hampe ni jambage). Pour le mot "word" de taille 128x48 pixels (fig. 7), nous avons ainsi obtenu un angle de 49° avec un segment de 46 pixels, et 79° sur 26 pixels pour le mot "rotation" de taille 94x46 pixels (fig. 8) ; soit q0 la mesure de cet angle.
Dans un second temps, sans recalculer la TH, on examine à nouveau les segments de droite compris entre -45° et +45° détectés dans l'accumulateur.
A chaque segment S, on affecte une mesure qui tient compte de trois grandeurs :
- la longueur,
- le nombre d'intersections avec les tronçons verticaux des lettres de l'image,
- l'angle formé par S0 et le segment S.
On cherche simultanément à maximiser la longueur du segment et le nombre d'intersections, en privilégiant la direction perpendiculaire à q0.
Enfin, pour les segments ayant une mesure supérieure aux trois quarts du maximum, la moyenne des directions nous donne l'inclinaison moyenne de l'axe du mot.
On obtient ainsi une direction presque horizontale pour le mot "word" et un angle de 12° pour le mot "rotation".
L'inclinaison des lettres, obtenue pour le mot "word", présente un biais visible sur le tracé de la lettre 'd' (fig.7). En effet, la direction du segment est de 49° tandis que la lettre 'd' est inclinée à 57°. Cependant, ce biais n'est pas plus important que l'irrégularité de l'inclinaison des segments composant les lettres "wor".
Les trois autres mesures sont satisfaisantes. L'axe du mot "word" obtenu par le calcul présente un angle de 2° au lieu de 0°. Pour le mot "rotation", l'inclinaison des lettres, obtenue par le calcul, est 79°, ce qui correspond au 78° mesuré ; l'angle de son axe calculé est 12°, ce qui est exact.
On peut maintenant effectuer une rotation de l'image de manière à faciliter tout autre traitement dans le but de la reconnaissance.
La mesure de l'inclinaison peut être étendue à la détection de l'orientation, non plus des mots, mais d'une série de lignes de texte. Pour cela, à l'aide de la TH, on détecte les droites d'inclinaison comprise entre ±30° sur des images (fig. 9a et 9b) représentant des échantillons de faibles résolutions (taille=100x100 pixels)
Les droites les plus fréquentes sont obtenues pour q=0° (fig. 9a) et pour q=4° et 8° (fig. 9b)
Deux critères ont été utilisés pour la sélection de chaque droite : le nombre élevé de pixels supportés par la droite (valeur de l'accumulateur) ainsi que le nombre peu élevé de pixels du fond (pixels blancs) [DARGENTON 90]. On remarque sur les figures 9a et 9b, que ces deux critères n'évitent pas totalement la présence de segments obliques reliant plusieurs lignes de texte différentes. Cependant, ceux-ci sont moins nombreux que les autres segments.
Une dilatation horizontale aurait pour effet de relier les mots d'une même ligne (méthode RSLA) [LIKFORMAN 93] ; le critère plus fiable des segments sans interruptions pourrait alors être utilisé.
1.1.2.2. Détection de l'épaisseur moyenne du trait
L'épaisseur moyenne du trait est un paramètre important car il permet d'obtenir une valeur de référence pour détecter un trait significatif. On peut dire que toute méthode, pour être fiable, doit reposer sur une détection automatique de ce paramètre, ou alors la reconnaissance est liée à l'instrument d'écriture utilisé [QUEGUINER 90].
L'épaisseur moyenne du trait est obtenue par l'examen des droites déjà détectées au paragraphe précédent (§ II.1.1.2.1.). Chaque intersection des segments de droite de tout type, I II ou III, avec le mot, définit des petits segments sans interruptions. L'histogramme des longueurs de ces segments montre l'existence d'un mode (cf. fig. 10), c'est-à-dire de la longueur des traits la plus fréquente, qui correspond à l'épaisseur moyenne du trait.
Cette mesure effectuée sur le mot "word" nous donne une épaisseur de 7 pixels (fig. 10), et une épaisseur de 3 pixels pour le mot "rotation".
Quand les mots sont écrits horizontalement, les résultats sont identiques à ceux obtenus en construisant l'histogramme des longueurs des segments, lorsque l'on effectue cette fois un simple balayage des lignes et des colonnes, sans utiliser la TH.
1.1.3. Segmentation
1.1.3.1. Détection du corps des mots
Dans cette étape, l'axe des mots ayant été ramené à l'horizontale, la première idée est de remplacer l'histogramme classique par celui du nombre des droites détectées parmi 16 directions comprises entre 45° et 135°, qui coupent chaque ligne horizontale. Cette disposition a pour effet de renforcer la partie de l'histogramme qui correspond aux lettres médianes. On sélectionne pour cela les segments ne comportant aucune interruption et de longueur supérieure à l'épaisseur du trait. Celle-ci a été estimée dans le paragraphe précédent.
La figure 11 permet de comparer les deux histogrammes et de voir que grâce à cette amélioration, les méthodes classiques basées sur l'histogramme ont maintenant davantage de chance de s'appliquer avec succès.
Figure 11a : Histogramme
des intersections de droites
Figure 11b :
Néanmoins, nous proposons aussi une autre méthode basée sur le principe de la Gestalt-théorie [GUBERMAN 91].
On note Ds l'ensemble des droites, détectées entre -10° et +10°, ayant au moins s points communs avec l'image du mot ; on considère alors le graphe qui associe à chaque valeur de s les lignes minimum et maximum atteintes par Ds. Le graphe indique aussi pour chaque ligne de l'image, jusqu'à quel seuil on peut trouver une droite horizontale dans la transformée.
On peut observer sur ce graphe (figure 12a) de brusques ruptures de pente correspondant à la zone des lettres médianes dans laquelle les droites horizontales présentent un maximum de points.
On construit alors une fonction qui, à chaque ligne, associe une valeur qui tient compte
- de la pente du graphe précédent,
- de la valeur du seuil maximum possible,
- du nombre d'alternances fond-forme.
Ce graphe, après lissage (figure 12b), présente un ou plusieurs pics. Un pic indique la zone médiane d'un mot sans hampe ni jambage, alors que deux pics indiquent les bords inférieur et supérieur de la zone médiane d'un mot avec hampe ou jambage.
1.1.3.2. Localisation des hampes et jambages
En poursuivant la démarche vers la segmentation des mots en lettres, nous nous sommes également intéressé à la localisation horizontale des hampes et jambages dans le mot.
Sur chaque colonne de l'image, on recherche l'existence de segments d'orientation comprise entre 45° et 135° et de longueur supérieure à la zone médiane du mot que nous avons déjà évaluée précédemment. Il suffit de classer ces segments en fonction de la position de leur extrémité par rapport à cette zone pour obtenir une mesure discrète de probabilité de présence d'une hampe ou jambage sur toute la longueur du mot. On code chacun des segments de la zone des hampes par 1, de la zone des jambages par 2, de la zone des hampes et jambages par 3 (pour la lettre 'f'), et par 0 tout autre segment. Par exemple, cela donne pour le mot trente le codage suivant :
01110000000011100
Cette mesure floue a l'avantage d'être plus souple pour la classification des lettres, qu'une méthode n'effectuant qu'une simple décision binaire sur chaque lettre qu'elle a pu discerner.
1.1.4 Bilan et discussion
La TH met en évidence les alignements des points les plus nombreux en fonction de chaque direction échantillonnée. Cette transformée est donc particulièrement indiquée pour détecter des orientations privilégiées de l'écriture. Celles-ci sont alors représentées par des segments que l'on peut localiser sur l'image. Cependant, le travail effectué dans ce sens montre que la sélection des segments obtenus nécessite une confrontation avec l'image, la seule sélection sur la fréquence et l'orientation étant insuffisante.
La TH a ainsi permis d'évaluer une éventuelle inclinaison des lettres ou une rotation du mot, même si le critère employé ne correspond pas toujours exactement à l'inclinaison que l'on cherche à mesurer (cas de l'inclinaison des lettres du mot "word" au paragraphe 1.1.2.1.).
La TH permet la construction d'histogrammes élaborés à partir de primitives globales de l'image : ceux-ci remplacent avantageusement les histogrammes classiques qui ne sont que de simples projections de lignes indépendantes les unes des autres. En outre, la TH permet une caractérisation globale du mot qui peut être discriminante dans le cas par exemple d'un faible vocabulaire (voir la localisation des hampes et jambages dans le paragraphe 1.1.3.2.)
La TH est encore relativement peu utilisée dans le domaine de la reconnaissance de mots manuscrits. On peut citer toutefois [OLIVIER 93] pour la détermination de l'axe médian des mots par la TH ainsi que [LECOLINET 93a] dont l'application est intéressante : elle consiste à schématiser complètement le tracé des lettres d'un mot à l'aide de segments de droites détectés par la TH.
Notre seconde étude concernera la transformée de Fourier.
1.2. La transformée de Fourier (TF)
La transformée de Fourier est fréquemment utilisée en traitement d'image lorsque l'on désire effectuer un filtrage un peu délicat qui ne pourrait être réalisé dans le domaine spatial à l'aide d'une simple convolution par un masque.
Le filtrage du spectre Fourier fait apparaître des informations
qui n'étaient pas visibles auparavant
Nous allons étudier, sans nous préoccuper outre mesure du temps nécessaire à l'exécution des opérations, son application à l'écriture manuscrite, essentiellement dans le but d'en extraire les éléments contribuant à réaliser la segmentation des mots en lettres.
L'intérêt de la TF est de mettre en évidence les phénomènes réguliers qui se répètent périodiquement dans une image. Chaque région définie du spectre de Fourier correspond à une période précise et contient une information concentrant une contribution de chaque point de l'image. Cette faculté sera appliquée à l'analyse et à la segmentation harmonique de l'écriture manuscrite. Nous rapporterons également une étude sur la reconnaissance harmonique des lettres et des mots entiers, qui est liée à notre recherche.
1.2.1. Aspects théoriques de la TF
1.2.1.1. TF d'un signal réel
Considérons un signal monodimensionnel de type temporel. La TF de ce signal est définie de la façon suivante :
Les signaux traités dans cette étude sont codés sur leurs parties réelles seulement, leurs parties imaginaires étant fixées à zéro.
Le module , appelé spectre d'amplitude, est une fonction paire. Le spectre de phase VX(f) = arg(X(f)), qui est une fonction impaire, sensible aux translations, ne sera pas pris en considération et nous nous limiterons donc à l'étude de |X(f)| pour les seules fréquences positives.
Dans la pratique, on ne peut observer le signal pendant un temps infini ; or, la limitation de la durée d'observation du signal (appelée fenêtre temporelle) entraîne la convolution de la TF du signal par le spectre fréquentiel de la fenêtre [MIQUEL 85], ce qui trouble l'observation (figure 1).
Examinons maintenant dans quelles conditions la discrétisation occulte ce défaut.
1.2.1.2. TF discrète (TFD) et TF rapide (TFR)
Soit Te la cadence à laquelle on prélève N échantillons pendant la durée T d'un signal x ; en introduisant les simplifications de notation suivantes :
x(k) = x(kTe/T) ;
X(n) = X(n/T*fe) ;
WN = exp(2ip/N) avec N pair
la Transformation de Fourier Discrète (TFD) est définie [NEIRYNCK 84] par :
et la transformation inverse par :
où x est le vecteur du signal discret monodimensionnel et X sa TFD.
Lorsque N est une puissance de 2, le calcul de la TFD peut être accéléré par la mise en facteur de termes, ce qui réduit le nombre de multiplications : cette procédure optimisée est appelée la Transformée de Fourier Rapide (TFR).
Ce calcul implique un échantillonnage du spectre, correspondant à celui du signal, de sorte que ce spectre sera observé seulement en certains points discrets : c'est l'effet de "barrière" [MIQUEL 85]. Si le nombre de périodes du signal étudié est entier, l'échantillonnage du spectre occultera exactement les valeurs parasites du spectre de la fenêtre comme le montre la figure 2.
La figure 3 [MIQUEL 85] illustre tous les problèmes d'échantillonnage ainsi que les phénomènes de périodicité qui en résultent. Le quatrième schéma montre comment un décalage des valeurs de la TF permet de replacer les fréquences symétriquement par rapport à 0, dans la réponse périodique, les fréquences négatives sont placées alors avant les fréquences positives. Par exemple, lorsque N=8, le recentrage des fréquences permet de visualiser le spectre de la façon suivante :
Fréquences obtenues : Fréquences visualisées :
0 1 2 3 4 5 6 7 4 5 6 7 0 1 2 3
| f 2f 3f 4f 5f 6f 7f -4f -3f -2f -f | f 2f 3f
-> continu fe/2 -> continu
fe est la largeur de bande du spectre et f est la fréquence d'échantillonnage du spectre
N=8 Te=T/8 fe=1/Te=8f
La fonction résultat est paire donc la TF est symétrique par rapport au continu (f=0), sauf en ce qui concerne la fréquence la plus élevée (-4f), du fait de la taille du spectre (N est une puissance de 2, N-1 est donc impair) :
la Transformée de Fourier Rapide d'une sinusoïde d'amplitude maximale 1 étudiée sur l'intervalle [0,2], définie à partir de x(t)=sin(t) et pour une valeur de N égale à 8 est représentée par 2 pics d'amplitude ½ aux fréquences f=1 et f=-1 ; x(k)=sin(2k/8) est de période 8 et la transformée est entièrement définie par les valeurs prises entre 0 et 7.
Sur le même intervalle, une sinusoïde de pulsation 2, de période , x(t) = sin(2t) ou x(k)=sin(k/2) a une TFR représentée par 2 pics d'amplitude ½ aux fréquences f=2 et f=-2.
x(t)=sin(3t), considérée comme x(k)=sin(6k/8), de pulsation 3, a une TFR représentée par 2 pics d'amplitude ½ aux fréquences f=3 et f=-3.
Tandis que la sinusoïde x(t)=sin(4t) considérée comme x(k)=sin(k) a une TFR représentée par un seul pic d'amplitude 1 à la fréquence f=4 (on peut remarquer que les valeurs en -4 et +4 sont réunies).
1.2.1.3. TF bidimensionnelle (TF2D)
Une image peut être interprétée comme un signal bidimensionnel, une application g, de deux variables réelles. La Transformée de Fourier bidimensionnelle continue de l'image g est définie de la façon suivante, en remplaçant la dimension t du temps par les deux dimensions x et y du plan :
où fx et fy sont les fréquences spatiales associées respectivement aux deux dimensions spatiales x et y.
Au niveau du calcul pratique, nous avons utilisé l'algorithme classique de [COOLEY 85] qui interprète la TF2D discrète comme la composée de deux transformées monodimensionnelles (TF1D = TFR). Le calcul des transformées des signaux constitués par chaque ligne de l'image permet de constituer un résultat intermédiaire, dont la transformée de chaque colonne donne le moyen d'obtenir le résultat de la TF2D.
Pour un signal x
X = TF2D(x) =
où x et X sont respectivement les matrices originale et transformée de l'image.
Par la suite, le terme TF désignera la TF2D discrète d'une image numérique g. Il est à remarquer que g(x,y) est un entier indiquant le niveau de gris du pixel représenté à la colonne x et à la ligne y de l'image. Néanmoins, des contraintes d'optimisation liées au calcul de la TF nous ont amené à coder ce nombre sur quatre octets (nombre à virgule flottante plutôt que nombre entier). Cette grandeur étant aussi utilisée pendant et après le calcul pour mémoriser le spectre.
Afin de visualiser la TF avec les fréquences recentrées de telle sorte que la composante continue se situe au centre du spectre, on multiplie chaque terme de l'image g(x,y) par -1(x+y), plutôt que d'effectuer une permutation des fréquences négatives sur les lignes et les colonnes.
1.2.1.4. Propriétés de la TF
La TF est une transformation linéaire orthogonale qui conserve l'énergie et l'entropie. Toute l'information de l'image est contenue dans sa transformée, c'est une transformation réversible.
A tout produit dans le domaine spatial correspond un produit de convolution dans le domaine fréquentiel, et réciproquement.
Le spectre d'amplitude est invariant par translation (celle-ci ne modifie que le spectre de phase). En dehors de la zone des hautes fréquences du spectre, la TF est relativement insensible au bruit car chaque point de l'image transformée contient une contribution de chaque point de l'image originale.
En revanche, la Transformée de Fourier est sensible à une rotation : la TF d'une onde plane sinusoïdale de période T et de direction normale parallèle à l'axe des x est représentée par deux pics alignés suivant la même direction fx, aux fréquences f=1/T et f=-1/T (figure 4a) ; la rotation d'un angle q de la normale au plan d'onde s'accompagne d'une rotation de même angle du spectre (fig. 4b).
On peut consulter [NEIRYNCK 84] pour retrouver l'ensemble des propriétés de la TF1D d'un signal temporel continu, avec les démonstrations correspondantes.
La définition et les propriétés de la TF étant précisées, étudions maintenant le spectre de Fourier de différents échantillons d'écriture afin de comprendre le changement de représentation de l'information qui est réalisé.
1.2.2. Analyse spectrale de l'écriture
1.2.2.1. Propriétés spectrales de l'écriture - Spectroscopie optique et numérique
La spectroscopie optique consiste à analyser les figures lumineuses obtenues au moyen de la diffraction optique ou d'un réseau de fibres optiques. Ces figures de diffraction sont équivalentes aux spectres 2D continus de Fourier [KABRISKY 70].
La spectroscopie optique est utilisée dans le domaine de l'expertise en écriture [GRUHIER 76] afin "d'extraire, de façon scientifique et objective, le caractère impondérable et original qui se retrouve dans toutes les productions écrites d'un même individu". Les applications paléographiques ou judiciaires consistent en l'authentification de l'auteur au moyen du calcul de corrélation entre plusieurs manuscrits. Le succès de cette méthode est dû à la propriété remarquable du spectre de Fourier : "quels que soient le nombre et la position des lettres dans une page, on obtiendra toujours une figure lumineuse dont la partie centrale (les basses fréquences) représente les graisses, l'allure générale des lettres, tandis que les hautes fréquences de la périphérie correspondent aux détails fins, contours, discontinuités, fioritures".
La corrélation permet de comparer une lettre moyenne type et la lettre correspondante figurant plusieurs fois dans un texte, elle présente un pic d'une intensité lumineuse proportionnelle à leur ressemblance. Si on dispose d'une classe de lettres moyennes pour chaque style et époque, on peut alors dater un texte. De la même façon, l'évolution de l'écriture chez un même scripteur au cours des ans peut être mesurée.
Au-delà de la mesure de corrélation, la spectroscopie optique permet d'évaluer un certain nombre de paramètres de l'écriture [CHARRAULT 77] tels que :
- l'espacement entre les lignes manuscrites et leur direction,
- l'inclinaison moyenne des lettres,
- le coefficient de régularité de l'écriture,
- la longueur moyenne des mots,
- la cohérence du graphisme, qui permettrait de déterminer un éventuel changement de scripteur sur l'échantillon observé (la cohérence est d'autant plus élevée que la dispersion des pics fréquentiels autour d'une direction donnée est faible).
L'utilisation du spectre de Fourier est également suggérée [ELLIMAN 90] dans le domaine de la segmentation de documents, afin de distinguer les textes dactylographiés, les textes imprimés, les diagrammes, les photographies ainsi que les photographies tramées.
L'idée que nous avons exploitée est que si la TF permettait en quelque sorte de caractériser un style d'écriture par extraction d'informations précises ou d'effectuer une segmentation globale d'un document par analyse de texture, elle est susceptible aussi d’apporter des solutions dans le cadre de la segmentation d'un mot en lettres. En effet, de manière très sommaire, les mots peuvent être considérés comme des successions de traits de directions globalement parallèles et reliés par des traits de direction perpendiculaire. Par un effet d'accumulation, ces traits doivent apporter des contributions importantes en certains points de l'image transformée.
Nous allons maintenant présenter la méthodologie employée dans le cadre de l'analyse spectrale d'échantillons d'écriture sur des images numériques.
Les images numérisées au scanner sont de type binaire. On peut cependant obtenir un codage sur plusieurs niveaux en effectuant un moyennage afin de réduire la taille des images. Par exemple, une taille de 64x32 pixels sur 5 niveaux (0, 1, 2, 3 et 4) est obtenue à partir d'une image binaire de taille originale 128x64 pixels grâce à un moyennage suivant x et y.
L'opération de filtrage comporte alors trois étapes :
- le calcul de la TF de l'image originale ;
- le filtrage du spectre par sélection de fréquences ;
- le calcul de la TF inverse pour obtenir l'image filtrée.
Procédons à l'analyse méthodique des fréquences du spectre afin d'identifier le rôle de chacune, de manière à corroborer ce qui est obtenu en spectroscopie optique.
1.2.2.2. Analyse de la répartition fréquentielle
La figure 5a montre le mot "word" sur lequel quatre filtrages différents ont été étudiés. Le mot est représenté en perspective sur la figure 5b. La surface représentée est celle d'équation z = g(x,y). L'image transformée est exposée sur la figure 5c.
Différents filtres ont été choisis sur les figures 6, 7, 8 et 9. Le filtre est donné dans le plan de Fourier sur les figures 6c, 7c, 8c et 9c.
Sur les figures 6a, 7a, 8a et 9a apparaissent les images résultant de la binarisation des quatre images filtrées représentées respectivement sur les figures 6b, 7b, 8b et 9b.
Figure 8b Figure 8c
Colonne a : Image binarisée vue à plat
Colonne b : Image vue en perspective
Colonne c : Spectre de Fourier
Figure 5 : mot "word" original en 128x32 pixels ; figure 6 : filtrage passe-bas 6-2 <=>
fx=-6, ... ,+6 et fy=-2, ... , +2 ; figure 7 : filtrage passe-bas 12-4 ; figure 8 : filtrage
passe-bas 24-8 ; figure 9 : filtrage passe-haut 32-12 ;
Ces figures illustrent la répartition fréquentielle de l'image du mot en quatre zones :
- les très basses fréquences (fig. 6c) donnent la forme globale du mot, c'est-à-dire son enveloppe (fig. 6a) ;
- en conservant jusqu'aux basses fréquences (fig. 7c), on obtient une indication sur l'épaisseur du trait (fig. 7a) ;
- en conservant jusqu'aux moyennes fréquences (fig. 8c), on obtient essentiellement l'information typographique concernant la structure et l'enchaînement des lettres (fig. 8a) ;
- les hautes fréquences (fig. 9c) sont impliquées dans toutes les variations brusques de 0 à 1, ou de 1 à 0, correspondant au contour des lettres (fig. 9a).
L'exploitation de la TF implique le choix d'un filtre adapté spécifiquement à l'information que l'on veut extraire de l'image ; ensuite, un second choix concerne le seuil de binarisation de l'image filtrée : il détermine la distinction entre l'objet et le fond et exerce une incidence très importante sur les résultats.
Le choix des quatre zones du domaine fréquentiel (très basses - basses - moyennes - hautes fréquences) présente un caractère arbitraire. Cela est dû, comme nous allons le montrer grâce à l'analyse des résultats, au fait que les limites entre ces quatre zones ne sont pas définies avec précision, car elles dépendent des images étudiées.
1.2.2.3. Analyse d'une raie caractéristique du spectre (détection des lignes d'écriture et de leur inclinaison)
L'échantillon analysé, un texte composé de plusieurs lignes d'écriture régulièrement espacées, est discrétisé avec une faible résolution. L'image (fig. 10a à gauche), de taille 64x64 pixels sur 5 niveaux, a été obtenue par le moyennage d'une image binaire originale de 256x256 pixels.
La transformée de Fourier fait apparaître deux pics d'amplitude importante, qui sont symétriques par rapport au continu situé au centre du spectre. Ces deux pics constituent la raie spectrale caractéristique de la direction moyenne des lignes d'écriture. En effet, en isolant ces deux pics par le filtrage de tous les autres pics d'amplitude inférieure, on obtient un spectre simplifié (fig. 10b) dont l'image par la TF inverse est constituée d'une onde sinusoïdale que nous avons pu superposer, sur la figure 10c, aux lignes d'écriture.
La fréquence spatiale de la raie caractéristique se situe en un point M (fx=2, fy=12). Cette raie définit, avec l'origine, une direction qui forme un angle de 9 degrés avec la verticale (arctan(12/2) = 80.5°, 90°-80.5° = 9.5°), ce qui correspond effectivement à la direction moyenne de l'écriture, suivant une période horizontale de 64 / 2 = 32 pixels (fx=2) et une période verticale de 64 / 12 = 5,33, soit 5 à 6 pixels (fy=12).
Lorsque la régularité des lignes d'écriture diminue, la notion de direction moyenne perd alors de son sens, et par conséquent, la raie caractéristique s'étale en se dispersant dans le spectre. Une étude des images obtenues par partition de l'image initiale permet de définir des fenêtres sur lesquelles une direction privilégiée apparaît nettement.
La TF permet donc de mettre en évidence la régularité des lignes d'écriture en précisant, lorsqu'elle est effective, leur direction et leur périodicité moyenne.
1.2.2.4. Analyse de l'axe d'inertie du spectre
Les figures 11 et 12 montrent la TF de deux échantillons d'alphabets. Le premier est en italique, tandis que le second ne contient que des segments verticaux et horizontaux. La propriété du spectre de Fourier que nous voulons illustrer par cet exemple est la mise en évidence de l'inclinaison moyenne de l'écriture. Par la suite, nous exploiterons cette propriété sur des mots cursifs.
Dans le premier alphabet, l'inclinaison globale des lettres par rapport à la verticale se traduit par la répartition des pics fréquentiels le long d'un axe présentant la même inclinaison, mais par rapport à l'horizontale (cf. § II.1.2.1.4.).
Cette inclinaison peut être mesurée sur le spectre par le calcul statistique de l'axe d'inertie des pics fréquentiels. Après l'élimination de l'image transformée des pics de trop faible amplitude, on recherche, par un critère des moindres carrés, la droite qui minimise la dispersion perpendiculaire à l'axe d'inertie.
Sur la figure 11, l'axe d'inertie spectral détecté est incliné de 25 degrés par rapport à l'horizontale, ce qui correspond effectivement à l'inclinaison moyenne des lettres par rapport à la verticale.
Sur la figure suivante (fig. 12), l'axe d'inertie du spectre est horizontal car les lettres sont verticales. On observe certains alignements de pics le long de la direction verticale, ce qui correspond à la succession des traits horizontaux composant les lettres de cet alphabet.
Poursuivons maintenant notre étude, cette fois sur des mots quelconques.
En analysant la TF d'images de mots, on cherche de la même façon à mesurer l'inclinaison des lettres par rapport à la verticale : l'axe d'inertie spectrale du mot "word" (fig. 13) fait avec l'horizontale un angle de 25°, ce qui correspond à une moyenne d'inclinaison des lettres entre 20° (lettre 'r') et 33° (lettre 'd'). Pour le mot "rotation" (fig. 14), l'axe d'inertie mesuré fait un angle de 6° par rapport à l'horizontale : il correspond au tracé régulier des lettres, compte tenu de l'inclinaison globale de l'axe du mot par rapport à l'horizontale. Cette inclinaison peut également être mesurée. Elle est représentée par l'axe secondaire d'inertie du spectre. Pour le mot "word", il y a effectivement une disposition de pics importants suivant l'axe vertical des fréquences (fig. 13b) ; en revanche, l'axe d'orientation du mot "rotation" par rapport à l'horizontale ne peut être mesuré avec précision. Les pics impliqués sont trop rapprochés du centre du spectre pour définir une direction moyenne précise du nuage dans l'espace discrétisé.
Cette étude nous donne donc un moyen de calculer des paramètres liés à l'écriture, au niveau d'un mot ou d'une ligne.
De plus, grâce à cette analyse du spectre de Fourier, nous sommes maintenant en mesure de choisir les critères fréquentiels afin de procéder à la segmentation harmonique des mots manuscrits.
1.2.3. Segmentation harmonique des mots manuscrits
Le filtrage présenté sur la figure 10 constituait un exemple de segmentation harmonique des lignes manuscrites. Notre objectif est maintenant d'analyser la segmentation harmonique des mots manuscrits, et l'intérêt qu'elle peut présenter pour l'extraction de primitives globales dans l'étape du prétraitement de l'écriture. Dans le souci de procéder méthodiquement, nous étudierons des filtrages d'une complexité progressive en commençant par la segmentation harmonique 1D (monodimensionnelle).
1.2.3.1. Segmentation harmonique 1D
1.2.3.1.1. Segmentation verticale (suivant fy) du spectre
Dans le plan des fréquences nous considérons une seule droite, celle d'équation fx=0. En se limitant à cette droite on effectue un filtrage passe-bas, suivant l'axe des fréquences (on ne retient que les deux premières fréquences). La TF inverse génère une surface cylindrique dont les sections sont des courbes planes sinusoïdales. La normale au plan d'onde est parallèle à Oy. La ligne de crête de cette surface englobe la zone médiane du mot, tandis que les lignes de vallée passent par les zones des hampes et jambages. Le seuillage, à la moitié de l'amplitude maximum de cette fonction, coïncide avec la zone des lettres médianes des mots "word" et "eight" sur les figures 15a et 15b.
1.2.3.1.2. Segmentation horizontale (suivant fx) du spectre
La segmentation horizontale part du même principe que la segmentation verticale, mais la normale au plan d'onde obtenu en traitant les fréquences horizontales du spectre (fy=0) est parallèle à Ox.
Suivant les fréquences sélectionnées dans le spectre, la fonction sinus se superpose aux lettres 'u' et 'n' successivement (basse fréquence fig. 16), ou bien elle se superpose aux quatre segments verticaux composant les lettres 'u' et 'n' (fréquence deux fois plus élevée fig. 17).
Ainsi, notre attention est concentrée sur les fréquences du spectre comprises entre la plus basse fréquence qui nous intéresse dans le mot, c'est-à-dire celle dont la période correspond à la lettre la plus large de l'alphabet - soit le "m"-, et la fréquence la plus élevée, c'est-à-dire celle dont la période correspond à la lettre la plus étroite de l'alphabet - soit le "i".
En conservant simultanément l'ensemble de ces fréquences de l'axe horizontal du spectre, on crée un filtre passe-bande dont la TF inverse est logiquement constituée d'une somme de sinusoïdes d'amplitudes variables suivant le mot analysé. On constate alors que les sommets de cette fonction coïncident avec les lettres du mot "mille" (fig. 18), tandis que les vallées correspondent aux jonctions entre ces lettres.
On remarque que le choix d'un seuil de binarisation unique de la fonction sur toute la longueur du mot ne permet pas d'isoler toutes les lettres du mot "mille". Pour cela, un seuil variable serait nécessaire pour distinguer la lettre 'e' du 'l', mais un seuil trop élevé entraînerait la fragmentation de la lettre 'm'.
Les oscillations de la fonction résultant du filtrage évoquent un certain phénomène de résonance qui coïncide avec les lettres, en établissant une hiérarchie des points de segmentation prioritaires : la segmentation entre le 'i' et le 'l' semble la plus évidente. Elle coïncide avec le milieu du mot et l'amplitude de la fonction en ce point est aussi profonde qu'au début et à la fin du mot, tandis que les autres points de segmentation sont moins marqués, par exemple entre le 'm' et le 'i'.
Les filtres 1D ne sont cependant pas adaptés à tous les cas, en particulier au cas des lettres inclinées, car ils ne permettent qu'une segmentation des lettres à l'aide de droites. Nous allons donc étudier le cas de la segmentation harmonique 2D.
1.2.3.2. Segmentation harmonique 2D
En conservant deux lignes de fréquences de part et d'autre de l'axe horizontal du spectre, on réalise une combinaison du filtre horizontal et du filtre vertical (cf. § 1.2.3.1.). Le filtrage passe-bande ainsi déterminé (les très basses fréquences ne sont pas utilisées car elles correspondent à l'enveloppe du mot, cf. § 1.2.2.2.), fait apparaître des vallées qui semblent contourner chaque lettre du mot grâce à un effet de lissage. La détection d'une vallée est obtenue (en gris fig. 19e) si on a un minimum à l'intérieur d'un masque 3x3 dans l'une des quatre directions privilégiées de l'espace discrétisé ; en outre, un minimum local correspondra à un minimum dans les quatre directions (points noirs aux croisements des vallées fig. 19e).
Figure 19c Figure 19d
On constate que ce critère de segmentation n'est pas valable pour les lettres 'u' et 'q' du mot "quarante" qui sont traversées chacune par une vallée. En ce qui concerne la lettre 'u', cela est normal si l'on souhaite également obtenir la segmentation par exemple d'une lettre 'i' avec ce même critère.
Pour déterminer si la segmentation des mots en lettres peut être réalisée à l'aide d'un filtre prédéfini, il est nécessaire d'en connaître les caractéristiques précises. Pour cela, on a segmenté manuellement les lettres d'un mot en supprimant les pixels reliant les lettres (cf. fig. 20c) ; puis, utilisant la linéarité de la transformée de Fourier, on a calculé la TF de la différence entre le mot et ce même mot segmenté (cf. fig. 20). Le spectre obtenu (fig. 20e), dont l'amplitude maximum est très faible (50 fois plus faible que celle du spectre du mot), montre que les fréquences impliquées dans la segmentation ne sont pas localisées dans un point précis du spectre, mais diffuses dans l'ensemble du spectre. Il en résulte que le simple filtrage rectangulaire du type passe-bas que nous avons expérimenté n'est pas suffisant pour assurer la segmentation des mots en lettres.
Figure 20a Figure 20b
Figure 20d Figure 20e
En revanche, si l'on considère maintenant un niveau de segmentation plus fin que la lettre, un résultat intéressant est obtenu à l'aide d'un filtre en croix (fig. 21d). Il est défini par l'ensemble des fréquences (fx, fy) telles que fx est quelconque et fy Î [-1, 1] ou fy est quelconque et fx Î [-1, 1].
En faisant varier le seuil de binarisation de l'image filtrée, le mot "trois" (fig. 21e) est progressivement divisé en petits segments horizontaux et verticaux qui sont des approximations linéaires des lettres plus ou moins rondes à l'origine. Les lettres 'i' et 't' étant rectilignes, elles restent bien formées lorsque le seuil est élevé.
Figure 21a Figure 21b
Figure 21c Figure 21d
Si la plage de fréquences retenue est plus grande par exemple en utilisant un filtre PB 32/8 (c'est-à-dire un filtre Passe-Bas tel que fx Î [-32, 32] et fy Î [-8, 8]), on obtient une représentation du mot par des segments obliques (fig. 22b). La figure 22a, qui représente une variation du seuil de binarisation autour de la valeur zéro, montre un plissement harmonique qui reproduit l'aspect du contour, tandis que la figure 22b montre l'effet de la variation du seuil autour d'une valeur plus élevée.
Pour récapituler, on constate que la segmentation harmonique des mots est assez sensible à la plage de fréquences du filtre :
- un filtre ajusté vers les trop basses fréquences entraîne une sous-segmentation du mot, tandis que
- un filtre ajusté vers les trop hautes fréquences entraîne une sur-segmentation.
Avant de formuler notre avis sur la segmentation harmonique, nous allons étudier la reconnaissance des lettres et des mots par la TF, car les résultats caractéristiques obtenus y sont liés.
1.2.4. Reconnaissance harmonique
1.2.4.1. Reconnaissance des caractères
Le principe de la reconnaissance par la TF est simple. Il s'agit de comparer le spectre d'une lettre à reconnaître avec l'ensemble des spectres des lettres apprises constituant la base de référence. La lettre dont la distance spectrale est la plus faible est reconnue et la méthode permet en outre d'établir la liste des lettres les plus proches en cas d'ambiguïté.
Une des premières études sur cette technique de base [KABRISKY 70], montre qu'une reconstruction reconnaissable de la plupart des caractères peut être obtenue en retenant seulement la portion des basses fréquences du spectre avant d'inverser la transformation. Donc, l'essentiel de l'information utile à la reconnaissance est véhiculé par les basses fréquences. On peut se rendre compte de ce fait par l'allure de l'image de la lettre 'H' résultant de quatre filtres passe-bas différents sur les figures 23cdef (c : filtre PB 2/2, d : PB 3/3, e : PB 4/4, f : PB 8/8).
Le spectre du 'H' (fig. 23b) est très différent de celui du 'o' (fig. 24b). En revanche les spectres des lettres 'o', 'a' et 'e' sont proches d'aspect. La barre verticale du 'a' a toutefois une incidence sur l'axe horizontal de son spectre, tandis que la barre horizontale du 'e' a une incidence sur l'axe vertical de son spectre.
La transformée de Walsh-Hadamard peut être rapprochée de la transformée de Fourier en ce sens qu'elle est une transformée orthogonale relativement à une autre base de fonctions. Elle a plusieurs fois été étudiée dans le cadre de la reconnaissance des formes [CRETTEZ 78]. Le travail le plus approfondi, la thèse de Mure-Ravaud remonte à 1976 [MURE-RAVAUD 76] ; il a été complété par un article de 1978 [MURE-RAVAUD 78].
Dans la transformée de Walsh-Hadamard le système de fonctions orthogonales n'est plus sinus et cosinus ; il est remplacé par un autre système de fonctions ; la matrice associée à la transformation est une matrice carrée d'ordre N (N=2n) contenant des éléments prenant des valeurs +1 ou -1. La transformation ne fait intervenir que des nombres réels. Elle est linéaire et orthogonale et conserve l'entropie et l'énergie. Il existe, comme pour la transformée de Fourier, un algorithme rapide, simple à réaliser.
Mure-Ravaud applique la transformée de Walsh-Hadamard à la reconnaissance des chiffres manuscrits et les résultats qu'elle obtient peuvent être transposés dans cette partie de notre étude. Ces résultats montrent que la transformée agit comme un processeur sélecteur de caractéristiques sur les caractères. En effet, le changement de représentation entraîne une concentration de l'information utile à la reconnaissance dans une région réduite de l'image transformée. La conséquence est la diminution de la corrélation des données représentant le caractère, et donc l'amélioration de la discrimination entre les classes pour un nombre donné de composantes.
Cependant, dans l'étude de Mure-Ravaud, les chiffres testés ne sont décrits que par des matrices 8x8 et 16x16. Une comparaison de la distance directe entre les pixels et de la distance entre les coefficients de la transformée fait apparaître que l'intérêt du changement de représentation ne semble être qu'un palliatif à la translation des caractères dans leur matrice ! D'autre part, la réduction effective du nombre de caractéristiques est exploitée seulement dans un but de rapidité car elle diminue le taux de reconnaissance qui est de 96% en 8x8 et de 98% en 16x16.
Une étude sérieuse sur la reconnaissance des mots entiers par la TF [O'HAIR 91], qui rend compte d'un travail de plus de vingt années de recherche, apporte certaines informations importantes sur l'utilisation de la TF en reconnaissance de texte.
O'Hair rappelle que, dès 1968, on conclut que 100% des lettres majuscules manuscrites étaient reconnaissables grâce aux basses fréquences de l'espace de Fourier, sous réserve seulement que les lettres soient isolées et lisibles pour un humain.
A l'origine de cette étude, les auteurs estimaient que le problème de la segmentation pouvait se résoudre en filtrant la TF du mot à l'aide de la partie des basses fréquences de la TF des lettres de l'alphabet. L'idée a été abandonnée, faute d'obtenir la précision exacte souhaitée sur les résultats. On a préféré s'attacher à la reconnaissance du mot entier, en appliquant cette méthode jugée plus proche du comportement humain de la lecture (excepté avec des mots non familiers). Dans le paragraphe suivant nous résumons les principaux résultats de cette étude [O'HAIR 91] qui mettent en relief l'intérêt de la TF pour la reconnaissance.
1.2.4.2. Reconnaissance harmonique des mots manuscrits
Chaque coefficient de la TF est considéré comme un composant d'un vecteur représentant le mot relativement à une base orthogonale. Chaque mot est un point de l'espace de dimension N qui est le nombre de coefficients utilisés.
Par exemple, les 5x5 premières fréquences donnent avec la composante continue 121 coefficients (N=11x11) ; les 4x2 (horiz. x vert.) premières fréquences donnent 45 coefficients (N=5x9).
La reconnaissance consiste à localiser le plus proche voisin du point dans l'espace à l'aide d'une distance. Deux distances ont été étudiées. La distance de Manhattan est parfois meilleure que la distance euclidienne.
Le premier travail a consisté à réduire le nombre de fontes typiques (25) afin d'obtenir une base minimale de reconnaissance en groupant par style les fontes proches. La division des styles de fonte est basée sur la différence entre les lettres 'a' et 'g'. Le nombre optimum de groupes est obtenu en calculant le taux de reconnaissance d'un corpus de 1000 mots pour chaque division de la base de fontes.
- Pour l'ensemble des 25 fontes, il y a 25000 distances à calculer (1000x25) et le taux de reconnaissance obtenu est de 80,6%.
- Pour 1 groupe (1 seule fonte qui est la moyenne des 25 fontes), il y a 1000 distances à calculer, et le taux de reconnaissance obtenu est de 86,8% ;
L'optimum est de 6 groupes de fontes avec un taux de reconnaissance de 98,2%. Ce résultat montre qu'il est important de bien choisir la base des fontes moyennes, c'est-à-dire avec un fort degré d'orthogonalité.
Les résultats significatifs de cette étude sont les suivants :
- Pour obtenir plus de 95% de reconnaissance correcte, on utilise n'importe quelle combinaison des cinq plus basses fréquences suivant l'axe horizontal et l'axe vertical, soit 36 coefficients [012345]x[012345] ; en doublant le nombre de coefficients de 55 à 121 on passe de 99,5% à 99,6% de reconnaissance, soit 20% d'erreurs en moins, ce qui est une amélioration relativement faible pour le calcul supplémentaire qu'elle représente. Cela confirme donc l'importance des basses fréquences.
- Les hautes fréquences caractérisent surtout le style de fonte.
- Les harmoniques horizontales sont plus importantes que les verticales : une reconnaissance de type 4x2 avec 45 coefficients produit 40% d'erreurs en moins que de type 3x3 avec 49 coefficients.
- L'importance de chaque coefficient est basée sur l'importance de sa variance et non sur l'importance de son énergie (amplitude du pic fréquentiel). Ainsi, dans les basses fréquences du spectre, les coefficients de basse et haute énergie ont la même importance.
- L'étude de la variation de l'espacement des lettres dans le mot montre qu'il n'influe pas sur la reconnaissance.
- Le taux de reconnaissance ne diminue que relativement peu lorsque le nombre de mots augmente (avec 4x2 coefficients) : avec 1000 mots il est de 99,4% ; avec 2000 il passe à 99,1% ; avec 5000 il n'est plus que de 98,6%.
Chaque point de l'espace de Fourier, qui représente un mot, est le centre de gravité d'un nuage d'une variance n-dimensionnelle autour de ce centre de gravité. Un degré de confiance, utilisé pour le rejet d'erreurs, est attribué au mot en fonction de cette variance pour chaque "matching". Un mot qui n'appartient pas au vocabulaire est associé au point le plus proche, mais avec une distance correspondante élevée. Dans ce cas, le mot peut être retraité d'une autre façon. D'autre part la direction et la distance à l'ancien centre de gravité, pour le cas de l'apprentissage d'un nouveau style de fonte, sont les mêmes pour tous les mots écrits suivant ce nouveau style de fonte.
En conclusion, l'algorithme est capable de reconnaître un large vocabulaire de mots (le vocabulaire le plus large testé est constitué des 5000 mots anglais les plus communs) sans avoir à segmenter les caractères individuels et en utilisant une distance ordinaire.
Les très larges variations de formes rencontrées dans une librairie de fontes typiques peuvent être gérées en construisant des groupes avec les caractéristiques moyennes de chaque fonte.
L'apprentissage automatique assure une bonne autonomie de l'algorithme.
La méthode est invariante en taille et substantiellement insensible au bruit. Elle convient à des fontes de style imprimé ou cursif.
L'espace de reconnaissance est énorme comparé au volume de groupes d'images de mots. Le vocabulaire usuel pourrait actuellement supporter tous les mots possibles de n'importe quel langage.
1.2.4.3. Conclusion sur la reconnaissance par la TF
La caractéristique la plus remarquable de la reconnaissance à l'aide de la TF, qu'il s'agisse des mots ou des lettres, est la simplicité de son principe. En effet, celui-ci est basé sur un calcul classique d'une distance entre les coefficients de l'espace de Fourier. Le nombre des coefficients utilisés détermine la précision que l'on souhaite ; en effet, la qualité de souplesse en reconnaissance est obtenue avec les coefficients de basse fréquence qui sont peu sensibles aux détails (lesquels sont liés aux hautes fréquences). En contrepartie la méthode convient mal à la discrimination de ces détails ; on note par exemple la difficulté à départager des mots proches entre eux. Les tests effectués donnent des résultats remarquables pour les mots imprimés, y compris ceux écrits avec une police cursive, lesquels correspondent à la qualité optimale des mots manuscrits.
On en conclut que l'utilisation de la TF pour la reconnaissance de l'écriture manuscrite de qualité quelconque ne peut être exploitée que dans le but de générer des hypothèses de mots proches, assurant ainsi le filtrage d'un grand vocabulaire, en n'utilisant pour cela qu’une faible précision de reconnaissance. Cependant, plus l'écriture sera régulière, meilleur sera le classement du mot correct dans la liste sélectionnée, ce qui constitue un avantage certain, car une écriture appliquée et régulière facilite la reconnaissance humaine de l'écriture.
Dans cette première partie, nous avons défini les bases de notre recherche concernant l'extraction de primitives globales. Nous avons développé des techniques nouvelles d'examen des droites détectées à l'aide de la TH, pour analyser et segmenter l'écriture manuscrite. Une méthode originale de segmentation globale par la TF a également été conçue.
Nous allons maintenant préciser plusieurs points remarquables mis en évidence dans notre étude.
Nous avons cherché à extraire des primitives globales sur l'écriture manuscrite en détectant des informations dans un espace transformé alors qu'elles n'auraient pu être perçues dans l'image directe, comme semble être capable de le faire tout lecteur humain. En effet, l'accumulation d'indices sur toute l'image permet de concentrer l'information pour la mettre en évidence. Nous avons tenté de mettre à profit cette propriété, qui est habituellement utilisée en Reconnaissance des Formes dans des images bruitées (cf. Sinus 2D § 1.2.), pour faire ressortir des informations globales sur un texte manuscrit.
Un des aspects de la reconnaissance de l'écriture, mis en évidence, est la perception fréquentielle. Il en est de même dans le domaine temporel où la perception d'une mélodie musicale consiste non pas à interpréter la forme d'onde du signal sonore, mais effectivement les rapports de fréquences entre les notes successives (ces rapports sont toujours définis avec exactitude et jamais quelconques). Dans le domaine spatial, cet aspect a été illustré par l'étude de la répartition des lignes ainsi que par l'inclinaison des lettres dans un texte : l'évaluation de la périodicité et l'étude de la distribution de ces deux paramètres ne peuvent être réalisées de façon pratique que par une étude globale du spectre. Elle fournit une mesure de régularité de l'écriture (la dispersion des pics trahit l'irrégularité), laquelle est exploitée naturellement par tout lecteur au premier coup d'oeil. Une mauvaise qualité de l'écriture entraîne une attitude plus attentive et plus prudente du lecteur. Or, les paramètres conditionnant le fonctionnement des systèmes de reconnaissance (les divers seuils et marges relatifs à l'écriture) sont la plupart du temps supposés connus à l'avance et fixes, comme nous le verrons dans la deuxième partie de ce chapitre.
Un autre aspect de la reconnaissance est la perception dans le plan polaire. Des alignements de pixels ont été mis en évidence par une accumulation d'indices sur toute l'image. Ces alignements ont été exploités pour le paramétrage des traits, des lettres, du corps des mots ainsi que des lignes de texte.
En ce qui concerne la segmentation des mots en lettres, l'extraction de primitives globales n'a pas permis d'obtenir des résultats satisfaisants. En particulier, nous n'avons pas pu obtenir une segmentation correcte évitant la sur-segmentation ou la sous-segmentation des mots. Ce constat nous amène à étudier la segmentation du mot manuscrit en graphèmes. Dans cette seconde partie, nous aborderons la segmentation grâce à une méthode de recomposition des lettres qui respecte la contrainte de cohérence globale des hypothèses de segmentation relativement aux mots d'un lexique. Nous montrerons alors que la segmentation en graphèmes nécessite la connaissance de plusieurs informations sur l'écriture qui ont été obtenues dans cette première partie, c'est-à-dire :
- la localisation des lignes de texte (TH & TF) ;
- l'inclinaison du mot (TH) ;
- la localisation des hampes et jambages dans le mot (TH & TF) ;
- l'inclinaison des lettres dans le mot (TF) ;
- l'épaisseur du trait de l'écriture (TH).
2. Segmentation par extraction de graphèmes
Le problème de la fragmentation de l'information n'a pu être évité avec la segmentation globale (cf. § 1.). Dans cette seconde partie, nous allons tenter de le résoudre en utilisant le principe de la génération et de la vérification des hypothèses de segmentation grâce à l'extraction des graphèmes. Cette opération ne comporte pas d'étape d'approximation, elle n'entraîne donc pas une réduction de l'information.
Nous avons développé une méthode originale de segmentation basée sur l'extraction des composantes connexes (cf. Chapitre I § 1.3.1.). Nous avons également conçu une méthode de reconnaissance qui n'utilise pas un dictionnaire de forme de mots codés en graphèmes. Au lieu de cela, nous utiliserons un lexique ordinaire de mots en toutes lettres ainsi qu'une table de substitutions des combinaisons de graphèmes en lettres.
Notre démarche dans cette seconde partie consiste à étudier le principe de la recombinaison et l'intérêt qu'elle présente pour dépasser l'obstacle de la segmentation. Ainsi, une base de mots réduite sera suffisante pour mettre bien en évidence les caractéristiques de l'approche ascendante au niveau des graphèmes.
2.1. Segmentation du mot
2.1.1. Détermination de la zone médiane du mot
Dans les méthodes comportant une segmentation explicite du mot en lettres (méthodes de reconnaissance analytique), la première étape est généralement la détermination de la zone médiane du mot, c'est-à-dire, par convention dans la suite du texte, la zone qui permet de distinguer les lettres à hampes ou à jambages, de celles qui en sont dépourvues. La méthode la plus simple utilisée est basée sur l'analyse de l'histogramme horizontal de l'image.
2.1.1.1. Analyse de l'histogramme horizontal
L'histogramme permet de mettre aisément en évidence la zone médiane du mot car la contribution des minuscules sans hampe ni jambage y est déterminante. C'est une fonction h :
h : [1, n] ® N+
i ® h(i)
où l'indice i représente l'indice des lignes et n le nombre de lignes de l'image.
On recherche dans un premier temps une ligne de l'image appartenant à la zone médiane, quelle que soit la combinaison des lettres constituant le mot. Pour cela, on suppose que la hauteur attendue de la zone médiane soit comprise aux alentours d'une valeur hM fixée à l'avance, car il n'est pas envisagé ici de reconnaître des mots de taille quelconque. On calcule, pour hM/4 < i <= n - hM/4, la somme S(i) suivante :
On opère ainsi un important lissage. L'indice i correspondant à la ligne où la somme S(i) est maximum, est noté M : dans la plupart des cas, cette ligne d'indice i se trouve à l'intérieur de la zone médiane du mot, même si elle est parfois plus près d'un bord de la zone que de l'autre.
Dans un deuxième temps, on recherche dans la partie supérieure à la ligne d'indice M ainsi que dans la partie inférieure, les indices des minimums de l'histogramme respectivement mh et mb. Dans le cas idéal, ces deux minimums délimitent la zone médiane. Mais, en pratique, l'histogramme est souvent étalé et dessine une lente décroissance autour de la zone médiane. On recherche donc plutôt les maximums de la dérivée de la fonction h afin d'obtenir l'indice pour lequel la variation est la plus importante. La dérivée étant très sensible aux petites fluctuations, on procède auparavant à un lissage simple de l'histogramme, c'est-à-dire ne faisant intervenir que trois lignes consécutives, ce qui définit une fonction hl.
La ligne de séparation entre les hampes et la zone médiane est obtenue au maximum de la dérivée de la fonction hl compris entre mh et M, tandis que la ligne de séparation entre la zone médiane et les jambages est obtenue au maximum de la valeur absolue de la dérivée de hl compris entre M et mb.
La figure 1 illustre la détection de ces paramètres sur le mot "trois".
Lorsque la zone médiane du mot est obtenue, les lettres à hampe ou à jambage sont distinguées des lettres médianes quand elles dépassent les limites de la zone médiane d'une grandeur supérieure à une marge fixée.
Le bon fonctionnement de cette procédure est naturellement tributaire de la direction de l'axe du mot : lorsque celle-ci est oblique, la zone principale de l'histogramme horizontal s'étale, la zone médiane devient ainsi plus difficile à localiser. Et même lorsque la zone médiane est assez bien localisée, les hampes et jambages ne peuvent être détectés que si leur taille est suffisante, c'est-à-dire s'ils présentent un dépassement supérieur à la somme du produit de la longueur du mot par le sinus de l'angle entre l'horizontale et l'axe du mot, et de la marge fixe. En même temps, les lettres sans hampe ni jambage au début et à la fin du mot risquent de dépasser la zone médiane (cf. figure 2).
Lorsque l'axe du mot est très oblique, deux solutions sont envisageables. La première, et la plus simple, consiste à effectuer une rotation inverse de celle détectée (cf. § 1.). La seconde est également intéressante mais plus laborieuse à mettre en oeuvre. Elle consiste à appliquer l'ensemble de la procédure de détection en tenant compte de l'inclinaison mesurée, ce qui suppose, entre autres, le calcul d'histogrammes directionnels.
Les essais effectués dans ce sens montrent que la reconnaissance des mots bien horizontaux présente suffisamment de difficultés pour considérer le redressement des mots obliques comme un problème supplémentaire à part entière.
Cette procédure de détection de la zone médiane du mot donne des résultats satisfaisants (cf. § 2.3. Reconnaissance des mots) lorsque la hauteur moyenne des lettres minuscules est connue a priori ; or il est courant de rencontrer des variations de ce paramètre du simple au double sur les échantillons d'un même scripteur, ce qui provoque inévitablement le problème de la sur-détection des hampes et jambages sur des mots n'en comportant pas, ou sinon de la sous-détection des hampes et jambages lorsque la hauteur supposée de la zone médiane est surévaluée. Il est donc nécessaire d'évaluer cette hauteur pour chaque mot, sans pour autant exclure une exploitation des diverses invariances globales sur le tracé des mots dans un texte en suivant l'évolution continue des paramètres. D'autre part, la marge de distinction des hampes et des jambages est également un paramètre qui doit être connu a priori : plus l'écriture est régulière et les hampes et jambages courts, plus la marge doit être faible, et plus l'écriture est irrégulière et les hampes et jambages longs, plus la marge doit être importante. Afin que cette procédure soit indépendante de la taille des lettres, nous allons extraire les informations dont nous avons besoin à partir de l'analyse des graphèmes. En effet, la segmentation du mot en graphèmes ne nécessite pas forcément la détermination de la zone médiane (cf. Chapitre I § 1.4.1.).
2.1.1.2. Analyse des graphèmes
Dans cette étape on cherche à estimer, à partir de l'analyse de connexité, la hauteur moyenne des lettres médianes ainsi que celle des hampes et des jambages. La segmentation des mots en graphèmes, bien que réalisée en partie, sera affinée par la connaissance de la position de la zone médiane du mot (cf. § 2.1.2.2 Traitement des graphèmes).
La détection des connexités permet de filtrer les connexités isolées qui modifient l'histogramme horizontal, telles que les points, les accents ainsi que les divers bruits de l'image.
On procède alors à l'estimation de la largeur moyenne de chaque graphème. Celle-ci fournit une longueur de référence relativement invariante que l'on utilise pour déterminer la hauteur minimale de la zone médiane du mot.
L'histogramme des hauteurs des graphèmes, après un important lissage, présente un maximum local représentant la hauteur de la zone médiane du mot, c'est-à-dire la hauteur la plus fréquente. Ce maximum est clairement distinct du second maximum représentant les hampes et jambages réunis, réunis car seule la hauteur relative des graphèmes est prise en compte (cf. figure 3b).
Le minimum de l'histogramme lissé se trouvant entre les deux maximums correspond au juste milieu pour distinguer les hampes et les jambages des lettres médianes, aussi l'utilise-t-on pour fixer la marge employée au paragraphe précédent.
Si le mot ne comporte ni hampes ni jambages, l'histogramme lissé ne présente qu'un seul maximum, la marge est ainsi définie en fonction de la position du maximum de l'histogramme par rapport à la hauteur maximum des graphèmes de l'image. S'il y a égalité, la marge est alors une fraction de la hauteur des graphèmes (cf. fig. 4ab).
Enfin, l'estimation de l'épaisseur moyenne du trait, qui est un paramètre invariant de l'écriture, est obtenue par le calcul de l'histogramme des longueurs des segments de droites horizontaux et verticaux mesurés sur toute l'image (cf. fig. 3c, 4c, 5c). Ce paramètre sert dans l'étape de traitement des graphèmes (cf. § 2.1.2.2) comme longueur de référence pour ajuster la valeur des différents seuils.
Des essais ont été entrepris pour détecter les deux lignes délimitant la zone médiane du mot à l'aide de la répartition des graphèmes, afin d'en déduire l'orientation de l'axe du mot qui est alors celle de leur bissectrice.
Cette méthode est similaire à celle employée par [BERCU 93] pour l'écriture on-line. Elle est basée sur l'estimation linéaire (au sens des moindres carrés) des points milieux des bords supérieurs et inférieurs de chaque graphème médian (cf. figure 3a, 4a, 5a). Elle s'est avérée insuffisamment stable pour détecter l'orientation des mots pris isolément. Nous estimons que l'orientation globale des lignes doit d'abord être détectée. On peut ensuite rechercher les faibles variations de l'orientation des mots autour de la direction des lignes.
La détermination de la hauteur de la zone médiane du mot à l'aide de l'analyse de connexité des graphèmes n'est que peu affectée par l'orientation du mot et par l'inclinaison des lettres. De plus, la méthode est insensible à l'irrégularité de la disposition des lettres par rapport à l'axe du mot, ainsi qu'à la présence de nombreuses hampes dans le mot (cf. fig. 5abc) ce qui n'est pas le cas de l'analyse de l'histogramme horizontal. En revanche, cette dernière reste nécessaire pour déterminer d'une façon robuste la zone médiane du mot, une fois que la hauteur moyenne des lettres médianes ainsi qu'une marge bien adaptée sont connues.
2.1.2. Segmentation du mot
Grâce à la connaissance de la zone médiane du mot, chaque graphème est identifié à une classe générique parmi cinq. Un traitement est ensuite appliqué sur ces graphèmes de façon à reformer certaines lettres sursegmentées lors de la capture de connexités (cf. Chapitre 1. § 1.4.1.).
2.1.2.1. Préclassification des graphèmes
Les cinq classes génériques sont notées 'H', 'J', 'f', 'M', et '?' respectivement Hampes, Jambages, hampes et jambages, graphèmes Médians et graphèmes ambigus.
Une hampe est détectée si l'ordonnée supérieure du graphème est située dans la zone supérieure à la zone médiane du mot à une distance supérieure à la marge (Position absolue).
Un jambage est détecté si l'ordonnée inférieure du graphème est située dans la zone inférieure à la zone médiane du mot à une distance supérieure à la marge (Position absolue).
Le graphème est classé Médian si sa hauteur est inférieure à celle de la zone médiane du mot (hauteur relative), à condition toutefois que le graphème ne dépasse pas les zones définies par les marges (Position absolue).
Sinon, si le graphème ne vérifie aucune de ces conditions, il est classé ambigu.
Enfin, si le graphème est classé 'M' ou bien '?' et est de largeur et de surface faibles, il est reclassé en 'i', ce qui est un affinement de la classe médiane. On remarque que la classe médiane tolère une irrégularité de l'écriture, car seule la hauteur relative des graphèmes est prise en compte entre les deux marges.
2.1.2.2. Traitement des graphèmes
Dans cette étape sont reformées les lettres, telles que 't' et 's', comportant dans leur contour supérieur un minimum local qui ne correspond manifestement pas à une liaison naturelle entre deux lettres. Il ne s'agit donc pas ici de reformer les lettres 'u' ou 'y'.
En fonction de plusieurs critères présentés ci-dessous, les fragments, qui sont de petits graphèmes, sont ressoudés aux graphèmes auxquels ils se rattachent le plus probablement. Chaque pixel constituant le graphème est initialement étiqueté par un code (cf. Chapitre 1 : § 1.4.1 Extraction des composantes connexes). La soudure consiste à remplacer le code de connexité du fragment par le code du graphème auquel il doit être soudé.
Les critères utilisés, qui dépendent à la fois du fragment et du graphème receveur, sont :
- la classe générique du graphème,
- la largeur du fragment,
- le milieu horizontal du graphème,
- la distance horizontale entre le milieu du fragment et le graphème,
- le dépassement du bord droit du fragment relatif au bord droit du graphème,
- l'aire du fragment,
- la position de l'ordonnée minimale du fragment relatif à la zone médiane du mot,
- le nombre de pixels mitoyens consécutifs entre le fragment et le graphème,
- le nombre de jonctions distinctes entre le fragment et le graphème,
- le côté de la jonction (fragment à droite ou à gauche du graphème),
- la solidarité du fragment (connexe ou isolé du graphème dans le cas du point, de l'accent, de la barre de 't' ou du bruit),
- le recouvrement horizontal du fragment relatif au graphème (inclusion, disjonction ou chevauchement).
Les traitements sont effectués dans l'ordre suivant :
- soudure des barres des lettres 't',
- soudure des fragments inscrits dans le rectangle englobant d'un graphème,
- soudure des fragments mitoyens sur une grande portion verticale ou bien connectés en plusieurs endroits à un graphème,
- soudure ou élimination des fragments de faible surface,
- soudure des graphèmes se recouvrant horizontalement.
2.1.2.3. Exemples de segmentation de mots en graphèmes
Les exemples suivants, sur les figures 6abcde comprenant également la détection des boucles et des concavités (cf. § 2.2.), illustrent le résultat de la segmentation de quelques mots en graphèmes.
Les principales opérations effectuées au cours de l'étape du traitement des graphèmes y sont récapitulées :
- soudure des barres de 't' : mot 'treize' fig. 6e ;
- soudure des fragments inscrits : lettre 'x' de 'dix' fig. 6a ;
- soudure des fragments mitoyens : lettres 'x' de 'dix' fig. 6a et de 'deux' fig. 6c ainsi que les deux lettres 'e' de 'treize' fig. 6e ;
- soudure des fragments connectés en plusieurs endroits : lettre 'a' de 'quatre' fig. 6d ; lettre 'd' de 'deux' fig. 6c ;
- soudure des fragments de faibles surfaces : lettre 'x' de 'dix' fig. 6a ; lettre 'e' de 'quatre' fig. 6d.
Pour les mots "dix" et "trois", les résultats sont à comparer avec ceux obtenus dans la première partie du chapitre I (§ 1.4.1. Extraction des composantes connexes).
Les résultats observés sur une centaine d'échantillons ont permis de relever un certain nombre d'erreurs fréquentes telles que la sursegmentation systématique des lettres 'a' et 'o' lorsque la boucle n'est pas fermée, ainsi que l'apparition fréquente d'une queue en fin de mot lorsque le tracé de la dernière lettre a tendance à se relever.
Le problème de la sous-segmentation est également apparu lorsque deux lettres ne présentaient pas de minimum local permettant de les séparer, par exemple les lettres 'oi' du mot 'trois' de la figure 6b ; cependant la détection des boucles (cf. § 2.2.1.) a permis de résoudre une partie de ces problèmes, on en voit le résultat sur la figure.
D'autres cas similaires de sous-segmentation ont été observés notamment sur les lettres 'fr' et 'tr'.
D'autre part, un certain nombre de lettres sont normalement sursegmentées. Leur recombinaison est systématiquement envisagée pour reformer les lettres potentielles d'un mot du lexique (cf. § 2.3.). Ce sont les cas des lettres 'd' du mot 'dix' fig. 6a, 'u' de 'deux' fig. 6c et 'quatre' fig. 6d ainsi que de la lettre 'q' de 'quatre' fig. 6d.
Les lettres collées telles que 'll' ou 'tt' ont été traitées de la même façon par une coupure verticale effectuée à partir du minimum local du contour supérieur ; seule une segmentation avec la connaissance a priori de la lettre pourrait permettre une meilleure séparation, mais dans ce cas cela ne serait que dans un but de vérification.
On remarque que même un faible minimum local sur le contour supérieur de la lettre génère une segmentation (lettre 'r' de 'quatre' fig. 6d). Cette sensibilité indique que les échantillons numérisés doivent être de bonne qualité ; en particulier, l'image doit contenir si possible des lettres incluses dans une seule composante connexe. Les taches, trous et divers bruits d'échantillonnage peuvent donc perturber la segmentation. D'autre part, si la résolution augmente, le nombre de minimums locaux indésirables augmente, à moins de procéder à un lissage du contour.
Nous montrerons dans la partie 2.2.2. (constitution de l'alphabet) quels types d'erreurs de segmentation peuvent facilement être corrigés, en fonction de la combinaison des graphèmes détectés, mais auparavant, nous allons affiner la description des classes génériques de graphèmes en les précisant à l'aide de la détection des boucles.
2.2. Classification des graphèmes
2.2.1. Détection des boucles
Lorsque les boucles sont présentes dans les lettres du mot, leur détection améliore la reconnaissance du mot ; si elles sont absentes, par exemple dans le cas des hampes sans boucles, ou non perceptibles (cas fréquent des lettres 'e'), les lettres restent ambiguës mais cela ne pénalise pas la reconnaissance.
La détection des boucles consiste ainsi à affiner la description des classes génériques en classes plus précises afin de profiter d'une caractéristique facilement détectée. Elle est simplement réalisée grâce à une procédure de remplissage du fond à partir du cadre extérieur du mot, de sorte que toute surface qui n'a pu être remplie est une boucle.
2.2.1.1. Remplissage
Le cadre extérieur englobant le mot est entièrement rempli à l'aide de l'algorithme de propagation de pixels indiqué plus bas :
On dispose d'une pile dans laquelle on peut mémoriser les coordonnées d'un nombre suffisant de pixels. Un premier pixel vide (de valeur nulle) est choisi, par exemple au coin en haut à gauche, pour initialiser le remplissage : il est placé en première position dans la pile.
Pour chaque pixel vide empilé :
on lui attribue une valeur non nulle (remplissage)
et chaque pixel à proximité, au sens de la 4-connexité, est empilé
seulement s'il est vide et compris dans les limites du cadre
Afin de réduire la taille nécessaire de la pile, on utilise une pile circulaire de sorte que l'emplacement mémoire des premiers pixels sera utilisé de nouveau pour empiler d'autres pixels. La procédure s'arrête lorsque l'indice courant devient égal à l'indice du dernier pixel empilé. Mais si c'est l'indice du dernier pixel empilé qui rattrape en premier lieu l'indice courant, cela signifie que la pile est saturée et qu'une taille plus grande doit être prévue au départ.
Les surfaces de l'image non remplies à l'issue de la procédure sont des boucles ou, plus rarement, des espaces fermés par deux lettres segmentées au niveau d'un minimum local du contour supérieur (par exemple, dans le cas des lettres 'fr' ou 'tr' ).
Seules les boucles de surface suffisante sont retenues.
2.2.1.2. Détermination de la classe des graphèmes
En fonction de la présence d'une boucle dans la zone des hampes, dans celle des jambages ou bien encore de la présence d'une ou plusieurs boucles dans la zone médiane du mot, on affine la classe générique parmi l'ensemble 'HJMfi' en une classe plus précise parmi l'ensemble 'bklogjq' (la classe 'f' est indifférente à la détection des boucles). Le tableau suivant récapitule l'ensemble des tests effectués :
médiane(s)
k d b t
l b h k t f
M, i, ?
o a e s x v
j z y g
q g p y z
Lorsque deux lettres ne présentent pas de minimum local dans le contour supérieur permettant de les séparer, la présence d'une boucle peut alors justifier la correction de la sous-segmentation. En effet, la plupart des lettres bouclées sont entièrement délimitées horizontalement par la largeur de la boucle. Un test à droite et à gauche de la boucle permet de vérifier si la même étiquette des pixels du graphème (cf. Chapitre I § 1.4.1.) est utilisée pour deux lettres. Dans ce cas, un nouveau graphème est créé grâce à une coupure effectuée à partir de la verticale passant au bord de la boucle. Ce cas est illustré dans le cas des lettres 'oi' du mot 'trois' de la figure 6b.
Lorsque la segmentation n'est pas facile à opérer entre deux lettres sous-segmentées dans un même graphème, il est alors plus simple de créer une classe nouvelle représentant les deux lettres à la fois. Par exemple la détection de deux boucles (ou plus) dans la zone des hampes ainsi que d'une boucle dans la zone médiane du mot (espace fermé entre les deux lettres) indique la présence du couple des lettres 'll' qu'il est parfois impossible de segmenter alors que le couple est facilement reconnaissable.
De même, on observe les cas de lettres, telles que 'fr', qui comportent une boucle supérieure et au moins une boucle dans la zone médiane.
Nous avons répertorié d'autres cas plus difficiles à détecter tels que les lettres 'oi', le 'i' étant collé au 'o', ou bien les lettres 'tr'.
Toutefois, on peut s'interroger sur l'intérêt de créer de nouvelles classes spécifiques dans chacun de ces cas. En effet, contrairement à la démarche suivie jusqu'à présent, qui est d'exploiter des caractéristiques faciles à extraire et donc fiables, l'utilisation de ces nouvelles classes ne sera qu'exceptionnelle. D'autre part, la correction des erreurs de classification implique une souplesse que doit assurer la forte redondance des classes.
Nous allons maintenant aborder la constitution d'un alphabet de transcription et étudier, par l'intégration de la détection des concavités, la manière d'augmenter la finesse de la reconnaissance sans diminuer son efficacité.
2.2.2. Constitution d'un alphabet de transcription de graphèmes en lettres
2.2.2.1. Table de coût
A l'issue de l'étape de détection des boucles, le mot est codé par une séquence linéaire de graphèmes déterminés parmi une quinzaine de classes, avec deux niveaux de précision : un premier ensemble de classes génériques "HJfM?" est basé sur la présence des hampes et jambages, et un ensemble de classes plus caractéristiques "tkblqgjoi" est basé principalement sur la présence et la position des boucles dans le graphème.
Ces classes présentent une forte redondance car les lettres finales peuvent être obtenues de plusieurs façons différentes : par exemple, la lettre 'b' figure dans cinq de ces classes, deux génériques ('H' et '?') et trois classes précises ('k', 'b' et 'l'). Cette redondance rend compte à la fois de la diversité avec laquelle on peut tracer naturellement la lettre 'b', mais aussi des différences d'extraction des primitives sur le graphème (petite boucle, petite hampe). Cependant, la probabilité de reconnaissance de la lettre peut être différente pour chaque classe de graphèmes.
Nous avons gradué cette probabilité d'une façon empirique, en attribuant un coût de transcription (traduction de la classe du graphème en lettre finale) parmi les valeurs suivantes, de zéro à cinq :
0 : Normal 1 : Eventuel 2 : Possible
3 : Peu fréquent 4 : Rare 5 : Exceptionnel
Ces valeurs de 0 à 5 pourraient être modifiées après une phase d'apprentissage.
La classe 'q' désigne les lettres avec jambage ayant une boucle dans la zone médiane, mais sans boucle dans le jambage.
q ® qgpyz ; 1133 <=> q ® q coût 0
® g coût 1
® p coût 1
® y coût 3
® z coût 3
La présence de la lettre 'y' dans cette classe (alors qu'elle devrait normalement être segmentée en deux graphèmes) tient compte de la possibilité que le tronçon gauche soit ressoudé au graphème lorsqu'il est de surface faible.
La classe générique 'J' désigne les jambages en général, sans aucune boucle détectée. Suivant la plupart des scripteurs, il est improbable que la lettre 'q' soit classée 'J', aussi son coût de transcription est-il fixé à trois.
De cette façon, les "probabilités" dépendent des caractéristiques absentes ou non détectées et sont graduées par rapport aux autres lettres de la même classe : la probabilité que le graphème de classe 'q' soit une lettre 'z' est inférieure à la probabilité que ce soit une lettre 'q' ou 'g'.
Les probabilités sont aussi cohérentes pour l'ensemble des classes de graphèmes : la probabilité qu'un graphème classé 'J' soit une lettre 'g' est faible, car la lettre 'g' doit être obtenue plutôt par la classe des graphèmes 'g' ou 'q'.
Par extension, la classe '?' des graphèmes ambigus désigne les graphèmes dont aucune caractéristique n'a pu être relevée (graphèmes sans hampe ou jambage net, ni boucle), ce qui est en fait une caractéristique importante, si on tient compte du nombre total de classes. La probabilité pour qu'un graphème '?' soit une lettre 'g' est donc encore plus faible que celle de 'J'.
2.2.2.2. Combinaisons de deux ou trois graphèmes
Afin de reformer les lettres systématiquement segmentées telles que 'u' et 'v', l'alphabet de transcription contient plusieurs combinaisons de deux graphèmes et une seule combinaison de trois graphèmes pour former les lettres 'm' et 'w'.
On observe alors une multiplication du nombre de combinaisons, que l'on va réduire en déclarant des équivalences : pour les combinaisons de deux graphèmes, le graphème '?' est équivalent à 'M' ou 'i', 'l' est équivalent à 'H', 'p' et 'j' à 'J', et pour les combinaisons de trois graphèmes, 'M' et '?' sont équivalents à 'i'.
De cette façon, on a 'oH' qui est traduit en la lettre 'd', mais 'ol' est équivalent à 'oH' et sera également traduit en 'd'.
Cependant, en dépit d'une équivalence, le coût de traduction peut être affiné si la combinaison est explicitement écrite dans l'alphabet. Par exemple, 'HM' est traduit en 'hkb', 'Ho' est traduit en 'kb' et 'lo' est également traduit en 'kb' mais avec un coût différent.
Seules les combinaisons figurant dans l'alphabet (explicitement ou par équivalence) seront formées. Le tableau suivant récapitule l'ensemble des classes de graphèmes utilisés ainsi que les dérivations entre elles :
3 graphèmes
htlfkdb
lbhktf
jpyzgqx
qgpyz
crinszeaoxmuvw
nuvrxmw
oaesxv
icersz
nuvrx
?=M, i
E : Equivalences pour les combinaisons de graphèmes
T : Classes déterminées dans la phase de Traitement des graphèmes
B : Classes déterminées dans la phase de détection des Boucles
C : Classes déterminées en fonction du Côté gauche ou droit des hampes ou jambages
2.2.2.3. Graphèmes multiples
L'alphabet de transcription ne peut contribuer qu'à corriger les erreurs de sursegmentation mais pas les erreurs de sous-segmentation. Nous avons pensé utiliser des transcriptions du type 'L' en 'll', 'L' étant la classe des graphèmes avec une hampe possédant deux boucles (ou plus) ainsi qu'une boucle dans la zone médiane du mot (cf. § 2.2.1.2.). Mais étant donné le faible nombre de cas traités, 'T' en 'tr', 'F' en 'fr' ou 'O' en 'oi', nous avons programmé directement ces transcriptions, sans la possibilité d'être indépendant du logiciel, comme l'est le fichier alphabet qui peut facilement être modifié.
2.2.2.4. Modulation des coûts en fonction des concavités
Le nombre de classes augmente rapidement avec le nombre de caractéristiques lorsque les graphèmes sont combinés par deux ou trois. Plutôt que d'affiner encore l'alphabet en créant de nouvelles classes, nous allons seulement effectuer une modulation des coûts de transcription, en lettres, des graphèmes déjà créés.
Deux types de concavités pertinentes pour la reconnaissance des lettres ont été retenus : la concavité représentée par la lettre 'n' et celle représentée par la lettre 'c'.
2.2.2.4.1. Détection des concavités
Ces deux concavités sont recherchées seulement à l'intérieur de la zone médiane du mot. De la même façon que pour la détection des boucles, un algorithme de remplissage est utilisé, car une concavité peut être considérée comme une cavité pouvant contenir un "liquide".
La détection de la concavité de type 'n' (figure 7) nécessite au préalable la détermination de la limite horizontale inférieure de la zone de remplissage (limite inférieure sur la figure 7). On recherche ensuite à l'intérieur de celle-ci un pixel vide pour initialiser le remplissage. Lorsqu'il est achevé dans les limites du graphème, si la surface remplie ne rejoint pas le bord du graphème, alors une concavité est détectée, sinon, cela trahirait la présence d'une brèche ou d'un trou dans la zone étudiée du graphème.
Si la surface remplie est supérieure au quart de la surface du graphème, et est supérieure à la surface minimale, alors la concavité est validée.
On procède de la même façon pour la concavité 'c'.
2.2.2.4.2. Modulation des coûts
En fonction de la détection des concavités 'n' et 'c', le coût de transcription de la classe des graphèmes est évalué pour chaque lettre dans chacune de ces quatre combinaisons '--', '-n', 'c-' et 'cn' : par exemple, le graphème de classe 'j' peut être traduit en chacune des lettres 'jzyg'.
j=001 001 ;
j : jzyg ;
-- 0205 ;
-n 0002 ;
c- 5225 ;
cn 5025 ;
Par exemple, si la seule concavité 'n' a été détectée, alors le graphème 'j' peut être traduit en la lettre 'g' avec un coût de 2.
La présence de la lettre 'g' provient de la possibilité de non détection de la boucle dans la zone médiane, soit parce qu'elle est non fermée (une concavité 'n' est probablement détectée dans ce cas) soit parce qu'elle est trop petite.
La présence d'une concavité de type 'c' dans la lettre 'j' a été considérée comme exceptionnelle.
Pour la combinaison de deux ou trois graphèmes, les concavités sont simplement additionnées (OU logique) pour éviter une trop grande augmentation du nombre des cas. Par exemple la combinaison 'ii' est traduite en 'n' avec un coût nul, si au moins une concavité 'n' a été détectée sur n'importe lequel des deux graphèmes 'i'.
La figure 6 (cf. § 2.1.2.3.) illustre le résultat de la détection des concavités sur chacun des graphèmes qui ont été déterminés sur les mots.
2.2.2.5. Constitution de l'alphabet
L'alphabet est présenté ci-dessous (figure 8) avec les images des lettres interprétant (parfois avec difficulté) l'ensemble des cas de figure prévus. Au début de chaque graphème sont indiqués trois champs représentant le codage 'HMJ' respectivement Hampes, Médianes et Jambages (cf. § 2.2.1.2.), et trois autres champs représentant les boucles détectées dans les zones 'HMJ' dans le même ordre (cf. § 2.1.2.1). L'étoile désigne qu'un champ donné peut prendre n'importe quelle valeur, et la lettre 'n' indique une ou plusieurs boucles (contrairement à une seulement).
HMJ HMJ
La classe 'j' désigne les lettres avec jambage comportant une boucle, mais n'en comportant pas dans la zone médiane.
g=001 0n1 ;
La classe 'g' désigne les lettres avec jambage comportant une boucle, avec également au moins une boucle dans la zone médiane.
Les classes 'd' et 'p', qui sont dérivées à partir des classes 'kb' et 'Jjgq' respectivement, sont déterminées par la position à droite de la hampe ('d') ou la position à gauche du jambage ('p'). Ces deux classes n'ont pas été utilisées par la suite en raison du manque de fiabilité du test permettant de les obtenir.
i=0*0 000 ;
i : icersz ;
-- 010035 ;
-n 010035 ;
c- 000035 ;
cn 000035 ;
o=0*0 0n0 ;
o : oaesxv ;
-- 000113 ;
-n 000003 ;
c- 310003 ;
cn 310003 ;
k=100 0n0 ;
k : kdbt ;
-- 2103 ;
-n 0123 ;
c- 2105 ;
cn 0125 ;
b=100 1n0 ;
b : bkd ;
-- 022 ;
-n 002 ;
c- 022 ;
cn 002 ;
l=100 100 ;
l : lbhktf ;
-- 002231 ;
-n 000032 ;
c- 002230 ;
cn 000032 ;
q=001 0n0 ;
q : qgpyz ;
-- 00132 ;
-n 00132 ;
c- 55532 ;
cn 55532 ;
g : gzy ;
-- 023 ;
-n 023 ;
c- 523 ;
cn 523 ;
H=100 000 ;
H : htlfkdb ;
-- 3000431 ;
-n 0024032 ;
c- 3004231 ;
cn 0025032 ;
M=010 000 ;
M : crinszeaoxmuvw
-- 31121313344555
-n 30100313344555
c- 01121003344555
cn 01113313344555
J=001 000 ;
J : jpyzgqx ;
-- 0502555 ;
-n 0110225 ;
c- 5542554 ;
cn 5350553 ;
oi : xaoe ;
-- 1222 ;
-n 1222 ;
c- 0221 ;
cn 0221 ;
oM : x ;
-- 4 ;
-n 3 ;
c- 2 ;
cn 1 ;
HM : hkb
-n 010
Ho : kb ;
-- 30 ;
-n 03 ;
c- 13 ;
cn 04 ;
lo : kb ;
-n 02 ;
c- 11 ;
cn 03 ;
MH : d ;
-n 1 ;
c- 0 ;
cn 0 ;
oH : d ;
-- 0 ;
-n 0 ;
c- 1 ;
ij : y ;
p=001 0n0
p : p ;
c- 3 ;
cn 3 ;
Jambe à gauche
d=100 *n0
d : d ;
Hampe à droite
t=100 000
t : t ;
f=101 ***
f : f ;
MJ : ygqz ;
-- 0555 ;
-n 0222 ;
c- 0335 ;
cn 0112 ;
oJ : gqz ;
-- 002 ;
c- 555 ;
cn 555 ;
JM : p ;
c- 5 ;
MM : nuvrxmw ;
-- 1100100 ;
-n 0010100 ;
c- 1100011 ;
cn 1100011 ;
ii : nuvrx ;
-- 11001 ;
-n 00101 ;
c- 11000 ;
cn 11000 ;
iii: mw ;
-n 00 ;
c- 32 ;
cn 32 ;
2.3. Reconnaissance des mots à l'aide d'un dictionnaire
La reconnaissance des mots à l'aide d'un dictionnaire consiste à établir la liste, classée par ordre de coûts croissants, de tous les mots compatibles avec la séquence des graphèmes reconnus. L'objectif est d'obtenir le mot correct en première position dans cette liste avec évidemment un coût inférieur aux coûts associés aux autres mots potentiels du dictionnaire.
2.3.1. Construction des séquences de graphèmes
En premier lieu, toutes les séquences de graphèmes sont construites avec des combinaisons autorisées par l'alphabet, afin de former l'ensemble des segmentations potentielles du mot. Ainsi, avec le mot 'treize', représenté par les graphèmes 'H?Mijo' (cf. fig. 9), neuf séquences sont formées. Chacune est comparée avec les mots du dictionnaire, mais dans ce cas une seule correspond à la segmentation correcte du mot 'treize' : 'H ? M i j o'. Toutefois, la combinaison 'H ? Mi j o' correspond également à un mot valide du dictionnaire : 'douze'.
H ? M i j o
H ? M ij o
H ? MM j o
H MM i j o
H MM ij o
H iii j o
HM M i j o
HM M ij o
HM MM j o
Figure 9 : liste des séquences de graphèmes
On note que la combinaison 'Mi' est équivalente à 'MM' pour former la lettre 'u' de 'douze'. De même, la combinaison 'H?' est équivalente à 'HM' pour former les lettres 'h', 'k' ou bien 'b'.
Toutes les combinaisons de deux ou trois graphèmes ne sont pas envisagées, car les combinaisons telles que 'jo', 'HMM' ou bien 'ijo' ne figurent pas dans l'alphabet (cf. § 2.2.2.).
2.3.2. Procédure élémentaire de recherche
La procédure de recherche des mots du dictionnaire, compatibles avec une des séquences de graphèmes s'écrit :
Pour chaque mot du dictionnaire :
tant que la lettre n°l de ce mot est présente dans la liste de traduction de la combinaison de graphèmes n°l correspondante (combinaison de 1 à 3 graphèmes)
alors on passe à la lettre l+1 ;
sinon on passe à la séquence suivante correspondant à une autre segmentation possible du mot ;
si toutes les lettres de ce mot sont compatibles avec une des séquences, alors le coût global du mot est calculé en effectuant la somme des coûts de traduction en lettres de chaque combinaison de graphèmes de cette séquence ;
sinon, le mot est rejeté ;
puis, les coûts de chaque mot sont classés dans l'ordre croissant, quelle que soit la séquence ayant permis d'obtenir le mot (s’il y a plusieurs séquences compatibles pour le même mot, seule celle de moindre coût est conservée).
L'exemple de la reconnaissance du mot 'treize' avec les graphèmes 'H?Mijo' montre en détail le fonctionnement de cette procédure :
Les lettres compatibles sont en majuscules tandis que les lettres incompatibles sont en minuscules (la recherche s'arrête à la première lettre incompatible de chaque séquence) :
zero : z ; z ; z ; z
deux : De ; De ; d ; d
cinq : c ; c ; c ; c
sept : s ; s ; s ; s
huit : HUi ; Hu ; HUi ; HUi
neuf : n ; n ; n ; n
onze : o ; o ; o ; o
cent : c ; c ; c ; c
trois : TROi ; TRo ; TRo ; t
douze : DOUz ; DOUZE : 3 0 1 0 0 : 4 ; Do ; d
seize : s ; s ; s ; s
vingt : v ; v ; v ; v
cents : c ; c ; c ; c
mi11e : m ; m ; m ; m
franc : FRAn ; FRa ; FRa ; f
quatre : q
treize : TREIZE : 0 0 1 0 0 0 : 1
quinze : q
trente : TREn
francs : FRAn
En tout, 2 mots seulement sur 34 sont compatibles avec les graphèmes reconnus : le mot douze avec un coût global de 4, et le mot treize avec un coût de 1 :
0+0+1+0+0+0 = 1
3+0+ 1+ 0+0 = 4
La traduction du graphème 'H' en 'd' est affectée d'un coût de 3 qui correspond à l'improbabilité de ne pas détecter de boucle dans la lettre 'd'.
Si une seule lettre d'un mot du dictionnaire est incompatible avec une combinaison de graphèmes correspondant à sa position dans le mot (car la lettre ne figure pas dans la liste de traduction), il y a rejet de ce mot. Ce manque de souplesse, que nous évaluerons quantitativement dans un test (cf. § 3.4.), montre la limite de la procédure élémentaire de recherche : la redondance de l'alphabet, bien qu'importante, est insuffisante pour permettre la reconnaissance des mots mal segmentés, et particulièrement celle des mots sous-segmentés. En effet, il est nécessaire de calculer une distance d'édition complète de chaque mot du dictionnaire avec l'ensemble des combinaisons de graphèmes de chaque séquence.
2.3.3. Calcul d'une distance d'édition
Une distance d'édition classique est utilisée entre deux chaînes de caractères [LECOLINET 90], la première chaîne est la séquence des combinaisons de graphèmes, et la seconde est une chaîne de lettres formant un mot du dictionnaire.
Pour ce calcul, un coût d'insertion est défini pour chaque lettre :
coût insertion = "35350555055530355035333355"
auquel est ajouté un coût d'insertion fixe égal à 5 ;
un coût de destruction de graphème ou combinaison de graphèmes est ensuite défini :
cd = "I ? i o k b l q g j p d t f H M J oi oM HM Ho lo MH oH ij MJ oJ JM MM ii HH iii"
cd = "5 5 0 3 5 5 5 5 5 5 5 5 5 5 5 3 5 5 5 9 9 9 9 9 9 9 9 9 9 9 9 9 "
auquel est ajouté un coût de destruction fixe égal à 5 ;
et enfin, un coût de substitution de graphème(s) en lettre : lorsque la substitution est prévue explicitement dans la liste de traduction de l'alphabet, le coût correspondant est utilisé comme pour la procédure de recherche élémentaire, sinon, un coût de substitution fixe (égal à 8), qui est supérieur à tous les autres coûts de substitution (de 0 à 5), est appliqué.
Cette procédure est réitérée pour chaque mot et pour chaque séquence de graphèmes. Toutefois, les séquences comportant plus de deux lettres par rapport au mot ne sont pas examinées (le nombre de lettres n'est jamais supérieur au nombre de graphèmes, les seuls cas de sous-segmentation envisagés ont été traités au paragraphe 2.2.2.3.). Seule la séquence de moindre coût est retenue.
Enfin, les mots sont classés par ordre de coût croissant.
On remarque que cette méthode consistant à construire l'ensemble des séquences possibles de graphèmes pourrait être remplacée par la programmation d'une procédure de substitution par concaténations multiples de deux ou trois graphèmes (cf. chapitre 3 : reconnaissance structurelle, § 2.2.2.) qui n'utiliserait qu'une seule séquence.
Cet algorithme est beaucoup plus long que la procédure élémentaire, car toutes les correspondances entre les deux chaînes sont systématiquement envisagées. Cependant, il est parallélisable, car chaque mot peut être testé indépendamment des autres.
Exemple de reconnaissance du mot "treize" avec la séquence de graphèmes
"H ? M i j o" :
Le coût d'appariement est égal à 1. Il est égal au coût obtenu précédemment (cf. § 2.3.2.) puisque le chemin de coût minimal dans le tableau ne passe que par des substitutions (code 1), sans aucune insertion de lettre (code 2) ni destruction de graphème (code 3).
Le test que nous avons réalisé est basé sur la reconnaissance d'une trentaine de mots du vocabulaire lié à la rédaction des chèques. Ces mots ont été écrits par trois scripteurs différents (figures 10a, 10b et 10c), sans d'autres contraintes que celle consistant pour les scripteurs à avoir connaissance du test au préalable : la reconnaissance d'échantillons recueillis sur des chèques réels est toujours plus délicate et comporte en outre une étape d'extraction du texte parmi le graphisme éventuel.
Figure 10a : Scripteur 1
Figure 10b : Scripteur 2
Figure 10c : Scripteur 3
Deux tableaux de résultats sont présentés ci-dessous : dans le premier est rapporté le bilan de la reconnaissance avec la procédure élémentaire de recherche (simple "matching" cf. § 2.3.2.) et dans le second sont présentés les résultats de reconnaissance par l'algorithme basé sur la distance d'édition.
Scripteur 2
Scripteur 3
Total Scripteurs
Coût de 1 à 4
Coût de 5 à 9
Coût sup. à 10

References: § 1
 § 1
 § 1
 § 1
 § 2
 § 1
 § 3
 § 1
 § 1
 § 1
 § 1
 § 2
 § 1
 § 2
 § 1
 § 2
 § 3
 § 1
 § 2
 § 2
 § 3
 § 2
 § 2
 § 1
 § 2
 § 2
 § 3
 § 1
 § 1
 § 1
 § 1
 § 1
 § 1
 § 2
 § 1
 § 2
 § 2
 § 1
 § 1
 § 2
 § 2
 § 2
 § 1
 § 2
 § 2
 § 2
 § 2
 § 2
 § 3
 § 2
 § 2
 § 2