La compression d’images par ondelettes - ibni

Ce document est une introduction interactive à la compression des images par ondelettes. Si vous ne voyez pas l'applet ci-dessus ne se charge pas, ou bien si un message d'erreur s'affiche, il vous faut télécharger la dernière version de Java. Cette applet permet de comprimer une image à l'aide d'une transformée en ondelettes, et de voir en temps réel le résultat. Le curseur au centre permet de régler le taux de compression. Ainsi, en plaçant le curseur sur "50%", vous obtiendrez un fichier compressé qui prendra moins de place sur le disque dur. Bien sûr, plus vous compressez l'image, plus vous perdez en qualité, on ne peut pas gagner sur tous les tableaux !

1. Introduction

Les multimédia ont fait entrer les images numériques partout dans notre vie : appareils photos numériques, internet, télévision, téléphones portables. Chaque jour des milliards d’images sont transférées sur internet, d’un appareil photo à un ordinateur ou d’un téléphone portable à un autre. La croissance de ces échanges ainsi que la volonté de stocker toujours plus d’images sur un support limité ont poussé les chercheurs et les ingénieurs à trouver des moyens de représenter les images de manière la plus concise possible. On mesure le volume qu’occupe une image en mémoire par sa taille en octets.

Exemples d’images avec différents poids (3 ou 4 exemples, de qualités et de dimension différentes).

1. Les images numériques

• Qu’est ce qu’une image numérique?

  Une image numérique est un tableau de nombres, d’où l’adjectif numérique. Peut être savez vous qu’un ordinateur utilise un langage binaire composé uniquement de 0 et de 1 appelé bits (binary digits). L’ordinateur utilise donc un alphabet à 2 caractères, il ne connaît ni les lettres ni les couleurs, en revanche avec des 0 et des 1 on peut créer des nombres plus grands et associer à ces nombres ce qu’on veut, des lettres par exemple pour écrire ou des couleurs pour regarder des images. Pour cela on regroupe les bits par blocks de 8 pour former des octets. Sur un octet on peut coder 256=2^8 nombres différents (faire un lien ici pour expliquer un peu plus). Pour une image monochrome en noir et blanc par exemple, on associe ensuite à un nombre une intensité lumineuse sur un pixel de l’écran, par exemple on associe 0 à une intensité nulle donc à un pixel noir et on associe 255 à une intensité maximale donc à un pixel blanc. Les valeurs comprises entre 1 et 254 correspondant à différents niveaux de gris.

  Une image couleur est une superposition de trois images monochromes rouge, verte et bleue.

• Que signifie compresser une image ?

  Compression du jus d’orange.
  Sans doute avez-vous déjà bu un jus d’orange à base de jus concentré. On le fabrique en extrayant l’eau du jus pressé et en ajoutant de l’eau avant de le mettre en bouteille. Pourquoi faire de telles opérations ? Pour le transport. Le jus concentré est beaucoup moins volumineux et coûte bien moins cher à transporter, comme pour les images. L’ajout final d’eau permet de restituer un jus presque identique à l’original. On a ainsi transporté l’essentiel du jus et laissé sur place ce qui peut être ajouter simplement à la fin.
  Dans l'exemple interactif que vous voyez, le jus d'orange c'est l'image, le concentré d'orange c'est les points foncés de la transformée en ondelettes à droite, les points blancs c'est l'eau. Les points très clairs correspondent à de l'eau avec un tout petit peu d'orange. On ne transporte dans la tranformée du dessous que les points les plus foncés, comme la grande majorité est clair on peut les supprimer sans altérer trop l'image, si on en garde trop peu, on modifie beaucoup l'image. Plus on arrive à séparer l'eau du concentré d'orange plus on peut compresser le jus, pour l'image c'est pareil, plus on arrive à obtenir de points blancs et peu de points très foncés, plus on arrive à compresser l'image.

  Compression des images.
  Compresser une image c’est la même chose, on extrait l’essentiel de l’image, du tableau de nombres en fait, en se permettant éventuellement d’omettre quelques détails. En pratique on remplace un tableau par un autre plus petit qui décrit de manière concise les informations contenues dans le grand. C’est le concentré d’orange. Il suffit ensuite à la personne qui souhaite lire l’image de savoir comment passer du petit tableau au gros.
  Il est parfois possible de compresser légèrement sans perte d’information et donc de qualité mais si on souhaite diviser le volume mémoire de l’image par 10 on a nécessairement des pertes de détails.

1. Comment compresser ?

