Brevet FR2691271A1 — publié le 19931119

La présente invention concerne le domaine de la compression et de la décompression de données, en particulier de la compression et de la décompression de données d'images numériques. Les avantages d'une compression de données sont bien connus Dans certains cas, une compression de données permet d'économiser de l'espace d'enregistrement tandis que dans d'autres cas elle réduit le temps de transmission de données De nombreuses techniques sont connues dans l'art antérieur pour une compression et une décompression de données vidéo numériques Par exemple, se référer au brevet des Etats Unis N O 5 046 119 intitulé "Method and Apparatus For Compressing and Decompressing Color Video Data With an Anti-Aliasing Mode" (procédé et dispositif pour une compression et une décompression de données vidéo couleurs avec un mode anti-crénelage), délivré au Déposant de la présente invention Le brevet des Etats Unis N O 5 046 119 décrit une technique de compression numérique appelée LOSSY (avec pertes) Des techniques de compression de données LOSSY sont affectées par un certain degré de perte de précision de l'image en train d'être représentée, dans un échange de données en vue d'augmenter leur compression Des techniques de compression LOSSY se sont avérées être efficaces lorsqu'elles sont appliquées à des images graphiques ou vidéo et à des données audio numérisées De telles techniques LOSSY sont basées sur le principe qu'un certain degré de perte de précision est acceptable pour représenter efficacement une source vidéo ou audio, c'est-à-dire analogique, dans un format numérique. D'autres techniques de compression LOSSY pour des données d'images vidéo ont été décrites par Nelson dans lhe Data Compression Book", M & T Books, une division de "M & T Publishing, Inc ", pages 347-408, ( 1992). D'autres techniques connues de compression de 2- données reproduisent exactement les données de la source d'origine lors d'une décompression De telles techniques de compression sont appelées LOSSLESS (sans pertes) Par exemple, se référer au brevet des Etats Unis N O 4 558 302 intitulé "High Speed Data Compression and Decompression Apparatus and Method" (procédé et dispositif pour compression et décompression de données à grande vitesse) Dans un procédé de compression de données LOSSLESS, aucune des données n'est perdue pendant une compression Des techniques de compression de données LOSSLESS sont typiquement utilisées pour mémoriser ou transmettre des données textuelles En dehors du brevet des Etats Unis N O 4 558 302, des techniques connues de compression LOSSLESS comprennent des systèmes de codage Huffman et différents systèmes dérivés opérant avec des algorithmes de compression Lempel-Ziv bien connus. Des techniques de compression de données LOSSLESS sont généralement considérées comme inutiles pour des données vidéo ou audio Généralement, cela est imputable à la distribution des données représentant l'image vidéo ou le son audio, et le temps nécessaire pour effectuer une compression/codage des données sous la forme d'un flux de données comprimées. Une compression de données LOSSLESS pour des signaux d'images vidéo est souhaitable pour des réalisations dans lesquelles la quantité de données utilisées pour représenter des valeurs de nuances de pixels est réduite au minimum Par exemple, pour des représentations graphiques en couleurs de 8 bits, une compression LOSSY peut donner lieu à des effets de crénelage Un crénelage est l'apparition étagée ou en escalier de lignes diagonales ou de cercles dans une représentation vidéo Une compression de données LOSSLESS pourrait être utilisée pour réduire au minimum de tels effets de crénelage. -3- En conséquence, un objet de la présente invention est de créer un procédé de compression/décompression de données sans pertes pour mémorisation et extraction de données d'images numériques. Un procédé et un appareil pour compression et une décompression sans pertes d'un bloc de données d'images en couleurs vont être décrits Le bloc de données d'images en couleurs est traité en incréments de bloc de pixels Le procédé de la présente invention est composé d'une façon générale des étapes consistant à: obtenir un bloc de pixels à partir dudit bloc de données d'images couleurs; établir une liste de couleurs; établir un mappage de pixels pour les couleurs des pixels se trouvant dans ledit bloc de pixels; comparer ladite liste de couleurs avec une ou plusieurs listes de couleurs correspondant à des blocs de pixels précédemment traités; déterminer si ladite liste de couleurs concorde avec une liste de couleurs d'un bloc de pixels précédemment traité; si ladite liste de couleurs concorde avec une liste de couleurs d'un bloc de pixels précédemment traité, coder ledit bloc de pixels en créant une référence pour ladite liste de couleurs dudit bloc de pixels précédemment traité et faire sortir ledit mappage de pixels; si ladite liste de couleurs ne concorde pas avec une liste de couleurs d'un bloc de pixels précédemment traité, coder ledit bloc de pixels en amenant une zone de type de bloc de commande sur une valeur correspondant au nombre de couleurs se trouvant dans ladite liste de couleurs, faire sortir le bloc de commande, les données de valeurs de couleurs pour chaque couleur intervenant dans la liste de couleurs et le mappage de pixels. Selon d'autres caractéristiques du procédé conforme à l'invention: -4ladite étape pour déterminer si ladite liste de couleurs concorde avec une liste de couleurs d'un bloc de pixels précédemment traité est en outre composée des étapes consistant à: a) comparer ladite liste de couleurs avec une liste de couleurs associée avec un présent bloc de commande pour déterminer une concordance; et b) comparer ladite liste de couleurs avec des combinaisons de couleurs dans une antémémoire de couleurs afin de déterminer une concordance, ladite liste de couleurs correspondant au nombre de couleurs dans ladite liste de couleurs. Ladite étape de codage dudit bloc auxiliaire de données de pixels par création d'une référence avec ladite liste de couleurs dudit bloc de pixels précédemment traité et de sortie dudit mappage de pixels est en outre composée des étapes consistant à: a) si ladite liste de couleurs concorde avec une liste de couleurs associée audit présent bloc de commande, référencer ladite liste de couleurs par incrémentation d'une zone de compte dudit présent bloc de commande; b) si ladite liste de couleurs concorde avec une entrée dans ladite antémémoire de couleurs, référencer ladite liste de couleurs par activation d'une zone d'indication située dans un bloc de commande et indiquant que ladite liste de couleurs se trouve dans une antémémoire de couleurs, activer une zone de type dans ledit bloc de commande en correspondance au nombre de couleurs se trouvant dans ladite liste de couleurs, sortir ledit bloc de commande et un index sur ladite entrée dans ladite liste de couleurs. Ladite étape de génération d'une liste de couleurs est en outre composée des étapes consistant à: a) identifier une couleur de pixel comme n'ayant -5- pas été précédemment rencontrée b) ajouter ladite couleur de pixel à ladite liste de couleurs; c) incrémenter un compte de couleur d) mémoriser ladite couleur dans ladite liste de couleurs; et e) répéter les étapes a)-d) pour tous les pixels se trouvant dans lesdits blocs de pixels. Ladite étape de comparaison de ladite liste de couleurs avec des listes de couleurs se trouvant dans une antémémoire de couleurs afin de déterminer une concordance est en outre composée des étapes consistant à: a) établir un masque d'entrée en antémémoire pour chaque entrée dans ladite antémémoire de couleurs, ledit masque d'entrée d'antémémoire identifiant des gammes de couleurs dans ladite entrée d'antémémoire; b) établir un masque de bloc de pixels, ledit masque de bloc de pixels identifiant des gammes de couleurs dans ledit bloc de pixels; c) comparer ledit masque d'entrée d'antémémoire avec ledit masque de bloc de pixels pour un seuil de concordance prédéterminé; d) si ledit seuil de concordance prédéterminé n'est pas satisfait, répéter l'étape c) pour une entrée suivante en antémémoire; e) si ledit seuil de concordance prédéterminé est satisfait, comparer les couleurs individuelles de ladite liste de couleurs et de ladite entrée d'antémémoire f) si un seuil de concordance exact et prédéterminé n'est pas satisfait, répéter l'étape c) pour une entrée suivante dans l'antémémoire; g) si ledit seuil de concordance exact et prédéterminé est satisfait, identifier ladite entrée d'antémémoire comme une concordance; et -6- h) répéter les étapes c)-g) jusqu'à ce qu'une concordance soit trouvée ou bien jusqu'à ce que toutes les entrées d'antémémoire aient été traitées. Ledit procédé de décompression comprenant les étapes consistant à: a) identifier la référence à une liste de couleurs en concordance avec ledit bloc de commande; b) recevoir un mappage de pixels; c) sortir des couleurs en concordance avec ladite liste de couleurs et ledit mappage de pixels; d) répéter les processus jusqu'à ce que tous les blocs de commande et tous les mappages de pixels aient été traités. Le procédé est caractérisé en outre en ce qu'il comprend les étapes consistant à: a) extraire un bloc de pixels d'un bloc de données d'images; b) établir une liste de couleurs et un compte de bloc de pixels; c) comprimer ledit bloc de pixels si ledit compte de bloc de pixels est inférieur à un premier nombre prédéterminé de valeurs de nuances de pixels en sortant des références de valeurs de nuances de pixels ainsi qu'un mappage de pixels identifiant la valeur de nuances de pixel pour chaque pixel se trouvant dans ledit bloc de pixels; et d) mémoriser ledit bloc de pixels comme n'étant pas comprimé si ledit compte de bloc de pixels est supérieur audit premier nombre prédéterminé de valeurs de nuances de pixels. Ladite étape de compression dudit bloc de pixels,si ledit compte de bloc de pixels est inférieur à un premier nombre prédéterminé de valeurs de pixels par sortie d'une référence de valeurs de nuances de pixels et d'un mappage de pixels identifiant la valeur de nuances 7- de pixels pour chaque pixel se trouvant dans ledit bloc de pixels, est en outre composée des étapes consistant à: a) comparer ladite liste de couleurs avec des listes de couleurs de blocs de pixels précédemment traités; b) si ladite liste de couleurs concorde avec une liste de couleurs précédente, établir un mappage de pixels en référence avec ladite liste de couleurs précédente; et c) si ladite liste de couleurs ne concorde pas avec une liste de couleurs précédente, établir un mappage de pixels en référence avec ladite liste de couleurs. Ladite étape de comparaison de ladite liste de couleurs avec une liste de couleurs de blocs de pixels précédemment traités comprend en outre l'étape consistant à comparer ladite liste de couleurs avec une ou plusieurs entrées dans une antémémoire de couleurs. Ladite référence de nuancement de valeurs de pixels constitue un index sur une entrée d'antémémoire contenant ladite liste de couleurs précédente. Ledit nombre prédéterminé de valeurs de nuances de pixels est égal à 8. L'invention concerne également un appareil de compression de données d'images couleurs caractérisé en ce qu'il comprend: a) un moyen d'extraction servant à extraire un bloc de pixels desdites données d'images couleurs; b) un moyen de génération de listes de couleurs pour un comptage des différentes couleurs dans ledit bloc de pixels et pour établir une liste de couleurs, ledit moyen de génération de liste de couleurs étant relié audit moyen d'extraction; c) un moyen de génération de mappage de pixels, ledit moyen de génération de mappage de pixels servant à engendrer un mappage de pixels en identifiant des valeurs -8- de couleurs dans chaque emplacement de pixel dudit bloc de pixels, ledit moyen de génération de mappage de pixels étant relié audit moyen d'extraction; d) une antémémoire de couleurs pour mémoriser plusieurs combinaisons de couleurs, chacune desdites combinaisons de couleurs étant mémorisée comme une entrée dans ladite antémémoire de couleurs; e) un moyen de comparaison relié audit moyen de génération de liste de couleurs, audit moyen d'extraction de pixels et à ladite antémémoire de couleurs, ledit moyen de comparaison servant à comparer une liste de couleurs avec une liste de couleurs précédente et avec une ou plusieurs entrées en antémémoire et servant à sortir des données comprimées si une concordance est trouvée et à sortir des données non comprimées si le nombre de couleurs dans ladite liste de couleurs est supérieur à un seuil prédéterminé. Selon d'autres caractéristiques de cet appareil: ledit moyen de comparaison comprend en outre: a) un moyen pour introduire une combinaison de couleurs dans ladite antémémoire de couleurs sous la forme d'une entrée; b) un moyen pour effectuer une recherche dans ladite antémémoire de couleurs; c) un moyen pour sortir un index d'antémémoire et un mappage de pixels si ladite liste de couleurs concorde avec une entrée dans ladite antémémoire; et d) un moyen pour sortir un mappage de pixels si ladite liste de couleurs concorde avec une liste de couleurs précédente. Ledit moyen de comparaison comprend en outre un moyen pour comparer un présent bloc de pixels avec un bloc de pixels précédent et, s'ils sont identiques, pour sortir des données comprimées indiquant que le bloc de pixels précédent devrait être dupliqué. -9- Chacune desdites entrées se trouvant dans ladite antémémoire de couleurs comporte un masque d'entrée d'antémémoire, ledit masque d'entrée d'antémémoire servant à identifier des couleurs dans5 ladite entrée d'antémémoire. D'autres caractéristiques et avantages de l'invention seront mis en évidence dans la suite de -10- la description, données à titre d'exemple non limitatif, en référence aux dessins annexés dans lesquels: la Figure la représente un système ordinateur qui peut comporter la réalisation couramment préférée de la présente invention. La Figure lb est un diagramme fonctionnel mettant en évidence la relation existant entre les moyens de compression/décompression de la réalisation préférée et d'autres composants du système ordinateur. Les Figures 2 a-2 b sont des organigrammes qui illustrent le procédé général de compression pouvant être utilisé par la réalisation préférée de la présente invention. La Figure 3 a représente le format d'un bloc de commande pour codage de données comprimées, tel qu'il peut être utilisé par la réalisation préférée de la présente invention. La Figure 3 b montre une séquence de blocs de commande o une liste de couleurs est alignée avec les données comprimées pouvant être établies par la réalisation préférée de la présente invention. La Figure 3 c représente une séquence de blocs de commande o un moyen d'indexage sur une entrée dans une antémémoire de couleurs est utilisé à la place de la liste de couleurs de la Figure 3 b, comme cela peut être mis en oeuvre par la réalisation préférée de la présente invention. La Figure 3 d représente une antémémoire de couleurs pouvant être créée et utilisée par la réalisation préférée de la présente invention. La Figure 3 e montre une séquence de blocs de commande o aucune des données n'a été comprimée, comme cela peut être mis en oeuvre par la réalisation préférée de la présente invention. La Figure 4 a représente un exemple d'une -11- compression de 4 couleurs o la liste de couleurs est incorporée dans le train de données, comme cela peut être codé par la réalisation préférée de la présente invention. La Figure 4 b représente un exemple, utilisant les mêmes blocs de pixels de la Figure 4 a et o la combinaison de couleurs a été précédemment introduite dans l'antémémoire, comme cela peut être codé par la réalisation préférée de la présente invention. Les Figures 5 a et 5 b sont des organigrammes qui définissent les étapes de recherche en antémémoire de couleurs dans les cas faisant intervenir quatre couleurs et huit couleurs, comme cela peut être effectué par la réalisation préférée de la présente invention. La Figure 6 est un organigramme illustrant le procédé de décompression/décodage, qui peut être mis en oeuvre par la réalisation préférée de la présente invention. Un procédé et un appareil de compression et de décompression de données d'images numériques dans un système ordinateur vont maintenant être décrits dans la suite Dans la description qui va suivre, de nombreux détails spécifiques seront donnés, comme des valeurs et structures spécifiques de codage, de façon à permettre une très bonne compréhension de la présente invention. Cependant, il sera évident pour un spécialiste de ce domaine que la présente invention peut être mise en oeuvre sans ces détails spécifiques Dans d'autres parties, des détails spécifiques de mise en oeuvre, comme des détails concernant des structures de données en antémémoires, n'ont pas été décrits de façon détaillée afin de ne pas obscurcir inutilement la présente invention Dans cette description, un bit correspond à une seule unité d'information binaire; un octet correspond à 8 bits d'information binaire; et un mot -12- correspond à 16 bits (ou 2 octets) De telles définitions et organisations de données binaires sont bien connues des spécialistes de ce domaine. On va maintenant donner une vue d'ensemble d'un système ordinateur intervenant dans la réalisation préférée Le système ordinateur de la réalisation préférée va être décrit dans la suite en référence à la Figure la La présente invention peut être mise en oeuvre dans un microordinateur d'utilisation générale, comme un des appareils de la famille Apple Macintosh, un des appareils de la famille des ordinateurs personnels de IBM, ou bien un des différents appareils pour stations de travail, pour utilisateurs multiples ou pour ordinateurs graphiques qui sont disponibles dans le commerce à l'heure actuelle De toutes manières, un système ordinateur pouvant être utilisé par la réalisation préférée comprend d'une façon générale un bus ou un autre moyen de communication 101 pour communiquer les informations, un moyen de traitement 102 relié audit bus 101 pour traiter des informations, une mémoire à accès sélectif, -ou mémoire vive (RAM), ou un autre dispositif de mémorisation 103 a (communément appelé une mémoire principale), relié audit bus 101 pour mémoriser des informations et des instructions pour ledit processeur 102, une antémémoire 103 b pour mémoriser des données faisant l'objet d'accès fréquents et/ou des données qui doivent faire l'objet d'accès rapides, une mémoire morte (ROM) ou un autre dispositif de mémorisation statique 104 relié audit bus 101 pour mémoriser des informations et instructions statiques pour ledit processeur 102, un dispositif de mémorisation de données 105, comme un appareil à disques magnétiques ou autres disques, relié audit bus 101 pour mémoriser des informations et des instructions, un dispositif d'entrée alphanumérique 106 comportant des touches alphanumériques et autres et relié -13- audit bus 101 pour communiquer des sélections d'informations et d'ordres audit processeur 102, un dispositif de commande de curseur 107, comme une souris, une boule de poursuite, des touches de commande de curseur, etc, relié audit bus 101 pour communiquer des sélections d'informations et d'ordres audit processeur 102 et pour commander un mouvement de curseur. Additionnellement, il est utile que le système comporte un dispositif de copiage 108, comme une imprimante, pour produire des copies permanentes d'informations Le dispositif de copiage 108 est relié au processeur 102 par l'intermédiaire du bus 101. Le système ordinateur de la réalisation préférée est également relié à un tampon de trame 109 qui est en outre relié à un dispositif d'affichage 110, de préférence un dispositif d'affichage capable d'afficher des images graphiques en couleurs Le tampon de trame 109 contient les données de pixel servant à actionner le dispositif d'affichage 110 Dans certaines réalisations, le dispositif d'affichage 110 peut être éventuellement relié à un dispositif de rendu 111, également appelé un "accélérateur graphique" Typiquement, un tel dispositif de rendu 111 est relié au bus 101 pour communiquer avec le processeur 102 et le tampon de trame 109 La réalisation préférée a été conçue pour être utilisée avec un ordinateur Macintosh, disponible auprès de la société "Apple Computer, Inc ", Cupertino, Californie. Il est à noter que le processeur 102 effectue différentes parties des processus de compression/décompression, comme une extraction de valeurs de nuances de pixels et une génération de blocs de commande En outre, les données comprimées ainsi obtenues peuvent être mémorisées dans la mémoire de données 105. En référence maintenant à la Figure lb, on va -14- décrire de façon plus détaillée la relation existant entre la présente invention et le système ordinateur Le moyen de compression/décompression 120 est relié au moyen de rendu 121 Le moyen de rendu 121 est utilisé pour établir des valeurs de nuances de pixels Dans certaines réalisations, le moyen de rendu extraira des données de nuances de pixels hors de la mémoire 122 après qu'elles auront été décomprimées par le moyen de compression/décompression 120 Le moyen de rendu 121 est en outre relié au tampon de trame 123 Le tampon de trame 123 contient l'information de données numériques qui est utilisée pour nuancer des pixels sur le moyen d'affichage 124 En outre, le tampon de trame 123 est relié au moyen de compression/décompression 120 Par exemple, lorsqu'un affichage d'images doit être mémorisé, les contenus du tampon de trame 123 sont transférés dans le moyen de compression/décompression 120 pour une compression Après la compression, les données sont mémorisées dans la mémoire 122. On va maintenant donner une vue d'ensemble du procédé de la présente invention La réalisation présentement préférée de la présente invention opère sur des valeurs de nuances de pixels de 8 bits Cependant, il apparaîtra comme évident pour un spécialiste que l'invention peut être étendue à des valeurs de nuances de pixels ayant des longueurs de bits plus grandes ou plus petites. Ces valeurs de nuances de pixels de 8 bits peuvent représenter soit des échelles de gris, des valeurs de couleurs, ou bien elles peuvent constituer un index sur une table de couleurs ou d'échelles de gris Par exemple, il peut se faire que les 8 bits représentent des données de couleurs RGB (rouge-vert-bleu), 3 bits étant utilisés pour représenter des données de rouge, 3 bits étant utilisés pour représenter des données de vert, et 2 bits étant utilisés pour représenter des données de bleu. -15- Cependant, le procédé de la présente invention serait également applicable pour d'autres organisations ou schémas de données de couleurs (par exemple YUV) Le procédé de la réalisation préférée groupe des pixels sous forme de blocs Dans la réalisation présentement préférée, ces blocs sont des blocs carrés de 4 x 4 pixels dans le tampon de trame Bien qu'un train séquentiel de valeurs de pixels puisse être utilisé, on a trouvé qu'en utilisant des blocs de 4 x 4 pixels, il était possible d'obtenir une plus grande compression Les blocs 4 x 4 sont créés, par exemple, en prenant les quatre premières valeurs de nuances de pixels d'une première ligne de balayage ou d'analyse, les quatre premières valeurs de nuances de pixels d'une seconde ligne de balayage, les quatre premières valeurs de nuances de pixels d'une troisième ligne de balayage et les quatre premières valeurs de nuances de pixels d'une quatrième ligne de balayage Un groupage de pixels de cette manière a été décrit dans le brevet des Etats Unis N O 5 046 119, qui a constitué une référence par rapport à l'art antérieur. Dans la suite de la description, les termes "couleur" ou "couleurs" seront utilisés pour définir des valeurs de nuances de pixels (qui peuvent, comme indiqué ci-dessus, être soit des données de couleurs, des données d'échelles de gris ou des index sur une table de nuances de pixels) De toute manière, les blocs de pixels sont codés en déterminant d'abord le nombre de couleurs de pixels à l'intérieur du bloc Une compression/codage du bloc de pixels se produit en fonction des résultats de codages de blocs de pixels précédents Le train de données comprimées/codées sera composé de blocs de commande et il sera suivi dans certains cas par une liste de couleurs ou par un index d'entrée dans une antémémoire de couleurs, en étant suivi par un ou plusieurs mappages de pixels Dans d'autres cas, un bloc de commande -16- indiquera que le bloc de pixels doit être ignoré ou bien que des blocs de pixels précédemment décomprimés devraient être directement copiés Une compression sera effectuée seulement pour des blocs de pixels comportant 8 couleurs ou moins Une exception pourra se produire dans le cas o un bloc de pixels est identique à un bloc de pixels immédiatement précédent. Le procédé général de compression/codage va être décrit en relation avec les Figures 2 a et 2 b En référence à la Figure 2 a, en premier lieu, un bloc de pixels est reçu, étape 201 Comme indiqué ci-dessus, le bloc de pixels est un bloc de 4 x 4 pixels Ensuite, on détermine si l'image en train d'être comprimé est sujette à une différenciation de trame, étape 202 Une différenciation de trame se rapporte à une technique de mémorisation d'image typiquement utilisée pour une animation ou une représentation vidéo o seulement les pixels qui sont différents d'une trame d'image dans une trame d'image suivante sont mémorisés Si une différenciation de trame est validée, alors le bloc de commande en cours sera contrôlé pour déterminer s'il constitue un bloc de commande de différenciation de trame, étape 203 a Dans la négative, un nouveau bloc de commande du type différenciation de trame est sorti, étape 203 b Dans l'affirmative, une zone de compte intervenant dans le bloc de commande de circuit sera incrémentée d'une unité, étape 203 c Dans l'un ou l'autre cas, une vérification est effectuée pour le dernier bloc de pixels, étape 224. Si une différenciation de trame n'est pas validée ou n'a pas donnée satisfaction, un bloc de répétition est vérifié dans l'étape 204 Un bloc de répétition est un bloc dans lequel le bloc de pixels immédiatement précédent est identique au bloc de pixels qui vient juste d'être reçu pour traitement Si un tel -17- bloc de répétition est rencontré, un bloc de commande présent est contrôlé pour déterminer s'il est du type bloc de répétition, étape 205 a Dans la négative, un nouveau bloc de commande du type répétition est sorti, étape 205 b Dans l'affirmative, une zone de compte se trouvant dans le bloc de commande présent est incrémentée d'une unité, étape 205 c Dans l'un ou l'autre cas, une vérification est faite pour le dernier bloc de pixels, étape 224. Si un bloc de répétition n'est pas trouvé, une vérification est faite en ce qui concerne un bloc de double répétition, étape 206 Lors d'un contrôleeffectué pour un bloc de double répétition, le second bloc de pixels qui vient d'être immédiatement traité est comparé avec un bloc de pixels présent et le bloc de pixels immédiatement précédent est comparé avec un bloc de pixels suivant Si les deux blocs sont identiques, un bloc de commande présent est contrôlé pour déterminer s'il est du type d'un bloc de double répétition, étape 207 a Dans la négative, un nouveau bloc de commande du type double répétition est sorti, étape 207 b Dans l'affirmative, une zone de compte se trouvant dans le bloc de commande présent est incrémentée d'une unité, étape 207 c Dans l'un ou l'autre cas, une vérification est faite pour le dernier bloc de pixels, étape 224. Si aucune des conditions indiquées ci-dessus n'existe, les couleurs se trouvant dans le bloc de pixels sont comptées et mémorisées dans une liste de couleurs, étape 208 On a déterminé que s'il y a plus de 8 couleurs dans un bloc de pixels particulier, les données doivent être mémorisées dans un état non comprimé En conséquence une vérification est faite pour déterminer s'il y a plus de 8 couleurs dans le bloc de pixels, étape 209 S'il y a plus de huit couleurs, un bloc de commande présent est contrôlé pour déterminer s'il est d'un type non comprimé, - 18- étape 210 a Dans la négative, un nouveau bloc de commande de type non comprimé est sorti en même temps que des valeurs de couleurs de pixels, étape 210 b Dans l'affirmative, une zone de compte se trouvant dans le bloc de commande présent est incrémentée d'une unité et les valeurs de couleurs de pixels sont sorties, étape 210 c Une vérification est à nouveau faite en ce qui concerne le dernier bloc de pixels, étape 224. En référence maintenant à la Figure 2 b, s'il y a 8 couleurs ou moins dans la liste de couleurs, un mappage de pixels concernant les couleurs est créé, étape 211 Un mappage de pixels est utilisé pour identifier les couleurs des pixels respectifs se trouvant dans un bloc de pixels Les couleurs se trouvant dans la liste de couleurs sont alors comparées avec les couleurs se trouvant dans des blocs de pixels précédemment traités, étape 212 En premier lieu, une vérification est faite pour voir si la liste de couleurs satisfait à des critères de concordance avec le bloc de pixels immédiatement précédent, étape 213 Si la liste de couleurs satisfait aux critères de concordance, alors un codage et une compression sont réalisés en incrémentant de 1 une zone de compte du bloc de commande présent et en sortant le mappage de pixels pour le bloc de pixels, étape 215 Une vérification est ensuite faite en ce qui concerne le dernier bloc de pixels, étape 224 Si la liste de couleurs ne satisfait pas aux critères de concordance avec le bloc de pixels immédiatement précédent, alors une antémémoire de couleurs fait l'objet d'un contrôle, étape 216 L'antémémoire de couleurs comporte des entrées qui contiennent différentes combinaisons de couleurs qui ont été rencontrées dans des blocs de pixels précédents Des descriptions des contenus d'une antémémoire de couleurs et le mode de recherche dans une antémémoire de couleurs seront décrits dans la -19 - suite Si la liste de couleurs ne satisfait pas aux critères de concordance avec une entrée dans une antémémoire de couleurs, un nouveau bloc de commande sera sorti et dans ce bloc, la zone de compte sera remise à zéro, étape 217 Il est à noter qu'une zone de compte remise à zéro indique qu'elle est associée au bloc de pixels présent Les couleurs se trouvant dans la liste de couleurs sont ensuite sorties, étape 218 Ensuite, le mappage de pixels est sorti, étape 219, et les couleurs sont mémorisées par introduction dans l'antémémoire de couleurs, étape 220 Les étapes 217 et 220 correspondent à un cas o la combinaison de couleurs dans le bloc de pixels n'a pas été précédemment rencontrée. Si les couleurs se trouvant dans la liste de couleurs satisfont à des critères de concordance avec les couleurs se trouvant dans une entrée de l'antémémoire de couleurs, alors un nouveau bloc de commande sera sorti, avec activation d'un bit d'antémémoire, étape 221. L'activation du bit d'antémémoire signalera que les couleurs concernant ce bloc de pixels peuvent être trouvées dans l'antémémoire de couleurs Ensuite un index pointé sur l'entrée de l'antémémoire de couleurs qui contient la combinaison de couleurs correspondant à ce bloc de pixels est sorti, étape 222 Il est à noter que cet index d'antémémoire est composé de sensiblement moins de bits de données que le nombre nécessaire pour représenter toutes les couleurs dans le bloc de pixels. Le mappage de pixels pour le bloc de pixels correspondant est ensuite sorti, étape 223 Finalement un contrôle est effectué pour le dernier bloc de pixels, étape 224 Si ce bloc ne constitue pas le dernier bloc de pixels, un nouveau bloc de pixels est reçu dans l'étape 201 S'il constitue le dernier bloc de pixels, alors les opérations de codage/compression sont terminées. L'expression "critères de concordance" qui a été -20- utilisée dans la description faite ci-dessus se réfère à une prédétermination de critères de telle sorte qu'une liste de couleurs ou bien une entrée dans l'antémémoire de couleurs contienne des couleurs qui peuvent faire l'objet de références par des blocs de pixels suivants. De tels critères de concordance se rapportent à des cas o: 1) le nombre de couleurs dans la liste de couleurs est inférieur au nombre de couleurs de concordance dans le bloc de pixels en train d'être traité; 2) les couleurs de la liste sont identiques; et 3) il existe des cas o la liste de couleurs ou bien l'entrée dans l'antémémoire de couleurs contiennent des couleurs "'non valables" ou inutilisées Des cas de ce genre seront décrits de façon plus détaillée dans la suite. Description de blocs de commande et de séquences de blocs de commande. La Figure 3 a montre le format d'un bloc de commande et les informations contenues dans celui-ci En référence à la Figure 3 a, un bloc de commande 301 est composé d'une zone de type de bloc 302, contenant 3 bits d'information concernant le type de bloc, une zone de compte augmenté (d'indication) 303 correspondant à un bit en antémémoire, cette zone fournissant une indication précisant les données qui suivront le bloc de commande 301, notamment à un index d'antémémoire, une liste de couleurs ou bien un octet de compte augmenté Enfin le bloc de commande 301 comprend une zone de compte 304, qui indique le nombre de blocs de pixels traités associés au bloc de commande La zone de compte 304 a une largeur de 4 bits; en conséquence, le bloc de commande a au total une largeur d'un octet ( 8 bits) La Figure 3 a représente en outre une table 305 La table 305 décrit le codage dans un bloc de commande La colonne "Valeur de Zone" 306 de la table 305 décrit le codage de la zone "type de bloc" 302 La colonne "Type de Bloc" 307 décrit le type -21- de bloc Enfin la colonne "indicateur" 308 décrit comment la zone "indication" 303 est utilisée pour les types de blocs respectifs. Comme indiqué, il existe 8 types différents de blocs de commande qui peuvent être établis Dans le cas d'une coloration uniforme (c'est-à- dire 1 couleur), la zone de type de bloc aura une valeur de 011 En outre, aucun mappage de pixels n'a besoin d'être établi du fait que toutes les valeurs de pixels seront les mêmes. Egalement, seulement une couleur unique doit être fournie à la sortie Dans le cas d'une couleur unique, la zone d'indication 303 signalera que l'octet suivant le bloc de commande est un octet de compte augmenté. Dans le cas de 2 couleurs, la valeur de zone sera 100 et la zone d'indication 303 signalera si l'information de couleur concernant le bloc de pixels suivra le bloc de commande (dans une liste de couleurs), ou bien sera contenue dans une antémémoire de couleurs. Dans le dernier cas, ce qui suivra le bloc de commande est un index d'antémémoire Les cas de 4 et 8 couleurs sont semblables au cas de 2 couleurs, la différence fondamentale étant le nombre de couleurs en considération Dans le cas de 4 couleurs, la valeur de zone est 010 tandis que dans le cas de 8 couleurs, la valeur de zone est 110 Un mappage de pixels dans un cas de 2 couleurs nécessitera seulement 16 bits Cela s'explique par le fait qu'un bit unique peut être utilisé pour faire une distinction entre les 2 couleurs De façon analogue, dans le cas de 4 couleurs, 2 bits sont utilisés pour faire la distinction entre les 4 couleurs, pour un total de 32 bits dans le mappage de pixels Enfin dans le cas de 8 couleurs, 3 bits sont utilisés pour faire une distinction entre les 8 couleurs, pour un total de 48 bits dans le mappage de pixels. Dans l'organisation de la réalisation préférée, -22- une mémoire peut faire l'objet d'un adressage en mots de 16 bits Dans les cas de 2 couleurs et de 4 couleurs, les mappages de pixels correspondront directement à cette organisation, en évitant ainsi toute absence d'utilisation d'emplacements de mémoire Le cas de 8 couleurs ne fait pas intervenir directement l'organisation de mémoire Dans le cas de 8 couleurs, 3 mots sont utilisés Les 12 premiers bits de chaque mot sont utilisés pour la mémorisation des données de pixels concernant les 3 premières rangées du bloc 4 x 4 pixels. Les 4 bits restants dans chaque mot sont utilisés pour la mémorisation des données de pixels concernant la rangée restante dans le bloc de pixels. En reconsidérant les types différents de blocs de commande, lorsqu'un bloc de pixels contient plus de 8 couleurs, aucune compression ne se produit A cet égard, une zone de type de bloc ayant une valeur de 111 indiquera que le bloc de pixels n'a pas été comprimé. Dans ce cas, aucun mappage de pixels ne sera établi pour ce bloc de pixels. Finalement, le bloc de répétition (valeur de zone 001), le bloc de double répétition (valeur de zone ), et la zone du bloc de commande représentant la différence de trame (valeur de zone 000) sont représentés par leurs valeurs de codage Le bloc de répétition et le bloc de double répétition permettent d'obtenir un degré maximal de compression par le fait qu'une information de couleur ou des mappages de pixels ne sont pas établis. La Figure 3 b montre une séquence de blocs de commande dans laquelle la combinaison de couleurs dans la liste de couleurs n'a pas été précédemment rencontrée pour les cas de 2, 4 et 8 couleurs Dans un bloc de commande 310 intervient une zone d'indication 311 La zone d'indication 311 est mise à 0 Cela indique que ce qui suivra le bloc de commande 310 est une liste de -23- couleurs, correspondant ici aux couleurs 312 Le nombre de couleurs 312 dépendra du nombre de couleurs dans la liste de couleurs Comme indiqué ci-dessus, ce nombre pourrait être un nombre quelconque entre 1 et 8 Enfin, à la suite des couleurs, il intervient des mappages de pixels 313 Ces mappages de pixels 313 sont utilisés pour identifier celle des couleurs de la liste de couleurs 312 à laquelle correspond chacun des pixels intervenant dans chacun des mappages de pixels Enfin, dans les cas de 2, 4 ou 8 couleurs, la zone de compte pour le bloc de commande 310 est limitée à 4 bits; dans cette condition, un maximum de 16 mappages de pixels peut intervenir à la suite. Bien que cela ne soit pas représenté, pour les types de blocs de commande (c'est-à-dire la différence de trame, la couleur uniforme, la répétition de trame et la double répétition de trame) qui permettent à des octets de compte augmenté de suivre le bloc de commande, il est possible que les blocs ce commande puissent faire référence à 4098 blocs de pixels. Codage pour 3, 5, 6, 7 couleurs. ________________________________ Il est maintenant utile de décrire le codage qui se produit lorsqu'il intervient un nombre impair de couleurs: notamment le cas de 3 couleurs, le cas de 5 couleurs et le cas de 6 couleurs et le cas de 7 couleurs. Dans le cas o le nombre impair de couleurs est inférieur au nombre de couleurs intervenant dans une liste de couleurs ou dans une entrée en antémémoire de couleurs, une référence peut être établie du fait que le mappage de pixels imposera l'utilisation d'une couleur En outre, dans le cas o la liste de couleurs, ou bien l'entrée en antémémoire, est codée avec moins de couleurs que le bloc de pixels en train d'être traité, les données concernant les couleurs précédentes pourront encore être utilisées. Du fait que le traitement est le même pour -24- chacun des cas, le cas de 3 couleurs sera utilisé à titre d'exemple Dans le cas de 3 couleurs, un bloc de commande de 4 couleurs est utilisé (dans les autres cas, un bloc de commande de 8 couleurs est utilisé) Dans ce cas, seulement 3 couleurs dans la liste de couleurs 312 sont valables (c'est- à-dire utilisés) Une quatrième couleur non valable (c'est-à-dire non utilisée) est également incluse, à titre de cohérence, dans le processus de compression/décompression Il est à noter que le mappage de pixels établi ne se rapporterait pas à cette quatrième couleur non valable Cependant, si un bloc de pixels de 4 couleurs intervient à la suite de ces 3 couleurs, avec une quatrième couleur différente, les données de couleurs de la liste de couleur pourront être modifiées afin d'indiquer l'existence de la quatrième couleur Si le bloc de pixels est en train d'être ajouté au bloc de commande existant, la nouvelle couleur peut simplement remplacer la quatrième couleur non utilisée dans la liste de couleurs Cela peut se produire lorsque les blocs de pixels sont adjacents Dans un cas o les 3 couleurs ont été introduites dans une antémémoire de couleurs, la quatrième couleur sera simplement ajoutée dans l'antémémoire de couleurs A nouveau, cela est possible du fait que le mappage de pixels dans le cas de 3 couleurs -ne fait pas référence à la quatrième (nouvelle) couleur. La Figure 3 c représente une séquence de blocs de commande o la liste de couleurs a été précédemment rencontrée et a été mémorisée dans l'antémémoire de couleurs En premier lieu, le bloc de commande 320 comporte une zone d'indication 321 qui a été activée, c'est-à-dire mise à une valeur 1 Cela indique qu'il interviendra à la suite du bloc de commande 320 un index en antémémoire 322 L'index en antémémoire 322 indique un emplacement ou une entrée dans une antémémoire o la -25combinaison de couleurs peut être trouvée La Figure 3 d représente une telle antémémoire de couleurs pour le cas de 4 couleurs Une antémémoire de couleurs séparée interviendra pour les cas de 2, 4 ou 8 couleurs D'une manière analogue pour toutes les antémémoires de couleurs, l'antémémoire 324 correspondant à 4 couleurs contient 256 entrées Cela correspond à la longueur d'un index d'antémémoire de 1 octet Dans le cas de 4 couleurs, 3 ou 4 couleurs sont mémorisées dans chaque entrée d'antémémoire L'antémémoire contient en outre une zone de masquage de pixels 325 Comme cela sera décrit de façon plus détaillée dans la suite, la zone de masquage de pixels 325 permet d'obtenir une amélioration des performances lors d'une recherche dans l'antémémoire En conséquence, un index d'antémémoire de 4 couleurs comportera des entrées ayant une largeur de 64 bits, chaque couleur comprenant 8 bits et des zones de masquage de 32 bits L'index d'antémémoire 322 de la Figure 3 c correspond à une des entrées dans l'antémémoire de couleurs Comme indiqué ci-dessus, la zone de compte est de 4 bits En conséquence, seulement 16 mappages de pixels 323 suivront l'index d'antémémoire 322. En référence maintenant à la Figure 3 e, celle-ci représente la séquence de blocs de commande o aucune compression ne se produit En premier lieu, la zone de type de bloc a la valeur 111 A la suite du bloc de commande interviennent des valeurs de pixels en couleurs 323 Ces valeurs correspondent aux 16 couleurs prévues pour chacun des 16 pixels intervenant dans le bloc de pixels Les couleurs interviennent dans l'ordre o elle apparaissent dans le bloc de pixels. Exemple de compression. Les Figures 4 a et 4 b montrent comment se produisent une compression et un codage dans le cas de 4 couleurs En référence à la Figure 4 a, des blocs de -26- pixels 401 et 402 sont représentés Le bloc de commande 410 est le bloc de commande qui serait codé pour les blocs de pixels 401 et 402 En premier lieu, la zone de type 403 pour le bloc de commande a une valeur 101 Cela peut être vérifié en se référant à la Figure 3 a et en observant que la valeur de zone 101 se rapporte au cas de 4 couleurs Il est à noter que, puisque cela correspond au premier exemple de cette combinaison de couleurs, la zone d'indication 411 est mise à O (c'est-à-dire n'est pas activée) Finalement, la zone de compte 412 est mise à 0001 afin d'indiquer qu'il existe deux blocs de pixels. En outre, les couleurs 404-407 sont indiquées Chacune des couleurs 404407 représente les couleurs qui ont été trouvées dans chacun des blocs de pixels 401 et 402 Les couleurs intervenant dans la séquence 404-407 sont présentées dans l'ordre o elles sont rencontrées lors de l'analyse du bloc de pixels de la gauche vers la droite et du haut vers le bas En outre, chacune des couleurs 404-407 a une valeur qui lui a été affectée en vue d'une utilisation par les mappages de pixels respectifs 408 et 409 afin d'identifier une valeur de nuance particulière pour un pixel correspondant. Dans cet exemple, si une mémorisation a été faite sous la forme de données non comprimées, 8 x 32, ou 256 bits de données seront nécessaires pour définir les valeurs de nuancement pour chacun des pixels intervenant dans les 2 blocs de pixels En utilisant le procédé de compression correspondant à la réalisation préférée, seulement 104 bits sont nécessaires pour les 2 blocs de pixels Il en résulte un rapport de compression de 2,5/1. Il est à noter que, quand le nombre de mappages de pixels augmente, le rapport de compression augmentera en correspondance. La Figure 4 b représente une séquence de blocs de commande correspondant aux blocs de pixels 401 et 402 de -27- la Figure 4 a, excepté que la combinaison de couleurs a été trouvée dans une antémémoire A cet égard, le bloc de commande 413 différera seulement par le fait que la zone d'indication 415 est activée Elle indiquera qu'il intervient à la suite du bloc de commande 413 un index en antémémoire 414 Comme indiqué ci- dessus, l'index en antémémoire est un index d'un octet intervenant dans une antémémoire de 4 couleurs A la suite de l'index en antémémoire, il intervient des mappages de pixels 408 et 409. Dans cet exemple, seulement 80 bits sont nécessaires pour représenter les blocs de pixels 401 et 402 Il en résulte qu'on a un rapport de compression supérieur à 4: 1. Recherche en antémémoire de couleurs. Une recherche dans une antémémoire de couleurs créée dynamiquement pour des combinaisons particulières de couleurs constitue un processus intensif Du fait qu'il existe 256 couleurs possibles pour une valeur de pixel de 8 bits, une comparaison directe des couleurs intervenant dans une liste de couleurs et des couleurs intervenant dans les entrées d'antémémoire peut être une opération assez longue Dans le cas de 2 couleurs, on a déterminé qu'une comparaison directe de couleurs est la plus efficace Dans les cas de 4 et 8 couleurs, l'opération de recherche en antémémoire a été grandement améliorée en utilisant des masques de couleurs, notamment un masque de bloc de pixels et un masque d'entrée en antémémoire Le masque de bloc de pixels identifie des gammes de couleurs dans lesquelles sont situés les pixels intervenant dans le mappage D'une façon analogue, le masque d'entrée en antémémoire identifie les gammes de couleurs dans lesquelles sont situées les couleurs intervenant dans l'entrée d'antémémoire Par une comparaison des deux masques, on réduit fortement le -28- nombre d'entrées en antémémoire qui seront examinées pour trouver des concordances. Dans la réalisation présentement préférée, les 256 couleurs possibles sont divisées en 32 gammes de 8 couleurs Chacune des 32 gammes de couleurs correspond directement à un seul bit d'un masque de couleur de 32 bits Ainsi une couleur particulière produira une activation du bit du masque correspondant à la gamme de couleurs dans laquelle est située la couleur particulière Cela correspond à la manière dont le masque de bloc de pixels est créé Inversement, le masque d'entrée en antémémoire est le résultat d'une inversion des valeurs du masque, après que les gammes de couleurs et les bits correspondants dans le masque ont été activés Cela s'explique par le fait qu'il faut identifier rapidement un nombre minimal de couleurs dans la liste de couleurs du bloc de pixels, ces couleurs n'étant pas situées dans l'entrée en antémémoire Cela facilite une identification rapide des entrées en antémémoire pour lesquelles il n'y a pas concordance. L'identification est illustrée par l'exemple suivant En utilisant à titre de simplification et d'illustration un masque hypothétique de 4 bits, on va supposer que le masque de bloc de pixels a une valeur de 1100 et que le masque d'entrée en antémémoire a une valeur de 1010 (sans inversion, cela correspondra à une valeur de 0101) Après une inspection visuelle rapide du masque de bloc de pixels et du masque d'entrée en antémémoire non inversé, on observe qu'il existe une bonne concordance de couleurs dans la position du second bit (lors d'une observation faite de la gauche vers la droite) En outre, on peut voir qu'il n'y a pas de concordance pour une des couleurs du bloc de pixels correspondant à la valeur 1 dans la première position de bit du masque de pixels et à une valeur O dans la -29- dans la première position de bits du masque d'entrée en antémémoire En conséquence, il existe, dans la liste de couleurs du bloc de pixels, au moins une couleur ne se trouvant pas dans l'entrée en antémémoire. Le fait qu'une couleur ne se trouve pas dans l'entrée en antémémoire est rapidement déterminé en effectuant une opération logique ET entre le masque d'entrée en antémémoire et le masque de bloc de pixels. Dans ce cas, l'opération logique ET effectuée pour les deux masques (c'est-à-dire 1100 ET 1010) donne comme résultat la valeur 1000 Par comptage du nombre de bits activés, c'est-à-dire ayant la valeur 1, dans le résultat, on détermine rapidement un nombre minimal de couleurs ne se trouvant pas dans l'entrée en antémémoire. Dans le cas considéré, cette valeur est 1. Le masque de bloc de pixels est créé lorsqu'une antémémoire de couleurs doit faire l'objet d'une recherche Comme décrit ci- dessus, le masque d'entrée d'antémémoire est mémorisé comme une partie de l'entrée en antémémoire de couleurs et il est créé lorsque la donnée de couleur est introduite dans l'antémémoire. Une fois qu'une entrée dans l'antémémoire de couleurs a été identifiée comme établissant une bonne concordance, les couleurs se trouvant dans l'entrée sont directement comparées avec les couleurs se trouvant dans la liste de couleurs du bloc de pixels. La Figure Sa est un organigramme qui illustre de façon détaillée l'échelonnement des recherches en antémémoire dans les cas de 4 et 8 couleurs, comme cela est effectué dans la réalisation présentement préférée. En premier lieu, un masque de bloc de pixels est établi pour le bloc de pixels en train d'être traité, étape 501. Le masque de bloc de pixels est établi en utilisant le processus décrit ci-dessus Ensuite, l'antémémoire de couleurs appropriée devant faire l'objet d'une recherche -30- est sélectionnée, étape 502 L'antémémoire de couleurs appropriée correspondra au nombre de couleurs se trouvant dans la liste de couleurs du bloc de pixels Pour l'antémémoire de 4 couleurs, il interviendra 3 ou 4 couleurs dans la liste de couleurs Pour l'antémémoire de 8 couleurs, il interviendra de 5 à 8 couleurs dans la liste de couleurs Une fois que l'antémémoire appropriée a été sélectionnée, le processus de discrimination des entrées en antémémoire est effectué En premier lieu, une entrée en antémémoire de couleurs est extraite et le masque d'entrée d'antémémoire est comparé avec le masque de bloc de pixels, étape 503. On détermine ensuite si le résultat de la concordance de masques est supérieur à un seuil de concordance prédéterminé, étape 504 Pour le cas de 4 couleurs, un seuil de concordance de masques est celui o on obtient au moins 3 concordances de gammes de couleurs. Pour le cas de 8 couleurs, le seuil de concordance de masques est celui o on obtient 5 concordances de gammes de couleurs Comme cela sera expliqué dans la suite, ce seuil correspond au fait qu'il peut exister dans l'antémémoire de couleurs des entrées qui utilisent moins de couleurs que le maximum possible (par exemple seulement 5 couleurs dans une antémémoire de 8 couleurs). De toute manière, si le seuil de concordance de masques n'est pas satisfait, une vérification de la dernière entrée en antémémoire de couleurs sera effectuée, étape 510 (décrite dans la suite). Si le seuil de concordance de masques est satisfait, les couleurs se trouvant dans l'entrée en antémémoire de couleurs seront comparées aux couleurs se trouvant dans la liste de couleurs du bloc de pixels, étape 505 Un contrôle pour déterminer si un seuil de concordance de couleurs est atteint sera effectué dans l'étape 506 Le seuil de concordance de couleurs est -31- identique, en ce qui concerne sa fonction et sa réalisation, au seuil de concordance de masques, excepté que des couleurs exactes, à la place de gammes de couleurs, sont comparées Le seuil de concordance de couleurs pour le cas de 4 couleurs est celui o on doit obtenir 3 concordances identiques Pour le cas de 8 couleurs, le seuil de concordance de couleurs est celui o on doit obtenir 5 concordances de couleurs identiques. Si le seuil de concordance de couleurs n'est pas satisfait, le traitement concernant l'entrée en antémémoire est terminé et un contrôle de l'entrée finale en antémémoire est effectué dans l'étape 510 Si l'entrée en antémémoire examinée ne constitue pas la dernière entrée, une nouvelle entrée en antémémoire est extraite, étape 511, et le processus de traitement retourne à l'étape 504. Si le seuil de concordance de couleurs est satisfait, une concordance en antémémoire a été trouvée. Cependant, un autre traitement est nécessaire pour déterminer s'il existe dans l'entrée d'antémémoire des entrées non utilisées qui sont vides et qui peuvent être utilisées par la liste de couleurs du bloc de pixels En correspondance, une vérification est faite pour déterminer si le nombre de couleurs se trouvant dans l'entrée d'antémémoire de couleurs est inférieur au nombre de couleurs se trouvant dans la liste de couleurs du bloc de pixels, étape 507 Dans la négative, l'index d'entrée en antémémoire est renvoyé pour être sortie dans le train de données comprimées, étape 508 Dans l'affirmative, il est connu qu'il existe des couleurs non utilisées dans la liste de couleurs du bloc de pixels. Dans ce cas, des couleurs supplémentaires sont ajoutées dans l'entrée d'antémémoire de couleurs, étape 508 Cela provoque également la création d'un nouveau masque d'entrée en antémémoire qui est établi et mémorisé Une -32- fois que ce processus est terminé, l'index d'entrée en antémémoireest renvoyé pour sortir dans le train de données comprimées, étape 508. Dans la réalisation présentement préférée, on utilise une structure d'antémémoire qui est circulaire. En conséquence, lorsque l Tantémémoire est remplie, c'est- à-dire lorsqu'elle contient 256 entrées, la demande suivante d'insertion en antémémoire provoquera une surécriture de la première entrée Des demandes suivantes d'introduction en antémémoire feront en sorte que les entrées suivantes de l'antémémoire soient soumises à une surécriture En outre, du fait qu'un masque d'entrée en antémémoire est seulement utilisé pendant une compression, il n'est pas nécessaire pendant une décompression du train de données comprimées En conséquence, pendant la génération d'une antémémoire de couleurs au cours d'une décompression, le masque d'entrée en antémémoire n'est pas engendré. Décompression. La Figure 6 met en évidence un procédé de décompression ou de décodage d'un train de données qui ont été comprimées/codées en utilisant le procédé correspondant à la réalisation préférée En premier lieu, un bloc de commande est reçu, étape 601 La zone de type de bloc du bloc de commande est examinée Si la zone de type de bloc contient la valeur 011, elle correspond à un bloc du type à couleurs uniforme Dans ce cas, la même valeur de pixel de couleur est sortie, étape 602 Cela se produit pour 16, c'est-à-dire le nombre de pixels se trouvant dans le bloc de pixels, multiplié par la valeur de la zone de compte du bloc de commande Il est à noter que, pour chacun des blocs de pixels, les valeurs de pixels correspondront à 4 pixels par ligne de balayage ou d'analyse. Si la zone de type de bloc contient la valeur -33- , 101, 110, on a alors affaire à un type dans lequel des couleurs sont comprimées, en utilisant efficacement une antémémoire de couleurs Dans chaque cas, le moyen de décompression effectuera une reconnaissance du type de bloc et une reconnaissance du nombre de couleurs en train d'être traitées et également de l'antémémoire appropriée devant faire l'objet d'accès En premier lieu, une vérification est faite pour déterminer si le bit d'antémémoire est activé, étape 603 Si le bit d'antémémoire est activé, alors les couleurs seront extraites de l'antémémoire de couleurs en utilisant l'index d'antémémoire qui suit le bloc de commande dans le train de données comprimées, étape 604 Les couleurs provenant de l'antémémoire sont ensuite mémorisées et sorties en concordance avec le ou les mappages de pixels qui sont associés au bloc de commande, étape 605 En variante, si le bit d'antémémoire n'est pas activé, il est connu que cela correspond à une nouvelle combinaison de couleurs Dans le cas considéré, il est connu que la liste de couleurs suivra le bloc de commande dans le train de données comprimées Les couleurs sont ensuite sorties dans une séquence en concordance avec le ou les mappages de pixels associés au bloc de commande, étape 606 Ensuite, les couleurs provenant de la liste de couleurs sont introduites dans l'antémémoire de couleurs, étape 607 Il est à noter que l'index concernant l'antémémoire de couleurs sera placé en correspondance correcte du fait que les données sont en train d'être décodées dans le même ordre qu'elles ont été codées Cela s'explique par le fait que les antémémoires de couleurs sont créées dynamiquement à la fois pendant une compression et une décompression et que le train de données comprimées est traité dans le même ordre que les données de pixels d'origine. Si la zone de type de bloc contient la valeur -34- 111, il n'y a pas de compression, étape 608 Dans ce cas, les valeurs de pixels sont sorties comme elles se produisent dans la liste de couleurs suivant le bloc de commande, en correspondance au nombre de blocs de pixels qui est spécifié dans la zone de compte du bloc de commande. Si la zone de type de bloc contient les valeurs 001 ou 010, alors le bloc de pixels précédent ou bien les deux blocs de pixels précédents sont respectivement dupliqués et sortis en correspondance au nombre de blocs de pixels spécifié dans la zone de compte du bloc de commande Finalement, si la valeur de type de bloc est 000, le nombre de blocs spécifié dans la zone de compte du bloc de commande sera sauté du fait qu'une différenciation de trame est validée. En conséquence, cela termine la description d'un procédé et d'un appareil pour une compression et une décompression sans pertes de données d'images vidéo. * -* * -35- REVENDICATIONS 1 Procédé de compression d'un bloc de données d'images couleurs pour créer un train de données comprimées, ledit train de données comprimées étant composé de blocs de commande codés dans lesquels sont réparties des données de valeurs de couleurs, ledit bloc de commande comprenant une zone de compte, une zone d'indication et une zone de type, ledit procédé comprenant les étapes consistant à: a) obtenir un bloc de pixels à partir dudit bloc de données d'images couleurs; b) établir une liste de couleurs c) établir un mappage de pixels pour les couleurs des pixels se trouvant dans ledit bloc de pixels; d) comparer ladite liste de couleurs avec une ou plusieurs listes de couleurs correspondant à des blocs de pixels précédemment traités; e) déterminer si ladite liste de couleurs concorde avec une liste de couleurs d'un bloc de pixels précédemment traité f) si ladite liste de couleurs concorde avec une liste de couleurs d'un bloc de pixels précédemment traité, coder ledit bloc de pixels en créant une référence pour ladite liste de couleurs dudit bloc de pixels précédemment traité et faire sortir ledit mappage de pixels; g) si ladite liste de couleurs ne concorde pas avec une liste de couleurs d'un bloc de pixels précédemment traité, coder ledit bloc de pixels en amenant une zone de type de bloc de commande sur une valeur correspondant au nombre de couleurs se trouvant dans ladite liste de couleurs, faire sortir ledit bloc de commande, ladite liste de couleurs et ledit mappage de pixels et introduire ladite liste de couleurs dans une antémémoire de couleurs. -36- 2 Procédé selon la revendication 1, caractérisé en ce que ladite étape pour déterminer si ladite liste de couleurs concorde avec une liste de couleurs d'un bloc de pixels précédemment traité est en outre composée des étapes consistant à: a) comparer ladite liste de couleurs avec une liste de couleurs associée avec un présent bloc de commande pour déterminer une concordance; et b) comparer ladite liste de couleurs avec des combinaisons de couleurs dans une antémémoire de couleurs afin de déterminer une concordance, ladite liste de couleurs correspondant au nombre de couleurs dans ladite liste de couleurs. 3 Procédé selon la revendication 2, caractérisé en ce que ladite étape de codage dudit bloc auxiliaire de données de pixels par création d'une référence avec ladite liste de couleurs dudit bloc de pixels précédemment traité et de sortie dudit mappage de pixels est en outre composée des étapes consistant à: a) si ladite liste de couleurs concorde avec une liste de couleurs associée audit présent bloc de commande, référencer ladite liste de couleurs par incrémentation d'une zone de compte dudit présent bloc de commande; b) si ladite liste de couleurs concorde avec une entrée dans ladite antémémoire de couleurs, référencer ladite liste de couleurs par activation d'une zone d'indication située dans un bloc de commande et indiquant que ladite liste de couleurs se trouve dans une antémémoire de couleurs, activer une zone de type dans ledit bloc de commande en correspondance au nombre de couleurs se trouvant dans ladite liste de couleurs, sortir ledit bloc de commande et un index sur ladite entrée dans ladite liste de couleurs. 4 Procédé selon la revendication 3, caractérisé -37- en ce que ladite étape de génération d'une liste de couleurs est en outre composée des étapes consistant à: a) identifier une couleur de pixel comme n'ayant pas été précédemment rencontrée; b) ajouter ladite couleur de pixel à ladite liste de couleurs; c) incrémenter un compte de couleur d) mémoriser ladite couleur dans ladite liste de couleurs; et e) répéter les étapes a)-d) pour tous les pixels se trouvant dans lesdits blocs de pixels. Procédé selon la revendication 2, caractérisé en ce que ladite étape de comparaison de ladite liste de couleurs avec des listes de couleurs se trouvant dans une antémémoire de couleurs afin de déterminer une concordance est en outre composée des étapes consistant à: a) établir un masque d'entrée en antémémoire pour chaque entrée dans ladite antémémoire de couleurs, ledit masque d'entrée d'antémémoire identifiant des gammes de couleurs dans ladite entrée d'antémémoire; b) établir un masque de bloc de pixels, ledit masque de bloc de pixels identifiant des gammes de couleurs dans ledit bloc de pixels; c) comparer ledit masque d'entrée d'antémémoire avec ledit masque de bloc de pixels pour un seuil de concordance prédéterminé; d) si ledit seuil de concordance prédéterminé n'est pas satisfait, répéter l'étape c) pour une entrée suivante en antémémoire; e) si ledit seuil de concordance prédéterminé est satisfait, comparer les couleurs individuelles de ladite liste de couleurs et de ladite entrée d'antémémoire; f) si un seuil de concordance exact et prédéterminé n'est pas satisfait, répéter l'étape c) pour 38- une entrée suivante dans l'antémémoire g) si ledit seuil de concordance exact et prédéterminé est satisfait, identifier ladite entrée d'antémémoire comme une concordance; et h) répéter les étapes c)-g) jusqu'à ce qu'une concordance soit trouvée ou bien jusqu'à ce que toutes les entrées d'antémémoire aient été traitées. 6 Procédé de décompression d'un train de données comprimées, en utilisant le procédé selon la revendication 1, ledit procédé de décompression comprenant les étapes consistant à: a) identifier la référence à une liste de couleurs en concordance avec ledit bloc de commande b) recevoir un mappage de pixels; c) sortir des couleurs en concordance avec ladite liste de couleurs et ledit mappage de pixels d) répéter les processus jusqu'à ce que tous les blocs de commande et tous les mappages de pixels aient été traités. 7 Appareil pour une compression de données d'images couleurs, caractérisé en ce qu'il comprend: a) un moyen d'extraction servant à extraire un bloc de pixels desdites données d'images couleurs; b) un moyen de génération de liste de couleurs pour un comptage des différentes couleurs dans ledit bloc de pixels et pour établir une liste de couleurs, ledit moyen de génération de liste de couleurs étant relié audit moyen d'extraction; c) un moyen de génération de mappage de pixels, ledit moyen de génération de mappage de pixels servant à engendrer un mappage de pixels en identifiant des valeurs de couleurs dans chaque emplacement de pixel dudit bloc de pixels, ledit moyen de génération de mappage de pixels étant relié audit moyen d'extration; d) une antémémoire de couleurs pour mémoriser -39plusieurs combinaisons de couleurs, chacune desdites combinaisons de couleurs étant mémorisée comme une entrée dans ladite antémémoire de couleurs; e) un moyen de comparaison relié audit moyen de génération de liste de couleurs, audit moyen d'extraction de pixels et à ladite antémémoire de couleurs, ledit moyen de comparaison servant à comparer une liste de couleurs avec une liste de couleurs précédente et avec une ou plusieurs entrées en antémémoire et servant à sortir des données comprimées si une concordance est trouvée et à sortir des données non comprimées si le nombre de couleurs dans ladite liste de couleurs est supérieur à un seuil prédéterminé. 8 Appareil de compression selon la revendication 7, caractérisé en ce que ledit moyen de comparaison comprend en outre: a) un moyen pour introduire une combinaison de couleurs dans ladite antémémoire de couleurs sous la forme d'une entrée; b) un moyen pour effectuer une recherche dans ladite antémémoire de couleurs; c) un moyen pour sortir un index d'antémémoire et un mappage de pixels si ladite liste de couleurs concorde avec une entrée dans ladite antémémoire; et d) un moyen pour sortir un mappage de pixels si ladite liste de couleurs concorde avec une liste de couleurs précédente. 9 Appareil de compression selon la revendication 8, caractérisé en ce que ledit moyen de comparaison comprend en outre un moyen pour comparer un présent bloc de pixels avec un bloc de pixels précédent et, S'ils sont identiques, pour sortir des données comprimées indiquant que le bloc de pixels précédent devrait être dupliqué. 10 Appareil de compression selon la -40 - revendication 9, caractérisé en ce que chacune desdites entrées se trouvant dans ladite antémémoire de couleurs comporte un masque d'entrée d'antémémoire, ledit masque d'entrée d'antémémoire servant à identifier des couleurs dans ladite entrée d'antémémoire. 11 Procédé de compression de données d'images, caractérisé en ce qu'il comprend les étapes consistant à: a) extraire un bloc de pixels d'un bloc de données d'images; b) établir une liste de couleurs et un compte de bloc de pixels; c) comprimer ledit bloc de pixels si ledit compte de bloc de pixels est inférieur à un premier nombre prédéterminé de valeurs de nuances de pixels en sortant des références de valeurs de nuances de pixels ainsi qu'un mappage de pixels identifiant la valeur de nuances de pixel pour chaque pixel se trouvant dans ledit bloc de pixels; et d) mémoriser ledit bloc de pixels comme n'étant pas comprimé si ledit compte de bloc de pixels est supérieur audit premier nombre prédéterminé de valeurs de nuances de pixels. 12 Procédé selon la revendication 11, caractérisé en ce que ladite étape de compression dudit bloc de pixels, si ledit compte de bloc de pixels est inférieur à un premier nombre prédéterminé de valeurs de pixels par sortie d'une référence de valeurs de nuances de pixels et d'un mappage de pixels identifiant la valeur de nuances de pixels pour chaque pixel se trouvant dans ledit bloc de pixels, est en outre composée des étapes consistant à: a) comparer ladite liste de couleurs avec des listes de couleurs de blocs de pixels précédemment traités; b) si ladite liste de couleurs concorde avec une -41- liste de couleurs précédente, établir un mappage de pixels en référence avec ladite liste de couleurs précédente; et c) si ladite liste de couleurs ne concorde pas avec une liste de couleurs précédente, établir un mappage de pixels en référence avec ladite liste de couleurs. 13 Procédé selon la revendication 12, caractérisé en ce que ladite étape de comparaison de ladite liste de couleurs avec une liste de couleurs de blocs de pixels précédemment traités comprend en outre l'étape consistant à comparer ladite liste de couleurs avec une ou plusieurs entrées dans une antémémoire de couleurs. 14 Procédé selon la revendication 13, caractérisé en ce que ladite référence de nuancement de valeurs de pixels constitue un index sur une entrée d'antémémoire contenant ladite liste de couleurs précédente. Procédé selon la revendication 14, caractérisé en ce que ledit nombre prédéterminé de valeurs de nuances de pixels est égal à 8.