Reconnaissance de structures bidimensionnelles

Caractéristiques de l’écriture manuscrite

En général, la reconnaissance optique de caractères (OCR : Optical Character Recognition) implique de concevoir des systèmes capables de transformer des textes typographiés ou manuscrits dans un format compréhensible par l’ordinateur. Initialement, l’OCR était dédiée à la reconnaissance de caractères, mais grâce aux progrès technologiques, ce domaine a connu beaucoup de développement. Des systèmes de reconnaissance de mots, textes, documents, schémas, etc. sont largement étudiés par les communautés de reconnaissance de formes et de vision par ordinateur. Néanmoins par abus de langage et pour simplifier, nous appelons tout ce qui est écrit ou dessiné à la main : un signal manuscrit, que ce soit du texte, un diagramme ou même une expression mathématique. l’étude de la reconnaissance de l’écriture manuscrite se divise en deux domaines : hors-ligne et en-ligne selon la source numérique du signal de l’écriture. Dans le cas d’un signal en-ligne, deux stratégies de reconnaissance peuvent être utilisées : l’interprétation à la volée ou l’interprétation a posteriori.
Des avancées significatives ont été réalisées dans le domaine de la reconnaissance de l’écriture manuscrite depuis une trentaine d’années .
Cependant, il reste toujours des problèmes et des difficultés qui ne sont pas complètement surmontés. On essaye alors de résoudre ces problèmes en imposant des contraintes d’entrée mais aussi en impliquant des connaissances du domaine en question.

Segmentation des expressions mathématiques

La segmentation est une étape indispensable pour la reconnaissance de l’écriture. Quelque soit la source (en-ligne ou hors-ligne) et la nature (manuscrite ou dactylographiée) du signal de l’écriture, une bonne segmentation des symboles est essentielle pour une bonne reconnaissance. La segmentation permet à la fois d’identifier les éléments de base qui forment le signal, et aussi d’introduire des informations spatiales indispensables dans les étapes d’analyse structurelle et de l’interprétation.
Dans un système de reconnaissance de mots non contraints , ce problème de segmentation pose déjà des difficultés évidentes. Pour les résoudre, on peut distinguer deux approches principales. L’approche globale considère le mot en tant qu’entité entière et elle esquive le problème de la segmentation. Dans ce cas, chaque mot est modélisé individuellement. Il est bien évident que la conception d’un tel système devient de plus en plus lourde lorsque la taille du lexique augmente. Dans ces conditions, une reconnaissance basée sur la segmentation (approche analytique) s’impose. Celle-ci va chercher à trouver et reconnaître les caractères du mot en question. Cette segmentation peut être explicite (INSEG), i.e. reconnaître les caractères en amont pour reconnaître le mot. Ou autrement, elle peut être implicite (OUTSEG), i.e. décider les points de segmentation en aval après avoir reconnu le mot. Bien entendu, dans ces conditions, la segmentation est rarement
unique, mais elle conduit à construire un graphe ou treillis dont l’exploration combinée à la reconnaissance, permettra de trouver la meilleure hypothèse de segmentation/reconnaissance. Il est à remarquer que le texte s’écrit systématiquement de gauche à droite (ou à l’inverse dans certains scripts). Cet ordonnancement spatial facilite notamment la segmentation des mots, et même celle des phrases.

Réseaux de neurones artificiels (RNA)

Un réseau de neurones artificiels est formé d’un grand nombre d’unités élémentaires, simples, et fortement interconnectées . Le fonctionnement de cette unité de base (appelé neurone) est fondé sur une approximation du fonctionnement du neurone biologique .
Plusieurs modèles connexionnistes de neurones ont été adaptés pour la reconnaissance de formes et la reconnaissance de l’écriture. Ce sont souvent les éléments de base des systèmes de reconnaissance de formes structurées. George et al. ont proposé d’utiliser les réseaux de neurones pour la reconnaissance des symboles du domaine de partitions musicales. Dimitriadis et al. ont proposé l’utilisation de réseaux de neurones de type ART (Adaptive Resonance theory). Harteman et al. Marzinkewitsch et al. ont pour leur part utilisé le fameux PMC (Perceptrons Multi couches). Ce dernier est un classifieur très compétitif et performant qui est souvent utilisé pour la reconnaissance des formes dans différents domaines. Les performances des PMC se rapprochent de celles des SVM, mais ils sont nettement meilleurs en termes de mémoire et de temps de traitement. Par exemple, pour la tâche simple de reconnaissance des 10 chiffres, il faut 452,000 paramètres pour un SVM par rapport à moins de 40,000 paramètres pour un PMC à une couche cachée. Par ailleurs, une variante de PMC, les réseaux de neurones à convolution (TDNN), est mise en œuvre pour la reconnaissance de l’écriture avec les mêmes propriétés du PMC en ajoutant une (ou plusieurs) couches de type convolution pour l’extraction de caractéristiques locales du signal d’entrée. En effet, un TDNN (Time Delayed Neural Network) est insensible aux variations de positions et de translations de l’écriture. Cette structure utilise des informations locales du signal au lieu de n’apprendre que sur une vue globale. L’architecture d’un TDDN se découpe en 2 parties : la partie extraction des caractéristiques pour la ou les couches basses, et ensuite un PMC classique.

