Dans ce travail, nous proposons une approche permettant de combiner plusieurs méthodes de segmentation selon le type de configuration de chaînage entre chiffres. A l’aide de quelques règles, nous définissons les chemins de segmentation afin de trouver le meilleur chemin de séparation des chiffres.
Trois méthodes de segmentation sont combinées basées sur l'histogramme de projection verticale, les points d'interconnexion et l'analyse des contours. Les performances de notre stratégie ont été évaluées en termes de taux de bonne reconnaissance en utilisant la matrice de confusion.
La segmentation des chiffres manuscrits est le module le plus important dans un système de reconnaissance des chiffres manuscrit. Elle reste difficile à cause du chevauchement et/ou l’accolement de deux chiffres consécutifs. Pour résoudre ce problème, plusieurs méthodes de segmentation ont été développées qui présentent cependant chacune des avantages et des inconvénients.
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:30443053
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: 305316
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
Foire aux questions
De quoi parle cet article sur la segmentation des chiffres manuscrits ?
Cet article traite de la segmentation des chiffres manuscrits connectés et/ou chevauchés, en vue d'améliorer les performances de reconnaissance par une combinaison de plusieurs méthodes de segmentation. Il explore différentes techniques pour déterminer le meilleur chemin de coupure pour isoler les chiffres.
Quelles sont les principales étapes de la reconnaissance automatique de l'écriture manuscrite, selon l'article ?
Selon l'article, la reconnaissance automatique de l'écriture manuscrite se déroule en plusieurs étapes : prétraitement (élimination des défauts), segmentation (séparation des chiffres), codage de l'image (extraction de caractéristiques) et prise de décision (classification des formes).
Pourquoi la segmentation est-elle considérée comme l'étape la plus difficile ?
La segmentation est considérée comme l'étape la plus difficile en raison de facteurs tels que l'inclinaison des chiffres, le chevauchement, la jonction des chiffres, et les défauts d'encrage.
Quelles sont les trois méthodes de segmentation combinées dans cet article ?
Les trois méthodes de segmentation combinées sont : segmentation basée sur l'histogramme de projection, segmentation basée sur l'analyse de contours, et segmentation basée sur les points d'interconnexion.
Comment fonctionne la segmentation basée sur l'histogramme de projection verticale (HPV) ?
La segmentation basée sur l'HPV localise les chiffres en recherchant les plages correspondant à un nombre de pixels noirs non nuls et détecte les passages par zéro de l'histogramme pour séparer les chiffres contigus. Elle est efficace pour les chiffres naturellement séparés mais moins pour les chiffres connectés ou chevauchés.
Comment fonctionne la segmentation basée sur les points d'interconnexion (PI) ?
Cette méthode analyse le nombre et la nature des points d'interconnexion entre les chiffres adjacents pour définir la position de coupure optimale. Elle utilise les points d'intersection (PI) et les points de bases (PB) pour déterminer le chemin de segmentation.
Comment fonctionne la segmentation basée sur les contours ?
La segmentation basée sur les contours utilise des informations sur le contour, extraites par morphologie mathématique sur les images binaires, pour séparer les chiffres, particulièrement lorsque ceux-ci se chevauchent. Elle est moins efficace pour les chiffres connectés.
Quelle est la stratégie de combinaison des méthodes de segmentation ?
La stratégie de combinaison se déroule en deux étapes : d'abord, détection de chiffres naturellement séparés via HPV. Ensuite, si des PI sont détectés, la coupe est réalisée à proximité du PI. Si aucun PI n'est détecté, l'analyse des contours est utilisée. Les seuils T1 et T2 sont déterminés à partir de l'analyse de la base de données des chiffres manuscrits.
Comment la méthode de segmentation est-elle évaluée dans l'article ?
La méthode de segmentation est évaluée en deux étapes : une évaluation manuelle (calcul du taux de bonne segmentation) et une évaluation du système complet (segmentation et classification) en utilisant un classifieur SVM.
Quels sont les résultats de l'évaluation de la combinaison des méthodes de segmentation ?
Les résultats montrent que la combinaison de méthodes de segmentation (CMS) améliore considérablement la segmentation. Cependant, la segmentation de certains chiffres, comme '0' et '6', reste plus difficile en raison des connexions et des chevauchements fréquents.
Quelle est la base de données utilisée pour l'évaluation ?
La base de données utilisée pour l'évaluation est NIST SD19.
Quelles sont les perspectives futures mentionnées dans l'article ?
Les perspectives futures incluent l'ajout d'un module d'analyse pour extraire des caractéristiques plus pertinentes et l'amélioration de la segmentation en ajoutant de nouvelles règles pour séparer les chiffres, notamment ceux connectés et chevauchés simultanément.
- Quote paper
- Dr. Abdeljalil Gattal (Author), 2010, Combinaison de méthodes de segmentation explicite pour la reconnaissance automatique des chiffres manuscrits, Munich, GRIN Verlag, https://www.grin.com/document/491269
