Brevet FR2516280A1 — publié le 19830513

?O Procédé pour comprimer les données d'une image à deux valeurs. La présente invention concerne un procédé pour comprimer les données d'une image à deux valeurs, notamment les données numériques d'un modèle de caractère original pour une photo- composition par un calculateur électronique. Dans un procédé classique, un modèle numérique de caractère original pour une photo-composition par un calculateur élec- tronique est constitué par une matrice de points à haute den- sité, du fait qu'un tel modèle de caractère original est né- cessairement agrandi, ce qui diffère d'un caractère pour un processeur de mots en caractères chinois. Lorsque le modèle de caractère original exprimé par un modèle de bits de la matrice de points à haute densité est traité par exemple sous la forme d'un modèle de bits, le stockage d'un caractère nécessite un grand nombre de bits Par exemple, une densité élevée de 480 x 480 = 230400 bits est nécessaire pour stocker un modèle de caractère original pour la photo- composition par le calculateur électronique. En ce qui concerne les modèles de caractères originaux pour la photocomposition par le calculateur électronique, le style du caractère est important ainsi que sa signification en tant que caractères normaux, et divers styles de caractères sont nécessaires De ce fait, les modèles de caractères originaux sont préparés sous forme de jeux ou fontes de styles de ca- ractères tels que le caractère Ming, le caractère gothique, etc En outre, il est souhaitable que les jeux de styles de caractères de ces modèles de caractères originaux pour la photo-composition par le calculateur électronique soient classés de façon à pouvoir toujours être consultés. Cependant, comme il est décrit ci-dessus, lorsque le modèle de bits d'un caractère est stocké sous forme de données de caractère tel quel il est nécessaire de disposer d'une capacité de mémoire très importante pour classer les modèles de caractères originaux En conséquence, au lieu de stocker le mo- dèle de bits tel cjuelon a proposé de comprimer les données pour chaque caractère par une technique de compression de zones pour le traitement d'images par transmission sans fil. Cependant, dans un système de longueur de course précédemment proposé, le taux de compression ne peut atteindre que 20 à 30 %. Par ailleurs, dans un système de vecteurs, on peut obtenir plusieurs pourcents de compression élevée, mais, dans une com- pression conventionnelle, le traitement du vecteur se fait presque entièrement à la main En conséquence, lorsqu'on ap- plique la méthode des vecteurs aux modèles de caractères ori- ginaux pour la photo-composition par le calculateur électroni- que, un temps et un travailconsidérables sont nécessaires pour effectuer la compression du jeu des modèles de caractères originaux. Par exemple, dans un système de vecteurs conventionnel, le modèle de caractère est agrandi à une certaine dimension de façon à pouvoir effectuer les opérations à la main, et les points pour produire les vecteurs grâce auxquels le contour du modèle de caractère peut être approximativemet eprésenté par des lignes droites, sont relevés manuellement en utilisant un numériseur. Afin d'exprimer le modèle de caractère par des vecteurs, de nombreux segments de lignes sont nécessaires et-notamment dans le cas des caractères de style Ming comportant de nom- breuses courbes, le nombre de points à relever est extrême- ment grand De ce fait, un temps et un travail importants sont nécessaires et, en outre, il faut une grande habileté pour relever ces points. Du fait que cette opération de relevé est effectuée manuel- lement par le numériseur, afin de réduire les erreurs de relevés, on doit préparer le modèle de caractère à introduire, lequel est agrandi au maximum En outre, il est nécessaire à la fin de reformer le modèle de caractère terminé. C'est un but de la présente invention de procurer un procédé pour comprimer les données d'une image à deux valeurs, qui ne présente pas les inconvénients précités, qui est développé sur la base du procédé des vecteurs déjà décrit, qui est ca- pable d'effectuer une compression plus élevée que la méthode des vecteurs conventionnelle, qui soit rapide sans erreur de relevé et qui n'exige pas l'agrandissement du modèle de ca- ractère et le relevé manuel de tous ces points. Selon la présente invention, un procédé pour comprimer les données d'une image à deux valeurs se caractérise en ce qu'il comporte les stades suivants: a) on divise une image d'ori- ginal en une multiplicité d'images d'original divisionnaires par des lignes de division; b) on détecte les intersections entre les lignes de division et les contours d'une surface de caractère de chaque image divisionnaire afin de déterminer les intersections détectées comme points de départ et points d'arrivée; c) on choisit des points caractéristiques pendant que les contours de la surface caractère de chaque image divisionnaire sont tracés depuis les points de départ jus- qu'aux points d'arrivée et d) on raccorde les contours des zones de caractères des images divisionnaires adjacentes aux points de départ et aux points d'arrivée. L'invention sera mieux comprise à la lecture de la descrip- tion 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 figure 1 est un schéma-bloc d'une machine de compression de données qui met en oeuvre un procédé selon la présente in- vention; la figure 2 montre un modèle de bits d'une image originale stocké dans une mémoire, quidoit être comprimé selon la présente invention; la figure 3 montre un modèle debits agrandi d'une image di- visionnaire, comprise dans le modèle de bits de la figure 2, qui est transféré à une autre mémoire; la figure 4 est un organigramme des opérations effectuées dans la machine de compression des données de la figure 1; la figure 5 est une vue partielle à grande échelle d'un con- tour d'une surface de caractère du modèle de bits, pour expli- quer le tracé du contour par les moyens de traçage de contour de la figure 1; la figure 6 montre d'autres surfaces de caractères comportant des points caractéristiques,et le modèle de bits de ceux-ci dans la mémoire; la figure 7 est une vue partielle à grande échelle d'un con- tour d'une surface de caractère du modèle de bits,pour expliciter une relation de points représentatifs alignés, dans le détec- teur de points caractéristiques de la figure 1; et les figures 8 à 10 sont des organigrammes montrant en détail le stade 26 de la figure 4. En se reportant aux dessins, on voit une machine de compres- sion de données mettant en pratique un procédé selon la pré- sente invention. Un modèle d'image originale est balayé photo-électriquement dans des moyens d'entrée d'images originales 1 pour obtenir des signaux d'images analogiques; ces signaux d'images analo- giques sont envoyés à un convertisseur analogique-numérique 2, appelé ciaprès convertisseur A/D, et y sont convertis en des signaux d'images numériques Les signaux d'images numé- riques sont envoyés à une mémoire d'images à deux valeurs 3 et y sont stockés. Les données du modèle d'image originale de l'image à deux valeurs, telles qu'un modèle de caractère A, qui doit être stocké dntns la mémoired'images à deux valeurs 3 et doit être comprimé, sont constituées par un modèle de bits d'une matrice de points, tel qu'on le voit sur la figure 2 La mémoire d'images à deux valeurs 3 comporte une multiplicité de blocs-mémoires Moo Mij alignés dans une matrice; chacun des blocs- mémoires MOO Mi 1 stocke le modèle debits d'une des images division- naires obtenues en divisant l'image à deux valeurs, appelée ci-après image originale, en une multiplicité de divisions. Ensuite, chaque image divisionnaire extraite de la mémoire d'images à deux valeurs 3 pour chaque bloc de mémoire est con- sécutivement transférée à une mémoire d'images divisionnaires 4 et y est stockée par bloc de mémoire par un signal de com- mande émis par une commande de mémoire 5. La commande de mémoire 5 commande l'écriture, la lecture et les adresses des données dans et hors des mémoires 3 et 4 se- lon un organigramme décrit ci-après. La figure 3 montre un modèle de bit agrandi d'une image divi- sionnaire stockée dans la mémoire d'images divisionnaires 4, correspondant au modèle de bits du bloc-mémoire M 03 de la figu- re 2 Ensuite, en fonction du modèle de bits extrait de la mémoire d'images divisionnaires 4, les intersections entre les contours de la surface de caractère A de l'image division- naire et les lignes de division qui divisent l'image origi- naleen les images divisionnaires sont détectées par un détec- teur de points de départ et de points d'arrivée 6 sous forme de points de départ et de points d'arrivée (P(S) et p(E)) pour tracer automatiquement les contours. Ensuite, les contours de la zone de caractère A du modèle de bits pour chaque image divisionnaire sont tracés à partir des points de départ P(S) jusqu'aux points d'arrivée P(E) dans des moyens de traçage de contour 7 Tandis que les contours de la surface de caractère A sont tracés, les caractéristiques des changements des contours sont détectées par un détecteur de points caractéristiques 8 pour obtenir un nombre approprié de points caractéristiques se rencontrant successivement sur et le long des contours De ce fait, les données des coor- données des points caractéristiques sélectionnés alignés à partir des points de départ P(S) jusqu'aux points d'arrivée P) deviennent les données comprimées du modèle de bit de l'image divisionnaire. Ainsi, les données comprimées obtenues de chaque image divi- sionnaire sont continuellement stockées dans une mémoire de données de segments de lignes 9 en vue du traitement Lors- qu'on a épuisé tous les blocs-mémoires M 00-M i, les contours des surfaces de caractères A divisées des images divisionnai- res sont raccordés aux points de départ P(S) et d'arrivée P(E) correspondants, obtenant ainsi les donndes comprimées pour l'image originale Ensuite, les données comprimées pour l'image originale sont stockées dans une mémoire de données comprimées d'images à deux valeurs 11. Ensuite, les données comprimées pour l'image originale ex- traites de la mémoire de données comprimées d'images à deux valeurs 11 sont envoyées à des moyens de sortie 12 pour affi- cher un modèle de l'image de reproduction sur un moniteur en fonction des données comprimées, ou pour stocker les don- nées comprimées dans des moyens de classement de données. Le procédé décrit ci-dessus est représenté sur l'organigram- me de la figure 4. Dans ce dernier, le procédé pour détecter les points de dé- part P(S) et les points d'arrivée p(E)dans le détecteur de points de dé- part et d'arrivée 6 correspond au stade 25 et l'exemple de ce procé- dé est décrit ci-après. L'espace d'adresses de la mémoire d'images divisionnaires 4 est adapté pour avoir la même structure que celui de chacun des blocs-mémoires M 00Mij dans la mémoire à deux valeurs 3-, et de ce fait les adresses périphériques de la mémoire d'ima- ges divisionnaires 4 correspondent à la périphérie de l'ima- ge divisionnaire. Comme on le voit sur la figure 3, les lignes de division des images divisionnaires et les contours des zones de caractères A de ces images sont détectés sous forme de lignes des élé- ments d'images, du fait que le modèle de bits de l'image divi- sionnaire est constitué par une matrice des éléments d'images. Les adresses périphériques de la mémoire d'images division- naires 4 sont adressées en sens inverse des aiguilles d'une montre depuis l'origine ( 0, 0) pour détecter les éléments d'images comportant les intersections entre les lignes de division et les contours des zones de caractères A en détec- tant les variations des bits d'éléments d'images dans les adresses périphériques du modèle de bits. Dans cette réalisation, il est défini que le bit d'élément d'image de la surface de caractère A représente "l" et que l'élément d'image de l'autre surface représente O". Ainsi, les bits d'éléments d'images des adresses périphériques du modèle de bits sont lus consécutivement un par un dans la mémoire d'images divisionnaires 4 en sens inverse des ai- guilles d'une montre et, lorsque le bit d'élément d'image passe de " 1 " à "", on détermine que c'est le point de dé- (S) part P, et lorsque le bit d'élément d'image passe de "O" à " 1 ", on détermine que c'est le point d'arrivée P(E> Les coordonnées (xi, Yi) des points de départ P S) et d'ar- rivée P ainsi obtenues sont conservées dans un registre approprié du détecteur des points de départ et d'arrivée 6, et sont ensuite envoyées aux moyens de traçage des contours 7 comme de valeurs initiales et valeurs finales. Le procédé dans les moyens de traçage des contours 7 corres- pond au stade 26 de l'organigramme de la figure 4. La figure 5 montre un contour de la surface caractère A du modèle de bits pour expliquer le traçage du contour par les moyens de traçage 7 Tout d'abord, les bits d'éléments d'ima- ges entourant le bit d'élément d'image considéré Q 1, contenant le contour de la surface de caractère A, sont détectés en sens inverse des aiguilles d'une montre, comme le montrent les flèches de la boucle L 1, de sorte que chaque bit d'élément d'image peut représenter " 1 " ou " O " Lorsque la valeur passe de " O " à " 1 ", le bit d'élément d'image ayant la valeur " 1 " est le bit d'élément d'image suivant Q 2 contenant le contour de la surface de caractère A. On recommence vis-à-vis du bit d'élément d'image Q 2 la même opération que pour le bit d'élément d'image Q 1 par l'inter- médiaire d'une boucle L 2, obtenant ainsi le troisième bit d'élément d'image Q 3 Cette opération est répétée jusqu'à obtenir les bits d'éléments d'images contenant le contour de la surface de caractère A, c'est-à-dire qu'on trace le con- tour de cette surface A. Lors du tracé de ce contour, certains des bits d'éléments d'images Q 1, Q 2 ' etc, sont sélectionnés comme points repré- sentatifs et ensuite certains de ces points représentatifs sont sélectionnés comme points caractéristiques pour vérifier la variation de l'alignement des points représentatifs. Une réalisation du procédé pour sélectionner les points carac- téristiques par le détecteur de points caractéristiques 8 est représentée dans les organigrammes des figures 8 à 10. Les points caractéristiques sont classés en quatre catégories, en fonction des conditions de la variation, et un exemple du modèle de bits contenant ces quatre catégories de points caracté- ristiques est représenté sur la figure 6. La figure 6 a montre une autre image divisionnaire à évaluer en deux valeurs, et la figure 6 b montre un modèle de bits de l'image divisionnaire de la figure 6 a, stocké dans la mé- moire d'images divisionnaires 4 comportant les quatre catégories de points caractéristiques Sur la figure 6 b, des flèches montrent les directions du contrôle des bits d'éléments d'images. La classification des points caractéristiques s'effectue comme suit: P( 1) : un point o la direction du contour change-brusquement; p( 2): un point o le contour s'incurve modérément dans une di- rection; P( 3): un point o le contour passe d'une ligne droite à une ligne courbe; et P( 4): un point o le contour passe d'une ligne courbe à une ligne droite. Le choix de ces points caractéristiques est effectué dans le détecteur de points caractéristiques 8 comme suit. Tout d'abord, avant d'inspecter la variation du contour, les points représentatifs sont-sélectionnés le long de ce contour Les points représentatifs Pl sont choisis dans les bits d'éléments d'images contenant le contour de la surface de caractère A à intervalles réguliers d'un certain nombre de bits d'éléments d'images, lorsque le contour est tracé depuis le point de départ P(S) par les moyens de traçage 7, comme décrit ci-dessus, et on obtient ainsi leurs coordon- nées Pl = (xi, yi). L'intervalle des bits d'éléments d'images pour sélectionner les points représentatifs Pl est déterminé en fonction du taux de compression des données recherché, de la fidélité etc Par exemple, lorsque l'intervalle est élargi, le taux de compression des données par rapport à une même image aug- mente, mais la fiabilité diminue En conséquence, on détermine cet intervalle en fonction de l'importance du taux de compres- sion des données ou de la fidélité de l'image de reproduction. Dans cette réalisation, l'intervalle est déterminé être quatre bits. Ensuite, les points caractéristiques p , p( 3 > et P( 4) sont choisis parmi les points représentatifs P sauf les d'arive (S) (E) points de départ et d'arrivée P et P Tout d'abord, on obtient un angle ei des deux vecteurs Pl P et p p des deux points représentatifs adjacents, P et P par référence au point représentatif Pi, excepté i+ 1 ' (S) (E) les points de dépa-rt P et d'arrivée P, comme on le voit sur la figure 7 dans ce qui suit e =p pp rcsi -; -I i i-h i i+l il F 1 i A partir de cet angle si, on détermine les points caracté- ( 1) ( 2) ( 3) ( 4) ristiques P, p, p et P par les méthodes de dis- crimination suivantes: 1 1 ( 1) Un point caractéristique p( 1) est un point ou la direction du contour change brusquement: Lorsque l'angle Hi pour le point représentatif Pl est supé- o i 1 > L'angle O ( 1) est déterminé sous forme d'une valeur fixe, par exemple 30 . ( 2) Un point caractéristique p( 2) est un point o le contour s'in- curve modérément dans une direction: Lorsque la somme des angles i depuis le point représentatif Pm au point représentatif Pm+n est supérieure à l'angle pré- déterminé 6 ( 1) Pm+ est choisi comme point caractéristique p( 2). n ( 1) 1 Z il > 6 () m Le point représentatif initial Pm du début de l'addition est le point de départ p(S) le point caractéristique p( 1) ( 2) antérieur ou le point caractéristique p( 2) Lors- qu'un point d'inflexion (symboles + et indiquant le chan- aement de courbure du contour) apparaît après ces points, le point d'inflexion est déterminé comme point représentatif initial P. m ( 3) ( 3) Un point caractéristique P( 3) est un point o le contour passe d'une ligne droite à une ligne courbe: Lorsque plusieurs (au moins trois) points représentatifs Pm -Pm+n se trouvent pratiquement sur une ligne droite et que le point représentatif suivant Pm+n+l n'est pas discriminé comme étant le point caractéristique p( 1) mais satisfait comme le point caractéristique P, maIs aifi la condition pour le point caractéristique p( 2) p est choisi comme point P 3 m ( 1)> Inn+ 11 > O ( 2) m L'angle prédéterminé ( 2) est une valeur fixe pour discrimi- ner si le contour est une ligne dreite et est donné par l'angle dont le point représentatif Pl est décalé d'un bit de la ligne droite C'est-àdire que O ( 2) = Arctg ( 1/distance entre deux points représentatifs) =-Arctg 1/4 = 140. ( 4) Un point caractéristique p( 4) est un point ou le contour passe d'une ligne courbe à une ligne droite: Lorsque plusieurs (au moins deux) points représentatifs Pm-Pm se trouvent sur une mmne courbe sans changement de courbure m+n et qu'ensuite les points représentatifs suivants (au moins deux) sont pratiquement sur une ligne droite, Pn est choi- 14) m+n si comme point P n I Zm Sgn(Oi) 1 > 2 et Sgn( 6 m nl) Sgn( m+n) l"O"t ou "-1 " correspondant aux symboles +, O ou -, qui indi- quent le sens de la courbure du contour, par exemple le sens in- verse des aiguilles d'une montre, la ligne droite ou le sens des aiguilles d'une montre, pour compter le nombre de ces symboles. ( 1 (quand O > 0) Sgn( 01) = ( O (quand e = 0) (-1 (quand 6 symboles qui indiquent ce qui suit. Oi: un angle Pl i J Pl produit par deux vecteurs Pi,pi et Pi Pi+ 1 de deux points représentatifs adjacents P et Pi+ 1 situés juste avant et après le point représentatif con- sidéré Pi; EMG O i: un compteur qui calcule la somme des angles 6 % pour les points représentatifs à partir du point caractéritique sélectionné immédiatement avant le point représentatif consi- déré; un compteur qui calcule la somme des angles Oi pour i les points représentatifs à partir du point d'inflexion dis- tingué immédiatement avant le point représentatif considéré; Sgn i: un code à trois valeurs " 1 " pour le sens inverse des aiguilles d'une montre, " O " pour le sens rectiligne, ou "-1 " pour le sens des aiguilles d'une montre au point repré- sentatif considéré; E Sgn Oi: un compteur qui calcule la somme des codes à trois valeurs pour les sens de courbure depuis le point caractéris- tique sélectionné immédiatement avant le point représentatif considéré; STRGIHT: un compteur qui montre une ligne droite depuis le point caractéristique sélectionné immédiatement avant le point représentatif considéré, distingué selon 6 i ( 2): un angle pour discriminer une ligne droite. Comme on le voit sur les organigrammes des figures 8 à 10, les points caractéristiques P ( 1) P( 4) sont sélectionnés afin de tracer le contour depuis le point de départ p(S)l et une combinaison des coordonnées (x 'yi) des points carac- ( 1 > ( 4 > i téristiques P P est stockée dans la mémoire des don- nées de segments de lignes 9, comme données comprimées de l'image divisionnaire. Les coordonnées des points stockés dans la mémoire de données de segments de lignes 9 sont converties en les coordonnées originales du modèle de bits de la figure 2 en fonction des numéros de blocs 00 ij des blocsmémoires M 00-M i 3 de la mémoire d'images à deux valeurs 3. Autrement dit, les coordonnées des points caractéristiques P( 1) _ P( 4) et des points de départ P(S) et d'arrivée P(E) sont stockées dans la mémoire de données de segments de lignes 9 comme coordonnées comprimées de chaque bloc-mémoire Mow- ou Mij, habituellement dans l'ordre point de départ P p o i N t S caractéristiques P ( 1) P ( 4) et point d'arrivée (E) c'est-à-dire que les données de segments de lignes de chaque image divisionnaire du modèle de bits de l'original sont stockées dans la mémoire de données de segments de lignes 9 de telle sorte que les points de départ P() et d'arrivée P(E) puissent tous deux être les extrémités de chaque segment de ligne. Les données comprimées de tous les blocs-mémoires "OC Mi sont rassemblées dans la mémoire de données de segments de lignes 9, et les points de départ P(S) et d'arrivée P(E) des contours de la surface de caractère A de chaque image divi- sionnaire sont reliés aux points d'arrivée P(E) et de départ p(S) des contours de la surface de caractère A d'une autre image divisionnaire adjacente à celle-ci dans l'assembleur de données d'images divisionnaires 10, obtenant ainsi les données comprimées du modèle de bits de l'image d'original de la figure 2, comme combinaison des coordonnées des points caractéristiques alignés sur les contours dans les directions dans lesquelles les contours des surfaces de caractères A divisées en images divisionnaires sont raccordés aux points (S) (E) de départ P et d'arrivée P Les contours des surfaces de caractères A de l'image ori- ginale sont formés dans les boucles fermées, comme on le voit sur la figure 2 Lorsque le contour de la surface de caractère est tracé en sens inverse des aiguilles d'une montre, l'inté- rieur de la boucle est noir, c'est-à-dire que c'est la surface de caractère A, et dans le sens des aiguilles d'une montre, l'in- térieur de la boucle est blanc, c'est-à-dire que ce n'est pas la surface de caractère Lorsque les boucles se recouvrent, la boucle blanche prédomine sur l'autre. On comprend aisément que la présente invention peut effectuer rapidement, exactement et de façon précise la compression des données du modèle de caractère et réduire considérablement les opérations manuelles En outre, selon le présent procédé, la capacité de la mémoire peut être largement réduite. Revendications. 1 Procédé pour comprimer les données d'une image d'original à deux valeurs, caractérisé en ce que (a) on divise par des lignes de division une image d'original en une multiplicité d'images divisionnaires; (b) on détecte les intersections entre les lignes de division et les contours d'une surface de caractère de chaque image divisionnaire pour déterminer les intersections détectées comme points de départ et d'arrivée; (c) on sélectionne des points caractéristiques pendant que les contours de la surface de caractère de chaque image divi- sionnaire sont tracés depuis les points de départ jusqu'aux points d'arrivée; et (d) on raccorde les contours des surfaces de caractères des images divisionnaires adjacentes aux points de départ et d'arrivée. 2 Procédé selon la revendication 1, caractérisé en ce que le point caractéristique du contour est sélectionné en fonc- tion d'une direction de deux vecteurs de deux points repré- sentatifs adjacents au point représentatif considéré, et d'un angle formé par les vecteurs du point représentatif con- sidéré et d'un autre point représentatif situé immédiatement avant lui, les points représentatifs étant sélectionnés à partir des bits d'éléments d'original comprenant le contour de la surface de caractère de chaque certain nombre de bits -d'élément d'original,contenant les points de départ et d'arrivée.