Brevet FR2831303A3 — publié le 20030425

FR 2831303 A3 20030425 FR 0113565 A 20011022 "PROCEDE DE RECONNAISSANCE DE CARACTERES" La présente invention se rapporte à un procédé de reconnaissance de caractères à partir d'une trace réalisée sur un écran tactile d'un ordinateur de poche par exemple. Un ordinateur de poche ou assistant numérique personnel, présente généralement un écran tactile sur lequel l'utilisateur peut saisir de façon naturelle au moyen d'un stylet un ensemble de caractères : lettres, chiffres... D'une façon générale, au niveau de la programmation le stylet est équivalent à une souris d'un micro-ordinateur conventionnel. La trace laissée par ce stylet doit être détectée puis analysée afin d'en déduire un caractère pré-déterminé. Habituellement, on utilise un algorithme qui représente la trace réalisée sous forme d'une suite de points ordonnés. Un traitement est alors effectué sur l'ensemble des points de façon à approximer un caractère pré-déterminé. Or, un tel traitement fait intervenir une suite de points d'une très grande taille ce qui rend l'algorithme complexe et lent. La présente invention à pour objet de simplifier un tel algorithme en limitant la quantité de données à traiter. La présente invention à également pour objet un nouveau procédé de reconnaissance de caractères présentant un traitement rapide et applicable pour tout type de tailles de caractères. L'invention propose donc un procédé de reconnaissance de caractères à partir d'une trace réalisée sur écran tactile. Avantageusement, ce procédé comprend : - une première étape de création de listes dans lesquelles on répertorie les coordonnées de l'ensemble des points composant la trace, - une seconde étape de vectorisation au cours de laquelle on définit un ensemble de vecteurs le long de cette trace, - une troisième étape de standardisation au cours de laquelle on traite l'ensemble des vecteurs ainsi définis de façon à aboutir à un nombre de vecteurs prédéterminé, et - une quatrième étape de reconnaissance au cours de laquelle on compare les vecteurs définis pour la trace avec un ensemble de vecteurs prédéfinis d'un même caractère, la comparaison étant effectuée pour chaque caractère préalablement saisie par un utilisateur et vectorisé selon la seconde étape, la trace étant assimilé à un caractère pour lequel la comparaison présente une erreur minimum. En d'autres termes, à chaque suite de coordonnées de points pour une trace donnée, on va associer un ensemble ordonné de vecteurs composant le squelette de cette trace. Donc, au lieu d'utiliser la représentation conventionnelle par points, on utilise une représentation vectorielle selon l'invention. Pour démontrer l'efficacité d'une telle approche, il faut savoir que une image ou trace d'une lettre nécessite environ 150x150 points, soit 22500 bits. Pour la même image l'ensemble des vecteurs nécessite seulement 8 points. Cette représentation selon l'invention permet également de représenter de la même manière des images semblables de tailles différentes. Les vecteurs prédéfinis peuvent provenir d'une phase d'apprentissage préalable au cours de laquelle on demande à l'utilisateur d'entrer tous les caractères. On associe un ensemble de vecteurs à chaque caractère saisi, de la même manière que la seconde étape, et on stocke ces vecteurs prédéfinis dans une base de données. Puis, on utilise cette base pour effectuer la reconnaissance au cours d'une phase d'utilisation. Selon une caractéristique avantageuse de l'invention, chaque liste correspond à un contour connexe, c'est-à-dire que les points dont les coordonnées sont inscrites dans une même liste correspondent à une partie connexe de la trace. Avantageusement, au cours de la première étape, on commence au début de la trace et on continue en avançant le long de cette trace. Dès qu'il y a une discontinuité, on entame une nouvelle liste. Plus précisément, la vectorisation consiste, en partant du point de départ de la trace et pour chaque liste créée, à définir un vecteur pour chaque changement soudain de direction ou chaque diminution de norme vectorielle. En fait, on effectue l'association de l'image de la trace à un ensemble de vecteurs. On commence la création des vecteurs à partir du début des listes des points des contours. On fait des parcours selon le contour, et on s'arrête au moment où la courbe, représentant le contour graphiquement, tourne d'une manière brusque, c'est-à-dire un changement soudain de direction ou bien une diminution de norme vectorielle. C'est alors que l'on entame la création d'un nouveau vecteur. Selon un mode mise en ouvre avantageux de l'invention, au cours de la troisième étape de standardisation, si le nombre des vecteurs définis est supérieur au nombre prédéterminé, on supprime les vecteurs définis les plus courts. Par contre, si le nombre des vecteurs définis est inférieur au nombre prédéterminé, on répète l'algorithme suivant autant de fois que la différence entre le nombre des vecteurs définis et le nombre prédéterminé : - on choisit le vecteur le plus long, et - on le partitionne en deux nouveaux vecteurs colinéaires et de même sens. Cette troisième étape est une étape de normalisation des vecteurs définis, de façon à standardiser ladite trace et à obtenir un ensemble de points se situant dans le carré [0, 1] x [1, 01. Ce carré comprend donc l'ensemble des vecteurs numérisés et recueillis. De préférence, on calcule l'erreur de la comparaison en sommant les normes vectorielles des différences entre chaque vecteur défini et le vecteur prédéfini correspondant.. Le caractère avec lequel l'erreur est minimale est considéré le plus semblable, donc la réponse à afficher. Suivant un autre aspect de l'invention, il est proposé un ordinateur de poche comprenant un écran tactile, des moyens de stockage et de traitement de données. Selon l'invention, cet ordinateur de poche comprend : - des moyens pour détecter l'ensemble des points d'une trace réalisée sur l'écran tactile, - des moyens pour créer des listes dans lesquelles on répertorie les coordonnées de l'ensemble des points composant ladite trace, - des moyens pour vectoriser ladite trace en définissant un ensemble de vecteurs le long de ladite trace, - des moyens pour standardiser cet ensemble de vecteurs en les traitant de façon à aboutir à un nombre de vecteurs prédéterminé, et - des moyens pour comparer ces vecteurs ainsi définis avec un ensemble de vecteurs prédéfinis d'un même caractère, la comparaison étant effectuée pour chaque caractère préalablement saisie par un utilisateur et vectorisé selon la seconde étape, et la trace étant assimilée à un caractère pour lequel la comparaison présente une erreur minimum. Il est décrit ci-après à titre d'exemple, nullement limitatif et en référence aux dessins annexés, un procédé de reconnaissance de caractères selon l'invention : - la figure 1 est une vue schématique simplifiée d'un assistant numérique personnel mettant en oeuvre un procédé selon l'invention ; - la figure 2 est une vue d'une trace vectorisée selon l'invention ; et - la figure 3 est un schéma illustrant une étape de standardisation selon l'invention. En référence à la figure 1, on voit un ordinateur de poche ou assistant numérique personnel 1 doté de moyens de traitement informatiques nécessaires (moyens de stockage, micro-processeurs, interface d'entrée/sortie,...) pour la mise en oeuvre de la présente invention. Cet assistant numérique personnel 1 présente un écran tactile 3 sur lequel on peut écrire au moyen d'un stylet 2. Pour la mise en oeuvre de l'invention, on demande à un utilisateur, par exemple lors d'une première utilisation, de saisir tous les caractères. A titre d'exemple, l'utilisateur écrit le caractère" " 4. Un algorithme selon l'invention, localisé dans les moyens de traitement de l'assistant numérique personnel, effectue une opération de vectorisation conformément à l'illustration de la figure 2. Cette étape correspond à une étape d'apprentissage ou d'étalonnage au cours de laquelle, pour chaque caractère saisi par l'utilisateur, on détermine un ensemble de vecteurs représentant le contour de ce caractère. Ces vecteurs sont ensuite stockés dans une base de données de l'assistant numérique personnel. Au cours de l'utilisation normale de l'assistant numérique personnel, lorsque l'utilisateur saisit un caractère, en réalité il effectue une trace pour laquelle l'algorithme selon l'invention doit déterminer un caractère correspondant, et permettre l'affichage de ce caractère. La première étape consiste à traiter la trace. Pour se faire, on créé des listes de points, c'est à dire un tableau de listes, chaque liste ne correspondant qu'à un seul contour connexe. En effet, on considère la série des points consistant la trace sous forme de plusieurs parties connexes. Par connexe, on entend une surface telle qu'on peut joindre deux quelconques de ces points par un trait continu sans quitter cette surface. De préférence, on change de listes à chaque fois qu'il y a une discontinuité. La seconde étape est une étape de vectorisation permettant d'affecter un ensemble de vecteurs au contour de la trace. On considère chaque liste les unes à la suite des autres. On commence la création des vecteurs à partir du premier point de chaque liste : on avance selon le contour, chaque point est représenté par un ensemble de coordonnées, si la norme du vecteur diminue alors qu'on avance ou si la norme de la différence entre les vecteurs avant et après ce prolongement est plus grande qu'une limite prédéterminée, on s'arrête pour définir un premier vecteur et on entame la définition d'un nouveau vecteur à partir de ce point d'arrêt. On répète ainsi la même opération jusqu'à la fin des points. La vectorisation permet d'obtenir un ensemble de vecteurs définis 6 le long de la trace 5 conformément à la figure 2. L'application du procédé peut conduire à une quantité de vecteurs définis différente pour des traces différentes. Selon l'invention, on prédéfinit un nombre de vecteur devant être reconnu. En d'autres termes, pour toute trace saisie par l'utilisateur, cette trace doit comprendre un nombre prédéterminé de vecteurs définis selon la seconde étape (voir figure 2). On réalise alors une troisième étape de standardisation au cours de laquelle on cherche à égaler le nombre de vecteurs définis selon l'étape 2 au nombre prédéfini. Pour se faire, si le nombre de vecteurs définis 6 est supérieur au nombre prédéterminé, on supprime les vecteurs définis les plus courts. Par contre, si le nombre de vecteurs définis 6 est inférieur au nombre prédéterminé, alors on calcule un nombre n égal à la différence entre le nombre prédéfini et le nombre de vecteurs définis 6, et on réalise n itérations de l'algorithme suivant dont une illustration est représentée sur la figure 3 : - pour chaque caractère, on prend l'ensemble des vecteurs définis 6 et on choisit le vecteur définit 6 le plus long, - on divise ce vecteur défini le plus long en deux parties qui peuvent être égales de sorte que le nombre de vecteurs définis 6 augmente d'une unité, - on classe ces deux nouveaux vecteurs définis en respectant l'ordre des coordonnées, c'est à dire que le premier nouveau vecteur correspond au début du vecteur le plus long jusqu'au milieu de ce vecteur le plus long, et le deuxième nouveau vecteur correspond au milieu de ce vecteur défini le plus long jusqu'à la fin de ce vecteur défini le plus long. L'ensemble des vecteurs obtenus à la suite du procédé illustré sur la figure 2 sont contenu dans l'ensemble 7. Par exemple, conformément à la figure 3, la première itération a permis de former deux nouveaux vecteurs rangés à la deuxième et troisième place de l'ensemble 8 à partir du vecteur (le deuxième) le plus long de l'ensemble 7. A la fin de toutes les itérations, on obtient un nombre de vecteurs définis 6 identiques au nombre prédéterminé. C'est avec cet ensemble de vecteurs définis 6 qu'on réalise l'étape 4 de reconnaissance. La trace saisie par l'utilisateur peut être une trace qui, vis-à-vis du caractère correspondant, est déformée, de grande ou petite taille. Pour réaliser la reconnaissance, on effectue d'abord une comparaison entre les vecteurs ainsi définis et chaque ensemble de vecteurs prédéterminés d'un caractère. Ainsi, on parcourt les caractères stockés dans la base de données et on calcule la somme des normes vectorielles des différences entre le premier vecteur défini avec le premier vecteur prédéfini, le deuxième vecteur défini avec le deuxième vecteur prédéfini, etc. On estime ensuite l'erreur comme étant la norme de la somme ainsi calculée et on choisit le caractère pour lequel l'erreur est la plus faible. C'est ce caractère qui sera affiché sur l'écran. Bien sûr, l'invention n'est pas limitée aux exemples qui viennent d'être décrits et de nombreux aménagements peuvent être apportés à ces exemples sans sortir du cadre de l'invention. REVENDICATIONS Procédé de reconnaissance de caractères à partir d'une trace réalisée sur un écran tactile, caractérisé en ce qu'il comprend : - une première étape de création de listes dans lesquelles on répertorie les coordonnées de l'ensemble des points composant ladite trace, - une seconde étape de vectorisation au cours de laquelle on définit un ensemble de vecteurs le long de ladite trace, - une troisième étape de standardisation au cours de laquelle on traite l'ensemble des vecteurs ainsi définis de façon à aboutir à un nombre de vecteurs prédéterminé, et - une quatrième étape de reconnaissance au cours de laquelle on compare les vecteurs définis pour ladite trace avec un ensemble de vecteurs prédéfinis d'un même caractère, la comparaison étant effectuée pour chaque caractère préalablement saisie par un utilisateur et vectorisé selon la seconde étape, et en ce que l'on assimile ladite trace à un caractère pour lequel la comparaison présente une erreur minimum. 2. Procédé selon la revendication 1, caractérisé en ce que chaque liste correspond à un contour connexe. Procédé selon la revendication 2, caractérisé en ce qu'au cours de la première étape, on entame une nouvelle liste à chaque discontinuité rencontrée. 3. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que la vectorisation consiste, en partant du point de départ de la trace et pour chaque liste crée, à définir un vecteur pour chaque changement soudain de direction ou chaque diminution de norme vectorielle. 4. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'au cours de la troisième étape de standardisation, si le nombre des vecteurs définis est supérieur au nombre prédéterminé, on supprime les vecteurs définis les plus courts, et en ce que si le nombre des vecteurs définis est inférieur au nombre prédéterminé, on répète l'algorithme suivant autant de fois que la différence entre le nombre des vecteurs définis et le nombre prédéterminé : - on choisit le vecteur le plus long, et - on le partitionne en deux nouveaux vecteurs colinéaires et de même sens. 5. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que pour chaque caractère, on calcule l'erreur de la comparaison en sommant les normes vectorielles des différences entre chaque vecteur défini et le vecteur prédéfini correspondant. 6. Ordinateur de poche comprenant un écran tactile, des moyens de stockage et de traitement de données, caractérisé en ce qu'il comprend - des moyens pour détecter l'ensemble des points d'une trace réalisée sur l'écran tactile, - des moyens pour créer des listes dans lesquelles on répertorie les coordonnées de l'ensemble des points composant ladite trace, - des moyens pour vectoriser ladite trace en définissant un ensemble de vecteurs le long de ladite trace, - des moyens pour standardiser cet ensemble de vecteurs en les traitant de façon à aboutir à un nombre de vecteurs prédéterminé, et - des moyens pour comparer ces vecteurs ainsi définis avec un ensemble de vecteurs prédéfinis d'un même caractère, la comparaison étant effectuée pour chaque caractère préalablement saisie par un utilisateur et vectorisé selon la seconde étape, et en ce que l'on assimile ladite trace à un caractère pour lequel la comparaison présente une erreur minimum.