FR 2608294 A1 19880617 FR 8617623 A 19861215 SYSTEME DE MARQUAGE ET D'IDENTIFICATION AUTOMATIQUES Les techniques de production et de distribution modernes imposent de plus en plus que chaque exemplaire du produit traité soit muni d'un marquage permettant son identification très rapide et très fiable par un moyen autsmatique. la technique la plus connue à l'heure actuelle est celle du code à barres associé à des capteurs de type scanner, qui est largement utilisée notamment sur les emballages de nombreux produits. Ces emballages étant généralement imprimés, il est facile d'incorporer le code à barres dans cette irpression, en bénéficiant d'une bonne qualité. Dans un système flexible, on peut se trouver devant la nécessité de réaliser des marquages pouvant varier de façon très fréquente (d'autant plus fréquente que l'on vise un traitement par petits lots). Le marquage ne peut plus alors se faire par impression classique, mais doit faire appel à une technologie flexible, permettant de modifier le message par des moyens instantanés, qui sont généralement du domaine de l'informatique. Nous citerons principalement, à titre d'exemple - les imprimantes à aiguilles - les imprimantes à jet d'encre. On peut ainsi marquer soit le produit lui-même, soit un support sur lequel circule le produit, soit l'emballage temporaire ou définitif. Pour ce type d'utilisation, le code à barres est moins bien adapte pour un certain nombre de raisons - Les techniques de marquage précitées précédent par juxtaposition de points. Les codes à barres ainsi obtenus sont de présentation médiocre, ce qui peut entrainer des problèmes de fiabilité pour la lecture. - Les Scanners de lecture ont une robustesse qui peut-être insuffisante dans certains milieux industriels. - la code à barres est relativement enocobrant, ce qui peut poser problème quand il s'agit de nraruer des produits de faible dimension, sur lesquels on peut ne disposer que d'une surface réduite. (Ce dernier argument pouvant être valable indQpendemment de tout autre problème). La méthode proposée dans le cadre de la présente invention vise à s'affranchir de ces inconvénients. Elle s'appuie sur les principes suivants - Constitution d'un message à base de points, et non plus de traits. - Utilisation de deux dimensions significatives, au lieu d'une seule. - Lecture possible par cameras de type statique, notamment à matrices de diodes, dont la fiabilité en milieu industriel est reconnue. la principe de base consiste à faire supporter le message par une grille matricielle dont chaque case contient une information de type binaire - O si la case est laissée en blanc. - 1 si la case est marquée d'un point. Dans une première approche, nous allons examiner comment réaliser des messages purement numériques, au moyen de matrices pour lesquelles on recherchera la dimension minimale. Une matrice étant définie par m lignes et n colonnes, et le nombre maximum à représenter étant désigné par Pmax, on cherchera donc à minimiser le produit m x n. - matrice "longue" : n m - matrice "haute" : m n - matrice "compacte" : m ~ n limite : matrice "carrée" : m = n Le nombre de lignes m sera défini de telle sorte que chaque colonne (comportant donc n cases) puisse définir en binaire tout nombre compris entre O et b-l, b étant une base de numération choisie préférentiellement parmi les puissances entières de 2, à savoir 2, 4, 8, 16 ...etc Décrivons la colonne du haut vers le bas, et affectons aux cases successives les valeurs correspondant aux puissances entières croissantes de 2, à savoir - lère case = 1 - 2eme case = 2 - 3ème case = 4 - dernière case = 2 Considérons que toute case non marquée compte pour zéro, et que toute case marquée compte pour sa valeur conventionnelle. la nombre représenté par la colonne sera la somme des valeurs de toutes les cases marquées. La valeur maximum de ce nombre, correspondant au marquage de toutes les cases , est donnée par la formule classique du calcul binaire 2 m - 1, correspondant à b = 2 Pour m = 1 (matrice réctilte à 1 ligne) on a b = 2, et chaque colonne peut prendre la valeur O ou 1. Pour m = 2, on a b = 4 et chaque colonne peut prendre les valeurs O, 1, 2, ou 3. Pour m = 3, on a b = 8, et chaque colonne peut prendre les valeurs comprises entre O et 7. Les représentations issues de ce dernier exemple sont données sur la figure 1. Considérons maintenant l'ensemble des valeurs des n colonnes de la matrice comme les chiffres représentatifs d'un nombre P, défini dans la base de numération b. Décrivons cet ensemble de la droite vers la gauche, et désignons par x1 , X2 , X3 , ... Xn les valeurs des colonnes rencontrées.Associons à cet ensemble un autre ensemble de nombres Y1, Y2, y3 .... y, définis comme suit Yi = X1 Y2 = x2 x b y3 = X3 X b Y4 = X4 X b Yn = Xn X bn- On aura alors : P = Y1 + Y2 + Y3 + ---- Yn La valeur Pmax correspond au marquage de toutes les cases de la matrice, c'est-a-dire à X1 = X2 = X3 = ------ Xa = b - 1 Ce qui donne: Pmax = (b-l) ( 1 + b + b2 + b3 + - soit, en effectuant Panax = bn -1 ou encore : Panax = (2m)n -1 = 2mn - 1 Ce qui montre - que la capacité de représentation numérique d'une matrice dépend uniquement de son nombre de cases mn. - que cette capacité est la meme si on inverse le nombre de lignes et le nombre de colonnes. On peut d'ailleurs noter que, si on balaye toutes les cases de la matrice, dans l'ordre croissant des colonnes, tout se passe comme si on rencontrait successivement toutes les puissances entieres de 2 2. à 2m - 1 pour la 1ère colonne 2m à 2m- pour la 2ème colonne 2(n-1)m à 2(n.m)-1 pour la nième colonne On pourrait donc procéder par codage en binaire pur, ce qui reviendrait à remplacer la matrice de dimensions m;n par une matricevecteur de dimensions 1; m.n, tout en conservant l'avantage de pouvoir jouer sur la forme géométrique du message. Entre le binaire pur, et le passage par les valeurs intermédiaires correspondant à chaque colonne, le choix ne pourra porter que sur des considérations de facilité de traitement, tant qu'on travaille en numérique pur. Par contre, si on travaille en alphanumérique, ou en numérique décimal, comme on le verra plus loin, le passage par les valeurs de colonnes devient beaucoup plus judicieux. La figure 2 donne la liste des matrices de 4 à 20 cases, avec les capacités Pmax correspondantes. On voit - que la capacité de représentation augmente très rapidement avec le nombre de cases. - que, pour une capacité souhaitée, on a toujours la possibilité de choisir, en fonction de l'emplacement dont on dispose, entre plusieurs solutions. Par exemple, si le nombre maximum à représenter est 30 000, on pourra utiliser au choix 3x5 ou 5 x 3 ; 2x8 ou 8 x 2 2 4x4 D'autres caractéristiques de l'invention ressortiront de la description qui va suivre de différents modes de réalisation de l'invention représentés aux figures 3 à 10. Le marquage selon la figure 3 comporte une matrice rectangulaire 10 à cinq colonnes 12 et trois lignes 14, définissant quinze cases 16. Chaque case 16 est soit vierge, soit marquée d'un point 18. lors d'un marquage des cases 16, selon la convention susmentionnée d'une valeur O pour une case vierge et d'une valeur 1, 2 et 4 associée aux cases 16, respectivement des première, deuxième et troisième lignes, marquées d'un point 18, il est facile de voir que la figure 3 donne, à titre d'exemple, la représentation du nombre 19987, (la base de numération étant 8). On peut bien entendu, sans sortir du cadre de l'invention, modifier les conventions utilisées jusqu'ici, ctest-àvdire décrire les colonnes du bas vers le haut ou les lignes de la gauche vers la droite, ou inverser les rôles des lignes et des colonnes. On peut également utiliser des bases de numération autres que les puissances entières de 2, en particulier la base 10. Pour celle-ci, il faut une matrice de 4 lignes, permettant à chaque colonne de représenter les nombres de O à 15, dont on utilisera que le sous-ensemble de O à 9. La figure 4 montre la représentation du nombre 19987 selon cette méthode, qui est moins performante que la précédente, puisqu'il y a des configurations de marquage non utilisées. Dans certains cas, ces configurations (au nombre de 6, correspondant aux nombres de 10 à 15) pourraient être récupérées, Si besoin était, pour représenter des symboles autres que des chiffres Si le nombre total de symboles à représenter est supérieur à 15, il faut passer à des matrices ayant un nombre de lignes plus élevé. Par exemple, une matrice de 6 lignes permet de représenter 64 symboles, parmi lesquels on peut avoir - les 10 chiffres de O à 9 - les 26 lettres de l'alphabet, correspondant, par exemple, aux nombres de 10 à 35. - 28 possibilités suFplémentaires pour tous les autres symboles dont on peut avoir besoin. Le message obtenu est alors une chaîne de symboles qui peut avoir une signification littérale, numérique, ou un mixage des deux. La figure 5 montre la représentation du message AX. 935 (en supposant que le point soit représenté par le nombre 36). Enfin, on peut également adopter des représentations mixtes pour des messages dont la structure présente des aspects invariables. Supposons par exemple la structure suivante, qui correspond d'ail leurs à l'exemple de la figure 5 - Deux lettres - point - un nombre de O à 999. pour représenter ce type de message dans un minimum d'encombrement, on utilisera une matrice de dimensions 5 x 4. Les deux premières colonnes seront consacrées aux deux lettres, ce qui explique le choix de la dimension 5. Cette dimension offre en effet 25 = 32 possibilités, ce qui est suffisant pour les 26 lettres de l'alphabet. Pour la partie numérique, deux colonnes suffiront, puisqu'elles permettent de constituer une sous matrice de dimensions 5 x 2, qui offre 1024 possibilités. Quant au point de séparation, on peut l'omettre, dans la mesure od il a un caractère systématique. La figure 6 donne la matrice qui représente le message AX. 935 selon ce principe. Par rapport à la figure 5, on peut noter une importante réduction d'encombrement. Bien entendu, le logiciel de décodage doit alors être spécifique à l'application traitée. Nous allons maintenant examiner des dispositions visant à améliorer la fiabilité de la méthode, ou la facilité de décodage des messages. La première disposition consiste à remplacer le point unique imprimé dans une case par un ensemble de plusieurs points. Cela ne présente pas de difficulté d'ordre pratique, si on utilise des inprimantes à aiguilles ou à jet d'encre, qui sont capables de délivrer très rapidement un grand nombre de points de petite dimension. A titre d'exemple, on peut imaginer que le marquage d'une case de la matrice soit matérialisé par 4 points disposés en carré. On peut alors conventionnellement admettre que la case sera considérée comme marquée si on constate la présence des 4 points, mais aussi seulement de 3, ou wême de 2 points, et comme non marquée si on observe zéro, ou seulement un point. On vise ainsi à se prémunir - Oontre un raté" de 1' inp'rimante se traduisant par la non-apparition d'un point qui devrait être présent (la probabilité d'avoir 2 ou 3 ratés adjacents étant extrêmement faible). - Oontre la présence d'une tache de petite dimension qui pourrait être interprétée comme un point marqué. La figure 7 donne un exemple de quelques interprétations possibles. La deuxième disposition consiste à délimiter la matrice par un cadre, ce qui est généralement nécessaire pour son interprétation (sauf si, lors de la lecture, le message est positionné de façon rigoureuse devant la camera). En effet, sur les figures 3 à 6, nous avons matérialisé les cases des matrices par des lignes horizontales et verticales. Généralement dans la réalité, ces lignes n'existeront pas, ce qui peut poser des problèmes de localisation, donc de confusion dans la lecture. La solution proposée consiste à encadrer la matrice dans un rectangle réalisé Sous forme d'alignement de points. L'analyse de l'image commence alors par une localisation optimale de ce rectangle dans le plan rétinien de la caméra, d'od on peut faire découler le positionnement de toutes les cases de la matrice. Il suffit alors d'analyser la lunière reçue pour chaque portion du plan rétinien correspondant à une case donnée pour déterminer si cette case est marquée ou non. La figure 8 est une présentation de la matrice représentative du noo- bre 2137 en base 16, faisant appel au marquage à 4 points par case, et faisant apparaitre le cadre rectangulaire. L'ensemble du message est contenu dans un rectangle de 10 x 8 points, ce qui est une forme particulièrement compacte. (Physiquement l'ordre de grandeur de l'encombrement pour rait descendre à un carré de 2 à 3 itin de côté, si né nécessaire). On pourrait encore réduire un peu en supprimant deux côtés adjacents du cadre rutaugulaire. Les dimensions de la matrice étant constantes, et connues du logiciel de décodage, il suffit en effet de placer 2 axes de coordonnées pour définir le positionnement de la matrice. La figure 8bis représente ce que devient la matrice de la figure 8 en ne conservant que les côtés inférieur et gauche du cadre. le fait d'avoir recherché la compacité maximum peut toutefois présenter un inconvénient. Le plan rétinien de la caméra étant en effet composé de cellules discontinues (pixels) il pourra arriver qu'un pixel soit à cheval sur 2 cases de la matrice, ou sur une case et sur le cadre externe. Ce phdnonfne peut rendre l'interprétation plus difficile. On peut s 'en affranchir dans une large mesure en créant des marges entre les cases d'une part, entre les cases et le cadre d'autre part, la largeur minimum de eette marge étant d'un module (module étant pris dans le sens de pas d'impression des points). La figure 9 donne une nouvelle représentation du nombre 2137, dans laquelle des marges de 1 module ont été introduites. Un autre avantage de cette dernière disposition est d'introduire une meilleure fiabilité vis à vis du problème des taches. En l'absence de marges, une tache couvrant une partie appréciable d'une case entraînera un risque de faire considérer cette case commue marquée même si elle ne l'est pas. Dans le systime avec marges, on peut détecter de nombreuses taches dans la mesure ou celles-ci intéressent les marges qui doivent normalement toujours rester vierges.Dès lors, toute anomalie de marge pourra être interprétée commue la présence d'une tache, donc rendre le message suspect et déclencher une alarme (le refus de lecture étant un défaut mineur, alors que l'erreur d'interprétation est un défaut majeur.) Une autre méthode permettant de bien séparer les cases les unes des autres consiste à le faire non avec des marges vierges, mais au contraire avec des bandes pleines. Ces bandes peuvent alors également être utilisées pour la localisation de la matrice, ce qui permet de se dispenser du cadre ou des axes de coordonnées. Cette méthode sera moins efficace pour déceler des taches éventuelles, mais le sera par contre pour déceler des manques dans l'impression. La figure 9bis représente la transposition de la figure 9 dans cette technique. Enfin, une dernière disposition visant à obtenir une fiabilité quasi parfaite consistera à mettre à profit le faible encombrement de la matrice utilisée pour en placer deux cote à cote et ne déclarer le message validé que s'il y a concordance entre l'interprétation des 2 matrices. (La probabilité pour que les 2 matrices présentent le même défaut au même endroit étant extrêmement réduite). En poussant le raisonnement encore plus loin, on peut placer 3 matrices, et valider le message s'il y a concordance entre 2 d'entre elles, ce qui permet d'éviter un refus de lecture en cas de défaut ponctuel. Rfmarquons pour terminer que toutes les figures présentées sont constituées de juxtapositions de points comme on peut en obtenir par exemple avec un marquage au jet d'encre, mais qu'elles peuvent avoir un aspect différent si elles sont réalisées par un procédé d'inpression classique, qui peut fournir des graphismes plus variés. La figure 9ter est un exemple de ce que pourrait devenir la figure 9 dans un tel cas. Sur les figures 8 à 9ter, les matrices ont été présentées avec des dimensions importantes, pour la clarté des dessins. Dans la pratique, elles peuvent être, si nécessaire, beaucoup plus petites (à un facteur 10 par exemple). Concernant la réalisation pratique, le dispositif de lecture se oomposera : - d'une caméra à matrice de pixels. - d'un dispositif d'éclairage (si nécessaire). - d'un dispositif de traitement. Concernant la caméra, celle-ci ne nécessite pas un niveau de sophis- tication très élevé . las dimensions de la matrice de pixels nécessaire dépendent évidement de celles de la matrice de points à lire, et de la précision avec laquelle se fait la prise de vue. Le paramètre de correspondant significatif est le rapport K entre le pas P1 des pixels et celui P2 de la matrice observée, ramenée à son image sur la rétine de la caméra. On trouvera sur la figure 10 un exemple avec K = 8, qui parait déja très suffisant pour éviter toute erreur d' interprétation. Si les dimensions de la matrice à lire sont par exemple 6 x 6, elle occupera sur la rétine de la caméra un carré de 48 x 48 pixels. Si la prise de vue est assez précise, une rétine légèrement plus grande, par exemple 60 x 60 pixels, sera suffisante. Dans le cas contraire, on pourra avoir besoin d'augmenter ce nombre, par exemple jusqu'à 100 x 100 pixels, ce qui est encore très peu par rapport aux possibilités des caméras actuelles, qui atteignent 500 x 500 pixels. Il n'y a donc pas de problème de performance de la caméra, la limitation de celle-ci au niveau requis ne se justifiant que par des considérations de prix. Bien entendu, si la matricé à lire est rectangulaire, ou si la prise de vue porte sur plusieurs matrices accolées, on peut utiliser une caméra à rétine rectangulaire. Enfin , selon l'utilisation, la caméra peut être montée sur un support fixe devant lequel vient se positionner l'objet à identifier, ou au contraire être de type portatif, par exemple pour être présentée par un opérateur devant ledit objet. Dans ce dernier cas, il faut évidemment compter sur une certaine irtprécision, donc faire en sorte que l'image de la matrice à lire sur la rétine de la caméra n'occupe pas une trop grande fraction de celle-ci. Il faut aussi envisager un certain défaut de parallélisme entre la matrice à lire et la trame des pixels de la caméra. Ce défaut n'entraine pas de problème particulier, si ce n'est de prévoir dans le logiciel de traitement l'algorithme nécessaire au positionnement de la matrice à lire sur la rétine, et à l'établissement de la correspondance entre les cases de la première et les pixels de la seconde. Un tel algorithme relève des techniques classiques du traitement d'image, et ne sera pas décrit ici. Concernant le dispositif de traitement, celui-ci n'a pas non plus à être très sophistiqué du point de vue de l'analyse d'image. En particulier,il n'est pas nécessaire de pouvoir sélectionner de nombreux niveaux de gris, puisque la mesure se fait par tout ou rien. En fonction du type de décodage à effectuer, le dispositif de traitement pourra se présenter sous deux formes - logique câblée : cette solution est possible si on fait appel à un codage de type universel, donc assez répétitif pour justifier la création de cette logique. Les avantages de cette solution sont l'économie et l'instantanéité du traitement. - microprocesseur, si on fait appel à un codage spécifique, pour lequel il faut pouvoir programmer à la demande des algorithmes de décodage. Dans tous les cas, le dispositif de traitement doit évidemment pouvoir émettre un signal de sortie exploitable par tout récepteur envisageable : écran, imprimante, automate programmable....etc. REVENDICATIONS 1) Système optique de marquage et d'identification caractérisé en ce que le support du message à véhiculer est une matrice (10) rectangulaire dont chacune des cases (16) porte une information binaire traduite par une case vierge, ou une case marqrée d'un point 818). 2) Système selon revendication 1 dans lequel le message est purement numérique, caractérisé en ce que chaque colonne (12) de la matrice (10) représente un nombre codé en binaire, et en ce que l'ensemble de ces nombres constituent les chiffres représentatifs du nombre général à représenter, dans une base de numération appropriée, et notamment la base la plus élevée compatible avec le nombre de lignes m de matrice à savoir 2". 3) Système selon revendication 1, caractérisé en ce que le message est une suite de symboles alphanumériques codés de telle sorte qu'à chaque symbole corresponde un nombre représentatif, chaque colonne (12) pouvant représenter un symbole quelconque par son nombre représentatif codé en binaire. 4) Système selon revendication 1, caractérisé en ce qu'on utilise un codage mixte, en utilisant certaines parties de la matrice en codage numérique, et d'autres parties en codage de symboles. 5) Système selon une quelconque des revendications précédentes, caracté risé par l'utilisation pour la génération de la matrice d'un équipe ment de marquage flexible procédant par impression de points. 6) Système selon revendication 5, caractérisé en ce qu'on recherche une amélioration de la fiabilité en réalisant le marquage d'une case (16) par plusieurs points (18) juxtaposés, et en considérant la case tomme parquée si un nombre minimum de points est effectivement présent. 7) Système selon une quelconque des revendications précédentes, caracté risé en ce qu'on détermine le positionnement de la matrice (10) en entourant celle-ci par un cadre rectangulaire, ou en la soulignant par deux axes de coordonnées oonstituant la moitié dudit cadre. 8) Système selon une quelconque des revendications précédentes, caracté risé en ce qu'on recherche une amélioration de la fiabilité en isolant les cases les unes des autres par le moyen de bandes placées entre les lignes et entre les colonnes, ces bandes pouvant être vierges ou pleines selon le but recherché. 9) Système selon une quelconque des revendications précédentes, caracté risé en oe qu'on recherche une amélioration de la fiabilité en imprimant plusieurs matrices, et en déclarant le message validé s'il est lu sur un nombre minimal de ces matrices. 10) Système selon une quelconque des revendications précédentes, caractérisé en ce que l'organe de lecture est constitué par une caméra à matrice de pixels, alimentant un organe de traitement d' image électronique de type câble ou programmable.