[PDF] Reconnaissance Structurelle de Formules Mathématiques

View - Download Reconnaissance Structurelle de Formules Mathématiques

Previous PDF

Next PDF

>G A/, i2H@yy8kjjdj ?iiTb,ffi?2b2bX?HXb+B2M+2fi2H@yy8kjjdj am#KBii2/ QM 8 P+i kyRy >GBb ˛ KmHiB@/Bb+BTHBM˛`v QT2M ˛++2bb ˛`+?Bp2 7Q` i?2 /2TQbBi ˛M/ /Bbb2KBM˛iBQM Q7 b+B@

2MiB}+ `2b2˛`+? /Q+mK2Mib- r?2i?2` i?2v ˛`2 Tm#@

HBb?2/ Q` MQiX h?2 /Q+mK2Mib K˛v +QK2 7`QK

i2˛+?BM; ˛M/ `2b2˛`+? BMbiBimiBQMb BM 6`˛M+2 Q` ˛#`Q˛/- Q` 7`QK Tm#HB+ Q` T`Bp˛i2 `2b2˛`+? +2Mi2`bX /2biBMû2 ˛m /ûT¬i 2i ¨ H˛ /BzmbBQM /2 /Q+mK2Mib b+B2MiB}[m2b /2 MBp2˛m `2+?2`+?2- Tm#HBûb Qm MQM-

Tm#HB+b Qm T`BpûbX

_2+QMMBbbM+2 ai`m+im`2HH2 /2 6Q`KmH2b

Ji?ûKiB[m2b hvTQ;`T?Bû2b 2i JMmb+`Bi2b

aiûT?M2 GpB`Qii2 hQ +Bi2 i?Bb p2`bBQM,

aiûT?˛M2 G˛pB`Qii2X _2+QMM˛Bbb˛M+2 ai`m+im`2HH2 /2 6Q`KmH2b J˛i?ûK˛iB[m2b hvTQ;`˛T?Bû2b 2i

LLh, X i2H@yy8kjjdj

UNIVERSIT´EDENICE-SOPHIAANTIPOLIS

´Ecole Doctorale des Sciences et Technologies de l"Information et de la Communication

Reconnaissance structurelle de

formules math´ematiques typographi´ees et manuscrites

TH`ESE

de doctorat pour obtenir le titre de

Docteur en Sciences

Discipline : Informatique

par

St´ephane LAVIROTTE

Soutenue le 14 juin 2000`a l"ESSI (Sophia-Antipolis)

Composition du jury

Pr´esident :Jean-Marc FEDOU Professeur `a l"Universit´e de Nice Sophia-Antipolis Rapporteurs :Karl TOMBRE Professeur `al"´Ecole des Mines de Nancy Guy LORETTE Professeur `a l"Universit´e de Rennes I Examinateurs :Lo¨ıc POTTIER Charg´e de Recherche `a l"INRIA Sophia-Antipolis Peter SANDER Professeur `a l"Universit´e de Nice Sophia-Antipolis Marc BERTHOD Directeur de Recherche `a l"INRIA Sophia-Antipolis

Universit´e de Nice Sophia-Antipolis / Institut National de Recherche en Informatique et Automatique

Mis en page avec la classe thloria.

Remerciements

Je tiens à remercier :

