Brevet FR2533040A1 — publié le 19840316

Procédé de compression des données La présente invention concerne un procédé pour compri- mer les données d'une image d'original à deux valeurs et no- tamment un procédé pour comprimer des données numériques pour un assortiment de caractères dans la photocomposition comman- dée par ordinateur. On sait très bien stocker des jeux d'assortiment sous forme d'un certain nombre de matrices de points Mais, pour représenter de façon précise un modèle de caractère compliqué tel que celui d'un caractère kanji (chinois) , une matrice de points extrêmement dense est nécessaire O Dans la photocomposition commandée par ordinateur, il est souhaitable de disposer des divers jeux d'assortiment tels que des caractères ming, des gothiques, etc, dans le ces de kanji, de manière à les retrouver aisément Du fait que le nombre de types de kanji est généralement de l'ordre de mil- liers dans les documents japonais courants et de dizaines de milliers dans les documents chinois, la dimension nécessaire de mémoire dans de tels cas devient très grande Par ailleurs, pour obtenir une qualité élevée, le modèle de bit de chaque caractère doit être constitué par une matrice de points extrê- mement dense, au contraire du cas des modèles de caractères pour les dispositifs de traitement courants des kanji pour traiter les documents en langue japonaise. Selon une technique conventionnelle, des points d'échantillonnage sont sélectionnés de façon appropriée le long de la ligne de contour d'un caractère ou d'un symbole, et la valeur des coordonnées X-Y de chaque point d'échantil-. lonnage est stockée sous forme de données du caractère ou du symbole Cependant, cette technique connue exige de sélec- tionner un grand nombre de points d'échantillonnage lorsqu'il y a de nombreuses parties courbes, -même dans le cas d'un caractère relativement simple tel que "hiragana" (alphabet japonais) et le volume des données à stocker devient très important. De ce fait, il est avantageux de faire varier la densité des points d'échantillonnage le long de la ligne de contour, en augmentant cette densité lorsque la courbure de la ligne de contour est grande et en diminuant la densité lorsque la ligne de contour est rectiligne ou légèrement incurvée, de sorte que le nombre des points d'échantillon- nage ou le volume des données à stocker peut être réduit sans sacrifier outre-mesure la qualité de reproduction des caractères Cependant, une sélection de points d'échantil- lonnage appropriée en fonction de la courbure de la ligne de contour n'est aucunement facile Elle exige une grande habileté et même un utilisateur expérimenté ne peut s'em- pêcher de faire des erreurs de temps à autre lorsqu'il traite un grand nombre de caractères et de symboles du fait que la procédure est ennuyeuse. Compte tenu des inconvénients des procédés classi- ques pour stocker les données des jeux de caractères, en particulier dans le cas des kanji, un but principal de cette invention est de procurer un procédé pour comprimer des données, dans le stockage des valeurs de coordonnées X-Y d'un grand nombre de points d'échantillonnage sélec- tionnés le long de la ligne de contour d'un caractère en sélectionnant des points d'échantillonage à un intervalle -relativement petit dans les portions ayant des courbures relativement grandes et en réduisant le nombre des points d'échantillonnage dans les portions qui sont recti- lignes ou légèrement incurvées et ont moins d'influence - sur la qualité des images de caractère reproduites. Un autre but de cette invention est de procurer un procédé pour comprimer des données en déterminant automati- quement des points d'échantillonnage nécessaires parmi ceux qui ont moins d'importance dans la reproduction précise des images de caractère. Selon cette invention, ces buts sont atteints grâce à un procédé pour comprimer des données dérivées du traçage de la ligne de contour d'un caractère ou d'un symbole, ca- ractérisé en ce qu'on sélectionne une multiplicité de points d'échantillonnage le long de la ligne de contour, on déter- mine la longueur d'un segment de ligne raccordant un point d'échantillonnage intéressant et un point d'échantillonnage précédent, on détermine l'angle défini par le segment de ligne mentionné et par un deuxième segment de ligne défini en raccordant le point d'échantillonnage intéressant mentionné et le point d'échantillonnage suivant, et en déterminant le point d'échantillonnage particulier comme donnée nécessaire qui doit être retenue ou comme donnée inutile qui doit être rejetée en fonction de la longueur du premier segment de ligne et de l'angle défini par le premier et le deuxième seg- ment de ligne. L'invention sera bien comprise à la lecture de la description détaillée, donnée ci-après à titre d'exemple seulement, d'une réalisation préférée, en liaison avec le dessin joint sur lequel: La Fig l montre comment on peut sélectionner des points d'échantillonnage le long d'une ligne de contour; La Fig 2 est un schéma bloc d'un dispositif pour mettre en oeuvre le procédé de cette invention; et La Fig 3 est un organigramme montrant l'action du dispositif de la Fig 2. La Fig 1 est un schéma montrant une multiplicité de points d'échantillonnage sélectionnés selon une ligne de contour désirée dans un plan de coordonnées X-Y En réalité, la ligne de contour d'un caractère forme au moins une ligne en boucle fermée, mais il n'est représenté ici qu'une por- tion d'une telle ligne en boucle fermée. Sur la Fig 1, les points PO à P 9 sont des points d'échantillonnage disposés le long de la ligne de contour graphique définie ci-dessus Il est possible de produire une reproduction précise d'une image d'original si toutes les données de ces points d'échantillon sont utilisées et si la ligne de contour est exprimée par les segments de ligne raccordant séquentiellement ces points sans aucune omission Cependant, cette procédure présente l'inconvé- nient que le volume des données à stocker dans le disposi- tif de mémoire devient excessivement grand comme il a été décrit précédemment. En conséquence, dans un travail réel, on approche la ligne de contour par des segments de ligne raccordant des points d'échantillonnage sélectionnés à intervalles appropriés, et on rejette un ou plusieurs points d'échantil- lonnage chaque fois que le segment de ligne est défini Dans l'exemple représenté sur la Fig 1, les points d'échantillon- nage P 1, P 3, P 4, P 7 et P 8 correspondent à ces points d'échan- tillonnage rejetés. Cependant, lorsque la courbure de la ligne de contour devient importante, la ligne de contour doit être exprimée en fonction des données de-tous les points d'échantillonnage intéressants Sur la Fig 1, les points P et P correspon- 6 dent à de tels points d'échantillonnage. En d'autres termes, les valeurs de coordonnées X-Y des points d'échantillonnage P O, P 2, P 5, P 6 et P 9 sont les données à stocker dans le dispositif de mémoire comme infor- mation nécessaire pour définir la configuration de la ligne de contour, tandis que des valeurs de coordonnées des points d'échantillonnage P, P 3, P 4, P 7 et P 8 sont des informations inutiles qui peuvent être rejetées. Cette invention permet de déterminer de façon automa- tique et précise si les valeurs de coordonnées sont des infor- mations nécessaires ou des informations inutiles en fonction du produit de la longueur du segment de ligne raccordant le point d'échantillonnage considéré au point-d'échantillonnage précédent par l'angle de courbure entre les deux segments de ligne en amont et en aval du point d'échantillonnage consi- déré De façon plus spécifique, en appelant Z et respecti- vement la longueur du segment de ligne raccordant les points d'échantillonnage P N et Pn+l et l'angle formé par ce segment de ligne et le segment de ligne précédent, on compare leur produit ú @ à une valeur constante prédéterminée k, et la valeur de coordonnée du point d'échantillonnage Pn+î est déterminée comme étant une information nécessaire lorsque ú.O > k ou comme information inutile lorsque ú O Lorsque la valeur de coordonnée du point Pneu est déterminée comme étant une information inutile, la même pro- cédure se répète avec le point d'échantillonnage suivant Pn+ 2 en relation avec le point d'échantillonnage précédent P. n Selon l'exemple représenté sur la Fig 1, le traite- ment jusqu'au point P 2 étant supposé être terminé, on obtient Z et O des valeurs de coordonnées de P 2 et de P 3 et, du fait que Z est petit puisque c'est la distance entre deux points d'échantillonnage situés à proximité et que O est petit, car les segments de ligne P O P 2 et P 2 P 3 forment un angle relative- ment obtus, le produit Z O est déterminé comme étant plus petit que la constante k et les données du point P 3 sont déterminées comme étant une information inutile. Le même processus se répète ensuite avec les données du point P 3 reirplacéespar les données du point P 4; dans ce cas, ú O est toujours inférieur à k et les données du point P 4 sont également déterminées comme étant une information inutile. Le traitement se répète ensuite avec les données du point P 4 remplacées par les données du point P; dans ce 4 5 cas, Q O > k les données du point P sont déterminées comme étant une information nécessaire De ce fait, la valeur de coordonnée du point P 5 est stockée dans le dispositif de mémoire. En répétant le même traitement pour les données des points P 5 et P 6, il est déterminé que ú O > k, du'fait que, dans ce cas, Z est petit, mais la courbure de la ligne de contour est grande et O a une valeur relativement importante. De ce fait, les données du point P 6 sont déterminées comme étant une information nécessaire. Comme il apparait dans la description ci-dessus, plus la valeur de la constante k est grande, plus le nombre de points d'échantillonnage rejetés devient grand, ce qui permet d'augmenter le taux de compression des données et de diminuer en conséquence la capacité nécessaire de la mé- moire; toutefois, d'autre part, il est inévitable qu'il apparaisse une certaine perte dans la fidélité de l'image reproduite par rapport au modèle de l'original Il est possible d'améliorer cette fidélité-en réduisant la valeur de k, mais au prix d'une capacité de mémoire plus grande. En conséquence, on doit sélectionner pour la valeur de la constante k une valeur appropriée au but de 1 'applica- tion et on doit pleinement prendre en compte les caracté- ristiques de l'équipement. Dans la description ci-dessus, on a envisagé les cas o ú O > k et Q O données sont à rejeter ou à conserver lorsque cette condi- tion est satisfaite. La Fig 2 montre un schéma bloc du circuit d'un dispositif adapté pour mettre en oeuvre le procédé de cette invention. Les repères 1 et 2 désignent les valeurs d'entrée des valeurs de coordonnées (xn, yn) et-(x+, Yn+l) des n N (n+ y)de points d'échantillonnage Pn et Pn+l Ces valeurs de coordon- nées peuvent être introduites en utilisant une table de numé- riseur, un traceur ou l'analogue et en conséquence sa des- cription détaillée est omise ici Les valeurs d'entiée 1 et 2 sont amenées à un circuit arithmétique 3, dans lequel la longueur X du segment de ligne et l'angle e entre ce segment de ligne et le précédent sont calculés en fonction de la formule suivante: = V (Xn+l xn) + (Yn+l Yn)2 e= en e n+l n o x n+ 1 xn e = tg n Yn+l -Yn x x en n-i -1 n n-i 8 n_ = tq - Yn Yn-1 Les signaux de sortie Z et O sont transformés en leur produit ú O dans un circuit de multiplication sui- vant 4 et ce produit est comparé dans un comparateur 5 à la constante k fixée dans un circuit de fixation de valeur constante 6. Le comparateur 5 fournit un signal d'indication d'entrée à un dispositif de commande d'entrée de données suivant 7, seulement lorsque Q @ > ko A la réception du signal d'indication d'introduction des données, le dispo- sitif de commande d'introduction des données 7 stocke la valeur de coordonnée (xn+l Yn+l) du point Pn+l dans le dispositif de mémoire, et le même processus se répète pour le point d'échantillonnage suivant. Si Q ^ nouveau, le suffixe n+l étant remplacé par n+ 2. L'organigramme de la Fig 3 illustre ce procédé. Comme décrit ci-dessus, le procédé de cette inven- tion permet de déterminer automatiquement et de façon pré- cise si l'information est nécessaire ou inutile en ce qui concerne la valeur de coordonnéesde chacun des points d'échantillonnage disposés le long de la lignje de contour et il permet de stocker seulement l'information nécessaire d'un caractère, d'un symbole ou l'analogue dans un disposi- tif de mémoire, et a ainsi une grande importance pour des applications pratiques. REVENDICATIONS 1 Procédé pour comprimer des données dérivées du traçage de la ligne de contour d'un caractère ou d'un symbole graphique, caractérisé en ce que on sélectionne une multiplicité de points d'échantil- lonnage le long de la ligne de contour on détermine la longueur d'un segment de ligne raccor- dant un point d'échantillonnage considéré et un point d'échan- tillonnage précédent; on détermine l'angle défini par le segment de ligne mentionné et un autre segment de ligne défini en raccordant le point d'échantillonnage considéré à un point d'échantillon- nage suivant; et on détermine si le point d'échantillonnage considéré est une information nécessaire qui doit être retenue ou une information inutile qui peut être rejetée en fonction de la longueur du premier segment de ligne et de l'angle défini par le premier et le deuxième segments de l Ugne. 2 Procédé de compression des données selon la reven- dication 1, caractérisé en ce que le point d'échantillonnage intéressant est déterminé comme étant une information néces- saire ou inutile en fonction du produit de la longueur du premier segment de ligne par l'angle défini par le premier et le deuxième segments de ligne. 3 Procédé de compression des données selon la reven- dication 2, caractérisé en ce que le point d'échantillonnage considéré est déterminé comme étant une information nécessaire seulement lorsque le produit du premier segment de ligne par l'angle défini par le premier et le deuxième segment 5 de ligne est supérieur à une valeur constante donnée. 4 Procédé de compression des données selon la reven- dication 2, caractérisé en ce que le point d'échantillonnage considéré est déterminé comme étant une information nécessair seulement lorsque le produit de la longueur du premier segmen de ligne par l'angle défini par le premier et le deuxième seg ment S de ligne est égal ou supérieur à une valeur constante donnée.