Accueil

Généralités

Pourquoi compresser ?

L'algorithme JPEG

La DCT

Codage statistique

Synthèse des algoritmes

D'autres méthodes

Notre programme

Le pathfinding(TIPE 2003/2004 de Math sup)

Vennez signer le livre d'or Livre d'or Vennez signer le livre d'or

Quelques liens


Delain

les vidcast

D'autres méthodes :

La compression des répétitions :

Prenons par exemple l'extrait suivant d'une image codée en 256 couleurs (soit 1 octet par couleur) :

01010001 01010010 10101110 10110100 10110100 10110100 11010111 11010111 11010111 11010111 10101100 00101111 00101111 00101111 00101111 00101111 11010000 11010001 11010010 00111100 00111100 00111100

Cet extrait contient 22 octets. Pour gagner de la place, nous allons coder cet extrait en fonction des répétitions d'octets. Pour cela, nous utiliserons un octet de signalisation (affiché en italique pour rendre la lecture plus facile). Le premier bit de l'octet de signalisation indiquera si l'octet de donnée qui suit se répète. Il sera mis à 1 s'il y a répétition ou à 0 dans le cas contraire. Les sept bits suivants indiqueront dans le premier cas, le nombre d'octets à répéter et dans le second cas, le nombre d'octets sans répétition.

Notre chaîne codée commence donc par : 00000011 01010001 01010010 10101110 (pas de répétition sur trois octets)
Nous avons codé ici sur quatre octets ce qui n'en prenait que trois !
Continuons, l'octet suivant se répète trois fois, il sera donc codé par 10000011 10110100 (3 se code 11 en binaire).
Cela nous donne : 00000011 01010001 01010010 10101110 10000011 10110100.

Nous obtenons finalement le code suivant :

00000011 01010001 01010010 10101110 10000011 10110100 10000100 11010111 00000001 10101100 10000101 00101111 00000011 11010000 11010001 11010010 10000011 00111100

Ce code contient 18 octets soit 4 de moins que le code original. Nous avons donc un taux de compression de 22/18=1,2.

Cette méthode est certes trés facile à comprendre et à mettre en oeuvre, mais elle n'est pas très efficace.

L'approximation par polynône :

Les variations de couleurs entre deux pixels consécutifs d'une image est souvent faible. On peut donc approcher la matrice de couleurs par une fonction polynôme de degrés plus ou moins élevés. Prenons pour exemple la série de couleurs suivantes : 255, 234, 204, 213, 203, 197, 169, 147.

x 0 1 2 3 4 5 6 7
série originale 255 234 204 213 203 197 169 147
f(x)=-13x+249 249 236 223 210 197 184 171 158
f(x)=-x²-10x+256 256 245 232 217 200 181 160 137
f(x)=-x³+9x²-35x+256 256 229 214 205 196 181 154 109

On mémorise ensuite le degré du polynôme ainsi que ses coefficients plutôt qu'une série de couleurs.

Le JPEG 2000 :

Contrairement au JPEG qui analyse l'image par blocs, le JPEG 2000 analyse l'image dans sa globalité. Il considère directement chaque ligne comme la variation d'un signal de luminosité et de couleur. Ce signal est ensuite décomposé par une suite d'ondulettes (voir ci-dessous) dont on élimine les moins significatives. Les ondulettes sont des fonctions inventées par Alfred HAAR qui sont nulles la plupart du temps, mais qui varient soudainement entre deux valeurs précises. Pour décompresser l'image, il suffit d'additionner ces ondulettes. Les images compressées avec l'algorithme JPEG 2000, pour une même qualité, occupent dix fois moins de place qu'avec le JPEG.

Ondulettes :

 

Retour à l'accueil.