- Loïc Pottier pour ses conseils, son expérience et l"encadrement de cette thèse; - les membres du jury, Jean-Marc Fédou, Peter Sander, Marc Berthod, et plus particu- lièrement Karl Tombre et Guy Lorette qui ont accepté de rapporter cette thèse; - les anciens membres de l"équipe SAFIR ainsi que les membres des projets CAFE et LEMME de l"INRIA qui m"ont tous accueilli avec beaucoup de gentillesse et de bien- veillance. - France Limouzis et Patricia Lachaume pour leur soutient et leur aide dans les dé- marches administratives. Je veux aussi remercier toutes les personnes qui ont travaillé ponctuellement, de près ou de loin avec moi : - Andréas Kosmala dans le cadre d"une collaboration avec l"Université de Duisburg; - Olivier Arsac avec qui les collaborations de travail furent nombreuses et toutes plus enrichissantes les unes que les autres; - Colas Nahaboo et Jean-Michel Léon ainsi que toute l"équipe KOALA pour leurs outils de développement, leur bonne humeur et leurs conseils avisés; - José Grimm pour tous ses précieux conseils sur L A TEX. Enfin, je remercie collectivement tous ceux qui ont bien voulu relire ma thèse, m"apporter leur aide et plus particulièrement Frédérique, qui a su me soutenir au quotidien. i ii

I do not fear computers.

I fear the lack of them.

Isaac Asimov

iii iv

Table des matières

Table des figures vii

1 Nos buts initiaux............................... 3

2 Motivations et applications possibles . . . .................. 3

3 Objectifs de l"étude . . . . . ......................... 5

4 Résultats obtenus............................... 5

4.1 Le composantOFR.......................... 5

4.2Irma: une application........................ 6

5 Plan de lecture . ................................ 6

6 Conventions typographiques ......................... 7

Chapitre IReconnaissance structurelle deformulesmathématiques :étatde l'art 9

1 Historique................................... 10

2 De nombreuses applications possibles . . .................. 11

2.1 Édition de formules mathématiques................. 12

2.1.1 Syntaxe linéaire . . . . .................. 12

2.1.2 Palette de modèles . . . .................. 14

2.1.3 Édition bidimensionnelle................. 15

2.1.4 Des modes d"édition “coûteux" . . . ........... 15

2.1.5 Vers une édition manuscrite................ 16

2.2 Bases de formules . ......................... 17

2.3 Extension des systèmes de reconnaissance de documents . . . . . . 18

2.4 Diverses autres applications . . . .................. 18

3 Définition des notations mathématiques . .................. 19

4 Difficultés par rapport à la reconnaissance de textes . . ........... 20

v

Table des matières

4.1 Bruit et petits symboles . . ...................... 21

4.2 Segmentation ............................. 22

4.3 Reconnaissance des symboles . . . . . ............... 22

4.4 Ambiguïtés sur le rôle d"un même symbole . . ........... 23

4.5 Ambiguïté sur le placement relatif des symboles.......... 24

4.6 Ambiguïté dans la notation ...................... 25

4.7 Peu de redondance de l"information . . ............... 26

5 Quelques traitements préliminaires ...................... 27

5.1 Seuil de numérisation . . . ...................... 29

5.2 Réduction du bruit . . . . ...................... 30

5.3 Réalignement de l"image . ...................... 31

5.4 Isoler une formule dans un document . ............... 33

5.5 Conclusion . ............................. 34

6 Segmentation et reconnaissance des symboles . ............... 35

6.1 Caractères typographiés . ...................... 35

6.2 Caractères manuscrits . . ...................... 37

6.3 Conclusion . ............................. 39

7 Reconnaissance de la structure . . ...................... 39

7.1 Identification des relations spatiales et logiques entre les symboles . 40

7.2 Reconnaissance de la structure de la formule . ........... 42

8 Diversité des approches existantes ...................... 42

8.1 Diversité des méthodes pour l"analyse structurelle.......... 42

8.1.1 Méthodes syntaxiques . . . . ............... 43

Grammaire de coordonnées . . ............... 43 Schémas de spécification de structure . ........... 45

Grammaires probabilistes . . . ............... 45

Grammaires de graphes . . . . . ............... 46

8.1.2 Méthodes logiques..................... 47

8.1.3 Méthodes mixtes liant analyse géométrique et syntaxique 48

Méthodes procédurales . . . . . ............... 48 Méthode de découpage par projections . ........... 48

8.2 Difficultés pour comparer les approches ............... 50

8.2.1 Diversité dans les données traitées . ........... 51

