Brevet FR2715752A1 — publié le 19950804

Procédé et dispositif de reconnaissance de caractères. en particulier de caractères standardisés du type E-13B La présente invention concerne la reconnaissance de caractè- res, en particulier de caractères standardisés du type E-13B. Elle trouve une application dans le traitement de documents tels que des chèques bancaires, titres ou documents analogues qui sont codés ou imprimés en encre magnétique. Par exemple, une ligne MICR (Magnetic Ink Character Recognition) est imprimée sur les chèques bancaires. Elle comprend, par exemple, un nombre formant montant, un numéro de banque et un numéro de chèque. On connaît déjà des dispositifs de reconnaissance de caractè- res, en particulier de caractères standardisés du type E-13B qui comprennent: des moyens de balayage pour balayer un caractère à recon- naître afin d'obtenir une forme d'onde représentative dudit caractère à reconnaître, et - des moyens de traitement pour traiter la forme d'onde ainsi obtenue, afin d'identifier le caractère à reconnaître. De tels dispositifs présentent l'inconvénient d'être dépen- dants des défauts d'impression des caractères, ce qui peut empêcher une identification correcte desdits caractères. La présente invention remédie à cet inconvénient. Ainsi, un but de l'invention est d'améliorer le traitement de la forme d'onde du caractère à reconnaître afin de l'identi- fier correctement en présence d'une mauvaise qualité d'im- pression sur le document à traiter. Un autre but de l'invention est de fournir un dispositif de reconnaissance de caractères destiné à être mis en place facilement et de façon peu onéreuse dans une chaîne de traitement de documents tels que des chèques bancaires. La présente invention porte sur un procédé de reconnaissance de caractères, en particulier de caractères standardisés E-13B, comprenant les étapes suivantes: - a) balayer un caractère à reconnaître afin d'obtenir une forme d'onde représentative du caractère à reconnaître, et b) traiter la forme d'onde ainsi obtenue afin d'identifier le caractère à reconnaître. Selon une définition générale de l'invention, l'étape b) comprend les étapes suivantes: - bl) échantillonner à une fréquence prédéterminée ladite forme d'onde ainsi obtenue afin de délivrer N signaux échantillonnés à reconnaître; - b2) déterminer et stocker la valeur numérique correspondant à l'amplitude de chaque signal échantillonné à reconnaître ainsi délivré ; - b3) acquérir au préalable K jeux de N signaux échantillon- nés de référence, K étant le nombre de caractères de référen- ce, - b4) déterminer et stocker la valeur numérique correspondant à l'amplitude de chaque signal échantillonné de référence ainsi acquis préalablement; - b5) calculer pour chaque jeu de N signaux échantillonnés de référence, la valeur absolue de la différence entre la valeur numérique de chaque signal échantillonné de référence et la valeur numérique de chaque signal échantillonné à reconnaître afin d'établir K listes de N valeurs absolues chacune; et - b6) choisir parmi les K listes, celle pour laquelle les N valeurs absolues présentent une valeur sensiblement constante à l'intérieur de ladite liste, le caractère à reconnaître correspondant au caractère de référence associé à la liste ainsi choisie. L'invention a également pour objet un dispositif pour la mise en oeuvre du procédé mentionné ci-avant, et qui comprend: - des moyens de balayage pour balayer un caractère à recon- naître afin d'obtenir une forme d'onde représentative du caractère à reconnaître; et - des moyens de traitement pour traiter la forme d'onde ainsi obtenue afin d'identifier le caractère à reconnaître. Selon une définition générale de l'invention, les moyens de traitement comprennent: - des moyens d'échantillonnage pour échantillonner à une fréquence prédéterminée ladite forme d'onde ainsi obtenue, afin de délivrer N signaux échantillonnés à reconnaître; - des premiers moyens pour déterminer et stocker la valeur numérique correspondant à l'amplitude de chaque signal échantillonné à reconnaître ainsi délivré ; - des moyens d'acquisition pour acquérir au préalable K jeux de N signaux échantillonnés de référence chacun, K étant le nombre de caractères de référence; - des seconds moyens pour déterminer et stocker la valeur numérique correspondant à l'amplitude de chaque signal échantillonné de référence ainsi acquis préalablement; - des moyens de calcul pour calculer pour chaque jeu de N signaux échantillonnés de référence, la valeur absolue de la différence entre la valeur numérique de chaque signal échantillonné de référence et la valeur numérique de chaque signal échantillonné à reconnaître, afin d'établir K listes de N valeurs absolues chacune, et - des moyens de sélection pour choisir parmi les K listes, celle pour laquelle les N valeurs absolues présentent une valeur sensiblement constante à l'intérieur de ladite liste, le caractère à reconnaître correspondant au caractère de référence associé à la liste ainsi choisie. D'autres caractéristiques et avantages de l'invention apparaîtront à la lumière de la description détaillée ci- après, et des dessins annexés dans lesquels: - la figure 1 est un synoptique illustrant la chaîne de traitement des caractères E-13B selon l'invention; - la figure 2 est un chronogramme illustrant la forme d'onde analogique obtenue selon l'invention; - la figure 3 est un organigramme illustrant le calcul de la valeur absolue de la différence entre la valeur numérique de chaque signal échantillonné de référence et la valeur numérique de chaque signal échantillonné à reconnaître selon l'invention; - la figure 4A illustre la détermination et le stockage de la valeur numérique correspondant à l'amplitude de chaque signal échantillonné du caractère de référence 0; la figure 4B illustre la détermination et le stockage de la valeur numérique correspondant à l'amplitude de chaque signal échantillonné du caractère de référence 1; - la figure 4C illustre la détermination et le stockage de la valeur numérique correspondant à l'amplitude de chaque signal échantillonné du caractère à reconnaître; - la figure 5A illustre la liste associée au caractère de référence 0 obtenue par le calcul de la valeur absolue de la différence entre la valeur numérique de chaque signal échantillonné du caractère de référence 0 et la valeur numérique de chaque signal échantillonné à reconnaître selon l'invention; - la figure 5B illustre la liste associée au caractère de référence 1 obtenue par le calcul de la différence entre la valeur numérique de chaque signal échantillonné du caractère de référence 1 et la valeur numérique de chaque signal échantillonné à reconnaître selon l'invention; et - les figures 6 et 7 sont des organigrammes qui illustrent la sélection parmi les K listes, de celle ayant les N valeurs absolues présentant une valeur sensiblement constante à l'intérieur de ladite liste selon l'invention. Dans la description ci-après, les procédé et dispositif de reconnaissance de caractères selon l'invention sont décrits dans une application de lecture de chèques bancaires. Bien évidemment, il s'agit d'une description destinée à faciliter la compréhension de l'invention. Il ne s'agit pas d'une limitation de l'invention dans la mesure o celle-ci trouve une application générale dans le traitement de tous documents portant des caractères standardisés, en particulier des caractères du type E-13B. Sur la figure 1, on a représenté une chaîne CH de reconnais- sance de caractères standardisés du type E-13B imprimés sur un chèque bancaire. Le premier maillon de cette chaîne est celui relatif à l'animation du chèque bancaire. Le déplacement du chèque se fait dans le sens longitudinal de celui-ci et à vitesse constante, par exemple une vitesse de l'ordre de 0,47 m/s dans le cas o le déplacement s'effectue à l'aide de moteurs pas à pas comme dans le lecteur de chèques vendu par le Demandeur sous la référence ETC 502. La flèche 2 illustre le déplacement du caractère CR devant une tête de lecture magnétique 10. Le second maillon 20 de la chaîne de traitement CH est celui relatif à l'obtention de la forme d'onde représentative du caractère à reconnaître. Le déplacement du caractère CR devant la tête de lecture magnétique 10 entraîne la génération d'un signal électrique analogique correspondant à la dérivée temporelle du change- ment intervenu dans le flux d'encre magnétisée. Ce signal est représenté par le signal analogique AG de la figure 2. Le signal analogique AG est transmis par la tête de lecture 10 à des moyens de mise en forme du signal analogique 20. Ces moyens de mise en forme 20 comprennent une chaîne d'amplification propre à amplifier, dans une échelle appro- priée, le signal analogique. Cette chaîne d'amplification est suivie de moyens de filtrage (non représentés) propres à éliminer les fréquences inutiles. Bien que le caractère CR soit imprimé au moyen d'une encre magnétique selon la police de caractères E-13B adoptée par l'American Banker Association, il est clair que le dispositif de reconnaissance selon l'invention peut être utilisé avec n'importe quelle autre police de caractères donnant lieu à un signal analogique particulier lors de la lecture effectuée par la tête de lecture magnétique 10. En pratique, la lecture du caractère à reconnaître s'effectue à l'aide d'une magnétisation obtenue par un aimant permanent, suivie d'une détection de la variation du flux magnétique obtenue par une tête magnétique, ou à l'aide d'une mesure de la variation de la réluctance obtenue par une tête magnéti- que. En variante, la magnétisation peut être obtenue par l'alimen- tation en courant continu de la tête magnétique. Les moyens d'amplification ont par exemple un gain ampli- ficateur de l'ordre de 1200, pour la vitesse mentionnée ci- avant. Les moyens de filtrage ont par exemple une fréquence de coupure de l'ordre de 6 kHz. Le signal analogique issu des moyens 20 est échantillonné, à une fréquence prédéterminée (par exemple de l'ordre de 12,5 kHz), par des moyens d'échantillonnage et de conversion analogique/numérique 30. Dans la mesure o les caractères standardisés de type E-13B ne génèrent pas, à la vitesse de déplacement du chèque mentionnée ci-avant, de variations rapides du signal à traiter (fréquences maximales inférieures à 1 kHz), le convertisseur analogique/numérique n'est pas nécessairement rapide. En pratique, la période d'échantillonnage est de l'ordre de microsecondes et le temps de conversion est inférieur à microsecondes, ce qui permet d'obtenir de l'ordre de échantillons par caractère. La résolution en bits de la conversion est par exemple de 8 bits. La valeur numérique des signaux échantillonnés est sauvegar- dée en mémoire 40, par exemple dans une mémoire de type volatile. Par exemple la capacité de la mémoire 40 est de l'ordre de 4 à 32 k octets. Il est à remarquer qu'en raison du nombre réduit d'échantil- lons et de la faible résolution nécessaire pour l'échantil- lonnage du chèque, on peut utiliser des mémoires de petite capacité et sauvegarder la totalité d'une ligne E-13B en une seule passe. Enfin, la chaîne de reconnaissance de caractères comprend des moyens de traitement 50 propres à traiter les données numériques ainsi obtenues selon un algorithme de reconnais- sance de caractères que l'on décrira plus en détail ci-après. Pour l'essentiel, les moyens de traitement sont articulés autour d'un microprocesseur ou d'un micro-contrôleur rudimen- taire, bon marché et très répandu dans les petits systèmes automatisés. Par exemple, comme dans le lecteur de chèques ETC 502, les moyens de traitement comprennent un micro-contrôleur 8 bits, vendu par la Société INTEL sous la référence 8051, avec une horloge externe d'une fréquence de 18 MHz. D'une manière générale, le procédé de reconnaissance de caractères selon l'invention comprend une phase d'apprentis- sage, une phase de stockage et une phase de décodage. La phase d'apprentissage a pour but de mémoriser les caractè- res de référence de la norme E-13B qui serviront de référence lors des phases de reconnaissance ultérieures. Après le passage du chèque devant la tête magnétique et l'échantillonnage de la forme d'onde obtenue, comme décrit en référence à la figure 1, les caractères de référence d'une ligne E-13B sont stockés dans la mémoire 40 sous forme de valeurs numériques. Sur la figure 4A, il est représenté un jeu désigné Vréf0 de N signaux échantillonnés du caractère de référence 0, o N est ici égal à 12. Par exemple, le premier échantillon a une valeur numérique égale à 6 correspondant à l'amplitude de l'échantillon 1. De même, l'échantillon No 2 a une valeur numérique égale à 9 correspondant à l'amplitude de l'échantillon No 2. Sur la figure 4B, il est représenté un jeu désigné Vréfl de 12 signaux échantillonnés du caractère de référence 1. Avantageusement, la phase d'apprentissage comprend en outre une étape de centrage du caractère dans laquelle on parcourt toutes les valeurs numériques des signaux échantillonnés du caractère de référence. Parmi toutes ces valeurs échantillon- nées, on localise ensuite au moins deux échantillons succes- sifs dont la valeur respective est supérieure à un seuil prédéterminé S. Par exemple, comme décrit en référence à la figure 2, on localise les échantillons successifs B et B' parce qu'ils présentent l'un et l'autre un niveau supérieur à S, tandis qu'on écarte les échantillons successifs A et A' parce que A' présente un niveau inférieur à S. Cette méthode permet non seulement d'éliminer les bruits et parasites (signaux des échantillons A et A'), mais surtout d'obtenir une fenêtre de décodage de N échantillons dans laquelle est défini le caractère. Cette fenêtre de décodage permet avantageusement de centrer la reconnaissance de caractère sur les signaux utiles. Comme on le verra plus en détail ci-après, cette fenêtre de décodage sert à la fois à la phase d'apprentissage, à la phase de stockage et à la phase de décodage. Il est à noter que le seuillage sur deux échantillons successifs s'est avéré satisfaisant pour écarter les parasi- tes et déterminer les échantillons utiles servant à la définition du caractère. Bien entendu, dans d'autres applica- tions, le seuillage peut être établi sur plus de deux échantillons successifs. Avantageusement, après l'opération de centrage du caractère, on calcule la valeur moyenne de la valeur numérique de chaque échantillon sur plusieurs acquisitions jusqu'à obtenir une stabilisation des données calculées. On obtient, à l'issue de cette opération de lissage, un signal lissé représentant le caractère de référence. Enfin, le signal ainsi lissé est stocké dans une mémoire non volatile (non représentée). Ainsi, dans cette mémoire non volatile, est stockée la valeur numérique correspondant à l'amplitude de chaque signal échantillonné de référence délivré à l'issue des opérations d'apprentissage mentionnées ci-avant (centrage et lissage compris), ce qui permet d'acquérir au préalable K jeux de N signaux échantillonnés de référence chacun o K est le nombre de caractères de référence et N est le nombre d'échantillons par caractère. Ces données de référence sont définies par le terme VréfK(i) o i varie de 1 à N. De son côté, la phase de stockage du caractère à reconnaître comprend les opérations d'animation du chèque 10, d'acquisi- tion numérique 20, 30, 40, et l'opération de centrage du caractère, comme décrit ci-avant. A l'issue de ces opéra- tions, il est obtenu N valeurs numériques correspondant à l'amplitude de chaque signal échantillonné à reconnaître. Sur la figure 4C, on a représenté les N valeurs numériques du signal Vx à reconnaître, avec N égal à 12 échantillons. Par exemple, l'échantillon No 1 du signal Vx a une valeur numérique égale à 5. L'échantillon No 2 a une valeur numéri- que égale à 8. Une fois obtenues, les valeurs Vx sont stockées dans une mémoire volatile de la même façon que les signaux Vréf obtenus précédemment lors de l'opération d'apprentissage avant leur stockage dans la mémoire non volatile. Il est à remarquer que l'opération de stockage associée au caractère à reconnaître ne comprend pas d'opération de lissage L'algorithme de reconnaissance de caractères selon l'inven- tion va utiliser les données issues de l'apprentissage et du stockage associé au caractère à reconnaître, pour identifier ledit caractère à reconnaître. Comme décrit en référence à la figure 3, l'algorithme comprend le calcul, pour les K jeux de N signaux échantillon- nés de référence chacun, de la valeur absolue de la diffé- rence entre la valeur numérique de chaque signal échantil- lonné de référence et la valeur numérique de chaque signal échantillonné à reconnaître, c'est-à-dire: V abs K(i) = IVx(i) Vréf K(i) 1. avec i variant de 1 à N et K variant ici de 0 à 13. Ce calcul permet d'établir K listes de N valeurs absolues chacune. Sur la figure SA, on a représenté la liste d'un exemple de valeurs absolues associée au caractère de référence 0, avec N égal à 12 échantillons. De même, sur la figure 5B, on a représenté la liste d'un exemple de valeurs absolues associée au caractère de réfé- rence 1, avec N égal à 12 échantillons. La liste en figure 5A peut être représentée par une courbe discrète s'apparentant à une équation du type F(X) = 1, c'est-à-dire une constante, tandis que la seconde liste (figure 5B) possède des discontinuités qui, comme on le verra plus en détail ci-après, permettent d'en déduire que le caractère à reconnaître ne correspond pas au caractère de référence 1 associé à cette seconde liste. L'invention consiste à sélectionner parmi les K listes, celle pour laquelle les N valeurs absolues présentent une valeur sensiblement constante à l'intérieur de ladite liste. Cette sélection permet avantageusement de s'affranchir des défaut d'impression des caractères sur les chèques. Comme vu ci-avant, le premier échantillon du signal Vx (ici l'échantillon B, figure 2) correspond au début du caractère à reconnaître grâce au programme de centrage décrit ci-avant. Le Demandeur a constaté de façon surprenante que les diffé- rences des valeurs absolues associées aux échantillons suivants de l'échantillon B doivent être sensiblement égale à celle de l'échantillon B pour considérer que le caractère à reconnaître correspond au caractère de référence associé à la liste de valeurs absolues ainsi analysée. En pratique, pour vérifier que les différences des valeurs absolues sont sensiblement égales à la première valeur absolue, l'invention prévoit un calcul selon l'équation I (en annexe). Si le résultat de l'équation I est strictement supérieur à une constante prédéterminée C, alors la somme des valeurs absolues divergentes est effectuée afin d'obtenir un coeffi- cient dit de ressemblance COEFK. Par contre, si le résultat de l'équation I est inférieur ou égal à la constante prédé- terminée C, alors la donnée en cours d'étude reste proche de la valeur absolue correspondant au premier échantillon, ce qui signifie que le signal vx ressemble au signal Vréf. En pratique, la constante C n'est pas nulle car la chaine d'amplification n'est pas parfaite. Par exemple, avec les données décrites en référence aux figures 4A et 4B, et avec une constante C égale à 1, on trouve la somme COEF0 associée au caractère de référence 0 égal à 0 et la somme COEF1 associée au caractère de référence 1 égale à 27. Avantageusement, afin de faire diverger les coefficients de ressemblance COEFK, il peut être effectué une multiplication des valeurs absolues par un facteur prédéterminé par exemple 2, lorsque le test de l'équation I est supérieur à la constante C, avant de les sommer. Ainsi, dans l'exemple men- tionné ci-avant, la somme COEF0 est égale à 0 et la somme COEF1 est égale 54. Enfin, la dernière opération de reconnaissance (figure 7) consiste tout d'abord à faire un tri croissant des sommes COEFK ainsi obtenues pour chacune des K listes. Ensuite, il convient de sélectionner les deux plus petites sommes. Enfin, pour déterminer le caractère en cours d'étude, il est effectué la différence D entre ces deux plus petites sommes. Si cette différence D est supérieure à une valeur de décision prédéterminée, alors le caractère en cours de décodage est égal à l'indice k de la plus petite somme COEFK. Dans l'exemple mentionné ci-avant, le caractère à reconnaître est le caractère de référence 0. Si la valeur de décision est égale par exemple à 15, le chiffre 0 peut être considéré comme le caractère à reconnaî- tre. Par contre, si la différence est inférieure à la valeur de décision, il est difficile d'affirmer avoir décodé un caractère, dans ce cas un point d'interrogation est affiché plutôt qu'une erreur. Il est à remarquer que la valeur de décision est déterminée empiriquement avec plusieurs essais. Par ailleurs, le fait de prendre les deux plus petites valeurs des sommes et non pas la valeur la plus petite est un point permettant d'authenti- fier la reconnaissance. Par ailleurs, en cas de non décodage, il est permis d'effec- tuer un recentrage du caractère et de refaire un décodage comme décrit ci- avant, le cas échéant en modifiant certains paramètres tels que le seuil S, le nombre N d'échantillons, les coefficients de ressemblance, la valeur de décision, etc. ANNEXE I i = | Vabs K (1) - Vabs K (i) I Revendications 1. Procédé de reconnaissance de caractères, en particulier de caractères standardisés du type E-13B, comprenant les étapes suivantes: - a) balayer un caractère à reconnaître afin d'obtenir une forme d'onde représentative du caractère à reconnaître, et - b) traiter la forme d'onde ainsi obtenue afin d'identifier le caractère à reconnaître, caractérisé en ce que l'étape b) comprend les étapes suivantes: - bl) échantillonner à une fréquence prédéterminée ladite forme d'onde ainsi obtenue afin de délivrer N signaux échantillonnés à reconnaître; - b2) déterminer et stocker la valeur numérique correspondant à l'amplitude de chaque signal échantillonné à reconnaître ainsi délivré ; - b3) acquérir au préalable K jeux de N signaux échantillon- nés de référence, K étant le nombre de caractères de réfé- rence; - b4) déterminer et stocker la valeur numérique correspondant à l'amplitude de chaque signal échantillonné de référence ainsi acquis préalablement; - b5) calculer pour chaque jeu de N signaux échantillonnés de référence, la valeur absolue de la différence entre la valeur numérique de chaque signal échantillonné de référence et la valeur numérique de chaque signal échantillonné à reconnal- tre, afin d'établir K listes de N valeurs absolues chacune, et - b6) choisir parmi les K listes, celle pour laquelle les N valeurs absolues présentent une valeur sensiblement constante à l'intérieur de ladite liste, le caractère à reconnaître correspondant au caractère de référence associé à la liste ainsi choisie. 2. Procédé selon la revendication 1, caractérisé en ce que l'étape b2) ou l'étape b4) comprend les étapes suivantes: - b2.1) parcourir toutes les valeurs numériques des signaux échantillonnés de caractère à reconnaître; - b2.2) parmi lesdites valeurs numériques, localiser au moins deux échantillons successifs dont la valeur numérique est supérieure à un seuil prédéterminé (S) afin d'éliminer les signaux inutiles et d'obtenir une fenêtre de décodage de N échantillons. 3. Procédé selon la revendication 1 ou la revendication 2, caractérisé en ce que l'étape b3) comprend les étapes suivantes: - b3.1) balayer un caractère de référence afin d'obtenir une forme d'onde du caractère de référence; - b3.2) échantillonner à une fréquence prédéterminée ladite forme d'onde ainsi obtenue afin de délivrer N signaux échantillons de référence. 4. Procédé selon l'une des revendications précédentes, caractérisé en ce que l'étape b6) comprend les étapes suivantes: - b6.1) pour chaque K listes de valeurs absolues, déterminer la valeur absolue dont la valeur diverge de celle du premier échantillon du signal à reconnaître; - b6.2) sommer les valeurs absolues divergentes ainsi déterminées afin d'obtenir un résultat de somme (COEFK) pour chaque liste associée chacune à un caractère de référence; - b6.3) trier par valeur croissante les résultats de somme (COEFK) ainsi obtenus et sélectionner un résultat (COEFK) selon une condition prédéterminée, le caractère à reconnaître correspondant au caractère de référence associé audit résultat de somme (COEFK) ainsi sélectionné. 5. Dispositif de reconnaissance de caractères, en particulier de caractères standardisés du type E-13B, comprenant: - des moyens de balayage (10, 20) pour balayer un caractère à reconnaître (CR) afin d'obtenir une forme d'onde (AG) représentative du caractère à reconnaître, et - des moyens de traitement pour traiter la forme d'onde ainsi obtenue afin d'identifier le caractère à reconnaître, caractérisé en ce que les moyens de traitement comprennent: - des moyens d'échantillonnage (30) pour échantillonner à une fréquence prédéterminée ladite forme d'onde ainsi obtenue afin de délivrer N signaux échantillonnés à reconnaître, - des premiers moyens (40) pour déterminer et stocker la valeur numérique correspondant à l'amplitude de chaque signal échantillonné à reconnaître ainsi délivré, - des moyens d'acquisition pour acquérir au préalable K jeux de N signaux échantillonnés de référence, K étant le nombre de caractères de référence, - des seconds moyens pour déterminer et stocker la valeur numérique correspondant à l'amplitude de chaque signal échantillonné de référence ainsi acquis préalablement, - des moyens de calcul (50) pour calculer pour chaque jeu de R signaux échantillonnés de référence, la valeur absolue de la différence entre la valeur numérique de chaque signal échantillonné de référence et la valeur numérique de chaque signal échantillonné à reconnaître, afin d'établir K listes de N valeurs absolues chacune, et - des moyens de sélection pour choisir parmi les K listes, celle pour laquelle les N valeurs absolues présentent une valeur sensiblement constante à l'intérieur de ladite liste, le caractère à reconnaître correspondant au caractère de référence associé à la liste ainsi choisie.