Brevet FR2766287A1 — publié le 19990122

PROCDE DE RECONNAISSANCE DE CARACTÈRES MANUSCRITS La présente invention concerne un procédé de reconnais- sance de caractères manuscrits, notamment du type o un utilisateur est contraint de suivre des repères visibles sur le support d' écriture. Les systèmes de reconnaissance de caractères manuscrits sont généralement utilisés dans des appareils o, pour des rai- sons de place, on ne souhaite pas installer un clavier. Les systèmes de reconnaissance de caractères les plus courants comportent un capteur matriciel de résolution élevée, destinés à numériser avec précision le tracé exécuté par l'utili- sateur. Le tracé numérisé est ensuite analysé par un procédé de reconnaissance de forme complexe pour identifier le caractère tracé. Dans un tel système, l'utilisateur est souvent contraint d'utiliser un alphabet spécifique facilement reconnaissable. L'article intitulé "Computer Identificaticn of Cônstrained Handprinted Characters with a High Recognition Rate" de IEEE Transactions on Systems, Man, and Cybernetics, Volume SMC-4, N 6, Novembre 1974, décrit un système de reconnaissance de carac- tères manuscrits o l'utilisateur doit s'efforcer de suivre des segments tracés sur le support d'écriture. Le tracé est numérisé à haute résolution puis analysé pour trouver l'ensemble des segments qui s'en rapprochent le plus. L'ensemble des segments identifiés pour un tracé permet d'identifier ou non un caractère à l'aide d'une table. Il n'existe aucune application commerciale utilisant un tel système de reconnaissance de caractères. La demande de brevet français 2 648 255 décrit un sys- tème de reconnaissance de caractères dans lequel le capteur est constitué d'une matrice de neuf zones de détection de tracé jointives. Lorsqu'un utilisateur trace un caractère sur ces zones, les excitations successives des zones sont analysées pour extraire une séquence de points singuliers du tracé, destinée à identifier le caractère tracé. Les points singuliers sont notam- ment les points de rupture, de rebroussement et de cambrure. Cette technique exploite un capteur particulièrement simple, mais elle nécessite que l'utilisateur reproduise de manière fidèle un alphabet spécifique. En effet, une faible distorsion dans le tracé d'un caractère peut entraîner une varia- tion de la séquence des points singuliers produisant une erreur d'identification. Un objet de la présente invention est de prévoir un système de reconnaissance de caractères manuscrits utilisant un capteur de faible résolution tout en garantissant une reconnais- sance fiable même si les caractères tracés présentent une distorsion importante. Cet objet est atteint grâce à un procédé de reconnais- sance de caractères manuscrits, comprenant les étapes suivantes: - offrir à un utilisateur un support de tracé muni d'une matrice de points de repère distinctement visibles et écartés, par lesquels l'utilisateur s'efforce de passer en traçant un caractère; - identifier chaque segment défini par deux points de repère successifs dans le tracé; et - extraire d'une table le caractère correspondant à 1 'ensemble des segments identifiés. Selon un mode de réalisation de la présente invention, la table stocke, pour chaque caractère à reconnaître, plusieurs ensembles de segments possibles. Selon un mode de réalisation de la présente invention, chaque point de repère est associé à un détecteur déclenché par le passage du doigt de l'utilisateur ou d'un stylet, l'étape d'identification des segments consistant à relever la séquence des points de repère dans l'ordre o les détecteurs correspon- dants sont déclenchés, et à associer un segment à chaque couple de points successifs de la séquence. Selon un mode de réalisation de la présente invention, les points de repère sont imprimés sur une feuille de papier, le procédé comprenant les étapes suivantes: - numériser l'image de la feuille de papier, et identifier comme successifs deux points de repère reliés directement 1 'un à l'autre par une portion de tracé. Selon un mode de réalisation de la présente invention, le procédé comprend l'étape consistant à valider, dans un mot comprenant un bit par segment possible, les bits correspondant aux segments identifiés, les entrées de la table étant consti- tuées de mots similaires ayant des bits adéquats validés. La présente invention vise également un dispositif de saisie de caractères manuscrits comprenant un support de saisie muni d'une matrice de points de repère distinctement visibles et écartés. Selon un mode de réalisation de la présente invention, chaque point de repère est associé à un détecteur susceptible d'être déclenché par le passage du doigt de l'utilisateur ou d'un stylet. Selon un mode de réalisation de la présente invention, le dispositif comporte des moyens de détection du contact du doigt ou du stylet avec le support de saisie. Selon un mode de réalisation de la présente invention, les moyens de détection du contact du doigt ou du stylet avec le support de saisie comprennent une première zone entourant les points de repère, et une deuxième zone entourant la première zone. Selon un mode de réalisation de la présente invention, la matrice comporte neuf points de repère. Ces objets, caractéristiques et avantages, ainsi que d'autres de la présente invention seront exposés en détail dans la description suivante de modes de réalisation particuliers faite à titre non-limitatif en relation avec les figures jointes parmi lesquelles: les figures lA et lB représentent un exemple de support de tracé selon l'invention comportant une matrice de points de repère; la figure 2 représente un exemple de jeu de caractères reconnaissable selon 1 'invention avec de nombreuses distorsions permises; la figure 3 illustre des exemples de distorsions permises pour les lettres A et C; et les figures 4A à 4D représentent des exemples de tracé et des données correspondantes stockées après une analyse des tracés. Un système de reconnaissance de caractères manuscrits selon la présente invention est basé sur un tracé contraint des caractères, c'est-à-dire que le support sur lequel l'utilisateur doit tracer des caractères comporte des repères visibles destinés à guider l'utilisateur dans son tracé. Toutefois, contrairement à ce que décrit l'article de IEEE susmentionné, les repères ne sont pas des segments mais des points espacés par lesquels l'utilisateur doit s'efforcer de faire passer le tracé. Bien entendu, chaque point de repère est en fait une zone distinctement visible de dimensions propres à permettre à l'utilisateur d'y faire passer le tracé sans difficultés. Par ailleurs, on détecte seulement le fait que le tracé passe par un point de repère et on ignore le tracé entre deux points de repère. En d'autres termes, seuls les points de repère sont munis, le cas échéant, de détecteurs de tracé. La figure 1A illustre schématiquement un exemple de support de tracé selon l'invention, tel qu'il est offert à un utilisateur. Ce support de tracé comporte une matrice d'un faible nombre de points de repère, par exemple neuf numérotés de 1 à 9. Les points de repère sont écartés les uns des autres de manière à occuper une zone de taille adaptée au mode de traçage utilisé, par exemple au doigt ou avec un stylet. Chaque point est claire- ment visible, et peut même comporter un repère tactile (un creux, une bosse, une rugosité...) pour le cas o les tracés sont exécu- tés avec le doigt. La figure 2 représente un exemple de jeu de caractères, comprenant des lettres majuscules, des lettres minuscules et des chiffres, que l'utilisateur peut tracer sur la matrice de la figure 1 en passant d'un point de repère à un autre. Selon un premier mode de réalisation, le support de tracé constitue un capteur dont chaque point de repère est associé à un détecteur de tracé. Alors, le tracé exécuté par l'utilisateur, passant par les points de repère, provoque une succession de déclenchements des détecteurs. Pendant ce tracé, le système analyse la séquence des points déclenchés pour identifier le caractère qu'a souhaité tracer 1 'utilisateur. Un tel capteur selon la présente invention se rapproche de celui décrit dans la demande de brevet français 2 648 255 susmentionnée, sauf que les détecteurs ne sont pas jointifs et sont repérés de manière visible. Comme on le verra ci-après, 1 'exploitation des informations fournies par les détecteurs diffère totalement de celle décrite dans cette demande de brevet français. Selon l'invention, on analyse la séquence de points déclenchés pour identifier les segments reliant ces points. Dans le cas de la figure 1A, on définit, comme cela est illustré en figure 1B, vingt segments désignés a à t, reliant les points rapprochés. On préfère ne pas considérer les segments reliant les points éloignés, par exemple les points 1 et 6. En effet, de tels segments ne seront généralement pas utilisés pour tracer un caractère et ils sont par ailleurs difficiles à tracer sans déclencher l'un des deux points entre lesquels le segment passe (par exemple le point 2 ou 5 pour le segment reliant les points 1 et 6). Chaque ensemble de segments identifiés lors d'un tracé permet de reconnaître un caractère sans ambiguïté et indépendam- ment de l'ordre d'identification de ces segments. Bien entendu, un même segment peut être parcouru plusieurs fois lors d'un tracé, mais seule la première identification compte. Ainsi, les entrées de la table de reconnaissance ne stockent qu'un seul ensemble de segments, sans notion d'ordre, pour chaque forme que 1 'on souhaite reconnaître. Les caractères de la figure 2 sont constitués de seg- ments identifiables à l'aide de la matrice des figures 1A et lB. Ce jeu de caractères n'est qu'un modèle qui tolère, pour chaque caractère, de nombreuses formes différentes ou "distorsions". En fait, 1 'utilisateur pourra généralement ignorer le modèle et tracer les caractères de manière intuitive sans que cela ne nuise à la qualité de la reconnaissance. La figure 3 illustre, à titre d'exemple, plusieurs for- mes acceptables pour la lettre A et la lettre C. Pour accepter les différentes formes d'un caractère, il suffit de stocker les ensembles de segments correspondants dans les entrées de la table de reconnaissance. Il existe irrémédiablement des possibilités de confu- sion entre certains caractères, par exemple entre le chiffre "0" et la lettre "0" ou "o", et entre la lettre "g" et le chiffre "9". Dans les cas ambigus, l'utilisateur sera moins libre dans le tracé et devra se conformer à un modèle et utiliser des conven- tions. Pour éviter la confusion entre la lettre "g" et le chiffre "9", de formes identiques, on peut adopter une convention selon laquelle les chiffres sont écrits dans l'une des moitiés de la matrice, tandis que les lettres minuscules, au moins celles présentant un risque de confusion, sont écrites dans l'autre moitié de la matrice. On s'aperçoit que les chiffres et la plu- part des lettres minuscules peuvent être tracés dans une moitié de la matrice. Comme l'illustre le modèle de la figure 2, on peut prévoir des formes du chiffre "O" et des lettres "o" et "O" suffisamment différentes pour lever toute ambiguïté. Les figures 4A à 4D illustrent des exemples de tracés de caractères et une solution pour coder les ensembles de seg- ments correspondants. Un ensemble de segments correspondant à un caractère est ici codé sous forme d'un mot de vingt bits ID, dont chaque bit est associé à l'un des segments a à t. Pour relever un tracé, le système doit être informé du début et de la fin du tracé. Plusieurs solutions peuvent être adoptées pour cela. Une solution commode et couramment utilisée consiste à détecter un début de tracé lorsque l'utilisateur pose le doigt ou le stylet sur le support de tracé, et à détecter la fin du tracé lorsque l'utilisateur lève le doigt ou le stylet. Dans ce cas, les caractères doivent être tracés d'un seul trait, c'est-àdire sans lever le doigt ou le stylet, d'o la nécessité de passer plusieurs fois sur un même segment pour certains carac- tères. La détection d'un début de tracé initialise le contenu du mot d'identification ID. La séquence de points déclenchés au cours du tracé est mémorisée puis analysée en considérant les points successifs par couples successifs. Chaque couple de points identifie le segment ayant ces points pour extrémités. Pour chaque segment ainsi identifié, le système valide le bit correspondant du mot d'identification ID. A la fin du tracé, ce mot ID est confronté aux entrées de la table de reconnaissance. Ces entrées, codées de la même manière que le mot ID, représen- tent toutes les formes acceptées du jeu de caractères choisi. Un caractère est reconnu lorsque le mot ID correspond à une des plusieurs entrées possibles pour ce caractère Quel que soit le parcours effectué pour déclencher les points constituant une même forme d'un caractère, le contenu du mot d'identification ID sera le même, étant donné que l'on iden- tifiera les mêmes segments. A la figure 4A, on trace la lettre "A" en passant successivement par les points 7, 4, 2, 6, 9, 6, 5, et 4. Les couples 7-4, 4-2, 2-6, 6-9, 9-6, 6-5 et 5-4, identifient respec- tivement les segments g, q, r, d, d, 1 et p, ce qui est indiqué par des "1" dans le mot ID (le bit correspondant au segment d est validé deux fois, ce qui ne change rien au contenu du mot). La figure 4B illustre le contenu du mot ID obtenu pour le tracé d'une forme possible de la lettre "B", exécutée en déclenchant successivement les points 7, 4, 1, 2, 3, 5, 4, 5, 9, 8 et 7. Comme cela est illustré, on valide dans le mot ID les bits correspondant aux segments a, b, e, f. g, h, k, m et p. Les figures 4C et 4D correspondent à deux tracés possibles de la lettre "c". La lettre "c", comme d'autres lettres minus- cules, peut être tracée dans un quart de la matrice de la figure 1, et peut donc être tracée à quatre emplacements différents. A la figure 4C, la lettre "c" est tracée en passant successivement par les points 5, 4, 7 et 8, ce qui permet d'iden- tifier, comme cela est illustré par le contenu du mot ID, les segments p, g et f. A la figure 4D, la lettre "c" est tracée en passant successivement par les points 3, 2, 5 et 6, ce qui permet d'iden- tifier les segments b, j et 1. Ainsi, pour une même forme d'un caractère, on peut identifier des ensembles de segments différents. Ces ensembles de segments peuvent bien entendu être stockés pour le caractère comIe s'ils correspondaient à des formes différentes acceptables du même caractère. Une autre solution consiste, pour une forme qui peut être tracée dans un quart ou dans une moitié de la matrice, à ne stocker dans la table que l'un des ensembles de segments et à opérer une translation sur la séquence de points déclenchés, afin de ramener ces points à la séquence correspondant à 1 'ensemble de segments que l'on a choisi de stocker. Un capteur matriciel de faible résolution selon la pré- sente invention peut être réalisé de diverses manières. Il peut être réalisé à partir d'une matrice de résolution élevée, telle que celles utilisées classiquement pour effectuer une reconnais- sance de forme, sauf qu'on n'exploitera que les points détecteurs situés en dessous des points de repère. Lorsque les tracés sont exécutés avec le doigt, les points de repère peuvent être constitués de capteurs capacitifs individuels, 1 'espace entre les points de repère constituant également un capteur capacitif pour détecter la présence ou 1 'absence du doigt. Les points de repère peuvent être affichés sur un écran tactile. De nombreuses autres solutions sont envisageables. Les segments peuvent être affichés au fur et à mesure de leur identification afin d'assister l'utilisateur. Ils peuvent être affichés sur le support de tracé lui-même, ou sur un écran, près de caractères précédemment reconnus. Dans le cas o le capteur matriciel est prévu pour que les caractères soient tracés d'un seul trait, il pourra compor- ter, comme oela est représenté à la figure 1A, deux zones de détection externes aux points de repère. Une première zone 10 entoure les points de repère et la deuxième zone 12 entoure la zone 10. Le contact avec le support de tracé est détecté par l'une ou l'autre des zones 10 et 12 afin de déterminer le début et la fin d'un tracé. Par contre, le système sera prévu pour n'identifier des segments que lorsque le tracé est exécuté dans la zone 10. Le système pourra alors identifier des segments non Jointifs pour reconnaître des caractères qui ne peuvent être tracés d'un seul trait (symboles diacritiques). Par exemple, comme cela est illustré en pointillés, le signe "=" pourra être tracé en passant par la zone 12 entre chacune des barres horizon- tales de ce signe. Si la zone externe 12 était omise, le tracé du signe "=" d'un seul trait pourrait être confondu avec les lettres "s", "z", ou "c". Selon un deuxième mode de réalisation de l'invention, plusieurs matrices de points de repère du type de la figure lA sont imprimées en ligne sur un support tel qu'une feuille de papier constituant un formulaire à remplir à la main. L'utilisa- teur remplit le formulaire en s'efforçant d'écrire comme précédemment, de manière que les tracés des caractères passent par les points de repère. Le formulaire est alors numérisé, et un logiciel de traitement d'image spécifique localise les points de repère. Les points de repère se distinguent facilement du fait qu'ils seront généralement nettement plus gros que le tracé des caractères. Le logiciel détermine alors les points de repère qui sont reliés directement l'un à l'autre par une portion de tracé pour identifier des segments. Une telle analyse graphique est particulièrement simple, car il suffit de déterminer que des points sont reliés l'un à l'autre, indépendamment de la forme du tracé qui les relie. De nombreuses options de la présente invention apparai- tront 1 'homme du métier. Par exemple, le contenu de la table de reconnaissance peut être modifiable par l'utilisateur afin que celui- ci puisse programmer des symboles non initialement prévus dans le jeu de caractères à reconnaître, ou ajouter des formes "abrégées" qui doivent être reconnues comme des caractères spéci- fiques. La table, en plus de permettre la reconnaissance de caractères, peut être prévue pour signaler au système d'exécuter des actions lorsque des symboles spécifiques sont reconnus. De cette manière, par exemple, il pourra être prévu que le tracé d'un symbole spécifique entraîne l'effacement du dernier carac- tère reconnu. La matrice de points de repère a été décrite comme une matrice 3x3. Ce choix permet d'obtenir une table de reconnais- sance de relativement faible taille pour les caractères latins et chiffres arabes. Bien entendu, si le jeu de caractères est plus complexe, on pourra prévoir des matrices plus grandes, par exemple 5x5 ou plus. REVENDICATIONS 1. Procédé de reconnaissance de caractères manuscrits, comprenant les étapes suivantes: - offrir à un utilisateur un support de tracé muni d'une matrice de points de repère (1-9) distinctement visibles et écartés, par lesquels l'utilisateur s'efforce de passer en tra- çant un caractère; identifier chaque segment (a-t) défini par deux points de repère successifs dans le tracé; et - extraire d'une table le caractère correspondant à l'ensemble des segments identifiés. 2. Procédé de reconnaissance selon la revendication 1, caractérisé en ce que la table stocke, pour chaque caractère à reconnaître, plusieurs ensembles de segments possibles. 3. Procédé de reconnaissance selon la revendication 1 ou 2, caractérisé en ce que chaque point de repère est associé à un détecteur déclenché par le passage du doigt de l'utilisateur ou d'un stylet, l'étape d'identification des segments consistant à relever la séquence des points de repère dans l'ordre o les détecteurs correspondants sont déclenchés, et à associer un segment à chaque couple de points successifs de la séquence. 4. Procédé de reconnaissance selon la revendication 1 ou 2, caractérisé en ce que les points de repère sont imprimés sur une feuille de papier, le procédé comprenant les étapes suivantes: - numériser l'image de la feuille de papier, et - identifier comme successifs deux points de repère reliés directement 1 'un à 1 'autre par une portion de tracé. 5. Procédé de reconnaissance selon 1 'une quelconque des revendication 1 à 4, caractérisé en ce qu'il comprend l'étape consistant à valider, dans un mot (ID) comprenant un bit par segment possible, les bits correspondant aux segments identifiés, les entrées de la table étant constituées de mots similaires ayant des bits adéquats validés. 6. Dispositif de saisie de caractères manuscrits comprenant un support de saisie muni d'une matrice de points de repère (1-9) distinctement visibles et écartés. 7. Dispositif de saisie selon la revendication 6, caractérisé en ce que chaque point de repère est associé à un détecteur susceptible d'être déclenché par le passage du doigt de l'utilisateur ou d'un stylet. 8. Dispositif de saisie selon la revendication 6 ou 7, caractérisé en ce que la matrice comporte neuf points de repère. 9. Dispositif de saisie selon la revendication 7, caractérisé en ce qu'il comporte des moyens de détection du contact du doigt ou du stylet avec le support de saisie. 10. Dispositif de saisie selon la revendication 9, caractérisé en ce que les moyens de détection du contact du doigt ou du stylet avec le support de saisie comprennent une première zone (10) entourant les points de repère, et une deuxième zone (12) entourant la première zone.