Brevet FR2533044A1 — publié le 19840316

Procédé d'introduction de données de modèles graphiques. La présente invention concerne un procédé pour introduire dans un dispositif de mémoire des données numérisées de modèles graphiques à deuxvaleurs d'un caractère ou d'un symbole, et en particulier elle concerne un tel procédé qui permet de tracer automatiquement sans erreur toutes les lignes de contour apparaissant dans chaque caractère. La présente invention est très utile, notamment dans la photo-composition à commande par ordinateur Une machine de photo-composition à commande par ordinateur est un disposi- tif pour enregistrer des documents en stockant électronique- ment un grand nombre de modèles graphiques de caractères et de symboles et en les utilisnt selon le besoin pour commander un dispositif d'enregistrement, par opposition à une machine de photo-composition classique qui projette et expose photographiquement des modèles de caractères tracés sur une plaque originale sur la surface d'un support photosensible au moyen d'un système de lentilles optiques. Pour qu'une telle machine de photo-composition à commande par ordinateur soit pratiquement utile, il est nécessaire de stocker sans omission les modèles graphiques de tous les caractères et symboles qui peuvent apparaltre dans les documents à reproduire Il en résulte la nécessité d'un dispositif de mémoire extrêmement vaste, notamment lors- que ce sont des documents japonais ou chinois qui doivent être enregistrés ou produits avec la machine, du fait que les documents japonais ou chinois comportent normalement des milliers de kanjis différents (caractères chinois). Comme technique pour numériser un modèle graphique et le stocker dans un dispositif de mémoire, on sait par exemple diviser les régions deemodèles de chaque caractère en un grand nombre de minuscules pixels et stocker l'état de chaque pixel sous forme d'un signal à deux valeurs selon que le pixel est noir (portion de ligne graphique) ou blanc (portion de non ligne graphique). Cependant, pour maintenir la qualité des images d'original reproduites, il est nécessaire de choisir aussi petite que possible la dimension de chaque pixel et augmenter le pou- voir de résolution D'autre part, l'accroissement du nombre de pixels entraîne la nécessité d'une capacité de mémoire plus grande et de ce fait une augmentation du volume de travail et des coûts impliqués dans l'introduction des données. La technique de compression des données connue sous le nom de procédélrun-length" présente l'inconvénient d'une capa- cité de compression insuffisante, le rendement de compres- sion étant compris entre 30 et 40 %. En particulier quand il s'agit de kanjis (caractères chinois) qui sont couramment utilisés au Japon, du fait qu'ils com- portent de nombreux éléments compliqués et que leur nombre est grand par comparaison avec l'alphabet romain, chaque caractère doit être divisé en un grand nombre de pixels et la capacité de la mémoire et le volume de travail exigés pour stocker les données afin de couvrir l'assortiment com- plet indispensable de caractères sont si grands que c'est considéré comme la raison majeure du retard constaté dans le développement et la popularisation de la photo- composition à commande par ordinateur au Japon. Un but principal de cette invention est de procurer un procédé pour introduire dans un dispositif de mémoire des données de modèles graphiques, qui permet de comprimer con- sidérablement les données à stocker sans endommager la qualité des images d'original reproduites 0- Le procédé de cette invention est basé sur le fait que la ligne de contour d'un modèle graphique qui est exprimée par unsignal à deux valeurs peut comporter une ou plusieurs lignes en forme de boucle fermée et, selon le procédé de cette invention, on sélectionne un point de référence sur chaque ligne de contour, et la ligne de contour est tracée à partir du point de référence/ les valeurs des coordonnées des points nécessaires le long de la ligne de contour détec-_ tés lorsqu'on trace cette ligne de contour sont introduites dans un dispositif de mémoire et y sont stockées comme données du modèle graphique. Selon le procédé de l'invention, les buts exposés ci-dessus peuvent être atteints en procurant un procédé pour intro- duire dans un dispositif de mémoire des données numérisées de modèles graphiques à deux valeurs d'un caractère ou d'un symbole, caractérisé en ce que la ligne de contour du modèle graphique est tracée à partir d'un point de départ disposé sur la ligne de contour et que les données de position des points d'échantillonnage détectés au cours du tracé de la ligne de contour sont stockées en séquende dans le dispo- sitif de mémoire comme données du modèle graphique. L'invention sera mieux comprise à la lecture de la descrip- tion détaillée, donnée ci-apriès à titre d'exemple seulement, d'une réalisation préférée, en liaison avec le dessin joint, sur lequel: la figure 1 est un organigramme indiquant les stades de lecture et de compression des données de modèles graphiques selon le procédé de cette invention:; 2.533044 la figure 2 montre des vues schématiques représentant une manière de sélectionner des pixels situés le long d'une ligne de contour; et la figure 3 eàt une vue schématique d'une table de modèle selon le procédé de cette invention, Tout d'abord, une région d'un modèle graphique à stocker est finement divisée par une grille en pixels et les données de chaque pixel sont stockées dans un dispositif de mémoire sous forme d'un signal à deux valeurs Ceci est similaire à ce qui est fait dans les procédés classiques. Cependant, selon le procédé de l'invention, l'ensemble des données stockées n'est pas destiné à être utilisé come données accumulées pour une machine de photo-composition à commande par ordinateur, mais seule la portion des données qui sont nécessaire epour reproduire et l'analogue concerné est extraite des données stockées. Ensuite, les pixels situés sur fa ligne de contour du modèle d'image d'original sont sélectionnés parmi la totalité des pixels Ceci est fait en comparant les données d'un pixel à celles des pixels adjacents, comme on le voit sur la figure 2. Sur la figure 2, les pixels hachurés et ceux repérés par un petit cercle étant supposés être respectivement noira(por- tion de ligne graphique) et blancs(portion de non ligne graphique), lorsque les données d'un ou de plusieurs pixels adjacents à un pixel central sont différentes de celles du pixel central comme on le voit sur la figure 2 (A), le pixel central est déterminé comme étant situé sur la ligne de contour; lorsque les données de tous les pixels adjacents à un pixel central sont les mêmes que celles du pixel central comme on le voit sur la figure 2 (B), alors le pixel central est déterminé comme étant en dehors de la ligne de contour. Il y a huit pixels adjacents autour du pixel central en R 533 044 comprenant ceux sur les;coins en diagonale, mais l'utilisa- tion de seulement quatre des pixels adjacents situés à la droite et à la gauche, au-dessus et en dessous du pixel central dans un tel procédé de détermination, suffit pour la plupart des applications pratiques. On sélectionne un point de départ sur la ligne de contour ainsi détectée Ceci est fait en définissant des lignes de table 9 P, ú 21 de façon qu'elles s'étendent en travers des lignes de contour dans la région du modèle graphique et on choisit l'une de ces intersections comme point de départ. Si le modèle graphique peut être formé par seulement une ligne en boucle fermée (comme dans le cas des hiraganas (alphabet japonais) " 3 " et "'IL" et des -lettres "H" et "E" de l'alphabet romain), une seule ligne de table suffit, mais généralement on définit une multiplicité de lignes de table comme on le voit sur la figure 3 de manière que les inter- valles entre les lignes de table soient plus petits que la plus petite boucle de toutes les lignes en boucle fermée formées par une multiplicité de lignes de contour De cette manière, on peut détecter sans omission les données de tou- tes les lignes de contour. Une orientation et un ordre de priorité sont données à chacune de ces lignes de table Par exemple, dans le cas représenté sur la figure 3, chaque ligne de table a une orientation allant de l'extrémité gauche à l'extrémité droite et les lignes supérieures ont une plus grande prio- rité que les lignes inférieures dans l'ordre de fit 9 úi' Ensuite, un ordre de succession est donné à chacune des intersections définies par les lignes de table et les lignes de contour en fonction de l'orientation et de l'ordre de priorité mentionné En d'autres termes, dans le cas représenté sur les figures 3, l'ordre de succession des intersections est exprimé par Pl et P 2 sur la ligne de table 9 11 P 3 et P 4 sur la ligne de table ú 2 ' etc, dans cet ordre. Selon le procédé de cette invention, une table dans laquelle les intersections des lignes de contour avec les lignes de table sont chacune désignées avec un ordre de succession est appelée"table de départ" La première intersection du premier ordre de succession (Pl dans cette réalisation) est choisie parmi toutes les inter- sections comme premier point de départ et la ligne de con- tour est tracée à partir de ce point de départ dans une direction La direction de ce tracé est choisie par-avance de façon que la région noire (portion de ligne graphique) soit toujours située à droite (ou à gauche) de la ligne de contour qui est tracée. Lorsque la ligne de contour est tracée avec le point Pl choisi comme point de départ et dans une direction telle que la région noire soit toujours située à droite, ceci revient à dire que la ligne de contour est tracée dans le sens des aiguilles d'une montre dans l'ordre de P 2, P 4, P 6, P 8, Lorsque l'intérieur de là ligne en boucle fermée définie par la ligne de contour est une région noire, la direction du tracé de La ligne de contour est dans le sens des aiguilles d'une montre comme indiqué cidessus, mais inversement, lorsque l'extérieur de la boucle fermée est une région noire, alors la ligne de contour est tracée en sens inverse des aiguilles d'une montre (comme c'est le cas avec les lignes de contour incluant P 12 et P 13, et P 18, P 19, P 24 et P 25). Les valeurs des coordonnées des pixels situés sur les lignes de contour sont alors introduites et stockées dans un dispo- sitif de manière séquentielle en fonction des points de départ et des directions de tracés décrits ci-dessus, mais, dans le travail réel, les données de tous les pixels situés sur les lignes de contour ne sont pas absolument nécessaires. h 3 044 Par exemple, dans la portion de la ligne de contour qui se trouve être une ligne droite, cette ligne droite peut être identifiée en donnant seulement la valeur des coordonnées des pixels des deux extrémités de cette ligne droite et Y même dans le cas d'une portion courbe, il n'y a pas d 3 in- convénients si la portion courbe est approchée par des segments de ligne droite définis en reliant des points représentatifs sélectionnés sur la ligne de contour à des pas appropriés en fonction de la courbure de la ligne de contour; ceci permet une compression considérable du volume des informations à stocker dans le dispositif de mémoire sans sacrifier la valeur pratique du procédé. Toutefois, dans l'introduction des données de modèles gra- -phiques d'un grand nombre de caractères et de symboles, le travail manuel qui dépend largement du jugement de l'exé- cutant entratne une fatigue mentale, mais rend également possibles des erreurs dans la détermination des points appropriés du fait d'erreurs de-jugement Il est en consé- quence souhaitable d'utiliser des moyens automatiques pour sélectionner les points représentatifs appropriés sur la ligne de contour. Dans la mise en oeuvre du procédé de cette invention, il est souhaitable d'utiliser la technique suivante Cette techni- que est décrite dans une autre demande de brevet japonais intitulée "procédé de compression des données", sa descrip- tion détaillée n'est pas-reproduite ici et on n'en donnera ci-après qu'un apergu. L'essence de l'invention décrite dans cette demande de brevet consiste à sélectionner un point d'échantillonnage parmi une multiplicité de points d'échantillonnage disposés le long de la ligne de contour d'un modèle graphique seulement lorsque le produit de la longueur ú d'un segment de ligne raccordant un point d'échantillonnage au point d'échantillon- nage suivant par l'angle O défini par ce segment de ligne et un segment de ligne précédent est supérieur à une valeur prédéterminée K, le point d'échantillonnage étant autrement écarté comme n'étant pas une information nécessaire. En d'autres termes, en déterminant si les segments de ligne obtenus en raccordant les points d'échantillonnage de ma- nière séquentielle satisfont la condition que úx O>K ou non, il est décidé si la valeur des coordonnées de chaque point d'échantillonnage particulier doit être stockée dans un dispositif de mémoire comme information nécessaire ou rejetée comme information inutile, de sorte que l'informa- tion à stocker peut être efficacement comprimée. Un avantage principal de cette technique qui utilise la relation úx G>K comme référence pour sélectionner chaque point représentatif-consiste en ce que les intervalles entre les points représentatifs peuvent être sélectionnés de façon appropriée en fonction de la courbure de la ligne de contour, En dilatres termes, lorsque la courbure de la ligne de contour est grande, du fait que l'angle O défini par deux segments de ligne adjacents est petit, la longueur ú devient grande pour satisfaire la relation Zx O>K et l'intervalle entre les deux points d'échantillonnage devient grand Au contraire, lorsque la courbure de la ligne de contour est petite, du fait que l'angle O est grand, la longueur devient petite de sorte que l'intervalle entre les points d'échantillonnage devient petit et qu'une appro- ximation relativement précise par des lignes droites devient possible. Ainsi, des points représentatifs sont sélectionnés en séquence en fonction du standard de référence basé sur la relation úx O>K avec un point de départ Pl sélectionné comme point de départ, et la ligne de contour est complète- ? ment tracéetandis que les valeurs de coordonnées de chaque point représentatif sélectionné sur la ligne de contour sont introduites et stockées dans un dispositif de mémoire En- suite, les données des intersections P 1, P 2, P 4, P 6, P 8, p 9 " Pl O O P 16 ' P 221 ' P 281 P 32 ' P 31 f P 27 ' P 21 ' P 151 P 141 -209 P 260 P 30 '1 29 ' P 23, P 17, P 11 P 72 P 5 et P 3 représentées sur la figure 3 sont, soit stockées dans le dispositif de mémoire comme informations nécessaires, soit rejetées comme informations inutiles lorsque ces points représentatifs sont situés sur la ligne de contour partant du point Pl dans le procédé de stockage des données de tous les points d'échantillonnage. A ce stade, toute intersection non traitée estrecherchée et le point Représentatif ayant la priorité la plus élevée, P 12 dans le cas représenté sur la figure 3, est sélectionné,, En sélectionnant le point P 12 comme nouveau point de départ, la ligne de contour est à nouveau tracée comme décrit précé-d; demment et des points représentatifs sont sélectionnés de façon que leurs valeurs de coordonnées puissent être stockées dans le dispositif de mémoire Dans ce cas, la ligne de contour contenant les points P 12 et P 13 est tracée Du fait que l'extérieur de la ligne de contour en boucle fermée est une région noire, la ligne de contour est tracée en sens inverse des aiguilles d'une montre de sorte que la région noire est toujours située à droite comme il est évident d'après la description précédente. Ensuite, toutes les autres intersections non traitées-sont recherchées et le point représentatif ayant la priorité;;la plus élevée parmi tous les points représentatifs restants est sélectionné comme point de départ de sorte que la ligne de contour contenant P 18, P 24, P 25 et P 19 peut être tracée et que les valeurs de coordonnées des points représentatifs le long de cette ligne de contour sont stockées. Dans l'exemple représenté sur la figure 3, le stockage des données est alors terminé en ce qui concerne les données de toutes les lignes de contour et, même si il arrive-que le caractère soit un caractère de forme plus compliquée et ayant davantage d'éléments de base, la simple répétition de la procédure ci-dessus un nombre de fois correspondant au nombre de lignes de contour en boucle fermée constituant le caractère particulier permet de stocker sans omission les données de toutes les lignes de contour. Comme il est décrit ci-dessus, selon le procédé de la pré- sente invention, il est possible de stocker très efficacement les données des modèles graphiques qui peuvent être repré- sentées par des signaux à deux valeurs tels que des carac- tèreset des symboles, par une sélection appropriée des intervalles entre points représentatifs en fonction de la courbure de la ligne de contour Le procédé de cette inven- tion est ainsi capable de maîtriser le volume d'informations à stocker d'une manière extrêmement précise et, entre autres avantages, le procédé de cette invention est extrêmement aisé à mettre en oeuvre. L'invention est ici décrite en liaison avec certaines de ses réalisations, mais il est bien entendu que celles-ci ne sont données qu'à titre d'illustration et qu'on peut appor- ter diverses modifications dans la réalisation et la dispo- sition des diverses parties ainsi que dans les phases du procédé, en restant dans l'esprit et le domaine de l'invention et des revendications annexées. il Revendications. 1 Procédé pour introduire dans un dispositif de mémoire des données numérisées de modèles graphiques à deux valeurs d'un caractère ou d'un symbole, caractérisé en ce que la ligne de contour du modèle graphique est tracée à partir d'un point de départ sélectionné à partir d'une multiplicité de points d'échantillonnage disposés sur la ligne de con- tour et que les données de positions des points d'échantil- lonnage détectés au cours du tracé de la ligne de contour sont stockées en séquence dans le dispositif de mémoire comme données de modèles graphiques. 2 Procédé selon la revendication 1, caractérisé en ce qu'une ligne de contour est sélectionnée dans chaque ligne de contour lorsque le modèle graphique est constitué d'une multiplicité de lignes de contour 0. 3 Procédé selon la revendication 2, caractérisé en ce qu'au moins une ligne de table est tracée en travers du modèle graphique et que le point de départ est défini comme intersection de la ligne-de contour avec la ligne de table. 4 Procédé selon la revendication 3, caractérisé en ce qu'une multiplicité de lignes de table sont tracées en travers du modèle graphique de manière que les lignes de table soient pratiquement parallèles l'une à l'autre et que les intervalles entre les lignes de table soient plus petits qu'un diamètre minimal des boucles définieis)par les lignes de contour. Procédé selon la revendication 4, caractérisé en ce que chaque ligne de table reçoit une orientation et un ordre de priorité et que les intersections des lignes de table avec les lignes de contour sont détectées en séquence en fonction de l'orientation et de l'ordre de priorité de telle manière que chaque ligne de contour soit tracée depuis une première intersection prise commè point de départ et qu'une intersection suivante est sélectionnée lorsque le tracé de la ligne de contour précédente est achevé, les intersections rencontrées au cours du tracé des lignes de contour étant rejetées et le point de départ r Y suivant étant sélectionné à partir de l'intersection qui n'a pas encore été tracée et a l'ordre de priorité le plus élevée