Discret Wavelet Transform (DWT: transformée par ondelettes discrète)

Algorithme récursif de Mallat

Le principe de l'algorithme consiste à diviser en quatre l'image à chaque itération : trois blocs concernant les détails de l'image, et le quatrième correspondant aux informations les plus importantes pour l'oeil (les basses fréquences), qui sert de base pour la prochaine itération.

Pour décomposer cette image, on utilise donc deux filtres issus du choix d'ondelette : un filtre passe-haut et un filtre passe-bas.

Seules deux types de transformations s'appuyant sur deux types d'ondelettes ont été choisis pour le format JPEG2000 :

• la transformation ``CDF 9/7'' pour Cohen-Daubechies-Fauvaue dans le cas d'une transformation irréversible.
• la transformation ``spline 5/3'' de Le Gall, beaucoup plus simple pour permettre une transformation reversible.

Les nombres 9 et 5 correspondant au nombre d'éléments du filtre passe-bas. Les nombres 7 et 3 correspondant au nombre d'éléments du filtre passe-haut.

NB : pour la CDF 9 7 :

$${ \begin{array}{cc} Passe-Bas\ h_0 = { \begin{array}{l} +0.... ...+0.045635881557(z^4+z^{-2}) \\ \end{array}} \par \end{array}}$$

Ces figures représentent les ondelettes discrétisées:

Figure: Ondelettes pour la transformation CDF 9/7 : Daubechies
Figure: Ondelettes pour la transformation Spline 5/3 : le Gall

A partir de ces ondelettes, nous formons donc les deux filtres : nous noterons H le filtre passe-haut, et L le filtre passe-bas. Cette phase s'appelle la phase d'analyse.

Figure: Principe de la DWT 2D

Figure: Organisation des couches

La ligne du haut correspond aux images convoluées avec le filtre L. La ligne du bas correspond aux images convoluées avec le filtre H.

L'itération suivante se fera en prenant pour image de base, la partie LL, correspondant à la convolution par le filtre passe-bas (horizontalement, et verticalement). Le format JPEG2000 limite le nombre d'itérations D entre 0 et 32, les valeurs par défaut étant la plupart du temps entre 4 et 8. Si on regarde plus généralement l'effet de cette transformation, il apparait que cet algorithme concentre l'énergie de l'image dans les blocs LL de plus haut niveau de décomposition. Ensuite tous les autres blocs ne sont que des détails de l'image. Ainsi des manières de compresser et donc de mettre à zéro une partie des coefficients de cette matrice reviennent à analyser les blocs de plus haut niveau de décomposition, et de faire une supposition : les valeurs faibles dans les hauts degrés de décomposition tendent vers zéro au fur et à mesure que l'on remonte les niveaux.

Cette méthode permettra de compresser énormément les zones relativement continues, mais en gardant l'ensemble des discontinuités, et cela en suivant le contour de l'image, puisque les filtres passe-haut sont appliqués dans toutes les directions : verticale, horizontale et diagonale (composition des deux).

Pour schématiser autrement :

Figure: Une Itération de la DWT

Figure: Decomposition sur une image : D = 3

Pour reconstituer ensuite l'image, nous procédons à la phase dite de synthèse. Pour cela on construit les filtres $g_0$ et $g_1$.

$$g_0[n] = \alpha^{-1}(-1)^nh_1[n]$$

$$g_1[n] = \alpha^{-1}(-1)^nh_0[n]$$

avec $\alpha$ un facteur de gain valant :

$$\alpha = \frac{1}{2}(h_0^{dc}h_1^{nyq} + h_1^{dc}h_0^{nyq})$$

$h_b^{dc}$ correspond au gain du filtre pour la phase d'analyse à la fréquence DC.

$h_b^{nyq}$ correspond au gain du filtre pour la phase d'analyse à la fréquence de Nyquist.

$$h_b^{dc} = {\displaystyle \sum_{n}h_b[n]}$$

$$h_b^{nyq} = {\displaystyle \sum_n(-1)^nh_b[n]}$$

pour b=0,1

Figure: Une Iteration de la IDWT