Optimisation simultanée de la segmentation, la reconnaissance et l’interprétation

Cette approche est de plus en plus adoptée ces derniers temps. En effet, s’il s’agit toujours d’utiliser les différentes approches proposées ou adaptées auparavant, ces différentes étapes se fondent dans un cadre global et s’appliquent simultanément pour reconnaître l’expression. L’idée s’inspire simplement de la perception humaine de l’expression mathématique. En fait, un humain perçoit la totalité de l’expression sans faire des perceptions et traitements séquentiels. D’où l’idée de simuler la perception humaine en faisant les tâches de segmentation, reconnaissance et interprétation de façon concomitante. L’expression la plus probable sera issue directement de la coopération des trois modules : la segmentation, la reconnaissance des symboles et l’interprétation. Un grand avantage de cette approche est de limiter la propagation des erreurs héritées d’une étape à une autre et de permettre de récupérer des solutions localement moins bonnes mais conduisant globalement à une meilleure solution.
Yamamoto et al. proposent de modéliser tout le processus de reconnaissance d’une expression manuscrite en-ligne par une grammaire stochastique hors contexte. La grammaire prend en compte l’ordre de l’écriture et la nature 2D des symboles. Elle contient également des règles de production des traits et des symboles. Chacune de ces règles est probabiliste, i.e. à l’application d’une règle on calcule sa probabilité en utilisant des méthodes classiques de classification de symboles. Le reste des règles modélise les relations spatiales et la syntaxe de l’expression en calculant une probabilité structurelle associée à chacune de ces règles. La probabilité structurelle est calculée en fonction des boîtes englobantes et de la région cachée de l’écriture.

Table des matières