• Méthodes naïves.

  Un premier exemple de compression consiste à réduire le nombre de nuances de couleurs. Au lieu d’utiliser 256 couleurs on peut décider d’en utiliser 2, noir et blanc. Au lieu d’utiliser 1 octet, ie 8 bits, par couleur on utilisera 1 bit, ce qui divise le volume de l’image par 8. En pratique c’est assez brutal. (Exemple avec 2 images).

Image originale (256 couleurs)	Image noir et blanc (2 couleurs)

• Une seconde méthode consiste à ne pas coder toutes les valeurs du tableau, par exemple on en code qu’une sur 4 et on essaie de deviner les autres à partir de celles qu’on a, le plus souvent à partir des valeurs voisines.

Codage de tous les pixels	Codage 1 pixel sur 4	Codage de 1 pixel sur 16

• Méthodes classiques.

  Le format de compression «.gif » diminue le nombre de couleurs comme dans la première méthode naïve. L’idée de cette compression est de choisir les couleurs qu’on garde pour être le plus proche de l’original et non pas de les fixer indépendamment de l’image.

Image .gif avec 256 couleurs (poids 70 Ko)	Image .gif avec 10 couleurs (poids 17Ko)	Image .gif avec 2 couleurs (poids 7 Ko)

• Le format de compression « .jpg » découpe d’abord l’image en blocs de taille 8 par 8 et traite séparément les différents blocs. Tous les éléments d’un même bloc sont traités ensemble, c’est pourquoi on a parfois l’impression de voir des pâtés sur les images codées en jpg.

Image .jpg (poids 63Ko)	Image .jpg (poids 5Ko)

1. Compression en ondelettes

Des ingénieurs et des mathématiciens ont développé indépendamment des idées proches dans les années 80 qui ont débouché sur l'outil mathématique à la base du format de compression « jpg2000 » : les ondelettes.

• Les légos.

• Vous pouvez presque tout construire avec de simples briques de légo, des ponts, des voitures, des châteaux, des vaisseaux spaciaux ... Pour construire ce que l'on veut il suffit d'assembler les briques d'une certaine manière. Les briques élémentaires sont simples et très bien adaptées à la construction.
  Ces briques élémentaires des images sont les pixels, en effet ils sont très simples et bien assemblés, c'est à dire mis aux bonnes valeurs, ils permettent de construire n'importe quelle image. Les briques de légo comme les pixels sont pratiques mais dès qu'on veut construire quelquechose d'un peu grand on a besoin de beaucoup d'éléments. Pour utiliser moins de briques de légo, une solution est d'utiliser des briques plus grosses là où ça peut remplacer plusieurs petites briques semblables. Si les petites pièces ne sont pas rigoureusement identiques, le remplacement par une brique plus grosse causera une petite modification.

• La multirésolution.

• Pour construire un gros objet, par exemple un gros bonhomme, je place d'abord les grosses briques pour avoir une version grossière du personnage. Quelques grosses briques pour le corps, les bras, les jambes et la tête, puis j'ajoute des briques moyennes pour le cou, les pieds, les mains, les aticulations, puis des briques un peu plus petites pour les yeux, le nez, les doigts, puis éventuellement des toutes petites pour fignoler les détails. Cette approche qui permet d'utiliser un nombre d'éléments très réduit est appelé multirésolution, car on construit un objet d'abord de manière grossière puis de plus en plus précise : en augmantant graduellement la résolution. C'est dans cet esprit qu'on été inventées les ondelettes qui sont des ensembles de pixels de différentes tailles. Pour être précis, les ondelettes ne sont pas des gros blocks rectangulaires mais des paquets plus ou moins gros qui ont la forme d'une vague, ou d'une onde d'où leur nom. Les grosses ondelettes vont permettre de construire une version grossière de l'image et les petites ondelettes vont apporter des détails plus fins.

Image avec des "briques" de petite taille.		Image avec des "briques" de taille moyenne.		Image avec des "briques" de grande taille.
Représentation 3D. Ona remplacé l'intensité lumineuse par une hauteur.		Représentation 3D.		Représentation 3D.

• La compression en ondelettes.

  Si on veut obtenir une image parfaitement identique à l'originale on doit utiliser toutes les ondelettes mais dans la plupart des zones unis il n'y a pas beaucoup de détails et on peut se permettre de ne pas les coder. En pratique une compression en ondelettes permet de coder précisément les zones complexes et coder grossièrement les zones uniformes. En d'autres termes, on ne code les détails que là où il sont nécessaires, comme un peintre qui passe plus de temps à réaliser les petits détails que les grands aplats.

Code Source Java