Chargement...

Combinaison de méthodes de segmentation explicite pour la reconnaissance automatique des chiffres manuscrits

Travail de Recherche 2010 9 Pages

Informatique - Intelligence artificielle

Extrait

1 Introduction

La reconnaissance de l'ecriture manuscrite interesse de nombreux domaines d’applications tels que le tri automatique du courier postal, le traitement automatique des dossiers administrates, ou encore l'enregistrement automatique du montant des cheques bancaires.

D’une maniere generate, la reconnaissance automatique de l’ecriture manuscrite s’effectue essentiellement en plusieurs etapes. La premiere etape concerne le pretraitement qui permet d’eliminer les defauts indesirables par une operation de filtrage (Trier et al, 1995). Cette etape est indispensable car elle permet de faciliter les traitements ulterieurs (lissage ou redressement des caracteres, homogeneisation de l'epaisseur du trait, etc.). La deuxieme etape est la segmentation dont l’objectif est la separation des chiffres les uns des autres, (Vellasques et al, 2008), (Jang et al, 1992), (Shridhar et al, 1986), (Shi et al, 1996). Elle consiste a decomposer le texte en symboles elementaires dont le nombre limite definit les classes distinctes possibles, rendant ainsi plus aisee la tache du systeme de classification. Afin de reduire la dimension de representation, et, ce faisant, rendre plus facile la conception du systeme de classification, une etape de codage de l’image est necessaire et consiste a extraire des caracteristiques en vue d’une meilleure description du symbole. La prise de decision s'effectue a l'aide d'un classifieur qui se prononce sur l'appartenance de la forme a une ou plusieurs classes de caracteres. (Vellasques et al, 2008)

La segmentation constitue l'etape la plus difficile, car liee a plusieurs facteurs tels que l’inclinaison des chiffres, le chevauchement de deux chiffres ou la jonction de deux chiffres consecutifs ainsi que le defaut d’encrage. La segmentation peut etre effectuee en tenant compte de trois situations suivantes: chiffres distincts, chiffres chevauches ou chiffres connectes. Dans la plupart des cas, les chiffres chevauches et lies sont les situations les plus frequemment observees. Ainsi, de nombreux algorithmes ont ete proposes pour separer les couples de chiffres contigus. Certains sont bases sur les contours et d'autres sur le squelette ou sur la taille, le nombre et la position du reservoir d'eau pour en deduire les points potentiels de decoupage (Ayat et al, 2000), (Dimauro et al, 1997), (Congedo et al, 1995).

Dans cet article, nous nous interessons a la segmentation des chiffres manuscrits connectes et/ou chevauches, ou nous tentons d’ameliorer les performances par une combinaison de plusieurs methodes de segmentation. Afin de proposer le meilleur chemin de coupure lorsque les caracteres sont naturellement lies, trois methodes ont ete selectionnees pour etre combinees : segmentation basee sur l’histogramme de projection, segmentation basee sur l’analyse de contours et segmentation basee sur les points d’interconnexion.

L’article est donc organise comme suit. Dans la section 2, nous presentons les trois methodes de segmentation utilisees ainsi que l’algorithme de combinaison. Les resultats obtenus sont presentes dans la section 3. Une conclusion ainsi que perspectives de ce travail sont presentees dans la section 4.

2 Methodes De Segmentation

L’etape de segmentation consiste a etablir une strategie permettant de selectionner le meilleur chemin de coupure pour isoler les chiffres (Ayat et al, 2000), (Hussein et al, 1999). Ces derniers se presentent avec differentes formes ou les chiffres peuvent etre isoles, deformes, lies par un ou plusieurs points de contact, partiellement superposes, ou au contraire en plusieurs morceaux. En outre, plusieurs facteurs tels que la variabilite du style et de l’outil d’ecriture augmente la complexite de segmentation. La figure 1 illustre quelques exemples de chiffres connectes ou chevauches.

Pour trouver tous les chemins possibles de segmentation, nous proposons de combiner trois methodes basees sur la projection de l'histogramme verticale, points d'interconnexion et analyse des contours. Nous passons en revue dans cette section les trois methodes utilisees pour la combinaison.

Abbildung in dieser Leseprobe nicht enthalten

FIG. 1 - Quelques exemples difficiles a segmenter (Base NIST SD19)

2.1. Segmentation basee sur I’histogramme de projection verticale

La segmentation basee sur l'histogramme de projection verticale (HPV) est utilisee quand les chiffres sont naturellement separes (non connectes ou chevauches). Le HPV est applique sur l'image binaire, qui consiste a localiser les chiffres en recherchant les plages correspondant a un nombre de pixels noirs non nuls. La separation des chiffres contigus consiste a detecter les passages par zero de l’histogramme de projection (Fujisawa et al, 1996). On peut alors determiner l'emplacement de chaque chiffre de l'image. L’avantage de cette methode est qu’elle permet de realiser une segmentation sans connaissance a priori des images des chiffres. En revanche, son inconvenient majeur est qu’elle ne permet pas d’isoler les caracteres lorsqu’ils sont connectes ou en chevauchement. De plus, cette methode est tres sensible a la rotation et a la variabilite du style d’ecriture (ecriture detachee). La figure 2 illustre un exemple de mauvaise segmentation lorsque les chiffres sont en chevauchement du a une ecriture oblique.

Abbildung in dieser Leseprobe nicht enthalten

FIG. 2- Segmentation des chiffres par l’histogramme de projection verticale (Base NIST SD19)

2.2. Segmentation basee sur les points d’interconnexion

Cette methode, proposee recemment, consiste a analyser le nombre et la nature des points d'interconnexion entre les deux chiffres adjacents afin de definir la position de coupure optimale pour separer un couple de caracteres (Vellasques et al, 2008). La premiere etape consiste a definir les points d'intersection (PI) et les points de bases (PB) a partir duquel la segmentation pourra demarrer. Les PB sont obtenus a partir des extrema (minima et maxima) locaux detectes sur le profil des composants connectes. Ainsi, les PI sont extraits en appliquant le code de Freeman sur le squelette selon les 8 directions dans le sens des aiguilles d'une montre. Souvent, les points de raccordement contiennent les PI, les PB ou toutes les deux a la fois. Donc, trois hypotheses peuvent etre envisagees pour la segmentation optimale :

- Hypothese 1 : Si la distance Euclidienne entre la projection du PB et le PI est inferieure a un seuil, la coupure est effectuee dans le voisinage du PI (Figure.3.a).
- Hypothese 2 : si le segment inferieur de PI est lie a un segment superieur du PI (ou vice-versa) et les deux PI sont pres de BP, le chemin squelettique liant les deux PI (chemin squelettique) est utilise en tant qu'element de la coupe de segmentation avec des chemins complementaires qui sont traces entre les PB et les PI (chemin compose) (Figure .3.b).

Combinaison de méthodes de segmentation pour la reconnaissance des chiffres

- Hypothèse 3 : Dans certains cas, même s'il y a une connexion entre deux chiffres, le chemin squelettique n'a aucun PI. Pour éviter la sous-segmentation (le manque de point de segmentation), l'algorithme construit un chemin de segmentation basé sur la projection verticale du PB (Figure.3.c).

Abbildung in dieser Leseprobe nicht enthalten

FIG. 3– Chemins de segmentation selon des positions de PI et de PB (a) Hypothèse 1 (b) Hypothèse 2 (c) Hypothèse 3

Lorsque deux chiffres adjacents se chevauchent, PB et PI ne sont pas definis. En consequence, la segmentation n'est pas possible.

2.3. Segmentation basee sur les contours

La segmentation fondee sur les contours est utilisee lorsque des caracteres consecutifs ne sont pas lies mais se chevauchent. Il permet de separer les caracteres en utilisant des informations sur le contour. L'extraction des contours se fait sur des images binaires en utilisant la morphologie mathematique. Chaque caractere est isole en utilisant une distance pour resoudre les problemes de chevauchement entre les caracteres. La Figure 4 illustre un exemple de chiffres en chevauchement. Cependant, cette methode ne permet pas la separation les chiffres lorsque ceux-ci sont connectes.

3 Strategic de Combinaison

L'utilisation d'une seule methode de segmentation ne permet pas de separer correctement les chiffres consecutifs. Par consequent, une combinaison de plusieurs methodes constitue une approche simple pour ameliorer la reconnaissance. Cette segmentation peut etre realisee en deux etapes :

- La premiere etape consiste a detecter si deux chiffres consecutifs sont naturellement separes. Pour cela, le HPV est utilise, qui consiste a evaluer la largeur de l'image de chiffres. Lorsque la largeur est superieure a un seuil T1, l'image numerique contient plus d'un chiffre. Sinon, elle contient un chiffre et donc la separation est realisee par la detection du passage par zero.
- La deuxieme etape consiste a detecter la presence de PI. Si le PI est detecte, la coupe est realisee dans la proximite du PI quand la distance euclidienne entre le PI et le PB est inferieure a un seuil T2. Si aucun PI n’est detecte, cela renseigne que deux chiffres consecutifs sont en chevauchent. Par consequent, l'analyse des contours est executee afin de separer les deux chiffres.

Ce processus est repete jusqu'a ce que tous les chiffres consecutifs soient segmentes.

Les seuils T1 et T2 sont determinees a partir de l’analyse de la base de donnees des chiffres manuscrits. Le seuil T1 est defini en cherchant la distance minimale entre deux chiffres consecutifs non connectes et non chevauches. Par contre le seuil T2 est determine en cherchant la distance euclidienne maximale entre PI et PB dans le cas des chiffres connectes.

4 Evaluation de la segmentation

L'evaluation d'une methode de segmentation est tres souvent subjective. Elle peut se faire en deux etapes. La premiere a pour objet d’evaluer la segmentation en se basant sur la connaissance a priori par rapport aux effets de segmentation. La deuxieme etape consiste a evaluer le systeme de reconnaissance des chiffres manuscrits en integrant la segmentation et la classification. Dans notre cas, nous utilisons ces deux modes devaluation pour apprecier la qualite de la segmentation sur une base de donnees standard NIST SD19 (Grother, 1995).

4.1. Evaluation manuelle

La base NIST SD19 est subdivisee en deux parties : la premiere composee de 5000 chiffres est utilisee pour l’apprentissage et la deuxieme de 500 chiffres est utilisee pour le test. La base de test contient 250 chiffres lies entre eux.

L'evaluation manuelle consiste a exprimer le nombre de chiffres correctement segmentes sur le nombre total de chiffres pour obtenir le taux de bonne segmentation (TS), qui est defini comme suit :

Abbildung in dieser Leseprobe nicht enthalten

Combinaison de méthodes de segmentation pour la reconnaissance des chiffres

Pour evaluer la qualite de la segmentation, nous calculons le TS pour chaque chiffre et pour chaque methode de segmentation : l'histogramme de projection verticale (HPV), l'analyse des Contours (AC), points d'interconnexion (PI) et la combinaison de methodes de segmentation (CMS). Les seuils T1 et T2 sont, respectivement, fixes a 44 et 7. Cette evaluation est reportee dans le tableau 1. Nous reportons egalement le Taux Global de Segmentation (TGS) obtenu pour chaque methode.

Abbildung in dieser Leseprobe nicht enthalten

TAB. 1 - Taux de segmentation obtenuspour chaque methode de segmentation

Lors de l'examen des resultats, nous pouvons noter que la CMS ameliore considerablement la segmentation. En revanche, l’examen de chacun des chiffres montre que la segmentation de '0 'et '6' fournit un resultat inferieur par rapport aux autres chiffres. Ce resultat est cependant previsible puisque plusieurs '0 'et '6' sont connectes ou chevauches. La strategie proposee est en mesure de fournir la bonne segmentation dans la plupart des cas. Toutefois, dans certains cas, cet algorithme ne permet pas de segmenter en raison de l’absence d’un chemin de segmentation.

4.2. Evaluation du systeme

L’evaluation du systeme permet de fournir le taux de bonne reconnaissance du systeme incluent la segmentation et la classification. Le module de reconnaissance utilise repose sur un classifieur SVM avec un noyau RBF. L’implementation Multiclasses utilisee repose sur un-contre-tous (OAA : One Against All). Les parametres du noyau RBF et de regularisation du SVM sont fixes a Y=1 et C=10.

L'evaluation est effectuee avec la methode de CMS sans l’extraction des caracteristiques afin d'apprecier la qualite de la segmentation. Cette evaluation est illustree dans la matrice de confusion reportee dans le tableau 2.

Abbildung in dieser Leseprobe nicht enthalten

Tab. 2 - Taux de reconnaissance obtenu pour chaque classe

Nous pouvons noter que le taux global est moins important relativement a revaluation manuelle. Ce fait est du a une confusion de certains chiffres particulierement entre les chiffres couples '0 'et '9', '1 'et '4', '3 'et '8'. Ces chiffres sont plus problematiques pour la reconnaissance, puisqu’ils sont parfois visuellement tres semblables. La decision est difficile, meme pour un operateur humain.

5 Conclusion et Perspectives

L'objectif de cet article est la presentation d'une strategie de combinaison de differentes methodes de segmentation pour trouver la meilleure option de coupure pour isoler deux chiffres contigus. La combinaison de methodes de segmentation permet d’ameliorer les performances et de remedier presque a tous les problemes rencontres, Trois methodes de segmentation ont ete combinees fondees sur l’histogramme de projection, les points d’interconnexion et l’analyse de contours. L’utilisation de l’histogramme de projection permet de detecter les chiffres connectes ou en chevauchement, l’analyse par les contours permet de gerer la separation entre les chiffres chevauches et la segmentation basee sur des points d’interconnexion pour trouver le chemin de separation lorsque les chiffres sont connectes.

D’une maniere generale, les premiers resultats obtenus sont encourageants puisque nous arrivons a suivre, avec une faible erreur de detection, tous les chemins possibles de segmentation. Cette combinaison utilise peu de regles et a l’avantage de fournir une segmentation correcte dans la majorite des cas. En perspective, nous tenterons de completer le systeme par l'ajout d'un module d'analyse pour extraire les caracteristiques plus pertinentes et ameliorer la segmentation par l’ajout de nouvelles regles pour separer les chiffres notamment ceux connectes et chevauches simultanement.

Combinaison de méthodes de segmentation pour la reconnaissance des chiffres

References

Dimauro, G., S. Impedovo, G. Pirlo, and A. Salzo. (1997). Automatic Bankcheck processing: A New Engineered System. International Journal of Pattern Recognition and Artificial Intelligence, 11:467-504

Vellasques, E., L. S. Oliveira, A. S. Britto Jr., A. L. Koerich and R. Sabourin (2008). Filtering segmentation cuts for digit string recognition. Pattern Recognition, 10:3044­3053

Congedo, G., G. Dimauro, S. Impedovo, and G. Pirlo (1995). Segmentation of Numeric Strings, Proc. of Third Int. Conf. on Document Analysis and Recognition, Montreal, pp.1038-1041. Canada

Jang, B, K. R., T. Chin (1992), One-pass parallel thinning: Analysis, properties, and quantitative evaluation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 14:1129-1140.

Shridhar, M., A. Badreldin (1986). Recognition of Isolated and Simply Connected Handwritten Numerals. Journal of Pattern Recognition, 19:1-12

Ayat, N. E. M. Cheriet et C.Y. Suen. (2000). Un systeme neuro-flou pour la reconnaissance de montants numeriques de cheques arabes. Colloque international francophone sur l'ecrit et le document, Montreal, pp. 03-07. Quebec, canada

Hussein, K. M., .A. Agarwal, A. Gupta, P. S. P. Wang (1999). A knowledge-based algorithm for enhanced recognition of handwritten courtesy amounts. Pattern Recognition, 32: 305­316

Fujisawa, H., Y. Nakano, and K. Kurino (1996). Segmentation Methods for Character Recognition: From Segmentation to Document Structure Analysis. Proceedings of the IEEE, vol 80, n°7, pp 1079-1091,pp. 21- 28

Trier, O., A. K. Jain (1995). Goal-Directed Evaluation of Binarization Methods. IEEE Trans. on Pattern Analysis and Machine Intelligence, 17:1191, 1201.

Shi, Z., V. Govindaraju (1996). Segmentation and recognition of connected handwritten numeral strings. Progress in Handwriting Recognition, World Scientific, pp. 515-518.

Grother, P. J. (1995). NIST Special Database 19 - Handprinted Forms and Characters Database. National Institute of Standards and Technology (NIST)

Summary

The segmentation of the handwriting digits is the most important module into a system for handwritten digit recognition. It remains difficult because of overlapped or/and connected consecutive digits. In order to resolve this problem, many segmentation methods have been developed which present however each one advantages and disadvantages. In this work, we propose an approach that allows combining many methods of segmentation according the chaining between digits. By help of some rules, we define the paths of segmentation in order to find the best path for separating the digits. Three methods of segmentation are combined based on the histogram of the vertical profile, the interconnection points and the contour analysis. Performances of our strategy have been evaluated in terms of recognition rates using the confusion matrix.

Résumé des informations

Pages
9
Année
2010
ISBN (Livre)
9783668987500
Langue
Français
N° de catalogue
v491269
Note
mots-clé
reconnaissance automatique chiffres manuscrits

Auteur

Précédent

Titre: Combinaison de méthodes de segmentation explicite pour la reconnaissance automatique des chiffres manuscrits