Introduction générale
Chapitre 1 : Reconnaissance de structures bidimensionnelles 
1.1. Contexte 
1.2. Caractéristiques de l’écriture manuscrite
1.3. Problématiques 
1.4. Motivations
1.5. La notation mathématique
1.5.1. Définitions
1.5.2. Spécificité des expressions mathématiques
1.5.2.1. Le nombre des symboles
1.5.2.2. La disposition bidimensionnelle des symboles
1.6. Quelques systèmes existants 
1.7. Conclusion 
Chapitre 2 : Etat de l’art 
2.1. Segmentation des expressions mathématiques 
2.1.1. Cas du signal hors-ligne
2.1.2. Cas du signal en-ligne
2.2. Classification des symboles 
2.2.1. Mise en correspondance de motifs (Template matching)
2.2.2. Approche structurelle
2.2.3. Les K-plus proches voisins (k-ppv)
2.2.4. Systèmes à vastes marges (SVM, « Support Vector Machines »)
2.2.5. Approche d’inférence floue
2.2.6. Réseaux de neurones artificiels (RNA)
2.2.7. Segmentation et reconnaissance simultanée
2.2.8. Détection et correction des erreurs
2.3. Interprétation 
2.3.1. La représentation de structure et de syntaxe d’expression mathématique
2.3.1.1. Arbre relationnel (SRT : Symbol Relation Tree)
2.3.1.2. Arbre structurel des lignes de base (BST : Baseline Structure Tree)
2.3.2. Analyse structurelle
2.3.2.1. Les informations spatiales des symboles
2.3.2.2. Relations spatiales
2.3.3. Analyse syntaxique
2.3.3.1. Approche grammaticale
2.3.3.2. Approche graphique
2.4. Optimisation simultanée de la segmentation, la reconnaissance et l’interprétation
2.5. … Vers un reconnaisseur générique des langages 2D : Reconnaissance des schémas
électriques manuscrits en-ligne 
2.6. Conclusion 
Chapitre 3 : Le problème de l’évaluation 
3.1. La base de données d’évaluation : Quoi ? Combien ? Comment ? 
3.2. Un générateur d’expressions mathématiques manuscrites en-ligne (LaTeX2Ink)
3.2.1. Structure du générateur
3.2.1.1. Analyse lexicale de la chaîne LaTeX
3.2.1.2. Analyse syntaxique : création de l’arbre de dérivation
3.2.1.3. Définition des boîtes englobantes
3.2.1.4. Ajout des symboles dans les boîtes englobantes
3.2.2. Protocoles de générations d’une base d’expressions
3.2.2.1. Un corpus d’expressions statiques/dynamiques
3.2.2.2. Une base d’expressions mono-scripteurs vs. avec scripteurs virtuels
3.3. Définition des corpus d’expressions 
3.3.1. Les corpus existants « Garain » et « Aster »
3.3.2. Le corpus « Calculette »
3.3.3. Le corpus « RamanReduced »
3.3.4. Le corpus Wiki_CIEL
3.4. Les bases de symboles/expressions mathématiques manuscrites
3.4.1. Symboles isolés
3.4.1.1. La base CIEL
3.4.1.2. La base IRONOFF
3.4.2. Expressions synthétiques
3.4.2.1. La base calculette
3.4.2.2. La base RamanReduced
3.4.3. Expressions réelles
3.4.3.1. La base RamanReduced Réelle
3.4.3.2. La base Wiki_CIEL
3.5. L’étiquetage de données manuscrites 
3.6. Comment évaluer un système de reconnaissance d’expressions mathématiques 
3.6.1. Mesures quantitatives
3.6.2. Mesures qualitatives
3.7. Conclusion 
Chapitre 4 : Système de reconnaissance d’expressions mathématiques manuscrites en-ligne
4.1. Architecture globale du reconnaisseur d’expressions mathématiques 
4.2. Générateur d’hypothèses de symboles 
4.3. Classifieur de symboles 
4.3.1. Prétraitements
4.3.1.1. Ré-échantillonnage et normalisation
4.3.1.2. Les caractéristiques utilisées pour la reconnaissance
4.3.2. Les réseaux de neurones
4.3.2.1. Le perceptron Multi couches (PMC)
4.3.2.2. Algorithme d’apprentissage
4.3.2.3. Paramétrage du réseau
4.3.2.4. Architecture du réseau de neurones
4.3.2.5. Réseaux de neurones à convolution (TDNN : Time Delayed Neural Network)
4.3.3. Différentes architecture de classifieurs
4.3.3.1. Classifieur de symboles isolés sans rejet
4.3.3.2. Classifieur hybride avec rejet
4.3.3.3. Classifieur global avec rejet
4.4. Apprentissage global du classifieur 
4.5. Représentation d’une expression mathématique manuscrite en-ligne 
4.6. Analyse structurelle 
4.6.1. Coût géométrique
4.6.2. Coût probabiliste
4.6.2.1. Apprentissage des modèles des relations
4.6.2.2. Estimation du coût structurel probabiliste
4.7. Analyse syntaxique (Modèle de langage)
4.8. Bloc de décision 
4.9. Conclusion 
Chapitre 5 : Expérimentations et résultats 
5.1. L’évaluation 
5.1.1. Bases de données
5.1.2. Les mesures d’évaluation
5.1.3. Protocole expérimental
5.1.4. Classifieurs utilisés
5.2. Performances isolées
5.3. Système de référence 
5.4. Optimisation des paramètres du reconnaisseur d’expressions mathématiques 
5.4.1. Optimisation des paramètres β ,δ
5.4.2. Optimisation du nombre de candidats retenus par le classifieur (topN et k)
5.4.3. Optimisation du paramètre α
5.5. Apprentissage global 
5.5.1. Effet du choix du modèle de grammaire pendant l’apprentissage (modèle libre
Vs modèle contraint)
5.5.2. Influence de l’utilisation de scripteurs virtuels
5.5.3. Choix de la stratégie d’apprentissage
5.5.3.1. Apprentissage globo-isolé
5.5.3.2. Apprentissage iso-global / iso en global
5.6. Choix du classifieur de rejet 
5.7. Coût structurel Vs coût probabiliste 
5.7.1. Mesurer la performance de la modélisation structurelle
5.7.2. Résultats
5.8. Au delà de la reconnaissance d’EM : la reconnaissance d’organigrammes manuscrits
en-ligne 
5.8.1. Acquisition des organigrammes
5.8.2. Une base d’organigrammes manuscrits en-ligne
5.8.3. Reconnaissance des symboles isolés
5.8.4. Approche globale d’apprentissage et de reconnaissance
5.9. Conclusion 
5.10. Applications 
5.10.1. Une calculatrice sur iPod
5.10.2. Une interface pour saisir des expressions mathématiques manuscrites
Conclusion et perspectives 
Annexes
Bibliographie

Télécharger le rapport complet