Compression par ondelettes

Série JPEG
Groupe JPEG	JFIF	JPEG-LS	Compression JPEG	JPEG 2000	Compression par ondelettes

Sommaire

1 Introduction aux ondelettes

2 Algorithme ondelettes

3 Transformée ondelettes

4 Transformée ondelettes à deux dimensions

5 Décompression ondelettes

6 Comparaison des algorithmes

7 Bibliographie

7.1 Français
7.2 Anglais

8 Voir aussi

Introduction aux ondelettes

Proche de la DCT, la technologie de compression à base d'ondelettes offre une plus grande finesse au niveau de l'analyse du signal, et permet de mieux s'adapter aux propriétés locales de l'image. Il s'agit d'une voie de recherche assez prometteuse, mais passée relativement sous silence à cause du succès des normes utilisant la DCT : JPEG et MPEG (vidéo). Les formats H.264 (dont le codec x264 en est une implémentation), Snow (encore en développement) et JPEG 2000 utilisent la compression en ondelettes

La transformation par Ondelettes est une technique inventée par Summus Ltd et qui consiste à décomposer une image en une myriade de sous-bandes, c’est-à-dire des images de résolution inférieure.

La transformée en ondelettes d'une image de résolution k donne trois « sous-images » de résolution (k+1) : celles des coefficients d'ondelettes, dont la nature particulière met en évidence de l'information sur les contours, les textures, leur localisation et leur orientation. Le choix de l'ondelette mère est très important et fait toujours l'objet d'expérimentations pour adapter l'analyse du signal image au système de perception visuel de l'homme.

Algorithme ondelettes

Image manquante Ondelette_schemat_de_compression.png Image:Ondelette schemat de compression.png
Figure 1 schéma de compression

La compression se compose donc des étapes suivantes :

Transformations par ondelettes
Quantification : les valeurs des images de détails inférieures à un certain niveau sont éliminées, en fonction de l'efficacité recherchée. C'est cette étape qui introduit des pertes.
Codage des valeurs restantes.

Transformée ondelettes

Pour commencer nous allons expliquer la transformée à une dimension.

Nous avons donc comme donnée originale :

Niveau 4 : $s^4_0 s^4_1 s^4_2 s^4_3 s^4_4 s^4_5 s^4_6 s^4_7 s^4_8 s^4_9 s^4_{10} s^4_{11} s^4_{12} s^4_{13} s^4_{14} s^4_{15} = S^4$

Etapes après étape nous obtenons :

Niveau 3 : $s^3_0 s^3_1 s^3_2 s^3_3 s^3_4 s^3_5 s^3_6 s^3_7 d^3_0 d^3_1 d^3_2 d^3_3 d^3_4 d^3_5 d^3_6 d^3_7 = S^3, D^3$

Niveau 2 : $s^2_0 s^2_1 s^2_2 s^2_3 d^2_0 d^2_1 d^2_2 d^2_3 d^3_0 d^3_1 d^3_2 d^3_3 d^3_4 d^3_5 d^3_6 d^3_7 = S^2, D^2, D^3$

Niveau 1 : $s^1_0 s^1_1 d^1_0 d^1_1 d^2_0 d^2_1 d^2_2 d^2_3 d^3_0 d^3_1 d^3_2 d^3_3 d^3_4 d^3_5 d^3_6 d^3_7 = S^1, D^1, D^2, D^3$

Nous obtenons finalement :

Niveau 0 : $s^0_0 d^0_0 d^1_0 d^1_1 d^2_0 d^2_1 d^2_2 d^2_3 d^3_0 d^3_1 d^3_2 d^3_3 d^3_4 d^3_5 d^3_6 d^3_7 = S^0, D^0, D^1, D^2, D^3$

Le passage d'un niveau à l'autre s'effectue à l'aide des formules suivantes :

