Notes sur le cours de codage, transmission, compression

Le bit

Le mot bit désigne deux choses qui n'ont rien à voir :

• Le bit est l'unité de mesure de la quantité d'information.
• Le bit est la quantité d'information minimale que l'on peut stocker physiquement dans la mémoire de l'ordinateur.

Le deuxième porte ce nom car il peut contenir jusqu'à 1 bit d'information, mais il peut en contenir moins (c'est pourquoi l'on a besoin de faire de l'équilibrage de probabilités).

Il est théoriquement possible de faire des mémoires dont l'élément de base permettrait de stocker plus d'un bit d'information. Mais les opérations réalisées serait plus complexe que la logique booléenne : http://www.cs.berkeley.edu/~randy/CLD/CLD.html

L'entier positif

Un entier positif peut-être écrit en base 2 (binaire), en peut donc le stocker en machine sous la forme d'une suite de bits de longueur variable

0() 1(1) 2(10) 3(11) 4(100) 5(101)

La valeur de l'entier : \(... + 8*b_3 + 4*b_2 + 2*b_1 + b_0\)

int est_impair(int entier)
{
 return entier - 2*(entier/2) ; // Si division entiere
 return entier % 2 ;            // % = le modulo
 return entier & 1 ;            // ET BINAIRE du langage C
}

void affiche_entier_en_binaire(int entier)
{
  if (entier)
    {
        affiche_entier_en_binaire(entier / 2) ;
        if (est_impair(entier))
            affiche('1') ;
        else
            affiche('0') ;
    }
}

void affiche_entier_en_decimal(int entier)
{
  if (entier)
     {
        affiche_entier_en_decimal(entier / 10) ;
        affiche( '0'  +  entier % 10 ) ;
     }
}

int decimal_en_entier(char *chaine)
{
 int entier = 0 ;
 while( *chaine )
      entier = 10 * entier + (*chaine++ - '0') ;
 return entier ;
}

       0123456789ABCDEF
Bit 0  .##..##..##..##.
Bit 1  ..####....####..
Bit 2  ....########....
Bit 3  ........########
              ^
              La position décodée est 7

Entier négatif

Le but est coder les entiers négatif de telle façon que les opérations fonctionnant sur les entiers positifs fonctionnent aussi sur les entiers négatifs sans modification.

Complément à 1 : Inverser la valeur des chacun des bits de l'entier.

Complément à 2 : Faire le complément à 1 et ajouter 1

Si l'on dispose de \(n\) bits, on code directement les entier positifs de \(0\) à \(2^{n-1} - 1\). Pour les négatifs, on applique le complément à 2 de sa valeur absolu, on peut coder de \(-2^{n-1}\) à \(-1\).

Il est tout de même nécessaire d'ajouter un indicateur de débordement de l'avant-dernier bit afin de savoir s'il y a eu un débordement. Attention, en langage C :

• on n'est pas prévenu de ce fait.
• la norme indique explicitement qu'en cas de débordement le résultat peut être n'importe quoi.

Un exemple du monde réel (noyau linux) :

int a, b ; // des valeurs quelconques

if ( a>0 && b>0 )
  if ( a + b < 0 )
    La somme de deux nombres positifs est un nombre positif.
    donc le compilateur a le droit d'enlever ce test.

Pointeur

Un pointeur est un entier permettant de retrouver une information en mémoire. Le pointeur est un indice dans un tableau d'élément commençant au début de la mémoire.

De nos jours les pointeurs indicent des tableaux d'octets. Le pointeur sur une donnée de base (entier, flottant) doit souvent être multiple de la taille de la donnée.

• Avantage : Uniformité.

• Inconvénients :

  • perte d'espace adressable,
  • impossibilité d'adresser le bit.
  • codage de pointeurs invalides : la donnée est à cheval sur deux mots mémoire. Ces pointeurs sont invalides ou bien ralentissent le processeur.

Les pointeurs retournés par malloc sont utilisables pour stocker un table de double, il faut donc qu'ils soient un multiple de sizeof(double).

Remarque concernant l'interpréteur LISP. Quelque bits du pointeur sont utilisés pour indiquer le type de l'objet pointé (entier, caractère, chaine, objet...).

Virgule fixe

Le nombre de chiffres (en base 2) après la virgule est constant : \(v\). On se contente donc de multiplier le nombre par \(2^v\) et de le coder comme un entier.

Cela ne change rien aux opérations habituelles, on réutilise donc toute les opérations entières. Mais attention, il faut renormaliser après les multpiplications et divisions.

On code 6.625 avec 4 bits après la virgule comme 110 1010

Diviseur vaut 2 puissance le nombre de bits après la virgule. La fonction suivante se termine toujours, pourquoi ?

int affiche_entier<1_decimal(int entier, int diviseur)
{
 if (entier)
  {
   entier = entier * 10 ;
   affiche( '0' + entier/diviseur ) ;
   affiche_entier<1_decimal(entier % diviseur, diviseur) ;
  }
}

Combien de bits après la virgule pour coder 0.3 ?

float a ;
a = 0.3 ;
if ( a != 0.3 ) printf("Programme faux\n") ;

Virgule flottante

Toujours se rappeler que virgule flottante ne signifie pas nombre réel, on ne peut pas coder les réels en machine (sauf exceptions rarissimes)

Un nombre flottant peut s'écrire sous la forme normalisée : \(mantisse * 2^{exposant}\) avec \(2 > mantisse >= 1\)

• On code l'exposant comme un entier biaisé et non signé. Pour un exposant si 8 bits, on code l'exposant \(3\) comme \(127+3 = 130\). Cela permet de simplifier les comparaisons et de choisir éventuellement d'autoriser plus de grandes puissances que de petites.
• La mantisse est codée comme en entier positif, auquel on enlève le premier bit (toujours égal à 1).

On code donc :

• le signe de la mantisse (0:positif)
• l'exposant + X
• la mantisse sans le premier bit

Pour un flottant simple (32 bits), 1 bit de signe, 8 bits d'exposant (-128...127) et 23 bits de mantisse :

Le résultat de la comparaison de deux flottants est le même que celui des deux représentations vu comme des entiers.

Caractères

ISO 8859-1    West European languages (Latin-1)
ISO 8859-2    Central and East European languages (Latin-2)
ISO 8859-3    Southeast European and miscellaneous languages (Latin-3)
ISO 8859-4    Scandinavian/Baltic languages (Latin-4)
ISO 8859-5    Latin/Cyrillic
ISO 8859-6    Latin/Arabic
ISO 8859-7    Latin/Greek
ISO 8859-8    Latin/Hebrew
ISO 8859-9    Latin-1 modification for Turkish (Latin-5)
ISO 8859-10   Lappish/Nordic/Eskimo languages (Latin-6)
ISO 8859-11   Latin/Thai
ISO 8859-13   Baltic Rim languages (Latin-7)
ISO 8859-14   Celtic (Latin-8)
ISO 8859-15   West European languages (Latin-9)
ISO 8859-16   Romanian (Latin-10)

+    0          1      2 3 4 5 6 7      8    9  A B C D E F
0  NUL ^@     DLE ^P     0 @ P ` p    0x80 0x90   ° À Ð à ð
1  SOH ^A     DC1 ^Q   ! 1 A Q a q    0x81 0x91 ¡ ± Á Ñ á ñ
2  STX ^B     DC2 ^R   " 2 B R b r    0x82 0x92 ¢ ² Â Ò â ò
3  ETX ^C     DC3 ^S   # 3 C S c s    0x83 0x93 £ ³ Ã Ó ã ó
4  EOT ^D     DC4 ^T   $ 4 D T d t    0x84 0x94 ¤ ´ Ä Ô ä ô
5  ENQ ^E     NAK ^U   % 5 E U e u    0x85 0x95 ¥ µ Å Õ å õ
6  ACK ^F     SYN ^V   & 6 F V f v    0x86 0x96 ¦ ¶ Æ Ö æ ö
7  BEL ^G \a  ETB ^W   ' 7 G W g w    0x87 0x97 § · Ç × ç ÷
8  BS  ^H \b  CAN ^X   ( 8 H X h x    0x88 0x98 ¨ ¸ È Ø è ø
9  HT  ^I \t  EM  ^Y   ) 9 I Y i y    0x89 0x99 © ¹ É Ù é ù
A  LF  ^J \n  SUB ^Z   * : J Z j z    0x8a 0x9a ª º Ê Ú ê ú
B  VT  ^K     ESC ^[   + ; K [ k {    0x8b 0x9b « » Ë Û ë û
C  FF  ^L \f  FS  ^\   , < L \ l |    0x8c 0x9c ¬ ¼ Ì Ü ì ü
D  CR  ^M \r  GS  ^]   - = M ] m }    0x8d 0x9d ­ ½ Í Ý í ý
E  SO  ^N     RS  ^^   . > N ^ n ~    0x8e 0x9e ® ¾ Î Þ î þ
F  SI  ^O     US  ^_   / ? O _ o DEL  0x8f 0x9f ¯ ¿ Ï ß ï ÿ

0x00000000 - 0x0000007F: 7 bits
    0xxxxxxx

0x00000080 - 0x000007FF: 11 bits
    110xxxxx 10xxxxxx

0x00000800 - 0x0000FFFF: 16 bits
    1110xxxx 10xxxxxx 10xxxxxx

0x00010000 - 0x001FFFFF: 21 bits
    11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

0x00200000 - 0x03FFFFFF: 26 bits
    111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx

0x04000000 - 0x7FFFFFFF: 31 bits
    1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx

Chaîne de caractères

Deux méthodes pour les coder :

• Le début de la chaîne contient la longueur (Pascal), l'inconvénient est que la chaîne a une longueur limité à moins d'utiliser un entier de longueur variable. Un autre inconvénient est que l'on ne peut pas passer la suite d'une chaine sans détruire le début.
• Un caractère de fin de chaîne existe, l'inconvénient est que l'on ne peut le coder dans la chaîne (à moins de faire un code d'échappement)

Codage des dates

La méthode la plus simple est de coder la date comme un nombre d'unités (..., secondes, minutes, heures, ...) depuis une date de base. Cette méthode est la plus compacte, permet des opérations aisées, est indépendante du calendrier à tous points de vue. Le seul inconvénient est la traduction de l'un à l'autre. (changement de calendrier cal 1752 ou minutes de 62 secondes)

http://www.naggum.no/lugm-time.html

Codage d'arbre binaire

Utile pour la suite du cours. Le codage est simple, il suffit d'ajouter un bit à 0 devant l'information concernant les noeuds et 1 devant l'information concernant les feuilles. Cela donne (en simplifiant) :

0 infos noeud 1 infos feuille 0 infos noeud 1 infos feuille 1 infos feuille

affiche(Arbre *a)
{
if ( noeud(a) )
   {
     affiche_bit(0) ;
     affiche_infos_noeud(a) ;
     affiche(a->gauche) ;
     affiche(a->droite) ;
   }
else
   {
     affiche_bit(1) ;
     affiche_infos_feuille(a) ;
   }
}

Arbre * lecture()
{
 if ( lit_bit() )
  return creer_feuille( lit_infos_feuille() ) ;
 else // Ce qui suit est faux. Pourquoi ?
  return creer_noeud(lit_infos_noeud(),
                     lecture(), lecture()) ;
}

Codage d'arbre quelconque

Très simple :

• Un bit à 0 indique la fin de codage d'un sous-arbre.
• Un bit à 1 est suivi de l'information associée au noeud, suivi du codage du premier fils, suivi du codage du frère suivant.
• On ne fait pas la différence entre une feuille et un noeud sans fils.

Exemple :

• : 0
• A : 1 A 0 0
• A B C D E : 1A0 1B0 1C0 1D0 1E0 0
• A(B C D E) : 1A 1B0 1C0 1D0 1E0 0 0
• A(B C D) E : 1A 1B0 1C0 1D0 0 1E0 0
• A(B(C(D(E)))) : 1A 1B 1C 1D 1E0 0 0 0 0 0

Codes détecteur/correcteurs d'erreur

Ce sont des codages permettant de détecter et/ou corriger des erreurs de transmission de données.

10001
01001 xyzt  = xyzt(x^y^z^t)
00101
00011

1000011 xyzt  = xyzt(x^z^t)(x^y^z)(y^z^t)
0100101
0010110
0001111

10001110
01001101
00101011 xyzt  = xyzt(x^y^z)(x^y^t)(x^z^t)(y^z^t)
00010111

ppppp   ....p   ....p   ....p   ....p
ppppp   ..@.p   .@..p   ....p   ....p
pp3p4   .@..p   ..@.p   ....p   ..*.1
ppppp   ....p   ....p   ....p   ....p
pp5p6   ppppp   ppppp   ppppp   pp2p7

Codage de sons

Un son est produit par une variation de pression de l'air. Pour coder un son, il suffit d'échantillonner dans le temps la valeur de la pression de l'air. Les principaux paramètres stocké dans l'entête sont :

• La fréquence d'échantillonnage (8000Hz par défaut pour la voix).
• Le nombre de bits par échantillon (8 par défaut).
• Le stockage des entiers : signé ou non.
• Le nombre de canals : 1 pour mono, 2 pour stéréo

Codage d'images

On a besoin de faire un échantillonnage spatial de l'image. Pour les pixels, on a deux principaux types de codage :

• Vrai couleur : La valeur des différents canaux.
• Palette de couleur : l'indice de la couleur dans la palette.

Il faut un fichier d'entête pour tout définir.

• 1 bit: image noir et blanc
• \(n\) bits avec généralement \(1\leq n \leq 8\) : c'est un index couleur.
• \(x\) bits pour le rouge, \(y\) bits pour le vert, \(z\) bits pour le bleu : c'est une vrai couleur. C'est le modèle RVB. Il peut être réduit à 3R+3V+2B pour tenir dans un octet.
• HLS/HUV: ou autre séparant la luminance du reste pour rendre meilleur la compression.
• Des tas d'autre choix possibles

A cela il faut ajouter la correction du gamma (contraste) en effet cette connaissance est obligatoire pour que les images apparaissent de la même façon sur des écrans différents.

Code de Shannon-Fano

L'idée : représenter chacun des caractères par une chaîne de bits dont la longueur est proportionnelle à la quantité d'information transporté. Les caractères rarissimes sont donc codés en utilisant plus de bits.

Comment trouver ces représentations ?

• Faire la table du nombre d'occurrences.

• Trier la table par nombre d'occurrences.

  • Couper la table en 2 de telle manière qu'il y ai autant d'occurrences au dessus et au dessous. Entre les 2 points de coupe, choisir le meilleur.
  • On ajoute à la représentation des symboles du haut le bit 0 et ceux du bas, le bit 1.
  • On recommence sur chacune des 2 tables.

Par construction les codes ne sont pas redondant, on n'a pas besoin de dire leur longueur. Le code donne le chemin dans un arbre binaire.

Le taux de compression ne peut dépasser 8 si cette technique est appliquée aux octets.

Il est nécessaire de passer l'arbre avant de commencer. L'arbre précédent peut être codé comme : 110A0B10C10D0E soit 49 bits pour l'arbre.

Pour la donnée elle-même : 2*(15+7+6) + 3*(6+5) → 89 bits

Un des événement doit être le celui indiquant la fin de fichier (obligatoire car le système ne donne la taille des fichiers qu'en octet...)

SI état courant = feuille de l'arbre
   ALORS
         Prendre en compte l'événement considéré
         Retourner à la racine
   SINON
         Lire le bit suivant
         SI bit 0
                ALORS état courant passe dans la branche de gauche
                SINON état courant passe dans la branche de droite

typedef struct
{
  unsigned int bits:9 ;   /* Bits restant à lire */
  unsigned int feuille:1 ;/* Vrai si feuille */
  unsigned int numero:8 ; /* Numéro feuille ou noeud */
} Etat ;

Etat table[255][512] ;    /* [numero_noeud][bit_a_lire] */

void decode()
{
  Etat courant ;
  int c ;

  courant.feuille = 0 ;
  courant.numero  = 0 ;
  courant.bits    = 1 ;

  for(;;)
    {
      if ( courant.feuille )
        {
          /* Faire l'action (qui peut être EOF) */
          printf("%d", courant.numero ) ;
          /* '[0]' car on repart de la racine */
          courant = table[0][courant.bits] ;
        }
      else
        {
          /* Plus de bits dans 'bits' */
          c = getchar() ;
          if ( c<0 )
            exit(1) ; // Ceci ne doit JAMAIS arriver
          courant.bits = 256 + c ;
          courant = table[courant.numero][courant.bits] ;
        }
    }
}

Code de Huffman

Les codes Huffman sont toujours légèrement meilleurs que les codes de Shannon-Fano.

On relie ensemble les symboles ou groupes de symboles de plus faible probabilité jusqu'à obtenir une table avec un seul élément.

Pour la donnée elle-même : 1*15 + 3*(7+6+6+5) → 87 bits

Le décodeur est identique au décodeur vu pour Shannon-Fano.

Événements dépendents.

Si un événement dépend de l'événement précédent, alors on va calculer la probabilité de l'événement en fonction de l'événement précédent. Il y aura donc autant de manière de coder qu'il y a d'événements. Dans un texte français la probabilité du 'u' après un 'q' est de 95%, lettre 'u' sera donc codée sur un seul bit si elle est après un 'q'.

La taille des tables est exponentielle en fonction du nombre d'événement précédents que l'on prend en compte. Il n'est donc pas possible transférer tous les arbres du compresseur au décompresseur.

Codage arithmétique (range encoder)

C'est l'équilibreur de probabilité optimal, les événements sont codés par un nombre de bits égal aux nombre de bit d'informations transportés. On peut donc coder des événements sur moins d'un bit.

L'idée : on code le fichier complet par un nombre flottant entre 0 et 1 qui possède une précision suffisante.

Exemple : on veut coder tet :

Les algorithmes de compression et décompression peuvent directement être programmé en C dans des double si le nombre de bits à stocker n'est pas trop important. Ceci n'empêche pas de stocker des milliers d'événements dans un seul double.

Soit \(p(i)\) la probabilité de l'événement numéro \(i\).

Soit \(S(i) = \sum_{j<i} p(j)\)

double somme  = 0 ;
double taille = 1 ;
Pour les événements i :
{
somme  += S(i) * taille;
taille *= p(i) ;
}

Tant que pas de fin fichier
{
Soit i Tq S(i) < somme < S(i+1)
Faire l'action i
somme -= S(i) ;
somme /= p(i) ; // entre 0 et 1
}

Le précision (indépendante de l'ordre des caractères) sera la largeur de l'intervalle : \(\prod_{e \in E} p(e)^{\text{nbcar}}\)

Exemple numérique : 1000000 de caractères dont 10 'A' et 999990 'B' \(\left( \frac{1}{100000}\right) ^{10} * \left( \frac{99999}{100000}\right) ^{999990} = 4.54 10^{-55}\)

Soit 181 bits pour coder ce nombre.

Dans la réalité on ne calcule pas avec tous les chiffres significatif, on bidouille en utilisant des notations flottantes redondantes.

C'est une méthode lente.

Asymmetric Numeral Systems (ANS)

Compresse autant que le codage arithmétique mais 30 fois plus rapide. Il peut même être plus rapide que Huffman pour le décodage statique. Découverte par Jarosław (Jarek) Duda (2007), maintenant utilisé dans différentes variantes par toutes les nouvelles méthodes de compression.

Contrairement aux autres méthodes, la décompression extrait les symboles dans l'ordre inverse de leur compression.

La suite de symboles est codée par un entier, le message vide est l'entier 1. La table suivante contient la liste des premiers messages dans le cas de 2 symboles A de probabilité ¼ et B de probabilité ¾.

Encodage d'un symbole :

entier := e Tel que Symbole[e] == symbole   et   Numéro[e] == entier

Décodage d'un symbole :

symbole := Symbole[entier]
entier := Numéro[entier]

On peut implémenter cette méthode sans utiliser de tableaux et en faisant des calculs sur des entiers longs. Mais dans ce cas elle est aussi longue que le codage arithmétique.

On peut par contre, moyennant une perte de compression la transformer en une méthode extrêmement rapide et permettant la transmission progressive (tANS). Au lieu de travailler sur des entiers de longueur quelconque on boucle quand on déborde. Pour le décodage, les entiers peuvent éventuellement avoir plusieurs prédécesseurs, pour choisir le bon on doit donc lire un certain nombre de bits dépendant du nombre de prédécesseurs possibles.

Avec l'exemple précédent, on peut prendre les entiers de 0 à 7 et obtenir par exemple :

Le décodeur :

• Lit l'entier final
• Génère le symbole
• Lit le nombre de bits indiqué par l'entier pour trouver l'entier précédent. Cela peut être 0

Remarques :

• Le tableau définissant le graphe de changement d'état va influencer sur le taux de compression, il existe différente manières pour le trouver.

• Cette méthode fonctionne quelque soit le nombre de symboles.

• Cette méthode n'est pas adaptée pour du codage adaptatif car le calcul

  de la table de changement d'état est trop coûteux.

  • Il suffit de mélanger les symboles initiaux pour crypter le message sans coût CPU supplémentaire.
  • Pour mieux comprendre : affichage graphique d'ANS

LZ77

Créé par Abraham Lempel et Jacob Ziv en 1977.

C'est la méthode qui permet d'obtenir la décompression la plus rapide qu'il soit possible de faire. En effet, le décompresseur reçoit des triplets :

• Une position relative dans le texte déjà décomprimé par rapport à l'endroit où l'on est.
• La longueur du texte à la position indiqué qu'il faut recopier à l'endroit où l'on est. Cette longueur peut être nulle.
• Un caractère à ajouter tel quel au fichier.

Le compresseur doit trouver dans le texte déjà envoyé la chaine la plus longue correspondant à ce qui reste à comprimer.

Les valeurs des triplets sont encodés en passant dans 3 équilibreurs de probabilités différents car les probabilités ne sont pas les mêmes.

La taille du buffer est a ajusté en fonction de la donnée à comprimer et du temps de calcul que l'on souhaite utiliser. Prendre un petit buffer permet de faire une compression locale.

LZ78

On remplace le couple position/longueur par un numéro de chaine. Lors de chaque envoi de chaine, une nouvelle chaine est créée, contenant la chaine envoyée + le caractère envoyé.

La localité disparait pour les gros fichiers. Il faut donc avoir des actions permettant de manipuler les dictionnaires.

LZW

Implémentation de Terry Welch en 1984.

On préencode les 256 caractères dans 256 chaines.

La chaine créée est la précédente envoyée + le premier caractère de celle que l'on vient d'envoyer.

C'est une méthode brevetée, mais qui est maintenant dans le domaine publique. Elle était notamment utilisée compresser les images GIF dans le premier compresseur de fichier Unix (extension .Z).

Cet algorithme n'a besoin que d'un seul égaliseur de probabilités. On peut remarquer que plus les codes sont anciens, moins ils sont utilisés. Il est donc plus intéressant pour augmenter la redondance de coder les numéros de chaine comme le nombre de chaines moins le numéro d'ordre. Les chaines récentes qui ont le plus de chance d'être utilisées, sont donc codées par de petits entiers.

Blocksorting (bzip)

Cet algorithme comprime par bloc de donnée de plusieurs centaines de kilo octets.

Voici le principe exemplifié avec le bloc 'BANANE' :

• On peut suprimer les répétitions dans le bloc initial en faisant du RLE (Run Length Encoding). En code le nombre de répétitions et le caractère à répéter.

• On crée une matrice carré virtuelle contenant les textes décalés.

  BANANE (*) Chaine initiale
  ANANEB
  NANEBA
  ANEBAN
  NEBANA
  EBANAN
  

• On trie les lignes.

  ANANEB
  ANEBAN
  BANANE (*) Chaine initiale
  EBANAN
  NANEBA
  NEBANA
  

• On extrait la dernière colonne qui dans les cas réels contient de nombreux caractères identiques successifs : BNENAA

• On applique l'algorithme MTF (Move To Front) qui maintient un tableau dont les éléments les plus courants ont le indices les plus petits. Le dernier élément envoyé prend toujours l'indice 0.

  B:66	N:78	E:70	N:1	A:65	A:0
  Table ASCII stand- ard B:66	B:0 N:78	N:0 B:1 E:69+1	E:0 N:1 B:2	N:0 E:1 B:2 A:65+3	A:0 N:1 E:2 B:3	A:0 N:1 E:2 B:3

• On peut appliquer des prétraitements (RLE) de supression des répétitions de 0 qui seront les plus courantes.

• Sur un exemple réel, les codes comportent de très nombreux entiers avec une faible valeur numérique. Le codage arithmétique donne le meilleur résultat, mais on peut se contenter de Huffman.

Pour décompresser.

• On obtient directement la première colonne en triant les lettres de la dernière.

• On parcour chacune des lignes du tableau de la première à la dernière. Pour chaque ligne on lui associe comme successeur la première ligne qui commence par le dernier caractère de la ligne courante et qui n'a pas encore de prédécesseur.

  Ceci fonctionne uniquement parce que la liste est triée et donc l'ordre des lettres identiques à droite est le même que l'ordre des lettres identiques à gauche !

  1 ANANEB 3
  2 ANEBAN 5
  3 BANANE 4
  4 EBANAN 6 le 5 est déjà pris
  5 NANEBA 1
  6 NEBANA 2
  

• On parcourt à partir de la ligne contenant le bon décalage, la liste circulaire créée dans le sens inverse : 3, 1, 5, 2, 6, 4

  On obtient donc en gardant les premières lettres : B A N A N E

Le compresseur permet de comprimer efficacement de gros blocs même s'ils sont hétérogènes car le tri permet de remettre ensemble les chaines similaires.

LZMA2

C'est actuellement le meilleur algorithme de compression généraliste. Il y a de nombreuses implémentations différentes de l'idée de base. C'est lui qui est utilisé dans 7zip.

Cet algorithme est en fait LZ77, la seule différence siginification est que l'on ne génère pas des triplets mais des paquets de différents types.

Les longueurs sont généralement courtes. Le codage optimise donc le transfert des petites valeurs.

Les distances sont codées par un numéro de slot sur 6 bits suivi d'un certain nombre de bits dépendant du slot. Certains bits du codage sont fixes car équiprobable, d'autres passent par le codeur arithmétiques.

Toutes les valeurs codées passent par un codeur arithmétique dont les tables dépendent des types des derniers paquets envoyés et du type de la valeur à coder. Tout ceci donne plus de 1000 tables contenant des probabilités.

Compression d'images binaires sans pertes

La compression d'image ou les pixels sont codés dans des octets se fait assez bien avec les algorithmes de compression de données. Par contre les résultats pour les images binaires (bitmap) sont décevants.

Réduire la précision du signal ou le transformer

Dans le cas des images, il est possible de réduire le nombre de couleurs utilisées en passant par une étape de quantification.

Une fois la palette de couleur définie, on peut soit :

• remplacer la couleur de chaque pixel par la couleur la plus proche de la palette. Dans ce cas on verra de grandes zones de couleur uniforme si la palette contient trop peu de couleur.
• remplacer globalement les couleurs sur un ensemble de pixel pour simuler un dégradé. C'est ce qui est utilisé pour l'impression papier, ce sont les très nombreuses techniques de dithering

Pour passer de couleur en niveau de gris :

Luminance = 0.3 Rouge + 0.59 Vert + 0.11 Bleu

Dans tous les cas, si quelques valeurs dans le signal empêchent d'obtenir un bon taux de compression, il faut les raboter car ces valeurs étant rares elles ne seront pas visibles pour un être humain.

Prédiction

Un signal est une fonction généralement continue et régulièrement échantillonnée.

On stocke la différence entre la valeur réelle du signal et la prédiction que l'on en a faite. Cette valeur est normalement très petite si la prédiction est correcte.

On peut donc faire la déduction suivante pour un signal 1D continu :

\(V_{i+1}\ \approx\ V_{i}\)

On voit que les valeurs nécessaires pour coder le signal sont bien plus petites :

La dérivé est généralement continue :

\(V_{i+1} - V_{i}\ \approx\ V_{i} - V_{i-1}\)

\(V_{i+1}\ \approx\ 2V_{i} - V_{i-1}\)

On voit que les valeurs nécessaires pour coder le signal sont encore plus petites que dans le cas précédent :

Si l'on va jusqu'à la dérivée seconde :

\(( V_{i+1} - V_{i} ) - ( V_{i} - V_{i-1} )\ \approx\ ( V_{i} - V_{i-1} ) - ( V_{i-1} - V_{i-2} )\)

\(( V_{i+1} - V_{i} ) \ \approx\ 2( V_{i} - V_{i-1} ) - ( V_{i-1} - V_{i-2} )\)

\(V_{i+1}\ \approx\ V_{i} + 2( V_{i} - V_{i-1} ) - ( V_{i-1} - V_{i-2} )\)

\(V_{i+1}\ \approx\ 3V_{i} - 3V_{i-1} + V_{i-2}\)

Le son donné en exemple est très bruité, il suffit d'écouter le fichier audio pour s'en rendre compte. Pour ce signal, passer à la dérivée seconde fait diminuer le taux de compression et n'est donc pas intéressant. La dynamique des valeurs suivantes est plus grande.

MP3

Les algorithmes de prédiction ne sont pas suffisant pour compresser le son. Pour pouvoir compresser fortement du son, il faut se rapprocher de sa nature, ce sont des oscillations qui s'ajoutent les unes aux autres. Il faut donc travailler dans le domaine fréquentiel.

Si l'on veut transmettre un son stéréo, on transmet la moyenne des deux sons ainsi que la différence. Cela augmente le taux de compression et permet de facilement oublier la stéréo en gardant le mono sans perte de qualité.

DCT : Transformée cosinus discrète

C'est la transformation généralement utilisée dans tous les compresseurs de son avec des variations. Elle travaille bloc par bloc, l'utilisation de grand bloc permet d'augmenter le taux de compression mais introduit un latence inacceptable pour une utilisation interactive (téléphone).

Le son à compresser est dans un tableau de flottant \(s\) dont les indices commencent à 0 et contenant \(n\) échantillons.

\(s'\) est le résultat de l'application de la DCT à \(s\) :

\(s'[i] = \frac{\sqrt{2}}{\sqrt{n}} \sum_j \frac{s[j]}{i=0 ? \sqrt{2}:1} \cos\left( i \pi \frac{ 2j+1 }{2n} \right)\)

\(s'[0]\) est la valeur moyenne du signal qui est généralement nulle pour un son. Ceci correspond à une fréquence nulle.

Si le bloc dure une seconde :

• \(s'[i]\) est l'énergie transportées par la fréquence \(i/2\)
• donc \(s'[1]\) est donc la fréquence ½Hz
• Si bloc contient 8000 échantillons, \(s'[7999]\) est l'amplitude de la fréquence \(\frac{7999}{2}\) Hz. Le théorème de Shannon indique que l'on doit obligatoire échantillonner au double de la fréquence maximum pour ne pas perdre d'information.

On voit alors dans \(s'\) que l'information se résume à quelques pics, le reste étant pratiquement nul. L'image suivante représente 8 blocs mis les uns après les autres. En effet au lieu de travailler sur un son complet, on travaille sur une partie du son car l'algorithme précédent est en temps \(O(n^2)\)

La transformée inverse est égale à :

\(s[i] = \frac{\sqrt{2}}{\sqrt{n}} \sum_{j} \frac{s'[j]}{j=0 ? \sqrt{2}:1} \cos \left( j \pi \frac{ 2i+1 }{2n} \right)\)

Comme vous le voyez, c'est exactement la même formule appliquée en inversant les indices. On peut donc exprimer le calcul comme un produit matrice/vecteur (voir la partie sur le JPEG).

On peut faire les calculs en virgule fixe (et donc en entier). Mais dans ce cas, on ne retrouve pas exactement le signal de départ lorsque l'on applique la formule inverse.

int virgule_fixe = 1<<24 ;       // 24 bits après la virgule
int inverse_epsilon = 1<<16 ;    // epsilon = 1/(1<<16)
int x = virgule_fixe ;           // Valeur réelle : 1
int y = 0 ;
while(x > y) // Un quart cercle
   {
      x -= y / inverse_epsilon ;
      y += x / inverse_epsilon ;
   }

JPEG

La compression JPEG (Joint Picture Expert Group) permet de comprimer des images en tenant compte d'un facteur de qualité. Le standard ne formalise que la manière de décomprimer.

Le compression d'image couleur se fait en compressant indépendemment les 3 composantes (pas RVB mais YUV ou un autre du même genre afin de rendre indépendant les canaux). On détaillera le cas d'image en niveau de gris.

La compression d'image se fait étonnament de la même manière que celle du son. La principale différence sera la façon de dégrader le signal. Contrairement au son, le signal n'a pas une moyenne nulle et il est 2D.

La DCT 2D est une DCT dans un sens puis dans l'autre. On peut réécrire la DCT comme un produit de matrice.

\(DCT(j, i) = \frac{\sqrt{2}}{\sqrt{n}} \cos( j \pi \frac{ 2i+1 }{2n} )\)

\(DCT(0, i) = \frac{1}{\sqrt{n}}\)

En JPEG, la taille de la matrice DCT a été fixée (par les experts) à 8×8 afin que l'algorithme puisse être codé directement sur le silicium. Voici la matrice DCT 8×8 avec les basses fréquences en haut à gauche et les hautes en bas à droite :

+0.3536 +0.3536 +0.3536 +0.3536 +0.3536 +0.3536 +0.3536 +0.3536
+0.4904 +0.4157 +0.2778 +0.0975 -0.0975 -0.2778 -0.4157 -0.4904
+0.4619 +0.1913 -0.1913 -0.4619 -0.4619 -0.1913 +0.1913 +0.4619
+0.4157 -0.0975 -0.4904 -0.2778 +0.2778 +0.4904 +0.0975 -0.4157
+0.3536 -0.3536 -0.3536 +0.3536 +0.3536 -0.3536 -0.3536 +0.3536
+0.2778 -0.4904 +0.0975 +0.4157 -0.4157 -0.0975 +0.4904 -0.2778
+0.1913 -0.4619 +0.4619 -0.1913 -0.1913 +0.4619 -0.4619 +0.1913
+0.0975 -0.2778 +0.4157 -0.4904 +0.4904 -0.4157 +0.2778 -0.0975

La compression de son se réécrit comme \(s' = DCT * s\) et sa décompression comme \(s = DCT^T * s'\)

Donc en 2D, pour l'image \(I\), sachant que \((A*B)^T=B^T*A^T\) on a :

\(I' = ( DCT * ( DCT * I ) ^ T ) ^ T = DCT * I * DCT^T\)

Image initiale affichant un dégradé de gris bruité :

 +45   +55   +63   +75   +85   +90  +100  +105
 +60   +72   +80   +89   +90  +109  +117  +116
 +77   +93  +102   +99  +116  +127  +127  +133
 +98   +97  +116  +127  +135  +133  +136  +149
+105  +123  +124  +140  +143  +147  +162  +173
+125  +134  +149  +153  +154  +164  +168  +177
+142  +149  +160  +172  +168  +191  +184  +199
+153  +169  +168  +177  +198  +203  +205  +219

Le résultat \(I'\) est une matrice qui contient des nombres généralement petits. Cette étape permet déjà de comprimer l'image. La DCT de l'image précédente :

+1051.8  -147.7    -9.7   -17.3    -2.5    -7.9    +2.7    -5.7
 -283.1    -1.1    -1.9    +1.7    -3.9    +4.9    -3.3    +4.6
   +0.3    -8.0    +2.9    +6.9    -4.3    -2.9    -0.8    -2.6
  -33.6    +1.8    +1.1    -7.0    +1.6    +7.8    -2.3    -3.6
   +2.7    -6.9    -0.7    -0.1   +11.5    -4.5    -8.1    +4.6
   -6.9    +5.8    -6.0    +1.2    +6.1    +2.0    +9.1    +0.3
   +0.1    +2.6    -1.0    +1.2    -2.5    -7.3    -0.6    +7.4
   +2.3    -6.0    +4.5    -0.4    -4.5    -5.0    -3.8    -3.5

L'inverse de la DCT :

\(I = (DCT^T * (DCT^T * I')^T) ^ T = DCT^T * I' * DCT\)

Pour la qualité, le principe n'a rien à voir avec ce qui est fait pour le son. Pour les images, on se contente dire que l'on a pas besoin des hautes fréquences et donc on les code avec moins de précision. Cette quantification est paramétrable, elle ressemble à :

\(I''(i,j) = \frac{I'(i,j)}{1+(i+j+1)Q}\)

Où \(0<Q<25\) est le facteur de qualité, 0 étant la meilleure. La DCT de l'image précédente quantifiée avec Q=1 :

+526   -48    -1    -2     0     0     0     0
 -93     0     0     0     0    +1     0     0
   0    -1     0    +1     0     0     0     0
  -6     0     0     0     0    +1     0     0
   0     0     0     0    +1     0     0     0
   0    +1     0     0    +1     0    +1     0
   0     0     0     0     0     0     0     0
   0     0     0     0     0     0     0     0

Dans le bas-droite de \(I''\) il y a beaucoup de 0. On ne va donc pas coder \(I''\) ligne par ligne mais en zig-zag.

Le codage se fait ensuite comme la DCT sur les sons.

Voici la différence entre l'image compressée avec perte et l'image initiale:

-12  +6  -1  -3  +2  -1   0  +1
 +1   0  +2  +3  -3  +3  -3  +2
 -3  +2  +3  -4  +3  +4   0  -1
 -3  -4  +1  +3  +4   0   0  -4
 -2  +4   0  +3  +1   0   0  +9
  0   0  +5  +3   0  -1  -9   0
 -5   0  -1  +5  -8  +4  -1  +1
  0  +3  +1   0  +4  +4   0  +6

Et si la taille de l'image n'est pas un multiple de 8 ? On la complète de la manière la plus naturelle possible afin de minimiser les hautes fréquence et ainsi augmenter le taux de compression en diminuant la visibilité des artfefacts. Par exemple en utilisant les fonctions de prédiction.

Pour l'encodage le décodage des fichiers JPEG, cherchez sur le web : « Understanding and Decoding a JPEG Image using Python »

MPEG

La compression MPEG (Moving Picture Expert Group) permet de comprimer de la vidéo en tenant compte d'un facteur de qualité afin de produire un débit constant.

• MPEG1 : Le but est de pouvoir lire une séquence vidéo et afficher de la vidéo avec un lecteur de CD classique (1.5 Mbit par seconde).

• MPEG2 : Le but est de pouvoir coder de la télévision en résolvant le problème de l'entrelacement. Parmi les ajouts:

  • Des canaux en plusieurs langues ou surround (5).
  • Sous titres

  De 3 à 10 Mbit par seconde.

• MPEG3 : Extension de MPEG pour la télévision haute définition. En fait cela fixe seulement quelques paramètres, aucun changement d'algorithme.

• MPEG4 : Compression de données multimédia pour diffusion avec une bande passante très faible.

  Idées principales:

  • Un dialogue entre le compresseur/décompresseur pour déterminer leurs possibilités respectives.
  • Un LANGAGE extensible de communication.
  • Le MPEG3 comme outil de base
  • Delivery Multimedia Integration Framework (DMIF) pour la communication.
  • Découpage de l'image en zone (quadtree) et couches (image de fond). Algorithmes spécifiques par zone. Utilisation de modèles 3D texturés.

Comme pour JPEG, le standard ne formalise que la manière de décompresser et donne seulement des indices pour la compression.

Pour le son, c'est ce qui a été décrit précédemment.

Les images sont dans l'espace YUV (U=R-Y, V=B-Y). Les images U et V sont classiquement à une résolution réduite car l'oeil est moins précis dans l'espace des couleurs. Les images sont découpées en block de 16x16 dans l'espace des Y.

Les images (frames) peuvent être Initiales, Prédites, Bidirectionnelle.

• Pour pouvoir faire de l'accéléré, (ou récupérer des erreurs de transmission) il faut coder régulièrement des images I.
• Les images P ne dépendent que de l'image précédente.
• Les images B sont une interpolation entre une image passé et une image futur. Elles ont disparues en MPEG2.

Quelques cas courants :

• IIIIIIIIIIIII : format MJPEG, c'est une succession d'images initiales. Seulement utilisé par les premiers appareil photo numériques permettant de faire de la vidéo.
• IPPPPPPPPPPPP : compression maximum pour le satellite et l'ADSL le zapping est lent. Les images I sont inserrés au moment des changements de scène
• IBPBIBPBI : augmente la latence et complique la compression.

Un image I ne comporte que des bloc JPEG de type I, une P peut contenir des I et P et une B des I, P et B. Le codage est le même que celui du JPEG mais il y a un code End Of Block pour éviter de coder le dernier nombre de 0.

Un bloc P est la DCT de la différence entre le bloc à compresser et un bloc de l'image précédente décalé par rapport à la position courante. Classiquement la différence est nulle car on retrouve le bloc ailleurs au bruit près. On a donc seulement besoin de coder la translation.

Un bloc B code la différence par rapport à la moyenne de deux blocs, un dans le passé et un dans le futur. Le futur doit donc déjà être transféré. Cela augmente donc la latence.

Le canal est décomposé en 3 sous-canaux (ou plus dans le futur): audio (2-5 sous-canaux), vidéo, système (synchro et autres informations) Le codage est fait de telle manière que cela reste compatible downward et upward. Le codage permet de multiplexer une hiérarchie de canaux.

MPEG1 : Compression du son 6:1, soit 0.25 Mbit/s, reste donc 1.25 Mbits/s pour le reste. L'image fait 352×240×30. Pour la coder, il faut une compression 26:1 (en fait entre 8 et 30)

Compression hiérarchique

Déjà abordé pour le JBIG.

L'ancêtre de la compression par ondelette est basée sur l'utilisation de pyramide Gaussienne et Laplacienne.

Image initiale :
9      8      5      4      2      1      1
Gaussienne, la résolution est divisée par 2 :
      7.5           3.75          1.25
Laplacienne calculée à partir de la Gaussienne :
7.5  6.5625  3.75   3.125   1.25  1.25   1.25
Erreur commise, c'est ce que l'on transmet :
1.5 1.4375  1.25   0.875   0.75 -0.25 -0.25

OPUS Audio Codec

Il est garanti que ceci contient des erreurs, comprendre cette méthode dans le détail nécessite des semaines de travail.

Le RFC en cours de rédaction (160 pages sans les sources) contient les sources du codeur et décodeur. Les sources fournis permettent de lever les ambiguïtés qui pourraient être présentes dans le texte anglais.

Compression fractale

Très complexe et peu utilisée actuellement car le temps de compression est trop important.

L'idée est de reconstruire un modèle fractale à partir de l'image ou de parties de l'image. On utilise un modèle fractal car les images sont couramment auto-similaires.

Les modèles utilisés sont souvent basés sur les IFS (Iterated Function Set). Un modèle IFS est défini par un ensemble de transformations \(T\) contractantes qui appliquées de nombreuses fois tendent vers le même objet. L'objet est défini de manière récursive.

Le fameux triangle de Sierpińsky :

Pour l'adapter à la compression d'image une transformation est couramment définie par :

• Rectangle de départ dans l'image
• Rectangle d'arrivé (plus petit que le rectangle de départ)
• Une valeur de correction de contraste entre 0 et 1 (qui multiplie la valeur du pixel calculé)
• Une valeur de correction de luminosité (qui s'additionne à la valeur calculée)

Remarques :

• L'image compressée est codée par l'ensemble des transformations.
• L'exécution d'une transformation prend le rectangle initiale, le réduit, corrige le contraste et la luminosité et stocke le résultat dans le rectangle final.

• Décompression de l'image :

  • On initialise l'image avec n'importe quoi.
  • On itère les transformations jusqu'à ce que l'image soit stable (ça marche car les transformations sont contractantes)

• L'ensemble des rectangles d'arrivé doit recouvrir la surface de l'image.
• L'image reconstruite peut être à n'importe quelle résolution.
• La compression est complexe car l'on doit trouver la transformation qui produit le rectangle final le plus ressemblant au rectangle original.

Compression vidéo par cellule

Utilisé pour les vidéoconférences. L'intérêt est que le taux de compression est constant et que la compression est rapide.

Pour l'ensemble de l'image on extrait une palette de 256 couleurs les plus utiles. On est pas forcé de le faire à chaque image.

Pour chaque cellule (groupe de 4×4 pixels, donc 48 octets)

• On calcule la moyenne de la luminosité
• On bipartitionne en fonction de la moyenne (on stocke 4×4 bits : 2 octets)
• On calcule les deux moyennes de couleurs des 2 zones
• On stocke les 2 couleurs moyennes (on stocke 2 index de 8 bits : 2 octets)

Taux de compression fixe de 12.

Les implémentations sont multiples, les extensions sont nombreuses :

• On utilise Huffman pour stocker les événements bitmap et moyennes
• On stocke la différence par rapport à une cellule de l'image déjà calculée.
• On change la palette de couleur pour l'améliorer peu à peu.

La difficulté est d'avoir un catalogue permettant une recherche rapide de l'image la plus ressemblante.

Codage et Compression de polyèdre

Beaucoup de chose sur la compression des coordonnées et de la connectivité. C'est un sujet toujours d'actualité.

Idées en vrac :

• Ne considérer que les triangles.
• Coordonnées relatives à la précédente dans des unités liées à l'objet : Coder des vecteurs au lieu de positions.
• On quantifie les vecteurs qui sont normalement petits.
• Ne jamais transmettre 2* le même point.
• Problème du codage de la normale à une surface (échantillonnage régulier de la surface de la sphère).
• Simplification inversible : on fourni une donnée minimum pour rajouter les facettes enlevées (même idée : on transmet le son milieu, puis le son gauche, ou bien les turbo code).
• Pour la topologie : arbres de triangles (2.2 bits par triangle en moyenne) ou bien le parcour du polyèdre en spiral si c'est possible.
• Pour la transmission simplifiée : enlève les facettes presque coplanaires.
• Utiliser des méthodes multirésolution, ondelettes par exemple.

Les polyèdres sans trou peuvent être représentés par des cartes planaires, c'est-à-dire un graphe sans croisement.

PNM

Utilitaires du package netpbm

Portable N.={Bit, Gray, Pixel} Map

L'entête pour les fichiers RAW (pas codé en décimal mais en binaire) :

• PGM RAW : P5\n%d %d\n%d\n avec la largeur en pixel, la hauteur en pixel, une valeur indiquant le nombre de bits par pixels qui est systématiquement 255.
• PBM RAW : Idem avec P4 et 1 bit par pixel
• PPM RAW : Idem avec P6 et 3 octets par pixel

Dans les 3 cas l'image est une suite de valeurs binaires non lisibles par un être humain.

La deuxième ligne peut être un commentaire, elle commence alors par #

Conversion d'image :

• Avec les outils netpbm on fait un pipeline avec des commandes Xtop[bgpn]m | p[bgpn]mtop[bgpn]m | p[bgpn]mtoY

• Avec la commande convert de imagemagick : convert toto.X toto.Y

• En langage C, pour écrire directement une image JPG sans stocker une image non compressée sur le disque :

  FILE * f = popen("ppmtojpeg >toto.jpg", "w") ;
  fwrite(votre image en PPM) ;
  pclose(f) ;
  

TIFF

La référence : http://partners.adobe.com/public/developer/en/tiff/TIFF6.pdf

TIFF est un format extensible pour stocker n'importe quoi, il a servi de base à beaucoup d'autres formats. Il est néanmoins limité à des fichiers de 4Go.

AVI

Un FOURCC est un code sur 4 octets créé par la concaténation de 4 caractères, ils sont lisibles par les êtres humains. Seulement 3 entités différentes :

• Entête : 'RIFF' fileSize fileType
• Une liste : 'LIST' listSize listType listData
• Un bloc de données (chunk) : FOURCC ckSize ckData

Le décompresseur peut analyser le fichier AVI sans rien savoir d'autre. Mais il ne comprendra pas les FOURCC définissant les blocs audio, vidéo...

Si l'on plonge en plein milieu d'un fichier il n'est pas très difficile de retrouver un endroit ou commencer à décoder.

EXIF

C'est un ensemble de TAG normalisés compatible TIFF que l'on peut insérer dans presque tous les formats de fichier.

La manière de l'insérer dépend malheureusement du format du fichier.

Portable Network Graphic

En vrac :

• Palette ou true-color.
• Meilleur compresseur que GIF.
• Code correcteur d'erreur : CRC
• Transparence paramétrable.
• Extensible.
• Gamma.
• Affichage progressif (gris puis couleur, général puis détails).
• Coordonnées XY (CIE 1931) du RVB et blanc.
• Données textuelles.

VRML et X3D

VRML 1.0 is a subset of the Inventor File Format (ASCII) with some additions to allow linking out to the Web and including other URLs. The linking out feature (WWWAnchor) provides the same feature that HREF anchors provide in HTML.

Just before the VRML press announcement, Mark described VRML in a "backgrounder" (URL is http://vrml.wired.com/arch/1010.html) " VRML is a language for describing multi- user interactive simulations -- virtual worlds networked via the global Internet and hyperlinked within the World Wide Web."

#VRML V1.0 ascii
Separator {
    DirectionalLight {
        direction 0 0 -1  # Light shining from viewer into scene
    }
    PerspectiveCamera {
        position    -8.6 2.1 5.6
        orientation -0.1352 -0.9831 -0.1233  1.1417
        focalDistance       10.84
    }
    Separator {   # The red sphere
        Material {
            diffuseColor 1 0 0   # Red
        }
        Translation { translation 3 0 1 }
        Sphere { radius 2.3 }
    }
    Separator {  # The blue cube
        Material {
            diffuseColor 0 0 1  # Blue
        }
        Transform {
            translation -2.4 .2 1
            rotation 0 1 1  .9
        }
        Cube {}
    }
}

Stéganographie

La stéganographie est l'écriture cachée. En clair, l'art de cacher une information dans une autre information. Cette technique suscite de nombreuses recherches car elle permet par exemple de stocker une information (un copyright) dans des données sans que celle-ci soit enlevable sans beaucoup abimer les données.

Exemple venant de : Neil F. Johnson, Steganography, Technical Report TR_95_11_nfj, 1995. http://www.jjtc.com/pub/tr_95_11_nfj/

News Eight Weather:  Tonight increasing snow.
Unexpected precipitation smothers eastern towns.  Be
extremely cautious and use snowtires especially heading
east.  The highways are knowingly slippery.  Highway
evacuation is suspected.  Police report emergency
situations in downtown ending near Tuesday.

En prenant la première lettre de chaque mot : Newt is upset because he thinks he is President

Pendant la seconde guerre mondiale, certain services secrets réécrivaient les correspondances pour éviter des transferts d'information par ces méthodes.

Dans le cadre d'une implémentation informatique (pas de standards pour le moments), 3 méthodes peuvent être cataloguées :

• Stéganographie simple : on extrait le message de la donnée. Cette méthode n'est pas fiable si l'agorithme est connu, on ajoute donc une graine qui définie la position de l'information.
• Filigrane (WaterMarking) : on extrait le message de la donnée et de la donnée initiale, le message est perdu si la donnée initiale l'est.
• Empreinte digitale (FingerPrint) : le message étant donné on regarde si on le retrouve dans la donnée.

Méthode simple pour les sons et images : on modifie des bits de poids faibles de la donnée. On peut enlever le marquage à condition de modifier tous les bits de poids faibles. L'inconvénient de cette méthode est quelle ne résiste pas à la DCT avec perte ou à des pertes de qualité d'image.

Méthode utilisant la DCT : on code le message dans les bits de poids faible des coefficients de la DCT après quantification. Cette méthode est plus résistante mais le message disparaît si l'on compresse avec une qualité moins bonne.

Compression entêtes TCPIP

La norme est définie dans le RFC1144

C'est pour les liaisons bipoint faible début (liaisons séries par exemple). Il faut qu'au 2 bouts le protocole compressé soit supporté.

L'implémentation de la méthode de compression fait 250 lignes de C 90 micro secondes sur un 68020 a 20MHz pour compresser l'entête.

Un header TCPIP classique occupe 20 octet pour IP et 20 octets pour TCP. Le header après compression se réduit à 3 octets.

Tout d'abord, les paquets venant d'une même connexion ont très peu de champs qui changent. Le codage va donc s'appuyer sur cela :

• Bit 1 : indique si c'est compressé.
• Nombre : Numéro session TCP - Numéro session TCP paquet précédent.
• Un mask de bits indiquant les champs variants dans le header TCPIP
• Pour chaque champs variant on stocke la différence par rapport à la valeur du paquet précédent de la même connexion.

Les nombres sont codés sur un nombre de bits variables (comme dans la DCT) si une des valeurs change de plus de 65536. On envoit un paquet non compressé.

On envoit en plus un CRC sur le paquet compressé, car des erreurs de transmission sur le paquet compressé ont tendance à générer des paquets TCPIP décompressés valides !

Si les 2 codes d'erreur ne détectent rien, une erreur passe à travers. Les paquets suivants ne vont pas passer car invalides. Dans ce cas, il n'y a pas de transmission d'acquittement. Au bout d'un timeout, la retransmission est faite avec un paquet non-compressé afin de reprendre proprement.

Cette compression fonctionne bien mieux qu'une compression LZW aveugle.

Il est plus intéressant de compresser séparement l'entête et les données. On peut activer dans les serveurs web une compression automatique des données transmises (pas des entêtes).

Anomalies

La compression peut être utile pour trouver des données anormales dans un ensemble de données. En effet, une donnée anormale se comprime moins bien qu'une donnée normale.

Application aux fichiers tabulés (fichier de log par exemple). On évalue le nombre d'informations pour stocker une ligne. Le principe est simple :

• On initialise la quantité d'information de chaque ligne à 0
• On recherche la colonne contenant le plus de caractères identiques. On bipartitionne alors l'ensemble des lignes.
  • Pour les lignes contenant ce caractère dans cette colonne on incrémente la quantité d'information de 1/nbLignes puisque le caractère est codé une seule fois pour toutes ces lignes. On enlève la colonne et on continue la récursion sur ces lignes.
  • Celles ne le contenant pas, on ne fait rien et on continue la récursion.

Une ligne complètement différente des autres se trouvera rapidement seule et la récursion se poursuivra à gauche en ajoutant systématiquement 1 à sa quantité d'information.

100 lignes identiques prendront 100 fois moins de mémoire.

Cette méthode permet de trouver toutes les anomalies dans les fichiers de log. Il convient d'intégré progressivement les informations dans les fichiers de log servant de dictionnaire afin qu'un pirate ne submerge les fichiers de log avec de nombreuses anomalies identiques.

Base de données

Les BD utilisent la compression comme critère de normalisation. En effet, dans un bon schéma de base de donnée aucune donnée n'est dupliquée. Cela a de nombreux avantages :

• Cela prend moins de place (mais lent si l'on ne crée pas les bonnes vues)
• Il ne peux pas y avoir d'incohérence.
• Cela force à structurer correctement la base de donnée.

Programmation

Voir la première partie de http://perso.univ-lyon1.fr/thierry.excoffier/COURS/COURS/TRANS_COMP_IMAGE/prog.html