Contribution à la Segmentation et à la Reconnaissance de l'Ecriture Manuscrite

TABLE DES MATIERES

REMERCIEMENTS : 3

INTRODUCTION 7

CHAPITRE I. METHODES ET OUTILS ACTUELS DE LA RECONNAISSANCE DES TEXTES MANUSCRITS 10

Introduction 10

1. Les primitives, outils de la reconnaissance 10

1.1. Les objectifs de l'extraction des primitives 10

1.2. La problématique de l'extraction de l'information 12

1.3. L'extraction des primitives 13

1.3.1. Les approches de l'extraction des primitives 13

1.3.2. Les catégories de primitives 14

1.3.3. Les étapes de l'extraction des primitives 15

1.4. Les techniques de changement de représentation 18

1.4.1. Extraction des composantes connexes 18

1.4.2. Représentation par le contour 23

1.4.3. Représentation par le squelette 25

2. La méthode de reconnaissance 29

2.1. Etude bibliographique sur la modélisation des mots manuscrits 29

2.1.1. Approximation du mot par des segments de droite 29

2.1.2. Modélisation à partir de l'axe du mot 29

2.1.3. Modélisation du mot à l'aide des graphèmes 29

2.2. Les catégories de méthodes 31

2.2.1. Paramétrage du mot 32

2.2.2. Modélisation de la forme du mot indépendamment des lettres 33

2.2.3. Modélisation de la forme du mot liée aux lettres 34

2.2.4. Modélisation de la forme des lettres dans le mot 34

2.2.5. Modélisation des lettres 35

2.2.6. Segmentation du mot en graphèmes 36

2.2.7. Schéma récapitulatif des méthodes de reconnaissance 37

3. La stratégie de reconnaissance 37

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

Conclusion 42

CHAPITRE II. ETUDE DE LA SEGMENTATION 44

Introduction 44

1. Segmentation globale de l'image par application de transformées mathématiques 45

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. Segmentation par extraction de graphèmes 86

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

Conclusion 119

CHAPITRE III. RECONNAISSANCE PAR APPARIEMENT DE GRAPHES STRUCTURELS 122

Introduction 122

1. Construction d'un graphe structurel représentatif d'une forme 122

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. Appariement des graphes structurels des lettres manuscrites 149

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. Reconnaissance structurelle de lettres manuscrites 172

3.1. Plausibilité de reconnaissance 172

3.2. Confrontation de plusieurs scores de reconnaissance 172

3.3. Exemple de reconnaissance 173

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

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. Les perspectives à partir du graphe structurel du mot non segmenté 191

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

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

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. Les perspectives à partir du graphe structurel du mot non segmenté 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. Détermination de la stratégie de reconnaissance 198

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

Conclusion 205

CONCLUSION 206

REFERENCES BIBLIOGRAPHIQUES 208

TABLE DES MATIERES 221

TABLE DES MATIERES PRINCIPALES 231

TABLE DES MATIERES PRINCIPALES

REMERCIEMENTS : 3

INTRODUCTION 7

CHAPITRE I. METHODES ET OUTILS ACTUELS DE LA RECONNAISSANCE DES TEXTES MANUSCRITS 10

Introduction 10

1. Les primitives, outils de la reconnaissance 10

2. La méthode de reconnaissance 29

3. La stratégie de reconnaissance 37

Conclusion 42

CHAPITRE II. ETUDE DE LA SEGMENTATION 44

Introduction 44

1. Segmentation globale de l'image par application de transformées mathématiques 45

2. Segmentation par extraction de graphèmes 86

Conclusion 119

CHAPITRE III. RECONNAISSANCE PAR APPARIEMENT DE GRAPHES STRUCTURELS 122

Introduction 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 208

TABLE DES MATIERES 221

TABLE DES MATIERES PRINCIPALES 231

FOLIO ADMINISTRATIF

THESE SOUTENUE DEVANT L'INSTITUT NATIONAL DES SCIENCES APPLIQUÉES DE LYON

NOM : DARGENTON	Date de SOUTENANCE
Prénoms : Patrice, Franck	14 / 12 / 1994
TITRE : CONTRIBUTION A LA SEGMENTATION ET A LA RECONNAISSANCE DE L'ECRITURE MANUSCRITE
NATURE : Doctorat Spécialité : INGÉNIERIE INFORMATIQUE	Numéro d'ordre : 94 ISAL0106
Code B.I.U. - Lyon : T 50/210/19 / et bis	CLASSE :
RÉSUMÉ : Cette étude constitue une contribution originale à la segmentation et à la reconnaissance de l'écriture manuscrite, grâce à la conception et à la réalisation de deux nouvelles méthodes complémentaires. Dans un premier temps, nous présentons une étude et une synthèse bibliographique afin de faire ressortir la problématique de la reconnaissance de l'écriture manuscrite. Dans un deuxième temps, nous avons poursuivi notre investigation d'un point de vue plus pratique avec l'implémentation de plusieurs méthodes classiques telles que l'extraction des composantes connexes, la segmentation des mots en graphèmes, ou la représentation des caractères par le squelette. Cette démarche nous a conduit à réaliser deux nouvelles méthodes : * La première est une méthode originale de segmentation "harmonique" et "polaire" basée respectivement sur les transformées de Fourier et de Hough; elles permettent d'obtenir des informations statistiques réparties qui sont naturellement exploitées dans la lecture. * La seconde est une méthode de reconnaissance par appariement de graphes structurels. Nous présentons l'approche de l'appariement de deux graphes structurels quelconques et son exploitation pour la reconnaissance des caractères manuscrits. Nous montrons que cette approche ouvre de nouvelles perspectives pour la reconnaissance des mots manuscrits.
MOTS-CLÉS : micro-informatique ; écriture manuscrite ; segmentation ; transformée de Fourier ; transformée de Hough ; reconnaissance de caractères ; appariement ; graphe structurel.
Laboratoire de recherches : LISPI - RFV Laboratoire d'informatique des systèmes et production industrielle - équipe Reconnaissance des formes et vision
Directeur de thèse : Mme N. VINCENT
Président du jury : C. BELLISSANT
Composition du jury : JP CRETTEZ , H. EMPTOZ, Y. LECOURTIER, Y. ROBERT, N. VINCENT