Extrait
Table des Matieres
Liste des figures
Liste des tableaux
Introduction generale
Chapitre 1: Reconnaissance de l’ecriture Manuscrite
1.1. Introduction
1.2. Differents aspects de reconnaissance des chiffres manuscrits
1.2.1. Reconnaissance en-ligne et hors-ligne
1.2.1.1. Reconnaissance en-ligne (on-line)
1.2.1.2. Reconnaissance hors-ligne (off-line)
1.2.2. Reconnaissance des chiffres
1.3. Contraintes des systemes de lecture
1.4. Organisation generate d’un systeme de reconnaissance hors ligne
1.4.1. Phase d’acquisition
1.4.2. Phase de pretraitements
1.4.3. Phase de segmentation :
1.4.4. Phase d’analyse
1.4.4.1. Normalisation
1.4.4.2, Squelettisation
1.4.4.3, Lissage
1.4.4.4. Extraction des caracteristiques
1.4.4.4.1 Les primitives structurelles
1.4.4.4.2 Les primitives statistiques
1.4.4.4.3 Les primitives globales
1.4.4.4.4 Les primitives topologiques ou metriques
1.4.5. Phase de classification
1.4.5.1. Approche statistique
1.4.5.2. Approche structurelle
1.4.5.3. Approche stochastique
1.4.6. Phase de post-traitement
1.5. Methodes de classification
1.5.1. Reseaux de neurones
1.5.2. Support Vecteur Machine (Machines a Vecteurs de Support)
1.6. Conclusion
Chapitre 2: Methodes de segmentation des chiffres manuscrits
2.1. Introduction
2.2. Segmentation primaire : Histogramme de projection
2.3.Segmentation secondaire
2.3.1. Probleme de chevauchement de caracteres
2.3.1.1 Corrections de pente et segmentation
2.3.1.2 Segmentation base sur le contour
2.3.2. Probleme des caracteres connectes
2.3.2.1. Algorithme Drop Fall
2.3.2.2. Algorithme “water reservoir”
2.3.2.3. Algorithme base sur les points interconnexion
2.3.3. Strategie de combinaison
2.3.3.1. Motivation
2.3.3.2. Regies de combinaison
2.4. C onclusion
Chapitre 3: Reseaux de neurones
3.1. Introduction
3.2. Neurone formel
3.3. Perceptron monocouche
3.3.1. Architecture du perceptron
3.3.1. Apprentissage
3.4. Perception multicouches
3.4.1. Architecture du reseau
3.4.2. Phase d'apprentissage
3.5. Conclusion
Chapitre 4: Resultats experimentaux
4.1. Introduction
4.2. complexite de la reconnaissance
4.3. Protocole experimental
4.3.1. Presentation de la base des cheques
4.3.2. Demarche devaluation
4.3.3. Matrice de confusion
4.4. Pretraitements
4.4.1. Extraction de 1 a zone d’interet
4.4.2. Probleme de pixels parasites
4.4.3. Defaut d ’encrage insuffisant
4.5. Evaluation manuelle
4.6. Evaluation du systeme
4.6.1. Description de 1 a base
4.6.2. Normalisation
4.6.3. Dimensionnement du reseau
4.6.4. Evaluation
4.7. Conclusion
Conclusion generale
Annexe
References bibliographiques
Resume
Dans un systeme de reconnaissance numerique d’un cheque bancaire, la phase la plus importante reside dans la separation des chiffres les uns des autres. Cette phase appelee segmentation reste cependant delicate a cause du chevauchement et/ou l’accolement de deux chiffres consecutifs. Pour resoudre ce probleme, plusieurs methodes de segmentation ont ete developpees qui presentent cependant chacune des avantages et des inconvenients. Dans ce travail, nous proposons une nouvelle demarche de segmentation basee sur la combinaison de plusieurs methodes de segmentation selon le type de configuration de chainage entre chiffres. A l’aide de quelques regles, nous definissons les chemins de segmentation afin de trouver le meilleur chemin de separation des chiffres. Trois methodes de segmentation ont ete combinees fondees sur l’histogramme de projection, les contours et les points d’interconnexion. Cette demarche a ete developpee pour etre integree dans un systeme de reconnaissance du montant numerique des cheques bancaires algeriens. Ce systeme est compose de quatre blocs : un bloc de pretraitement pour l’extraction de la zone d’interet, un bloc de segmentation, un bloc de normalisation des chiffres et un bloc de classification qui permet d’affecter le chiffre a une classe predefinie. Les performances de notre strategie ont ete evaluees en termes de taux de bonne reconnaissance en utilisant la matrice de confusion.
Mots Cles: reconnaissance des chiffres manuscrits, segmentation des chiffres manuscrits, reseaux de neurones, cheques bancaires algeriens.
Abstract
In a recognition digital system of the amount bank check, the most important step is the separation of digits from each other. This step called segmentation remains difficult because of overlapping and / or joining two consecutive numbers. To resolve this problem, several methods of segmentation have been developed, however, each one having the advantages and disadvantages. In this work, we propose a new approach to segmentation based on a combination of several methods of segmentation depending on the configuration link between numbers. With the help of a few rules, we define our segmentation paths to find the best way for the separation of digits. Three segmentation methods were combined based on the histogram projection, contours and interconnection points. This approach was developed to be integrated into a recognition system of the amount of digital Algerian checks. This system is composed of four blocks: a block of pre-processing to extract the area of interest, block segmentation, a block of data normalization and classification block that allows assigning a digit image to a predefined class. The performance of our strategy has been evaluated in terms of correct recognition rates using the confusion matrix.
Keywords: recognition of handwritten digits, segmentation of handwritten digits, neural networks, Algerian checks.
Remerciement
Nous remercions Allah de nous avoir donne la volonte et le courage qui nous ont permis de realiser ce travail, veuille t-il nous guider dans le droit chemin.
Nous aimons specialement remercier Mr Y. CHIBANI pour leur grande disponibilite pendant toute la duree de ce travail, pour nous avoir toujours encourage face a la difficulte, mais aussi pour leur gentillesse et leur hospitalite.
Nous remercions aussi les membres de jury pour avoir accepter dejuger notre travail.
Pour terminer, nous remercions toute personne ayant participe de pres ou de
loin pour la realisation de ce travail.
Dedicaces
A me tes ches parents qui ont toujours ete le pour mo, e qui m'ont donne un magnifique modele de labeur et de perseverance et tout mon amour ; A me oncles; A me dies frees e sours;
Je dedie ce memoire.
Liste des Figures
Figure Titre Page
Chapitre 1:
Fig. 1.1. Schema general d’un systeme de reconnaissance de caracteres.
Fig. 1.2. Exemple de deux types de redressement.
Fig. 1.3. Exemple sur la squelettisation.
Fig. 1.4. Division d’une image en zones.
Chapitre 2:
Fig.2.1. Segmentation des chiffres par l’histogramme de projection verticale.
Fig.2.2. Correction de pente et l’histogramme de projection.
Fig.2.3. L'extraction des contours.
Fig.2.4. Segmentation des caracteres en chevauchement.
Fig.2.5. Impossible de separer entre les caracteres connectes.
Fig.2.6 Exemple la segmentation avec un algorithme Drop Fall.
Fig.2.7. Les 4 variantes de l’algorithme « drop fall ».
Fig.2.8. Echec de la segmentation avec une telle initialisation pour un drop fall.
Fig.2.9. Les reservoirs “haut” et les reservoirs "as”.
Fig.2.10. Segmentation “drop fall” ascendant avec initialisation par les reservoirs.
Fig.2.11. Les points elementaires ou les points de base (PBs).
Fig.2.12. Le secteur connecte contenant les PBs et PIs.
Fig.2.13. Procedure de segmentation si PB pres d’un PI.
Fig.2.14. Graphe de segmentation.
Fig.2.15. Chemin de segmentation.
Fig.2.16. Segmentations basees sur le PB seulement.
Fig.2.17. Organigramme de la strategie de combinaison.
Chapitre 3:
Fig.3.1. Le neurone formel.
Fig.3.2. Perceptron monocouche.
Fig.3.3. Perceptron'multicouches.
Chapitre 4:
Fig.4.1. Chaine de traitement pour la reconnaissance numerique des cheques bancaires
Algeriens
Fig.4.2. Different model des cheque.
Fig.4.3. Differents types d’ecriture (a) ecriture en batons, (b) ecriture attachee.
Fig.4.4. Differents types d’ecritures.
Fig.4.5. Principe de recherche des coordonnees de la zone d’interet.
Fig.4.6. Presence des pixels parasites.
Fig.4.7. Exemples de difficulte de la segmentation.
Fig.4.8. Representation de la base.
Fig.4.9. Exemples de chiffres de la base BNA.
Fig.4.10. Transformer le caractere d'original ver un caractere normalise.
Annexe :
Fig.5.1. Fenetre principale.
Fig.5.2. Exemple de selection d’un cheque.
Fig.5.3. Extraction de la zone d'interet.
Fig.5.4. Segmentation basee sur le contour.
Fig.5.5. Segmentation basee sur l’histogramme de projection.
Fig.5.6. Selectionner les chiffres connectes.
Fig.5.7. Segmentation basee sur les points interconnexion.
Fig.5.8. La combinaison.
Fig.5.9. Resolut le probleme des points e les virgules.
Fig.5.10. La phase de classification.
Fig.5.11. La reconnaissance automatique.
Liste des Tableaux
Chapitre 3:
Tableau 3.1 Differentes fonctions du neurone formel
Chapitre
Tableau 4.1 Exemple d'une matrice de confusion
Tableau 4.2 La base des cheques utilises.
Tableau 4.3 Les resultats devaluation manuelle
Tableau 4.4 Les resultats de quatre variantes
Tableau 4.5 Les resultats de la segmentation pour chaque methode de combinaison
Tableau 4.6 Resultats de reconnaissance pour chaque classe
Tableau 4.7 Levaluation manuelle et du systeme
Abbildung in dieser Leseprobe nicht enthalten
INTRODUCTION GENERALE
La reconnaissance automatique de caracteres manuscrits a pour objet de convertir des images qui sont comprehensibles par 1 ’homme, en un code interpretable par un ordinateur.
Deux disciplines peuvent etre degagees: la reconnaissance en-ligne et la reconnaissance hors- ligne. En reconnaissance en ligne, les caracteres sont reconnus quand ils sont ecrits. L'information est monodimensionnelle et dynamique est representee par la trajectoire du stylo. Dans la reconnaissance hors-ligne, au contraire, 1 e processus d’ecriture n’est pas accessible. L’information est bidimensionnelle et consiste en 1’image digitalisee des caracteres. Dans ce travail, nous nous interesserons a la reconnaissance hors-ligne pour la lecture automatique du montant numerique des cheques bancaires Algeriens.
La reconnaissance hors-ligne elle-meme peut etre divisee en deux methodes, en fonction du nombre de personnes dont l'ecriture doit pouvoir etre reconnue. Lorsque ce nombre est limite, le systeme de reconnaissance peut supporter un entrainement specifique sur la base de l'ecriture propre aux personnes concernees. C'est ce qu'on appelle la reconnaissance monoscripteur. Lorsqu’un tel entrainement n'est pas possible parce que les ecritures viennent d'un tres grand nombre de personnes differentes, on parle de reconnaissance multiscripteur. C’est a ce niveau que s ’inscrit c e travail.
La reconnaissance numerique des cheques bancaires Algeriens s’effectue essentiellement en trois etapes. La premiere etape consiste a analyser le cheque brute fournie par un peripherique de digitalisation doit s’effectuer a relativement a haute resolution de maniere a ootenir une bonne qualite de representation des caracteres et assurer ainsi qu’une procedure efficace de reconnaissance puisse etre menee. La segmentation permet de localiser et isoler les caracteres les uns des autres. Afin de mieux representer 1 ’information portee par 1 e chiffre, une phase d’extraction des caracteristiques ou primitives est executee. Celle-ci permet de reduire l’information. La derniere etape consiste a affecter chaque chiffre a une classe predefinie.
Dans ce travail, nous nous interessons plus specifiquement a la segmentation des chiffres manuscrits. Aussi, plusieurs methode ont ete developpees qui presentent chacune des avantage est des inconvenients. De maniere generale, la segmentation des chiffres se deroule en deux etapes : segmentation primaire et segmentation secondaire. La segmentation primaire est une methode de separation de caracteres qui s’appuie sur le principe de l’histogramme de projection tandis que la segmentation secondaire est executee dans le cas des chiffres en chevauchement ou connectes. Pour la segmentation du chiffre en
chevauchement deux methodes sont generalement utilisees :
- Methode basee sur la correction de pente qui consiste a calculer la divergence entre la ligne de point de base et 1 a direction de passage par zero de l’histogramme de projection angulaire correspondant.
- Methode basee sur le contour qui consiste a selectionner chaque contour de caractere separement en utilisant une distance puis separer individuellement avec une distance fixee par un seuil.
Tandis que, les methodes de segmentation des chiffres connectes reposent sur la recherche du meilleur chemin de separations pour isoler deux chiffres contigus. Pour cela, trois methodes ont ete selectionnees basees sur les algorithmes « Drop Fall », « Water reservoir » et 1 es points d’interconnexion.
- Algorithme Drop Fall consiste a segmenter la composante selon le chemin emprunte par une goutte d’eau qui coulerait s el on les contours de la composante. Lorsque la goutte est bloquee au fond d’une vallee, celle-ci coupe la composante et continue sa chute.
- Algorithme Water Reservoir (Reservoir d’eau) est une amelioration de 1’algorithme
Drop Fall qui consiste a choisir le meilleur point de depart pour 1 a goutte d’eau de l’algorithme Drop fall en evitant 1 es minimums 1 ocaux.
- Les points d’interconnexion cherchent a analyser le nombre et la nature des points d’interconnexion entre les caracteres pour definir la position de coupure optimale pour separer un couple de caracteres.
Ce travail est organise en quatre chapitres. Le premier chapitre peut etre considere comme une introduction a la reconnaissance de 1 ’ecriture manuscrite. Nous presentons les differents modules du schema standard de reconnaissance des chiffres manuscrits en mettant l'accent sur le role de chacun des modules du systeme de reconnaissance.
Le deuxieme chapitre est consacre a la presentation des differentes methodes de segmentation pour lesquelles nous presentons les avantages et les inconvenients de chacune d’elle. Par la suite, nous decrivons la strategie de combinaison entre differentes methodes de segmentation pour chercher le meilleurs chemin de separation afin d’isoler au mieux les chiffres les uns des autres.
Le troisieme chapitre decrit le classifieur utilise fonde sur les reseaux de neurones avec ses differentes architectures.
Le quatrieme chapitre decrit les differentes experiences realisees sur une base de donnees de chiffres manuscrits des montants du cheque de la Banque National d’Algerie. Dans une premiere etape, les differentes methodes sont evaluees manuellement sur les cheque bancaire poor apprecier 1 ’apport de chaque methode de segmentation. La deuxieme etape portera sur 1’evaluation du systeme complet incluant le classifieur base sur les reseaux de neurones.
Dans la conclusion, nous rappelons l'objectif du travail, les resultats obtenus ainsi que les perspectives de ce travail.
Chapitre 1:
La reconnaissance de l’ecriture manuscrite
Resume :
La reconnaissance de l'ecriture manuscrite est un traitement informatique qui a pour but de traduire un texte ecrit en un texte code numeriquement. Dans ce chapitre, nous presentons d’une maniere generale les differents modules qui permettent la reconnaissance des chiffres manuscrits . Le systeme de reconnaissance s'articule autour de quatre modules distincts. Un module de pretraitements, un module de segmentation, un module d’analyse et un module de classification suivis eventuellement d ’un module de post-traitement.
1.1 Introduction
La 1 ecture automatique de 1 ’ecriture manuscrite a ete des domaines de recherches actives. En effet, de nombreuses publications ont realise a ce sujet,[5] [12] [16] [18] [20] [30] [31] [33] [38]. II presente un interet indeniable dans 1 ’accomplissement des taches fastidieuses comme celles que l’on rencontre dans certains domaines : la lecture de cheques bancaires, le tri postal, la lecture des bordereaux, des bons de commande, des feuilles declaration...
Dans le domaine de la reconnaissance, il faut faire une nette distinction entre un texte imprime ou dactylographie et un texte manuscrit. Si dans le premier cas, on peut considerer que les principales difficultes ont ete surmontees, la situation est entierement differente en ce qui
concerne la reconnaissance d'un manuscrit que nous presenterons dans ce present chapitre pour le cas des chiffres, ou les difficultes resteront celles de la variabilite de l'ecriture[19] [32].
Nous presentons dans ce chapitre les differentes phases de reconnaissance des chiffres manuscrits en mettant l'accent sur toutes les phases du systeme de reconnaissance.
1.2 Differents aspects de reconnaissance
II n’existe pas de systeme universel de reconnaissance des chiffres manuscrits qui permet de reconnaitre n’importe quel caractere dans n’importe quelle police de caractere. Tout depend du type de donnees traitees et b ien evidemment de 1 ’application visee. I 1 existe plusieurs modes de
classification des systemes de reconnaissance des chiffres manuscrits parmi lesquels on peut citer[10]:
- Les systemes qualifies de « en-ligne » ou « hors-ligne » suivant 1 e mode d’ acquisition.
- Les approches globales ou analytiques s el on que 1 ’analyse s’opere sur la totalite du mot, ou par segmentation en caracteres.
- Les approches statistiques, structurelles ou stochastiques relatives aux traits caracteristiques extraits des formes considerees.
1.2.1 Reconnaissance en-ligne et hors-ligne
La saisie des caracteres manuscrits y est faite selon deux modes : en-ligne ou hors-ligne. Chaque mode a ses propres outils d’aquisition et ses algorithmes correspondants de reconnaissance. Les systemes en-ligne prennent en compte l information chronologique des mouvements du bras du scripteur tandis que les systeme hors ligne traitent 1 ’information en differe independament du temps.
1.2.1.1 Reconnaissances en-ligne (on-line)
Ce mode de reconnaissance s ’opere en temps reel (pendant 1 ’ecriture) c ’est a dire l'echantillon d'encre est constitue d'un ensemble de coordonnees ordonnees dans le temps. Il est ainsi possible de suivre le trace, de connaitre les poses et leves de stylo et eventuellement l'inclinaison et la vitesse. C’est 1 e cas notamment d es stylos numeriques ou des stylets sur agendas electroniques ou sur les Tablets PC. Les symboles sont reconnus au fur et a mesure qu’ils sont ecrits a la main. Ce mode est reserve generalement a l’ecriture manuscrite. C’est une approche « signal » ou la reconnaissance est effectuee sur des donnees a une dimension[1]. L’ecriture est representee comme un ensemble de points dont les coordonnees sont fonction du temps[25].
La reconnaissance en-ligne presente un grand avantage dans la possibilite de correction et de modification de l'ecriture de maniere interactive vu la reponse en continu du systeme.[24].
1.2.1.2 Reconnaissances hors-ligne (off-line)
La reconnaissance hors-ligne s’execute sur une image d’un document numerise. Dans ce contexte, il est impossible de savoir comment ont ete traces les differents motifs. Il est seulement possible d'extraire des formes a partir de l'image (Elle convient aux documents imprimes et les manuscrits deja rediges, apres 1 ’acquisition), en s'appuyant sur les technologies de reconnaissance de forme.
Ce mode peut etre considere comme le cas le plus general de la reconnaissance de 1 ’ecriture. L’interpretation de 1 ’information est independante de la source de generation[39].
1.2.2 Reconnaissance des Chiffres
Qualifie de hors-ligne, la reconnaissance des dix (10) chiffres manuscrits n'est pas encore parfaitement resolue bien que l'on sache atteindre des taux de reconnaissance superieure a 90% dans diverses applications telsque bancaires ou postales,. Dans ce cas, il s'agit de realiser un systeme pour lire le montant d'un cheque ou pour lire une adresse postale sur une enveloppe.
1.3 Contraintes des systemes de lecture
La tache de la reconnaissance des chiffres manuscrits n’est pas aisee, divers problemes compliquent le processus de reconnaissance, parmi lesquels on peut citer[1] [6] [10]:
- La qualite du document : un document telecopie ou photocopie plusieurs fois est plus difficile a traiter que la copie originate. L’ecriture peut devenir plus mince ou au contraire plus epaisse.
- La discrimination de la forme : selon le style de la fonte utilisee, son corps et sa graisse..., le caractere change de graphisme. Le nombre de formes est d’autant plus important que 1 e nombre de styles d’ecriture est e leve.
- Le support de l’information, tel que le papier, joue egalement sur les performances de la reconnaissance par sa qualite : son grammage, sa granulation et sa couleur.
- L ’acquisition : la numerisation en temps reel introduit souvent des anormalites dans l image. Dans notre cas (hors-ligne) la qualite du texte numerise est un compromis entre les variations de la position (inclinaison, translation, retrecissement...), la proprete de 1 a vitre du dispositif de numerisation et sa resolution (La resolution plus grande done le resultat plus satisfait).
En plus de ces problemes, un systeme de reconnaissance des chiffres manuscrits devrait etre capable de distinguer entre un texte et une figure, de reconnaitre les caracteres attaches et d’etre independant des variations de 1 ’espace aussi bien inter-mots que de 1 ’interligne.
1.4 Organisation generale d’un systeme de reconnaissance hors ligne
Un systeme de reconnaissance fait appel generalement aux etapes suivantes : Acquisition, pretraitements, segmentation, extraction des caracteristiques, classification, suivis eventuellement d’une phase de post-traitement (Fig. 1.1).
Abbildung in dieser Leseprobe nicht enthalten
Fig. 1.1 : Schema general d’un systeme de reconnaissance de caracteres modifie selon[7].
1.4.1 Phase d'acquisition
La phase d’acquisition consiste a capter 1 ’image d’un texte au moyen des capteurs physiques (scanner, camera,...) et d e la convert en elevations numeriques adaptes au systeme de traitement, avec un minimum de degradation possible. Durant cette phase, malgre la bonne qualite des systemes d’acquisition , des bruits parasites peuvent apparaitre et causer une heterogenite du fond . Ceci est du a la nature de la texture, l'aire de travail et de son eclairage.
1.4.2 Phase de pretraitements
Le pretraitement consiste essentiellement a reduire le bruit superpose aux donnees et essayer de ne garder que l information significative de la forme representee. Le bruit peut etre du aux conditions d’acquisition (eclairage, mise i ncorrecte du document, ...) ou encore a 1 a qualite du document d ’origine.
L’un des problemes rencontres en la reconnaissance des caracteres manuscrits est 1 ’ inclinaison des 1 ignes du texte, qui introduit des difficultes pour 1 a s egmentation. L’inclinaison peut provenir de la saisie, si le document a ete place en biais, ou etre intrinseque au texte. Il convient alors de le redresser afin de retrouver la structure de 1 ignes horizontales d’une image texte. Nous pouvons distinguer deux types de redressement[7]:
- Le redressement de la ligne de base. L'idee est de rendre horizontaux les mots a l'aide d'une transformation geometrique de type rotation isometrique des points de l'image (voir Fig. 1.2.a). Si a est 1 ’angle d’inclinaison, pour redresser 1 ’image, une rotation isometrique d’angle - a est operee grace a la transformation lineaire (par exemple La transformation de Hook) suivante[37]:
Abbildung in dieser Leseprobe nicht enthalten
- Le redressement des ecritures penchees. Cette technique facilite la segmentation prealable des mots en caracteres. L'idee est de trouver l'angle moyen d'inclinaison puis de faire une transformation geometrique de type cisaillement de l'image (voir Fig. 1.2.b).
Abbildung in dieser Leseprobe nicht enthalten
Fig. 1.2: Exemple de deux types de redressement.
1.4.3 Phase de segmentation
La s egmentation des chiffres manuscrits en elements i soles est 1 ’etape 1 a plus difficile dans un systeme de reconnaissance du montant numerique d’un cheque bancaire. Le but de cette etape en general est de generer un decoupage de 1 ’image en elements susceptibles d’etre reconnus par le classifieur[4]. Cette phase est la plus importante dans le processus de reconnaissance et permet la separation des chiffres les uns des autres. Deux approches sont possibles pour la segmentation : la segmentation dite explicite, et la segmentation dite implicite.
- Segmentation explicite: ou discrete s’effectue par la recherche du meilleur chemin pour separer les chiffres les uns des autres avant la reconnaissance.[13]
- Segmentation implicite: ou continue considere tous les points du trace comme points de segmentation potentiels. La segmentation et la reconnaissance sont realisees conjointement. Cette approche ne cherche pas a separer les chiffres mais plutot a les integrer implicitement dans le module de reconnaissance.[13]
Dans notre cas, la segmentation explicite a ete adoptee pour la reconnaissance des chiffres manuscrits.
1.4.4 Phase d'analyse
C’est l’une des etapes les plus delicates et les plus importantes en reconnaissance des caracteres manuscrits. La reconnaissance d’un caractere passe d’abord par 1 ’analyse de sa forme et 1’extraction de ses traits caracteristiques (primitives) qui seront exploites pour son identification.
Parmi les operations d’analyse generalement utilisees, nous pouvons citer :
- La normalisation
- La squelettisation
- Le lissage
- L’extraction de caracteristiques
1.4.4.1 Normalisation
La normalisation permet de ramener les images de chiffres a des tailles standard. Cette phase peut etre indispensable pour certains classifieurs comme les reseaux de neurones. Apres la normalisation de la taille, les images de tous les caracteres se trouvent definies dans une matrice de meme taille, pour faciliter les traitements ulterieurs. Cependant cette operation introduit generalement de legeres deformations sur les images des chiffres differents methodes de normalisation peuvent etre utilisees pour garder l’aspect initial du chiffre.[37]
1.4.4.2 Squelettisation :
La squelettisation est une operation souvent utilisee en modelisation ou en representation de l'ecriture manuscrite. Le but de cette technique est de simplifier 1 ’image du caractere en une image a « ligne » plus facile a traiter en la reduisant au trace du caractere.
La squelettisation sert a obtenir une epaisseur egale a 1 pixel du trait d'ecriture et de se ramener ainsi a une ecriture lineaire[7].Les algorithmes de squelettisation se basent sur des methodes iteratives. Le processus s’effectue par passes successives pour determiner si un tel ou tel pixel est essentiel pour le garder ou non dans le trace[37].
Squelettisation. Detection des points sinsuliers.
Caractere Squelette
Fig. 1.3: Exemple de squelettisation.
1.4.4.3 Lissage :
Le lissage permet d e reduire au maximum les discontinuites i ntroduites dans 1 ’image au cours des differentes transformations et ainsi de retablir la regularity et la continuity du contour du caractere[21]. Le lissage consiste a examiner 1 e voisinage d’un pixel et de lui attribuer la valeur 1 si le nombre de pixel noir dans cette zone est superieur a un seuil.
L’operation de nettoyage permet de supprimer 1 es petites taches et 1 es excroissances de la forme. Pour le bouchage il s ’agit d’egaliser les contours et de boucher les trous internes a la forme du caractere en lui ajoutant des points noirs.
Selon la qualite du document a traiter, le type de 1 ’ecriture et la methode d’analyse adoptee, une ou plusieurs techniques de pretraitement sont utilisees.
1.4.4.4 Extraction des caracteristiques
L’objectif de 1 ’extraction des caracteristiques dans 1 e domaine de la reconnaissance consiste a exprimer les primitives sous une forme numerique ou symbolique appelee codage[9].Le caractere est observe dans une matrice de points dont on extrait les caracteristiques qui se pretent le mieux a une description mathematique.
Les types de caracteristiques peuvent etre classes en quatre categories principales de primitives: structurelles, statistiques, globales (transformations globales) et topologiques ou metriques[1] [17].
1.4.4.4.1 Les primitives structurelles:
Les primitives structurelles (ou primitives locales) basees sur une representation lineaire du caractere (decomposition du caractere en segments de droites et courbes, contours du caractere, squelette)[9].
Les primitives structurelles sont generalement extraites non pas de l'image brute, mais a partir d'une representation de la forme par le squelette ou par le contour[17]. Ainsi, parmi ces caracteristiques, il s'agit principalement des segments de droite, des arcs, boucles et concavites, des pentes, la hauteur et la largeur du caractere...
1.4.4.4.2 Les primitives statistiques :
Elles portent une information sur la distribution des pixels dans l'image du caractere ou chiffres, Les primitives statistiques decrivent une forme en termes d'un ensemble de mesures extraites a partir de cette forme. Les caracteristiques utilisees pour la reconnaissance des chiffres manuscrits sont:
- Le zonage (zoning) : consiste a partager 1 ’image en region ou zones[9], L’image de depart est une image binaire de taille N x M. Pour chacune des regions resultantes, il s’agit de calculer la moyenne ou le pourcentage de points en niveaux de gris.
Abbildung in dieser Leseprobe nicht enthalten
- L'histogramme representant le nombre de pixels sur chaque ligne ou colonne de l'image, en est un exemple classique et simple a calculer histogramme directionnel, histogramme des transitions ...),
Il est possible egalement d’utiliser aussi une autre primitive statistique basee sur un moyennage des pixels situes a l'interieur d'un masque rectangulaire. La construction d'une matrice de masque recouvrant la totalite de la forme permet une representation statistique a partir d'un nombre tres reduit de valeurs correspondant a chaque masque[17].
1.4.4.4.3 Les primitives globales :
Les primitives globales sont naturellement basees sur une transformation globale de l'image. La caracteristique d'une primitive globale est de dependre de la totalite des pixels d'une image[17], ces primitives sont donc derivees de la distribution des pixels. Ils dirigent trois familles de caracteristiques telles que : les moments invariants, les projections et les profils.[10]
Une des transformations les plus simples est celle qui represente le squelette ou le contour d’un caractere sous forme d’une chame de codes de directions[1]. Parmi les methodes de transformation, nous pouvons citer les transformees de Hough et de Fourier.
1.4.4.4.4 Les primitives topologiques ou metriques :
La topologie est 1 ’etude des proprietes de 1 ’espace (et des ensembles) du seul point qualitatif.
II s ’agit d’effectuer une mesure sur l'echantillon au moyen d’une metrique . Parmi les mesures, nous pouvons citer[17]:
- compter le nombre de trous,
- evaluer les concavites,
- mesurer des pentes et autres parametres de courbures et evaluer des orientations principales,
- mesurer la longueur et l'epaisseur des traits,
- detecter les croisements et les jonctions des traits,
- mesurer les surfaces, les perimetres,
- determiner le rectangle delimitant l'echantillon, ou le polygone convexe,
- evaluer le rapport d'elongation (ou allongement) longueur/largeur, ...
- rendre compte de la disposition relative de ces primitives.
Toutes ces mesures peuvent etre integrer dans un seul vecteur caracteristique pour la reconnaissance du chiffre manuscrit.
1.4.5 Phase de classification
La classification est l’elaboration d’une regie de decision qui transforme les attributs caracterisant les formes en appartenance a une classe par un critere de decision[9]. Le terme classification regroupe en fait trois approches qui impliquent des strategies differentes[2].
- classification supervisee: cette technique est basee sur 1 ’etiquetage des observations en affectant chaque observation a une classe.
- classification semi supervisee : c ette technique est basee sur 1 ’etiquetage d’une partie des observations.
- classification non supervisee : aucune des observations n’est etiquetee.
Il est sur que la complexite de la tache est croissante avec le nombre de donnees non etiquetees. Dans le cas de la reconnaissance des chiffres manuscrits, la classification supervisee a ete adoptee car elle simplifie considerablement le probleme. Elle se deroule en deux etapes :
- etape d’apprentissage : elle consiste a apprendre au classifieur des formes connues pour caracteriser les classes[9].
- etape de Reconnaissance et decision : elle cherche parmi les modeles de reference en presence, ceux qui lui sont les plus proches. Le probleme revient a affecter une forme inconnue a 1 ’une des classes obtenues pendant 1 ’apprentissage[1]. Le resultat de la decision est un « avis » sur l'appartenance ou non de la forme aux modeles de l'apprentissage.[8] [36]
La reconnaissance peut conduire a :
- Un succes si la reponse est unique (un seul modele repond a la description de la forme du caractere).
- Une confusion si la reponse est multiple (plusieurs modeles correspondent a la description).
- Un rejet de la forme si aucun modele ne correspond a sa description.
Dans les deux premiers cas, la decision peut etre accompagnee d’une mesure de vraisemblance, appelee aussi score ou taux de reconnaissance[10]. Les approches de reconnaissance peuvent etre regroupees en quatre groupes principaux : 1 ’approche statistique, 1 ’approche structurelle, l’approche stochastique et 1 ’approche hybride.
1.4.5.1 Approche statistique
La reconnaissance est fondee sur 1 ’etude statistique des mesures que l’on effectue sur 1 es formes a reconnaitre[10]. Elle a besoin d’un nombre eleve d’exemples afin de realiser un apprentissage correct des lois de probability des differentes classes. L’etude de 1 eur repartition dans un espace metrique et la caracterisation statistique des classes permet de prendre une decision du type : p lus forte probability d’appartenance a une classe. Cette approche beneficie des methodes d’apprentissage automatique qui s’appuient sur des bases theoriques connues telles que :
- Les methodes parametriques (la regle de Bayes, les reseaux de neurones, les chaines de Markov...)[10] [19]
- Les methodes non parametriques (methode des k plus proches voisins, ... )[8] [10]
1.4.5.2 Approche structurelle
Les methodes structurelles reposent sur 1 ’extraction de primitives en prenant compte de l information structurelle (la structure physique des caracteres)[9]. De maniere generale, les approches syntaxiques ou structurelles permettent la description de formes complexes a partir de formes elementaires. La difference principale entre ces methodes et les methodes statistiques est que ces caracteristiques sont des formes elementaires (les primitives sont de type topologiques) et non pas des mesures[21]. On distingue plusieurs techniques telles que les structures de graphes, les structures syntaxiques, le calcul de distance d’edition entre deux chaines et la programmation dynamique, les methodes de tests, la comparaison de chaines,...
1.4.5.3 Approche stochastique
L’approche stochastique utilise un modele pour la reconnaissance, prenant en compte la grande variabilite de la forme. Dans ce type d’approche, les modeles sont souvent discrets et de nombreux travaux reposent sur la theorie des champs de Markov et l'estimation bayesienne. Les champs de Markov permettent de ramener des proprietes globales a des contraintes locales. Le modele decrit ces etats a l’aide de probabilites de transitions d’etats et de probabilites d’observation par etat. La comparaison consiste a chercher dans ce graphe d’etat, le chemin de probabilite forte correspondant a une suite d’elements observes dans la chame d’entree.[10]. Les methodes les plus repondues dans cette approche sont les methodes utilisant les modeles de Markov caches (HMM).
1.4.6 Phase de post-traitement
L’objectif du post-traitement est 1 ’amelioration du taux de reconnaissance des lettres ou des chiffres ou des mots. Comme la classification peut aboutir a plusieurs candidats possibles, le post-traitement se charge egalement de verifier si la reponse est correcte (meme si elle est unique) en se basant sur d’autres informations non disponibles au classifieur. Cette etape permet de reduire considerablement des erreurs[15].
1.5 Methodes de classification statistiques
L’approche statistique a ete retenue pour la reconnaissance des chiffre qui s ’appuient s ur des bases theoriques telles les methodes parametriques. Parmi les methodes de classification qui ont ete developpees dans ce contexte (machine d'apprentissage), nous distinguons par exemple les reseaux de neurones et les machines a vecteurs de support (SVM : Support Vector Machines).
1.5.1 Reseaux de neurones
Un reseau de neurones est un assemblage de neurones connectes entre eux. Un reseau realise une ou plusieurs fonctions algebriques de ses entrees, par composition des fonctions realisees par chacun des neurones. La capacite de traitement de ce reseau est stockee sous forme de poids d'interconnexions obtenus par un processus d'apprentissage a partir d'un ensemble d'exemples d'apprentissage. Cette methode de classification a ete retenue dans notre systeme et sera explicitee plus en detail au chapitre 4.
1.5.2 Support Vecteur Machine (Machines a Vecteur de Support)
SVM est une methode issue recemment d'une formulation de la theorie de l'apprentissage statistique due en grande partie a l'ouvrage de Vapnik en 1995 intitule the nature of Learning theory[41]. Cette theorie impose que le nombre de parametres soit lineairement lie au nombre des donnees d'apprentissage. L'avantage principal provient du fait qu'il y a peu de parametres a regler comparativement aux reseaux de neurones.
[...]