Brevet FR2591050A1 — publié le 19870605

PROCEDE ET DISPOSITIF DE COMPRESSION PAR CODAGE CONDITIONNEL D'IMAGES NUMERIQUES SANS PERTE D'INFORMATIONS La présente invention se rapporte à un procédé et à un dispositif de compression par codage conditionnel d'images numé- riques sans perte d'informations. On connaît d'après la demande de brevet français 83 18132 un procédé de compression d'informations numériques représentatives des pixels d'une image numérisée. Ce procédé permet d'obtenir un bon taux de compression, sans perte d'informations, alors que les procédés antérieurs ne permettaient d'obtenir des taux de compres- sion intéressants qu'avec une certaine dégradation de l'image, donc avec perte d'informations, ce qui est rédhibitoire lorsqu'il s'agit d'images médicales radiographiques. Toutefois, dans certaines utilisations, comme par exemple l'obtention d'images d'angiographie numérisées, dont le stockage doit se faire en occupant le moins de mémoire fossible et à cadence vidéo, les taux de compression obtenus par le procédé de la susdite demande de brevet français ne sont pas suffisants. D'aure part, on connait d'après l'article de H. GHARAVI "Conditional Variable-length Coding for Gray-level Pictures" publié dans le BST3, vol. 63, N 2 de février 1984, un procédé de compression par codage conditionnel, mais ce procédé part d'une image dont la numérisation (sur trois éléments binaires) induit une distorsion sur l'image originale. La présente invention a pour objet un procédé de compression d'informations numériques permettant d'obtenir un taux de compres- sion élevé, sans perte d'informations, et elle a également pour objet un dispositif de mise en oeuvre de ce procédé, dispositif qui soit simple et peu onéreux à réaliser. Le procédé de la présente invention consiste à effectuer un codage conditionnel pour chaque pixel de l'image numérisée en assignant à chaque pixel courant un code à longueur variable compte tenu de sa valeur et des valeurs d'au moins deux pixels voisins, et selon un aspect avantageux de l'invention, on regroupe les différents codes en un nombre plus faible de classes de codage présentant toutes sensiblement la même probabilité d'apparition et on regroupe sous un même préfixe plusieurs valeurs de codes peu probables que l'on distingue par un suffixe. Le dispositif de mise en oeuvre de l'invention comporte essentiellement une mémoire vive mémorisant les valeurs de pixels successifs d'une image analysée en nombre au moins égal au nombre de pixels contenus dans une ligne de cette image, cette mémoire vive étant reliée à un dispositif convertisseur fournissant, en fonc- tion des valeurs respectives des pixels voisins du pixel courant des numéros de classes de codage, ce dispositif convertisseur étant relié à un dispositif de codage fournissant, en fonction des numéros de classes précités des codes à longueur variable correspondants. Pour permettre la mémorisation des codes des pixels succes- sifs d'une image analysée, le dispositif de l'invention comporte un dispositif formateur à concaténation composé essentiellement d'un registre à entrées parallèles dont la sortie série est reliée à une entrée série d'un autre registre de même capacité à sorties paral- lèles, les entrées du premier de ces registres étant reliées audit dispositif de codage et les sorties du second à un dispositif de mémorisation de masse, ledit dispositif de codage comportant une sortie de longueur de code à longueur variable reliée par un contrôleur à une horloge elle-même reliée aux entrées de signaux d'horloge des deux registres et à un compteur dont le nombre d'états de comptage et égal à la capacité de chacun des deux-registres, la sortie de ce compteur, activée à l'arrivée au dernier état de comptage, étant reliée à l'entrée de commande de validation des sorties du deuxième registre précité. La présente invention sera mieux comprise à la lecture de la description détaillée d'un mode de réalisation, pris comme exemple non limitatif et illustré par le dessin annexé sur lequel: - la figure 1 est un bloc diagramme d'un codeur conforme à 2 5 9 1 0 5 0 l'invention, et - la figure 2 est un bloc diagramme d'un décodeur conforme à l'invention. L'invention est expliquée ci-dessous en réf érence à la compression de données numériques correspondant à des images d'angiographie, mais il est bien entendu qu'elle n'est pas limitée à une telle application, et peut être utilisée dans tous les cas o l'on doit comprimer des données par utilisation d'un codage numérique à longueur de code variable. Des mesures réalisées sur différentes images d'angiographie numérisées ont montré qu'il faut prendre en compte lors du codage de chaque pixel d'une telle image, un maximum possible de pixels voisins intra ou inter- image de chaque pixel codé de l'image pour augmenter le taux de compression du codage réalisé. Ainsi, si l'on code un pixel X en tenant compte uniquement du pixel Y précédent (codage différentiel), on obtient un taux de compression (rapport du nombre d'éléments binaires résultant de la numérisation d'un pixel au nombre d'éléments binaires après codage) d'environ 2 si l'on -ne tolère pas de distorsion. Si l'on tient compte à la fois du pixel Y précédant celui que l'on code et du pixel Z de même rang de la ligne d'analyse précédente (codage conditionnel), on peut obtenir un taux de compression d'environ 4, ceci bien entendu grâce au fait que les images en question ne sont pas des images de "bruit blanc" (c'est-à- dire des images dans lesquelles les valeurs des pixels successifs sont aléatoires), mais des images dont les pixels successifs présentent une forte corrélation. Si l'on numérise une image d'angiographie avec une résolution de huit éléments binaires par exemple (256 niveaux de valeurs), le codage conditionnel des pixels tenant compte des deux pixels voisins nécessite, si l'on ne veut pas perdre d'informations, une mémoire de codage d'une capacité de 28.28= 216 valeurs de codes possibles, chacun d'eux devant coder 256 éventualités de valeur du pixel X. Dans ces conditions, l'utilisation classique de 65536 codes de longueur variable tels que les codes de HUFFMAN (pouvant aller de 1 à 16 éléments binaires par exemple) permettrait d'atteindre la valeur de taux de compression précitée, mais nécessiterait, dans l'état actuel de la technologie, un nombre prohibitif de circuits de mémoire. La présente invention permet, comme expliqué cidessous, de réduire considérablement le nombre de circuits nécessaires à la mise en oeuvre d'un tel codage. Pour éviter l'emploi d'une telle mémoire de valeurs codées, la présente invention propose, d'abord, de répartir l'ensemble des couples de valeurs (Y, Z) en un nombre plus faible de classes de codage, et ensuite de regrouper sous un seul préfixe plusieurs valeurs que l'on distingue par un suffixe. Plusieurs regroupements ont été testés sur un grand nombre d'images réelles d'angiographie, et il a été trouvé que la partition suivante en 61 classes constitue le meilleur compromis entre l'efficacité de la compression et la facilité de réalisation: Y-Z -3 -2 -1 0 1 2 3 fYZl>4 0 5 6 7 0 - - - 4 14Y 164Y431 21 22 23 16 17 18 19 20 324Y447 29 30 31 24 25 26 27 28 48 4 644Y 804Y 4195 53 54 55 48 49 50 51 52 964Y 61 62 63 56 57 58 59 60 Dans le tableau ci-dessus, donnant en fonction des valeurs respectives de (Y-Z)- et Y un numéro de code sur six éléments binaires (valeurs de 0 à 63), les numéros de code 1, 2 et 3 n'existent pas puisque les valeurs des pixels Y et Z ne peuvent être que positives ou nulles. Pour les numéros de code 0, 5, 6 et 7, il existe 4 codages de Huffman s'appliquant à la valeur du pixel courant X, et pour chacun des autres numéros de code (4 et 8 à 63), un codage de Huffman adapté s'applique à la différence X - (Y 2-) Bien entendu, on pourrait encore augmenter le taux de compression en prenant en compte un plus grand nombre de pixels, mais cela nécessiterait, dans le cadre de l'invention, une augmen- tation de la capacité de la mémoire de codage généralement trop élevée eu égard à la relativement faible augmentation du taux de compression. Le codeur représenté sur la figure 1 reçoit, sur une borne 1, d'un dispositif de numérisation (non représenté), une succession de données binaires, codées sur huit éléments binaires dans le cas présent, résultant de l'analyse, ligne par ligne, d'une image d'angio- graphie, puis de la numérisation des valeurs obtenues. On appelle X la valeur du pixel courant (celui qui est en train d'être codé), Y la valeur du pixel précédent, et Z la valeur de celui ayant le même rang que le pixel X dans la ligne précédente. Bien entendu, on pourrait choisir d'autres pixels parmi les pixels voisins du pixel courant, que ce soit dans l'image courante/- ou dans les images précédentes de la séquence. La borne 1 du codeur est reliée à l'entrée d'une mémoire 2, avantageusement constituée d'une mémoire vive, permettant de mémoriser un nombre de valeurs de pixels égal au nombre de pixels d'une ligne d'image analysée. La mémoire 2 comporte deux sorties 3, 4 sur lesquelles apparaissent respectivement les valeurs courantes Y et Z pour une valeur courante incidente X, ceci grâce à un adressage de la mémoire 2 évident à réaliser pour l'homme de l'art. La sortie 3 est reliée à l'entrée d'addition d'un additionneur 5 dont l'entrée de soustraction est reliée à la sortie 4. La sortie 4 est également reliée à l'entrée d'une mémoire 6, qui peut être une mémoire morte, mais de préférence une mémoire vive, et qui, en fonction de la valeur de Y, fournit sur trois éléments binaires, une partie du numéro de code (en fait, l'une des huit lignes du tableau ci- dessus). La sortie de l'additionneur 5 (sur laquelle on recueille la valeur Y-Z) est reliée à l'entrée d'une mémoire 7, qui peut être, comme la mémoire 6, une mémoire morte, mais de préférence une mémoire vive. Cette mémoire 7 fournit, en fonction des huit classes de valeurs de (Y-Z), les trois autres éléments binaires du numéro de code. L'entrée 1 est, par ailleurs, reliée à une entrée d'un multi- plexeur 8, et à l'entrée d'addition d'un additionneur 9, dont l'entrée de soustraction est reliée à la sortie 3. La sortie de l'additionneur 9 est reliée à l'entrée d'addition d'un autre additionneur 10 dont l'autre entrée d'addition est reliée à la sortie de l'additionneur 5 avec décalage d'un rang vers les éléments binaires de poids faibles, de façon à prélever la moitié de la valeur de sortie de dernier, c'est-à- dire (Y-Z)/2. La sortie de l'additionneur 10 est reliée à une autre entrée du multiplexeur 8. Les sorties des mémoires 6 et 7 sont reliées d'une part à une mémoire 1 dont la sortie est reliée à l'entrée de commande du multiplexeur 8, et d'autre part, conjointement avec la sortie du multiplexeur 8, à l'entrée d'une mémoire de codes 12. Dans le cas présent, la sortie de l'additionneur 5 est définie sur neuf éléments binaires (on tient compte du signe), comme celle du multiplexeur 8, et la mémoire 12 est donc adressée sur quinze éléments binaires. La mémoire 11 commande le choix, par le multiplexeur 8, de la valeur X (de la borne 1) ou bien de la valeur X - Y2 Z en provenance de l'additionneur 10, selon les classes de codage respectives (0, 5, 6, 7) ou (4 et 8 à 63). La mémoire 12, qui est également, de préférence, une mémoire vive, fournit sur une sortie 13 une information C qui représente soit le code à longueur variable, soit un préfixe auquel on adjoindra en suffixe la valeur X du pixel courant (au niveau du registre 16). L'information C a, dans le cas présent, une longueur L de quinze éléments binaires au maximum, et cette information L (déterminée sur quatre éléments binaires) se présente sur une sortie 14 de la mémoire 12. Enfin, sur une troisième sortie 15 de la mémoire 12, se présente une information P indiquant, sur un élément binaire, si l'information C est un code à longueur variable ou un préfixe. Les sorties 13 et 15 de la mémoire 12, ainsi que la borne 1, sont reliées aux entrées parallèles d'un registre 16 dont la sortie série est reliée à l'entrée série d'un autre registre 17. Les sorties parallèles (seize dans le cas présent) du registre 17 sont reliées via un registre tampon 18 à une mémoire de masse 19 qui peut être, par exemple une unité à disques souples. La liaison entre le tampon 18 et la mémoire 19 peut se faire sur huit ou seize éléments binaires. Les sorties 14 et 15 de la mémoire 12 sont reliées à un contrôleur 20, qui peut par exemple être un décompteur, lui-même relié à l'entrée de commande d'une horloge 21. La sortie de l'horloge 21 est reliée à l'entrée de signaux d'horloge des registres 16 et 17 et à un compteur 22 monté en compteur par 16, dont la sortie est reliée à l'entrée LD de commande du chargement du registre 18. Le circuit de formattage branché en aval de la mémoire 12 fonctionne de la façon suivante. A la première valeur incidente de X, le registre 16 est chargé depuis la mémoire 12 soit avec un préfixe et la vaieur de X via l'entrée 1, soit avec le code à longueur variable correspondant. Le contrôleur 20 fait envoyer par l'horloge 21 un nombre d'impulsions égal à la longueur L1 de l'information chargée dans le registre 16, ce qui fait que cette première infor- mation est transférée dans les L1 premières cellules du registre 17 (celles les plus proches de l'entrée série). Si cette longueur L1 est inférieure à 16, le compteur 22 n'atteint pas sa valeur de déclen- chement, et le registre 17 contient (16-LI) éléments binaires de valeur quelconque, et L1 éléments binaires de code. A la seconde valeur incidente de X, le registre 16 est chargé avec l'information correspondante de longueur L2, et le contrôleur 20 fait émettre par l'horloge 21 L2 impulsions. Si L2 est supérieure à (16-L1), dès que l'horloge 21 a émis (16-L1) impulsions, le compteur 22 arrive à 16 et émet à sa sortie un signal qui commande l'envoi par le registre 17 de son contenu sur ses sorties parallèles. Ce contenu se compose des L1 éléments binaires de l'information correspondant au premier pixel analysé et des (16-L1) premiers éléments binaires de l'information correspondant au second pixel analysé. Ces 16 premiers éléments binaires sont-ensuite chargés dans la mémoire de masse 19. Bien entendu, si L2 est inférieure à (16-LI), le compteur 22 ne se déclenche pas, et le registre 17 attend le chargement d'autres informations en provenance du registre 16. Dans le cas o L2 est supérieure à (16-L1), les (L2-(16-L1")) derniers éléments binaires de la seconde information restent dans les premières cellules du registre 17. Ensuite, une troisième information de longueur L3 est chargée dans le registre 16 et transférée en série dans le registre 17, et si ce dernier reçoit au moins seize éléments binaires d'informations, c'est-à-dire si (LI + L2 + L3 - 16) est supérieur ou égal à 16, le contenu du registre 17 est transféré vers la mémoire 19, sinon le registre 17 attend l'arrivée d'une ou de plusieurs autres informations suivantes, jusqu'à ce que cette condition soit remplie. Ce processus de concaténation des informations se poursuit jusqu'à la fin de l'analyse de l'image ou des images à mémoriser, la dernière information étant avantageusement suivie d'un nombre de signaux d'horloge supplémentaires suffisants pour la transférer du registre 17 à la mémoire 19. Ces signaux d'horloge supplémentaires remplissent le registre 17, du côté de son entrée série, d'une succession d'éléments binaires, par exemple une suite de "0" résul- tant du forçage à "0" des cellules du registre 16. Ces signaux d'horloge supplémentaires peuvent être produits par un dispositif, non représenté, et de réalisation évidente pour l'homme de l'art: cela peut par exemple être un dispositif validé juste après l'analyse du dernier pixel et comportant un décodeur décodant l'état E du compteur 22 et envoyant (16-E) impulsions d'horloge à la place de l'horloge 21 ou la forçant à les envoyer. On a représenté sur la figure 2 le bloc diagramme d'un circuit décodeur permettant de restituer à partir des informations mémo- risées dans la mémoire de masse 19 l'image d'origine. Comme on le verra, le circuit décodeur décrit ci-dessous reprend tous les élé- ments constitutifs du circuit de la figure 1, mais avec certaines différences de branchement. Ainsi, l'homme de l'art peut facilement réaliser les deux circuits à l'aide d'un seul jeu d'éléments consti- tutifs, et les commuter de façon appropriée selon qu'il veut obtenir un codeur ou un décodeur. Cependant, afin de ne pas compliquer inutilement la description et le dessin, ces deux circuits sont décrits ici séparément. La mémoire de masse 19 est reliée par un tampon 23 à l'entrée parallèle d'un registre 24 dont la sortie série est reliée à l'entrée série d'un autre registre 25. Dans le cas présent la liaison entre la mémoire 19 et le tampon 23 peut se faire sur huit ou seize éléments binaires, et celle entre le tampon et le registre 24 se fait sur seize éléments binaires, les deux registres 24 et 25 ayant chacun seize cellules. La sortie parallèle du registre 25 est reliée à l'entrée d'un décodeur 26 constitué d'une mémoire morte, ou, de préférence, d'une mémoire vive. Le décodeur 26 comporte une sortie 27 de laquelle émane le mot décodé (qui est soit X, soit X - 2() ), sur neuf éléments binaires dans le cas présent (valeur sur huit éléments binaires et le signe), et une sortie 28 sur laduelle se présente une information concernant la longueur du mot décodé. Cette sortie 28 est reliée à un contrôleur 29, qui comporte par exemple un décomp- teur, et dont la sortie est reliée à l'entrée de commande d'une horloge 30. La sortie de l'horloge 30 est reliée aux entrées de signaux d'horloge des registres 24 et 25, ainsi qu'à l'entrée d'un compteur 31 monté en compteur par 16. La sortie, activée à l'arrivée à l'état 16, du compteur 31 est reliée à l'entrée de signaux d'horloge du tampon 23. La sortie 27 (sans le signe) du décodeur 26 est reliée à une entrée d'un multiplexeur 32 ainsi qu'à l'entrée d'addition d'un addi- tionneur 33 (avec le signe) dont la sortie est reliée à l'entrée d'un autre additionneur 34, la sortie de ce dernier étant reliée à une autre entrée du multiplexeur 32. La sortie du multiplexeur 32 est reliée à une borne 35, sur laquelle on recueille, pour traitement subséquent, les valeurs numé- risées des pixels X (sur 8 éléments binaires dans ce cas présent), ainsi qu'à l'entrée d'une mémoire 36 qui a les mêmes caractéris- tiques que la mémoire 2. La sortie "Y" de la mémoire 36 est reliée à l'entrée d'une mémoire 37 ainsi qu'à l'entrée d'un additionneur 38. L'entrée de soustraction de l'additionneur 38 est reliée à la sortie "Z" de la mémoire 36, et sa sortie est reliée à l'entrée d'une mémoire 39. Les sorties des mémoires 37 et 39 sont reliées à l'entrée du décodeur 26, ainsi qu'à l'entrée d'une mémoire 40 dont la sortie est reliée à l'entrée de commande du multiplexeur 32. Les caractéristiques des mémoires 37, 39 et 40 sont les mêmes que celles des mémoires 6, 7 et 11 respectivement. La sortie "Y" de la mémoire 36 est reliée à une autre entrée de l'additionneur 33, et la sortie de l'additionneur 38 est reliée, avec décalage d'un poids vers les poids faibles (division par 2), à l'entrée de soustraction de l'additionneur 34. Pour obtenir, à partir de la mémoire 19, sur la borne 35 les valeurs des pixels successifs d'une image, on lit, dans l'ordre dans lequel elles y ont été mémorisées, des tranches de 8 ou 16 éléments binaires qui sont chargées dans le tampon 23. Au premier char- gement du tampon 23, un dispositif de commande (non représenté) lui envoie une impulsion d'horloge, et son contenu est transféré dans le registre 24. Le contrôleur 29 fait envoyer par l'horloge 30 aux registres 24 et 25 un nombre d'impulsions correspondant à la longueur du code précédemment présenté à l'entrée du décodeur 26 pour l'évacuer dès que le décodeur a fourni à sa sortie 27 la valeur décodée X ou X - _2 Z). La première valeur codée présente dans le registre 24 correspond à la valeur X du premier pixel, et dans le cas, le contrôleur 29 fait envoyer 16 impulsions par l'horloge 30, pour la transférer dans le registre 25. La mémoire décodeur 26, qui est de préférence, une mémoire vive, reçoit sur ses entrées d'adressage, d'une part les 6 éléments binaires correspondant à la classe du code associé au couple (Y, Z), d'autre part les 8 premiers bits du contenu du registre 25. La valeur apparaissant à la sortie 27 du décodeur 26 est envoyée au multiplexeur d'une part directement (sans son signe), et d'autre part via les additionneurs 33 et 34, et à la sortie de ce 1l dernier on a, lorsque la valeur présentée à la sortie de 27 est X - (- +) la valeur: X - (y) + Y y (- 2) = X, le multiplexeur 32 étant basculé vers la sortie de 34 (puisqu'au codage du même pixel cette même valeur X - (Y + Z) avait été enregistrée). Dans le cas o l'on a directement à la sortie 27 la valeur X, le multiplexeur est basculé vers cette sortie (cette même valeur ayant été enregistrée au codage). Ainsi, on retrouve sur la sortie 35 les mêmes valeurs successives des pixels X que celles ayant été envoyées sur l'entrée 1 du codeur. La valeur apparaissant à la sortie 28 de la mémoire décodeur 26 est envoyée au contrôleur 29 pour indiquer à celui-ci la longueur, sur 4 éléments binaires, du code reconnu dans les 8 premiers éléments binaires du registre 26. 2 5 9 1 0 5 0 REVENDICATIONS 1. Procédé de compression d'images numériques selon lequel l'on effectue un codage conditionnel pour chaque pixel de l'image numérisée en assignant à chaque pixel courant un code à-longueur variable compte tenu de sa valeur et des valeurs d'au moins deux pixels voisins, caractérisé par le fait qu'on effectue un codage conditionnel sans perte d'informations en regroupant les différents codes en un nombre plus faible de classes de codage présentant toutes sensiblement la même probabilité d'apparition. 2. Procédé selon la revendication 1, caractérisé par le fait que selon la classe de codage on code soit la valeur courante du pixel soit la différence entre ce pixel et une combinaison des pixels voisins. 3. Procédé selon la revendication 2, caractérisé par le fait que les pixels voisins appartiennent à la même image que le pixel courant. 4. Procédé selon la revendication 2, caractérisé par le fait que les pixels voisins appartiennent à une image autre que celle du pixel courant. 5. Procédé selon l'une quelconque des revendications 2 à 4, caractérisé par le fait que la combinaison est la moyenne des Y+Z valeurs des pixels voisins 2 6. Procédé selon l'une des revendications précédentes, carac- térisé par le fait que l'on regroupe sous un même préfixe plusieurs valeurs de codes peu probables que l'on distingue par un préfixe. 7. Procédé selon l'une des revendications précédentes, carac- térisé par le fait que l'on code directement la valeur du pixel courant lorsque le code comprimé que l'obtiendrait dans sa classe est trop long, ce codage du pixel courant consistant à faire précéder sa valeur d'un préfixe. 8. Dispositif de compression par codage conditionnel d'images numériques sans perte d'informations, caractérisé par le fait qu'il comporte une mémoire à décalage (2) comportant au moins deux sorties (3, 4) sur lesquelles se présentent, pour chaque valeur de pixel incidente (X) les valeurs des pixels voisins (Y, Z), ces sorties étant reliées chacune à une mémoire (6, 7) fournissant un numéro de code, ces deux mémoires étant reliées à une mémoire de codes compresses (12) dont la sortie est reliée à un dispositif de format- tage et de concaténation de codes (16 à 22). 9. Dispositif selon la revendication 8, caractérisé par le fait que les mémoires de numéro de code (6, 7) sont également reliées à l'entrée de commande d'un multiplexeur (8) via une autre mémoire (11), l'une des entrées du multiplexeur recevant les valeurs de pixels incidentes (1), et l'autre une valeur (X - y-) fonction de. la diffé- rence entre les valeurs de pixels incidentes et les valeurs de pixels voisins, la sortie de ce multiplexeur étant également reliée à la mémoire de codes compresses. 10. Dispositif selon l'une des revendications 8 ou 9, caractérisé par le fait que le dispositif de formattage comporte deux registres en série (16, 17), l'entrée parallèle du premier étant reliée à la mémoire de codes compresses, et la sortie parallèle du second à une mémoire de masse (19), ces entrées de signaux d'horloge de ces deux registres étant reliées à une horloge (21) commandée par un contr8- leur (20) relié à une sortie de la mémoire de codes. 11. Dispositif selon l'une des revendications 8 à 10, caractérisé par le fait que les mêmes éléments que ceux utilisés pour le codage servent au décodage des informations mémorisées dans la mémoire de masse, avec des connexions modifiées (figure 2).