8.2.2 Grande diversité des approches.............. 51

8.2.3 Diversité des notations mathématiques.......... 51

9 Conclusion . . . . . ............................. 52

Chapitre II Concepts pour la reconnaissance de formules 53

1 Réutilisabiblité ................................ 54

1.1 Équations, matrices et notations “exotiques" . . ........... 54

1.2 Manuscrit et Typographié . . . . .................. 54

2 Évolutivité................................... 55

2.1 Introduction de nouvelles notations................. 55

2.2 Adaptation aux différentes notations................. 56

3 Interprétation de l"arbre de syntaxe . . . . .................. 56

4 Communication des résultats ......................... 57

5 Composants pour l"analyse de formules . .................. 58

5.1 Détail des différents composants . .................. 58

5.2 Critiques possibles de l"architecture en modules ........... 59

6 Conclusion . . ................................ 59

Chapitre III Méthode et outils 61

1 Architecture d"OFR.............................. 61

2 Analyse de l"image . . . . . ......................... 63

2.1 Enveloppe d"un symbole . . . . . .................. 63

2.2 Résultat type attendu de l"OCR . .................. 65

2.3 Extrapolation de données . . . . . .................. 66

2.3.1 Taille relative . . . . . .................. 66

2.3.2 Ligne de base . . . . . .................. 66

3 Analyse lexicale ................................ 67

4 Analyse géométrique . . . . ......................... 69

4.1 Introduction des graphes . . . . . .................. 69

4.2 Définition d"un graphe........................ 70

4.3 Construction du graphe initial . . .................. 71

4.3.1 Analyse de proximité . .................. 71

4.3.2 Critères géométriques et graphiques ........... 72

4.3.3 Critères divers . . . . . .................. 74

4.3.4 Rôle du type lexical . . .................. 75

4.3.5 Conclusion ......................... 75

4.4 Optimisation . . . . ......................... 76

4.5 Les limites de la construction du graphe . . . . ........... 78

5 Rappels sur les grammaires . ......................... 79

5.1 Rappels sur les grammaires . . . .................. 80

vii

Table des matières

5.1.1 Grammaires formelles . . . . ............... 80

5.1.2 Grammaires attribuées . . . . ............... 81

5.2 Grammaires de graphes . . ...................... 83

6 Analyse structurelle . ............................. 86

6.1 Grammaire de graphes et formules mathématiques . . . . . . . . . 86

6.2 Construction du contexte des règles . . ............... 87

6.2.1 Exemple . . . . ...................... 87

6.2.2 Superpositions dans l"application des règles . . . . . . . 88

6.2.3 Grammaire sans ambiguïté . ............... 91

6.3 Analyse structurelle . . . ...................... 93

6.3.1 Analyse ascendante . . . . . ............... 93

6.3.2 Attributs synthétisés . . . . . ............... 94

6.3.3 Mise à jour incrémentale du graphe . ........... 95

6.4 Optimisation ............................. 95

7 Conclusion . . . . . ............................. 96

Chapitre IV Applications et Validation 99

1 Notations mathématiques typographiées . . . . ............... 99

1.1 Un comparatif des logiciels pour la reconnaissance de symboles . . 100

1.1.1 Quelques critères..................... 101

Formats traités . . ...................... 101

Numérisation et traitement de l"image . ........... 101 Analyse du document et reconnaissance des symboles . . . 102 Adaptabilité et Évolutivité . . . ............... 102

1.1.2 Protocole de comparaison................. 103

1.1.3 Tableau comparatif . . . . . ............... 103

1.1.4 Conclusion . . . ...................... 104

1.2 Développement d"un OCR dédié et adaptatif . ........... 104

1.2.1 Numérisation du document . ............... 105

1.2.2 Extraction des composantes connexes ........... 105

1.2.3 Extraction des caractéristiques des symboles . . . . . . . 106

1.2.4 Apprentissage . ...................... 108

