Brevet FR2533041A1 — publié le 19840316

Procédé de compression des données pour une image d'original à deux valeurs. La présente invention concerne un procédé de compres- sion des données d'une image d'original à deux valeurs et notamment un procédé de compression des données numériques pour un assortiment de caractères dans la photocomposition à commande par ordinateur. Dans la photocomposition à commande par ordinateur, il est souhaitable de disposer en mémoire et de manière à les retrouver aisément des jeux d'assortiment tels que des caractères ming, gothique, etc, dans le cas de kanji (carac- tères chinois) Par ailleurs, pour satisfaire les exigences de grande qualité, le modèle de bit doit être constitué par une matrice de points extrêmement dense, au contraire du cas des modèles de caractères pour des unités de traitement habituelles de kanji. Il en résulte ainsi la nécessité d'un dispositif de mémoire extrêmement vaste lorsqu'on tente de stockerun nom bre de modèles de caractères d'au moins plusieurs milliers sous forme de données de caractères qui représentent de façonf précise les modèles de caractères originaux. On a proposé diverses méthodes pour comprimer des données de caractères au lieu de stocker simplement chaque caractère sous formed'une simple matrice de points et la plupart de ces procédés étaient basés sur des techniques de compression de largeur de bandes développées dans le domaine de la technologie de la transmission des images. Toutefois, les résultats obtenus jusqu'ici ne sont en aucun cas impressionnants Par exemple, la méthode "run-length"connue ne permet d'atteindre qu'un taux de com- pression de 20 à 30 % Et la méthode des vecteurs, qui peut atteindre un taux de compression de l'ordre de quelques pourcents exige un tel travail manuel qu'elle est pratique- ment inapplicable à la photocomposition à commande par ordi- nateur. Un taux de compression des données est décrit dans la demande de brevet US N O 440 539 (demande de brevet japo- nais N O 56-180 649) effectue une percée dans ce domaine technique; elle présente une solution au problème précité qui permet d'atteindre un meilleur taux de compression que le procédé "run-length"conventioinnel ou le procédé des vec- teurs, qui facilite le classement d'images d'original à deux valeurs et permet une réduction notable de la capacité de mémoire nécessaire par un degré très élevé de compression des données. Cette invention est une amélioration de l'invention décrite dans la demande de brevet précitée et son but princi- pal est de procurer un procédé adapté pour comprimer des données à un degré très élevé en détectant les caractéristi- ques des lignes de contour d'images d'original partielles, qui sont obtenues par division de l'image d'original, par rapport aux images d'original partielles voisines. Selon cette invention, un tel but technique est obtenu grâce à un procédé de compression des données pour une image d'original à deux valeurs, caractérisé en ce qu'on divise l'image d'original en une multiplicité d'images par- tielles, on détermine un point de départ et un point terminal de chaque ligne de contour trouvée dans chacune des images d'original partielles en trouvant les intersections entre la ligne de contour et les lignes divisant l'image d'original en les images partielles, on détecte des points caractéristi- ques dans chaque ligne de contour en traçant la ligne de contour dans chacune des images partielles en partant du point de départ et du point terminal correspondanton extrait ces points de départ et ces points d'arrivée qui se raccor- dent à ceux dans les images partielles voisines et les points caractéristiques comme points de coordonnée nécesssaires pour déterminer un groupe de segments de lignes en boucle fermée sous forme d'un agrégat de lignes de contour, et en ce qu'on comprime les données de l'image d'original en éliminant toutes les données des points de coordonnée redondants par compa- raison des gradients des segments de ligne en boucle fermée pour chaque point de coordonnée voisin. L'amélioration de cette invention par rapport à la demande de brevet US en instance consiste en l'élimination de toute redondance dans les données et ce but peut être atteint de façon appropriée en éliminant des points de coor- donnée qui ont les mêmes gradients que les points de coordon- née précédents sur la ligne de contour. L'invention sera mieux comprise à la lecture de la- description détaillée, donnée ci-après à titre d'exemple seulement, d'une réalisation spécifique, en liaison avec le dessin joint sur lequel La Fig 1 est un schéma-bloc d'un dispositif de com- pression des données adapté pour mettre en oeuvre le procédé de cette invention; La Fig 2 est un modèle de bit dans la mémoire mon- trant une image d'original typique dont les données graphi- ques doivent être comprimées; La Fig O 3 montre en détail deux images partielles mutuellement adjacentes de l'image originale représentée sur la Fig 2 avec les modèles de bits stockés dans les blocs- mémoire correspondants; - La Fig 4 est un schéma-bloc montrant une structure concrète des moyens de comparaison'de gradients/d'élimination de la Fig O 1; et Les Fig 5 et 6 sont des organigrammes illustrant l'action du dispositif de compression des données représenté sur la Fig 1. Le modèle d'original dont les données graphiques doi- vent être comprimées est analysé photoélectriquement d'une manière appropriée et est transformé en le signal d'original par un dispositif d'entrée d'original 1, et le signal d'ori- ginal est transformé en un signal numérique par un conver- tisseur analogique/numérique 2 et ensuite amené à-un dispo- sitif de mémoire d'image d'original à deux valeurs 3. Les données du modèle d'original stockées dans le dispositif de mémoire d'images d'original à deux valeurs 3 sont constituéespar un modèle de bit d'une matrice de points comme il est représenté s ur la Fig 2; le modèle d'original qui est exprimé par le modèle de bit est l'image d'original à deux valeurs (appelée ci-après image d'original) qui doit être comprimée selon cette invention. Le dispositif de mémoire d'image d'original à deux valeurs 3 est constitué par une multiplicité de blocs- mémoire M 6 m disposés dans une matrice, et chacun des blocs mémoire M 00M stocke l'une des i x j images de parties d'original obtenue par division de l'image d'origi- nal. Ensuite, chaque image de partie d'original est transférée du bloc mémoire correspondant M -M à un dispo- sitif de mémoire d'images de parties d'original, en séquences et pour chaque bloc de mémoire, selon l'ordre de commande émanant d'un dispositif de commande de mémoire 5. Le dispositif de commande de mémoire 5 commande l'écriture, la lecture et l'adressage des données en ce qui concerne à la fois les dispositifs de mémoire 3 et 4 selon la procédure donnée par un organigramme ci-après. La Fig 3 est une vue agrandie des modèles de bits de deux images de parties d'original qui ont été transférés au dispositif de mémoire d'images de parties d'original 4, et celles représentées sur le dessin correspondent au modèle de bits des blocs mémoire M 3 et M 13 de la Fig 2. Selon ce modèle de bit -dans le dispositif de mémoire d'images de parties d'original 4, les bits de pixel sur les intersections entre les lignes de contour de l'image de par- tie d'original et les lignes séparant l'image de partie d'oni- ginal considérée des images de parties d'original voisines sont pris comme point de départ P(S et comme point d'arrivée (E) En d'autres termes, la périphérie extérieure des adresses du dispositif de mémoire d'images de parties d'ori- ginal est désignée séquentiellement depuis l'origine ( 0,0) en sens inverse'des aiguilles d'une montre et les changements des bits de pixel sur la périphérie extérieure du modèle *de bits sont déterminés. Dans le modèle de bits ici, les bits dans la région du caractère sont exprimés par " 1 ", tandis que ceux dans la région du fond -sont exprimés par O " En d'autres termes, les bits de pixel sur la périphérie extérieure des adresses dans le modèle de bits de parties d'original sont lues en 253 O l O séquences en sens inverse des aiguilles d'une montre et le bit correspondant à "i 1 l, lorsque le bit lu est sur le point de passer de 1 à 11 " 01 est déterminé comme point de départ P(S), tandis que le bit correspondant à " 1 ", lorsque le bit lu est sur le point de passer de 'OV à " 1 " est déterminé comme point terminal P(E) La ligne de contour du modèle de bit s'étend géné- ralement sur la périphérie des pixel mais, pour simplifier la description suivante, ces pixel ou une rangée de pixels ayant une ligne de contour au moins sur une extrémité sont supposés constituer une ligne de contour. Les valeurs de coordonnée (x, y) du point de départ P(S)etdu point terminal P(E) déterminées par des moyens de détection de points de départ/terminal sont stoc- kées dans un registre approprié et amenées à des moyens de traçage de lignes de contour 7 de sorte qu'une ligne de con- tour peut être détectée avec les points terminaux définis par le signal en provenance du registre. Les bits de pixel sur la ligne de contour tracée par les moyens de traçage de ligne-de contour 7 sont donnés à des-moyens de détection de points caractéristiques 8 de telle sorte que les changements dans les caractéristiques de la ligne-de contour peuvent être détectés et qu'un nom- bre approprié de points caractéristiques sur la ligne de contour peuvent être détectés en séquence. Ces points caractéristiques peuvent être placés par exemple de la manière suivante en fonction du type des chan- gements dans la ligne des contours. p(l): point auquel la direction de la ligne de contour change brusquement, ( 2) P: point auquel la direction de la ligne de contour change progressivement dans une direction, P( 3): point auquel la ligne de contour passe d'une ligne droite à une ligne courbe, P( 4): point auquel la ligne de contour passe d'une ligne courbe à une ligne droite. Le groupe constitué par les points de coordonnée obtenus en traçant en séquence les points de coordonnée de ces points caractéristiques depuis le point de départ p(S) jusqu'au point terminal P (E) sont écrits dans un dispositif de mémoire des données de segment de ligne 9 sous forme de données de compression de l'image de parties d'original. Chacun des points de coordonnée dans le dispositif de mémoire des données de segments de ligne est transformé en le point de coordonnée du modèle de bit d'original en fonction du numéro de bloc 00-ij du bloc mémoire 00- M i En d'autres termes pour chacun des blocs mémoire ( 1) ( 4) - M 00-M, les points caractéristiques P -P et les points 00113 (S)) de départ P et terminal P associés disposés aux extré- mités respectives des points caractéristiques sont écrits dans le dispositif de mémoire de données de segments de ligne 9, normalement, dans l'ordre du point de départ Pl S, des points caractéristiques P 1)-P 4), et du point terminal P(E) sous forme de données comprimées. Après que toutes les données de compression du dispo- sitif de mémoire de données de segments de ligne 9 ont été collectées en ce qui concerne tous les blocs mémoire des M 00-M i# les données de compression sont amenées à des moyens de raccordement de données 10 pour les parties d'image d'original. e(E) (S) de sorte que le point terminal P et le point de départ P qui doivent être mutuellement raccordés entre les lignes de contour qui sont séparées l'une de l'autre sous forme d'images de parties d'original séparées>sont raccordés ensemble et sont transformés en données de segments de ligne en boucle fermée constituées sous forme d'un tout de plusieurs boucles fermées. Le traitement des signaux décrit jusqu'ici est iden- tique à celui représenté par l'organigramme de la Fig 5 et a déjà été discuté en détail dans la demande de brevet japo- nais N O 56-180 649 précédemment mentionnée. La partie essentielle du procédé de compression des données selon cette invention se trouve dans les moyens de raccordement 10 entre les différentes images de parties d'ori- ginal représentées sur la Fig 1 et ensuite. Dans les moyens de raccordement 10 entre différentes images de parties d'original, le point de départ P(S) et le point terminal P(E) correspondant à chacune des données de segments de ligne sont raccordés ensemble de sorte que la ligne de contour pour l'image de l'original tout entier peut être reproduite et écrite dans un dispositif de mémoire de groupes de segments de ligne en boucle fermée 11 après avoir été transformée en une multiplicité de segments de lignes en boucle fermée. Le modèle d'original et la ligne de contour de son modèle de bit sont chacun constitués par une boucle fermée comme on le voit par un exemple donné sur la Fig 2. Chaque donnée de segment de ligne en boucle fermée est alors amenée à des moyens de comparaison et d'élimination de gradient 12 de sorte que les gradients des bits de pixel situés sur les lignes délimitant les images de parties d'ori- ginal et les lignes de contour par rapport aux points de coor- donnée voisins sont détectés et les points de pixel ayant les mêmes gradients en amont et en aval sont éliminés des données de points de coordonnée. De façon spécifique, les moyens de comparaison et d'élimination de gradient 12 peuvent être constitués, par exemple, de trois mémoires tampon de données 21, 22 et 23, de deux circuits de calcul de gradient 24 et 25, d'un circuit de comparaison 26, d'un circuit de porte 27. Les données de points de coordonnée d'un certain groupe de segments-de ligne en boucle fermée sont stockées en séquences dans les mémoires tampon de données 21, 22 et 23 sous forme de points de coordonnée Pn Pn+' Pn+ 2 ' etc, à partir du dispositif de mémoire il pour le groupe de segments de ligne en boucle fermée sous l'ordre de commande provenant d'un circuit de commande de tracé de boucle-fermée 13. Les mémoires tampon de données 21 et 22 sont raccor- dées au circuit de calcul de gradient 24 et les mémoire tampon de données 22 et 23 sont raccordées au circuit de calcul de gradient 25 Le gradient entre les points de coordonnée Pn et Pn+l est calculé dans le circuit de calcul des gradients 24 tandis que le gradient entre les points de coordonnée Pn+ et Pn+ 2 est calculé dans le circuit de calcul des gradients de sorte que les gradients ainsi obtenus sont amenée au circuit de comparaison 26. Lorsque les gradients de Pn Pnl et de Pn+l Pn+ 2 ne n n+l n+ 1 n+ 2 sont pas concordants, la sortie du circuit de comparaison 26 est amenée au circuit de porte 27 et les données sorties de la mémoire tampon de données 22 stockant le point de coordon- née Pn+l est envoyé au dispositif de mémoire des données com- primées 14. Inversement, lorsque les gradients de Pn Pn+l et de n n+ 1 Pn+l Pn+ 2 concordent, les données correspondant au point de n+l n+ 2 coordonnée Pn+ l ne sont pas envoyées au dispositif de mémoire des données comprimées 14. Par exemple, le traitement dans les moyens-de compa- raison et d'élimination des gradients 12 en ce qui concerne les données (S)(G) (S> ( 2) (E) les données Pn v Pn+l t Pn+ 2 ' n+ 3 ' PN+ 4 du groupe de segments de ligne en boucle fermée sur les blocs mémoire M 03 et M 13 s'effectue comme indiqué dans ce qui suit et la séquence de données qui est produite sera analogue à celle indiquée dans ce qui suit. ( 1) Les gradients Y Y/Xn+l X entre les points de n+ 1 N n+ 1 n coordonnée Pn(Xn Yn) et Pn+l(Xn+l, Yn+l) et les gradient Yn+ 2 Yn+ /Xn+ 2 Xn+ entre les points de coordonnée n 2n+l n+ 2 n+ 1 Pn+l(Xn+l, Yn+l) et Pn+ 2 (X+ 2 Yn+ 2)n+ 2 sont compares l'un avec l'autre. ( 2) Lorsque les points de coordonnée Pn, Pn+l et Pn+ 2 sont détectés comme étant sur une même ligne, les données P +(E) correspondant au point de coordonnée Pn+l(Xn+l,Yn+l) n+l n+l n+ 1 n+ 1 sont bloqués par le circuit de porte 27 et ne sont pas produits. ( 3) Les points de coordonnée dans les mémoires tampon de données 21, 22 et 23 sont renouvelés et Pn+l(Xn+i, Yn+l), Pn+ 2 (Xn+ 2 ' Yn+ 2) et Pn+ 3 (X+ 3 Yn+ 3) sont stockés, après quoi on compare les gradients entre Pn+l et Pn+ 2 et entre Pn+ 2 et Pn+ 3 ' ( 4) Lorsque et Pn+ 3 sont détectés comme étant n+l' n+ 2 n+ 3 sur une même ligne, le point de coordonnée Pn+ 2 (Xn+ 21 Yn+ 2) n'est pas sorti. ( 5) Les points de coordonnée dans les mémoires tampon de données 21, 22 et 23 sont renouvelés et P n+ 2 (X, Yn+ 2), Pn+ 3 (Xn+ 3 yn+ 3) et Pn+ 4 (X n+ 4 Yn+ 4) sont stockés, après quoi on compare les gradients en Pn+ 2 et Pn+ 3 et en Pn+ 3 etn 4 est alors sorti. ( 7) Cette procédure est répétée pour tous les points de coordonnée dans le groupe de segments de ligne en boucle fer- mée et les données des points de coordonnée des bits de pixel qui divisent les blocs mémoire M 03 et M 13 sous la forme de Pn, P + 3 ' Pn+ 4 " sont éliminées de la mémoire dans le dispo- sitif de mémoire des données comprimées 14 pour une image d'original à deux valeurs. Les données comprimées, dans lesquelles les données re- dondantes de points de coordonnée sont éliminés, sont stockées en séquences dans le dispositif de mémoire des données com- primées 14 pour une image d'original à deux valeurs pour cha- cune des boucles fermées dans le modèle d'original et sont ensuite fournies au dispositif de sortie 15 à des moments appropriés La Fig 6 est un organigramme de la procédure de traitement précitée. Lorsque la direction du tracé de cette ligne de con- tour à boucle fermée est en sens inverse des aiguilles d'une montre, l'intérieur de la boucle (ligne de contour) est déter- minée comme étant noire (portion caractère) et, lorsque la direction du tracé est dans le sens des aiguilles d'une montre, l'intérieur de la boucle est déterminé comme étant blanc (portion vierge) Si la boucle est multiple ou s'il y a une autre boucle à l'intérieur, la boucle intérieure a la prio- rité. Tel qu'il est décrit ci-dessus selon l'invention, les données redondantes de points de coordonnée sont éliminées d'un original qui est finement divisé en une multiplicité d'images de parties d'original en détectant le gradient de la ligne de contour croisant dans une image de partie d'ori- ginal voisine de sorte que les données comprimées de l'image d'original peuvent être obtenues En conséquence, la capacité de mémoire nécessaire pour le classement peut être réduite drastiquement O Il est évident pour l'homme de l'art que l'inven- tion ne se limite pas à l'exemple de réalisation décrit et que l'on peut apporter à celui-ci des modifications sans sortir du cadre de l'invention. REVENDICATIONS 1 Procédé de compression des données pour une image d'original à deux valeurs, caractérisé en ce que on divise une image d'original en une multiplicité d'images de parties d'original on détermine un point de départ et un point terminal de chaque ligne de contour trou Vée dans chacune des images de parties d'original en trouvant les intersections entre la ligne de contour et les lignes divisant l'image d'original en les images de parties d'original on détecte des points caractéristiques dans chaque ligne de contour en traçant la ligne de contour dans chacune des images de parties d'original à partir du point de départ correspondant et du point terminal; on extrait ces points de départ et ces points termi- naux qui se raccordent à ceux dans les images de parties d'ori- ginal voisines et les points caractéristiques sous forme de points de coordonnée nécessaires pour déterminer un groupe de segments de ligne en boucle fermée sous forme d'un agrégat des lignes de contour; et on comprime en outre les données de l'image d'original en enlevant les données redondant des points de coordonnée par comparaison des gradients des segments de ligne en b:oucle fer- mée pour chaque paire de points de coordonnée voisine sur la ligne de contour particulière. 2 Procédé selon la revendication 1, caractérisé en ce que chaque point caractéristique des lignes de contour est sélectionné sur la base des directions de deux vecteurs des points de coordonnée adjacents au point de coordonnée particu- lier considéré le long de la ligne de contour particulière, les points de coordonnée correspondant aux emplacements des bits de pixel le long de la ligne de contour. 3 Procédé selon la revendication 2, caractérisé en ce que les données redondant de points de coordonnées sont cons- tituées par les points de coordonnée qui ont les mêmes gra- dients que les points de coordonnée précédents le long des lignes de contour.