Brevet FR2619269A1 — publié le 19890210

La présente invention concerne un procédé de codage numérique d'une base de données. Lorsqu'on a à coder, en numérique, une quantité finie de données d'une base, le procédé le plus simple et le plus évident consiste à affecter à ces données, comme codes, respectivement les bits représentatifs des nombres binaires correspondant aux nombres de la suite continue des premiers nombres décimaux entiers, en quantité égale à celle des données de la base. Un tel codage, tout d'abord,peut requérir des séparateurs entre les données codées, faute de quoi des ambiguités pourraient surgir au cours de leur lecture ultérieure. En outre, une telle affectation de codes, qui ne tient pas compte des spécificités respectives des données, peut, dans certains cas, engendrer une quantité impressionnante de bits, sans parler de ceux des séparateurs. Il en est ainsi lorsque les données à coder sont des couleurs d'une table exploitée dans un système d'imagerie, par exemple cartographique, notamment géographique, géologique, médicale. La présente invention veut donc proposer un procédé de codage numérique de données d'une base, sans séparateurs entre elles, et comprimées au mieux, la compression visant à réduire le nombre de bits. On connaît le codage de Huffman, par le document "Digital Image Processing", de Rafael et al.- Addison-Wesley, 1977. Le codage de Huffman tient déjà compte d'une certaine spéci- ficité des données, à savoir leur fréquence d'apparition. Ainsi, la donnée apparaissant avec la plus grande fréquence est affectée du code constitué d'un bitpar exemple, de valeur 0. 26 1 9269 La donnée apparaissant avec la fréquence immédiatement inférieure est affectée du code constitué du même bit de valeur O et d'un deuxième bit, de poids immédiatement supérieur, de valeur 1, et ainsi de suite. Ainsi, la donnée apparaissant avec la fréquence de rang i est affectée du code constitué de (i-l) bits de valeur 1 et d'un dernier bit, de poids le plus faible, de valeur O. Bien que le codage de Huffman n'engendre pas d'ambiguités à la lecture des données, la compression n'est pas parfaite et, de surcroît, c'est un codage assez dégradant. On connait aussi le codage RLC (run length coding), selon lequel chaque donnée est codée avec certains bits, de valeur O ou 1, suivi par exemple d'un bit de doublement x, de poids le plus faible, x étant égal à 1 si 'la donnée est répétée deux fois de suite, ou doublée, à O si elle est suivie d'une autre donnée. Pas plus ce dernier codage que la combinaison de celui-ci avec le codage de Huffman ne conduisent à une compression appropriée. La présente invention vise donc à proposer un codage mieux comprimé que ceux connus jusqu'ici. A cet effet, la présente invention concerne un procédé de codage numérique de données d'une base, sans séparateur entre elles, dans lequel, après avoir déterminé les fréquen- ces d'apparition des données, on leur affecte des codes comportant respectivement des nombres de bits augmentant avec la diminution des fréquences d'apparition, caractérisé par le fait qu'on affecte à au moins certaines des données les plus fréquentes des codes comportant au moins un bit de répétition et qu'on adapte les codes à la statistique d'ap- parition des données. Avantageusement, on affecte le bit de répétition en tant que bit de poids le plus faible. Avantageusement encore, on affecte à la donnée la plus fréquente l'unique bit de valeur 0. Dans la mise en oeuvre préférée du procédé de l'invention, on répartit les données en groupes de données de fréquences d'apparition sensiblement voisines auxquelles on affecte des codes d'un même nombre de bits. Dans ce cas, les codes d'au moins certains des groupes de fréquence déterminée peuvent comporter autant de bits, de plus que ceux de groupes de fréquence supérieure, qu'en comporte le nombre binaire correspondant au nombre,décimal, de données des groupes considérées. Dans ce même cas toujours, les codes d'au moins certains des groupes peuvent comporter une série de bits identiques précédant une série de bits en quantité égale à celle desbits qu, comporte le nombre binaire correspondant au nombre, décimal, de données des groupes. Alors, la série de bits identiques des codes d'au moins certains des groupes peut comporter autant de bits, de plus que la série identique de bits de codes de groupes de fréquence supérieure, qu'en comporte le nombre binaire correspondant au nombre, décimal, de données des groupes considérés. L'invention sera mieux comprise à l'aide de la description suivante d'une mise en oeuvre préférée du procédé de codage de l'invention, à savoir le codage des couleurs d'une table associées à des pixels, c'est-à-dire des éléments d'image (picture elements), d'un ensemble de cartes géographiques à enregistrer sur un support d'archivage, tel qu'un disque optique numérique. L'exemple considéré est donc emprunté au domaine de l'imagerie cartographique. Soit, en l'espèce, une table de douze couleurs à coder. On détermine, pour chaque couleur C, le nombre N de pixels à enregistrer de cette couleur; N est représentatif de la fréquence d'apparition de la couleur C. Aux fréquences d'apparition décroissantes N1, N2,... Nll, N12 correspondent les couleurs C1, C2,... Cll, C12, C1 étant la couleur la plus fréquente, C2 la couleur de fré- quence immédiatement inférieure, et ainsi de suite. Dans l'exemple considéré, la proportion de pixels de couleur C1 est de 45 5 environ; la proportion de pixels de couleur C2 est de 20 ï0 environ; les pixels de couleurs C3, C4 ou C5 ont respectivement des fréquences d'apparition sensiblement voisines, la proportion de pixels de couleurs C3, C4, C5 étant globalement de 25 5 environ; les pixels de couleurs. C6-C ont aussi respectivement des fréquences d'apparition 6 9 sensiblement voisines, la proportion de pixels de couleurs C6, C7, C, C9 étant globalement de 10 X'v environ; les pixels de couleurs C 1O-C12 n'apparaissent que très rarement. Ainsi, les codes des couleurs Cl-Cl2 peuvent être répartis en premiers groupes de codes avec le même nombre de bits, en l'espèce six (G1, G2, G3, G4, G5, G6), le code de la couleur C6 étant sorti du groupe G des codes des couleurs 6 5 C7, C8, Cg, pour une raison qui sera expliquée plus loin, pour former à lui seul le groupe G4. Le code de la couleur C1, la plus fréquente, forme le groupe G1, celui de la couleur C2, le groupe G2, ceux des couleurs C3, C4, C5, le groupe G3, celui de la couleur C6 donc le groupe G4, ceux des couleurs C7, C8, C9, le groupe G5, et ceux des couleurs CO, Cl, Cl2 le dernier groupe G6. Le tableau ci-dessous donne les codes adoptés: G1 C1 G2 C2 1 0 x C 1 1 ' 0 x G3 C4 1 1 0 1 x Ol' Oi0x !G4 C6 1 0 0 1 0 1 x I.- - c7 01 10x I G C8 1 i 1 1 0 1 x C9 1 1 1 1;1 0 x i C lo 1 1 1 1 0 0 G6 Cll 1 11 1 i 1 1 C12 1 1 1 1 1 1 0 La couleur C est affectée du code 0. Le code 1 aurait pu aussi être adopté. La couleur C2 est affectée du code, ici, à 3 bits 10 x. En cas, ici, de doublement de la couleur C2, elle sera codée 101. Si elle précède une autre couleur, elle sera codée 100. L'en- registrement de deux pixels adjacents de cette couleur C2 ne requiert donc que 3 bits, alors que, selon le codage de Huffman, il aurait fallu 4 bits (deux fois 10). Selon le codage de Huffman, deux couleurs ne sont codées que sur trois bits que-s'il s'agit des couleurs C1, C2. Comme la probabilité, que deux pixels adjacents soient de même couleur, est ici supérieure à 0,5, on conçoit donc que le codage de l'invention, statistiquement parlant, et, au niveau de ces deux couleurs, soit déjà plus performant. Les couleurs C3, C4, C5, du groupe G3, sont codées sur cinq bits, avec un bit de doublement x de poids le plus faible. Les codes de ce groupe comportent deux bits de plus que le code lOx de C2, puisque ce groupe comporte trois codes, et que 3 dans le système binaire s'écrit avec deux bits. En outre, les trois codes comportent une série de deux bits identiques 11 précédant une série de deux autres bits et le bit de doublement. Les couleurs C7, C8, C9 du groupe G5 sont codées sur sept bits, avec un bit de doublement x de poids le plus faible. Les codes de ce groupe comportent deux bits de plus que les codes du groupe G3, puisque ce groupe comporte trois codes. Si le code de la couleur C2 avait été intégré à ce groupe, il aurait fallu coder les couleurs sur un bit supplémentai- re, 4 en binaire s'écrivant avec les trois bits 100. Les codes du groupe G5 comportent une série de quatre bits identiques llll précédant une série de deux autres bits et le bit de doublement. La couleur C6 est affectée du code lOOlOlx. La raison en est la suivante. Trois pixels adjacents de couleur C2 peu- vent être codés 1.01 lO0 ou 100 101. Selon le codage de l'invention, on a volontairement écarté la deuxième solu- tion qu'on a ainsi réservée à la couleur C6. Les couleurs C l0, Cl C12, du groupe G6 sont codées sur huit bits. Les trois codes de ce groupe comportent une série de six bits identiques 11llllll, soit deux de plus que la série identique de codes du groupe G5, précédant une série de deux autres bits. Compte-tenu de la rareté d'apparition de ces couleurs, leurs codes ne comportent pas de bit de doublement. Les codes ainsi proposés seront lus ultérieurement sans aucune ambiguité. Avec le codage le plus simple, et alors que la table comporte douze couleurs (1100 dans le système binaire), il aurait fallu quatre bits par pixel. Avec le codage de l'invention, on a constaté que la quantité de bits à en- registrer n'était plus que de 2,25 par pixel. La compres- sion est donc tout-à-fait notable. On a, dans l'exemple décrit ci-dessus, considéré qu'une couleur pouvait être doublée, c'est-à-dire que deux pixels de la même couleur pouvaient se suivre. Il va de soi que la répétition des couleurs, dans le cadre de la présente invention, ne doit pas être limitée à un doublement. Alors, la répétition ne serait plus codée avec un seul bit x, mais avec autant de bits x qu'il faut pour exprimer, en binaire, le nombre décimal de répétitions. Revendications 1. Procédé de codage numérique de données d'une base, sans séparateur entre elles, dans lequel, après avoir déterminé les fréquences d'apparition des données, on leur affecte des codes comportant respectivement des nombres de bits augmentant avec la diminution des fréquences d'apparition, caractérisé par le fait qu'on affecte à moins certaines des données les plus fréquentes (C2-C9) des codes comportant au moins un bit de répétition (x) etqu' adapte les codes à la statistique d'apparition des données. 2. Procédé de codage selon la revendication 1, dans lequel on affecte le bit de répétition (x) en tant que bit de poids le plus faible. 3. Procédé de codage selon l'une des revendications 1 et 2, dans lequel on affecte à la donnée la plus fréquente (Cl) l'unique bit de valeur 0. 4. Procédé de codage selon l'une des revendications 1 à 3, dans lequel on répartit les données en groupes (G3, G5, G6) de données de fréquences d'apparition sensiblement voisines auxquelles on affecte des codes d'un même nombre de bits. 5. Procédé de codage selon la revendication 4, dans lequel les codes d'au moins certains des groupes (G3, G5, G6) com- portent une série de bits identiques (11; 1111; 111111) précédant une série de bits (00; 01; 10) en quantité égale à celle des bits que comporte le nombre binaire correspon- dant au nombre, décimal, de données des groupes. 6. Procédé de codage selon l'une des revendications 4 et 5, dans lequel les codes d'au moins certains des groupes (G3, G5) comportent autant de bits, de plus que ceux de groupes (G2, G3) de fréquence supérieure, qu'en comporte le nombre binaire correspondant au nombre, décimal, de données des groupes considérés (G3, G5). 7. Procédé de codage selon la revendication 5, dans lequel la série de bits identiques des codes d'au moins certains des groupes (G3, G5, G6) comporte autant de bits, de plus que la série identique de bits de codes de groupes de fréquence supérieure (G2, G3, G5), qu'en comporte le nombre binaire correspondant au nombre, décimal, de données des groupes considérés (G3, G5, G6). 8. Procédé de codage selon l'une des revendications 1 à 7, dans lequel la base comporte douze données (Cl-C12) aux- quelles on affecte les codes du tableau suivant: G1 C1 G2 C2 1 0 x C3 1 1 0 0 x G3 C4 1 1 0 1 x C5 1 1 1 0 x G4 C6 1 0 0 1 0 1 x C7 1 1 1 1 0 0 x G5 Cs 1 1 1 1 0 1 x i9.11 1 1 1 0x C l ll llllO0 C10 1 1 1 1 1 1 0 0 G6 Cil 1 1 1 1 1 0 1 C2 i1 1 1 1 1 1 0