1.2.5 Identification du caractère et résultat fourni . . . . . . . . 109

1.2.6 Évaluation des performances ............... 110

2 Notations mathématiques manuscrites . . . . . ............... 111

2.1 Présentation du système NeuroGraph . ............... 111

viii

2.2 Reconnaissance des symboles manuscrits . . . ........... 112

3Irma: Dualité du système développé . . .................. 114

3.1 Adaptation au format des données .................. 115

3.2 Adaptation aux notations reconnues................. 115

3.3 Adaptation du format de sortie . . .................. 116

3.4 Communication à l"aide d"OpenMath................ 116

4 Validation................................... 118

4.1 La grammaire de graphes . . . . . .................. 118

4.2 Résultats............................... 122

4.3 Quelques exemples caractéristiques................. 123

5 Conclusion . . ................................ 127

Chapitre V Implémentation d'OFR129

1 Langages de script . . . . . ......................... 130

1.1 Bref historique des langages . . . .................. 130

1.2 Quelques caractéristiques des langages . . . . ........... 132

1.2.1 Machine virtuelle . . . .................. 132

1.2.2 Typage . . ......................... 133

1.2.3 Modèle objet........................ 133

1.3 Conclusion . . . . . ......................... 134

2 Critères de choix pour un langage de script .................. 134

2.1 Efficacité et fiabilité ......................... 134

2.2 Environnement de développement .................. 134

2.3 Extension possible . ......................... 135

2.4 Sauvegarde des données dans le langage . . . . ........... 135

2.5 Une interface graphique . . . . . .................. 136

3 Une comparaison des langages de script . .................. 136

3.1 Langages de script testés . . . . . .................. 136

3.2 Conclusion . . . . . ......................... 138

4 Choix d"un langage . . . . . ......................... 139

4.1Klone................................. 139

4.2Klm: une extension graphique deKlone.............. 140

4.3 Communication avec d"autres systèmes :OpenMath........ 141

5 Implémentations............................... 143

6 Conclusion . . ................................ 143

Table des matières

Conclusion 145

Irma149

1 Exemples de polices et de variations..................... 153

2 Symboles textuels les plus courants..................... 154

2.1 Alphabet latin ............................. 154

2.2 Accentuations ............................. 154

2.3 Chiffres . . . ............................. 155

2.4 Ponctuations ............................. 155

3 Symboles mathématiques les plus courants . . . ............... 155

3.1 Alphabet grec ............................. 155

3.2 Opérateurs mathématiques ...................... 156

Annexe C Un document de test 159

x

Table des figures

Chapitre I 9

1 Édition linéaire dans Maple V.5........................ 13

2 Édition par palette de modèles........................ 14

3 Les étapes de l"analyse d"un document papier . . . . . ........... 28

4 Exemples de différents seuils de numérisation . . . . . ........... 30

5 Méthode de projection de textes pour différentes orientations . . . . . . . . 31

6 Méthode évaluant les angles de droites entre voisins pour un texte . . . . . 32

7 Méthode de projection appliqué à la formule

9 i=0 x 2i ............. 32

8 Méthode évaluant les angles de droites entre voisins pour la formule

9 i=0 x 2i 33

9 Arbre syntaxique de l"expressionax

quotesdbs_dbs47.pdfusesText_47

[PDF] maths or maths capital letter

[PDF] maths pcsi exercices corrigés

[PDF] Maths PGCD (3eme cned)

[PDF] maths phare 3eme corrigé 2012

[PDF] maths phare 4eme

[PDF] maths planète du système solaire

[PDF] Maths pliz merci

[PDF] Maths pour demain

[PDF] Maths pour demain HELP

[PDF] Maths pour demain rien compris

[PDF] MATHS POUR DEMAIN SVP HELP

[PDF] maths pour élèves non francophones

[PDF] Maths pour lundi (1ex)

[PDF] Maths pour très bientôt !

[PDF] Maths pourcentage