$s_i^{k-1} = {s_{2i}^k + s_{2i + 1}^k \over 2}$
$d_i^{k-1} = {s_{2i}^k - s_{2i + 1}^k \over 2}$
Equation 1 Transformée ondelettes

Le premier calcule la moyenne de deux pixels ce qui va permettre de calculer les fréquences deux fois plus basses. Le deuxième calcule la différence entre deux pixels, ce qui correspond à l'amplitude de la fréquence à l'endroit donné. On remarque donc que la transformée DCT donne des informations sur l'amplitude des fréquences, la transformée en ondelettes donne l'amplitude de la fréquence à un endroit donné. Ce qui est plus proche de la perception humaine car pour le son par exemple, on remarque s'il y a des basses ou des aigus à un instant donné. On peut également remarquer que dans le cas de la DCT, les fréquences varient de façon linéaire tandis que dans le cas de la transformée par ondelettes les fréquences varient de manière logarithmique ; ce qui est également plus proche de notre perception.

Transformée ondelettes à deux dimensions

On distingue 4 étapes différentes pour procéder à la transformation:

Moyenner les pixels de l'image originale deux à deux suivant l'axe horizontal ; par exemple : $H(x) = {X_n + X_{n+1} \over 2}$
Calculer l'erreur entre l'image originale et l'image sous-échantillonnées dans le sens horizontal ; par exemple : $G(x) = {X_n - X_{n+1} \over 2}$
Pour chacune des deux images intermédiaires, moyenner les pixels deux à deux suivant l'axe vertical ; par exemple : $H(y) = {Y_n + Y_{n+1} \over 2}$
Pour chacune des deux images intermédiaires, calculer l'erreur suivant l'axe vertical ; par exemple : $G(y) = {Y_n -Y_{n+1} \over 2}$

Ce qui donne graphiquement :

Image manquante Ondelette_par_niveaux.png Image:Ondelette par niveaux.png
Figure 2 schéma de transformation d'un niveau à l'autre

Le résultat est une image d'approximation qui a une résolution divisée par deux et trois images de détails qui donnent les hautes fréquences de l'image originale. Cette transformation est répétée autant de fois que nécessaire pour obtenir le nombre voulu de sous-bandes.

Niveaux après niveaux nous obtenons :

Image manquante Ondelette_à_deux_dimentions.png Image:Ondelette à deux dimentions.png
Figure 3 transformée en ondelettes niveau après niveau

Décompression ondelettes

La transformation inverse par ondelettes reconstruit une image originale. La construction de l'image à partir des sous-bandes restitue l'image en mode progressif. L'affichage de l'image peut s'effectuer en deux modes :

Soit la taille de l'image augmente au fur et à mesure de la lecture du fichier compressé.
Soit la résolution de l'image augmente au fur et à mesure de la lecture du fichier compressé.

Comparaison des algorithmes

Les principaux avantages par rapport à JPEG sont :

Le fait que l'algorithme s'adapte mieux aux propriétés locales de l'image
Le fait qu'il ne contient pas de tables permet de créer de très petit fichier < 1 ko
L'algorithme est plus simple donc plus rapide (il permet de coder une image test en 1s contre 3s pour JPEG)
On peut atteindre des taux de compression d’environ 50 contre 25 pour JPEG tout en ayant une qualité d'image raisonnable.

Bibliographie

Français

http://www.ondelette.com/ Site dédié aux ondelettes
http://cm.bell-labs.com/who/wim/cascade/index.html Applet recréant les fonctions ondelettes

Anglais

http://www.ms.washington.edu/~s530/ Wavelets: Data Analysis, Algorithms & Theory
http://ppur.epfl.ch/livres/2-88074-398-2.html Wavelets and their application - Cahier de physique de la presse polytechnique et universitaire romande de Stefan Goedecker

Voir aussi

Transformée en ondelette discrète

Image manquante
Symbole-ordinateur.png

Portail Informatique - Accédez d'un seul coup d’œil à toute la série des articles de Wikipédia concernant l'informatique.