Lifting en ondelettes

Un lifting en ondelettes est, en mathématiques, un schéma d’implantation d’une transformation en ondelettes un peu différent de celui plus habituel réalisé par les bancs de filtres.

Le lifting en ondelettes est l’expression retenue pour désigner le procédé d’amélioration des propriétés des ondelettes par utilisation réciproque des bandes passe-bas et passe-haut. On obtient ainsi une transformation qui, à partir d’une ondelette à (admettons) $\ n\$ moments nuls, produit une transformée dont les propriétés sont similaires à une ondelette à $\ {\tilde {n}}\$ moments nuls supérieur à $\ n\$.

Avantages et applications

Le procédé d’élévation (lifting) décrit ici a pour avantage d’avoir une complexité très faible, de l’ordre de la moitié de celle de la transformée rapide de Fourier FFT. La transformation peut être effectuée in situ, c’est-à-dire sans utilisation de mémoire supplémentaire. On perd cependant la propriété d’invariance par translation.

Cette technique de transformation est notamment utilisée dans l’algorithme de compression d’images JPEG2000, et trouvera d’autres applications dans le traitement numérique du signal en général et la transmission ou le stockage de données échantillonnées (notamment la compression du son, ou de mesures physiques de précision).

Introduction

Le but de ce document est de synthétiser de façon concise les techniques et connaissances permettant la réalisation de la transformation version lifting en ondelettes, et en particulier, de réaliser la transformation d’entiers en coefficients d’ondelettes entières. Voir en fin d’article les références essentielles aux articles théoriques et tutoriels.

Transformée en ondelettes version lifting

Description générale de la transformée en ondelettes version lifting

La transformation en ondelettes version lifting est un processus permettant entre autres d’optimiser le nombre d’opérations à exécuter et l’occupation mémoire (le coût de calcul est la moitié du coût de calcul de la FFT !).

Le processus le plus courant pour obtenir une transformation en ondelettes est d’utiliser un banc de filtres (cf. Figure 1), cependant lorsqu’on regarde cette façon de procéder on constate que l’on effectue un sous-échantillonnage par deux après une opération de filtrage : on a donc dépensé en pure perte la moitié du coût de calcul effectué par le filtrage.

L’opération de lifting en ondelettes peut-être vu comme la transformation réalisée par le banc de filtres, mais en intervertissant les phases de filtrage et de sous-échantillonnage. On limite ainsi le nombre d’opérations à effectuer mais, nous perdons en revanche la propriété d’invariance par translation.

Une autre propriété intéressante est que le schéma de lifting est facilement inversible.

Le schéma de lifting est aussi lié aux processus d’échantillonnage et d’interpolation (non explicitement étudié ici) pour la transformation de signaux continus.

On désignera ici par $\ \gamma \$ les coefficients d’ondelettes et par $\ \lambda \$ les coefficients d’échelle obtenus par la transformation.

Pour une ondelette particulière (c.à.d. un couple de filtres $(h,\ g)$ ou $({\tilde {h}},\ {\tilde {g}})$ dans l’implémentation par banc de filtres) caractérisée en outre par (disons) $\ n\$ moments nuls (jouant un rôle dans le processus de décroissance des coefficients d’ondelettes à travers les résolutions) pour le filtre primaire et $\ {\tilde {n}}\$ moments nuls pour le filtre dual, le schéma d’implantation par lifting permet d’obtenir facilement des ondelettes de moments $\ n\$ et $\ {\tilde {n}}\$ plus élevé. On a donc élevé (lifté) l’ordre de cette ondelette par ce schéma (d’où la justification du nom lifting).

Dans la Figure 1, le signal original $\left(\ X\ \right)$ passe par les deux filtres complémentaires $\left[\ {\tilde {h}}\ \right]$ (passe-bas) et $\left[\ {\tilde {g}}\ \right]$ (passe-haut), en sortie on peut sous-échantillonner par 2 $\left[\ \downarrow 2\ \right]$ et on obtient alors respectivement des coefficients d’ondelettes $\left(\ \gamma \ \right)$ et des coefficients d’échelle $\left(\ \lambda \ \right)$.

Figure 1

Figure 1. Schéma d’une implémentation en banc de filtres d’une transformation en ondelettes.

La reconstruction du signal s’effectue par sur-échantillonnage par insertion de zéros $\left[\ \uparrow 2\ \right]$ et passage par les filtres de synthèse $\left[\ h\ \right]$ et $\left[\ g\ \right]$, puis par simple addition pour obtenir le signal $\left(\ Y\ \right)$.

On utilisera :

• les ondelettes paresseuses (lazy wavelets) qui servent à séparer un vecteur en composantes paires et impaires,
• ainsi qu’une matrice polyphase qui permet de travailler sélectivement sur les composantes paires ou impaires du signal.

On va factoriser la matrice polyphase et introduire alors deux opérations :

• une opération de prédiction (predict) qui prédit les échantillons de rang pair à partir des échantillons de rang impair ;
• une opération de mise à jour (update) qui permet de conserver sur une partie du signal la valeur moyenne de l’ensemble du signal.

Le formalisme utilisé est celui des articles de références [Sweldens, Valens]. (Attention cependant aux écarts de notations entre les différents articles).

Cette transformation va en outre permettre de réaliser une transformation sur des entiers qui donne des entiers. Cependant il faudra utiliser une étape supplémentaire utilisant aussi le lifting pour la mise à l’échelle.

Vers la réalisation de l’ondelette de Haar version lifting

On part des filtres d’analyse et de reconstruction de l’analyse multi-résolution classique par banc de filtres suivant le schéma classique de la Figure 1 :

• ${\tilde {h}}[n]={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1\\{\underline {1}}\end{bmatrix}}$
• ${\tilde {g}}[n]={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1\\-{\underline {1}}\end{bmatrix}}$
• ${\tilde {h}}(z)={\frac {1}{\sqrt {2}}}(1+z^{-1})$
• ${\tilde {g}}(z)={\frac {1}{\sqrt {2}}}(1-z^{-1})$
• $h[n]={\frac {1}{\sqrt {2}}}{\begin{bmatrix}{\underline {1}}\\1\end{bmatrix}}$
• $g[n]={\frac {1}{\sqrt {2}}}{\begin{bmatrix}{\underline {1}}\\-1\end{bmatrix}}$
• $h(z)={\frac {1}{\sqrt {2}}}(1+z^{-1})$
• $g(z)={\frac {1}{\sqrt {2}}}(1-z^{-1})$

Attention aux notations utilisées ci-dessus :

• dans certaines références, on trouve souvent ${\tilde {g}}(z^{-1})$ et ${\tilde {h}}(z^{-1})$.
• dans les expressions des filtres, le coefficient souligné correspond à l’indice $n=0$.

Les filtres doivent en outre satisfaire les formules suivantes :

• $h(z){\bar {h}}(z^{-1})+g(z){\bar {g}}(z^{-1})=2$
• $h(z){\bar {h}}(-z^{-1})+g(z){\bar {g}}(-z^{-1})=0$

On a besoin de construire la matrice polyphase ${\tilde {P}}$ ainsi que sa matrice duale ${P}$ (le terme polyphase vient de la théorie du filtrage numérique où il est utilisé pour décrire le partitionnement d’une séquence d’échantillons en plusieurs sous-séquences qui peuvent être traitées en parallèle, les sous-séquences peuvent-être vues comme des versions d’elles-mêmes décalées en phase, d’où le nom). On utilise la formule suivante de décomposition polyphase sur les filtres précédents :

• $x(z)=x_{e}(z^{2})+z^{-1}\ x_{o}(z^{2})$, où $x_{e}$ désigne les échantillons pairs (even) et $x_{o}$ les échantillons impairs (odd) (moyen mnémotechnique : even a un nombre de lettres pair, odd a un nombre de lettres impair).
• ${P}(z)={\begin{pmatrix}{h_{e}}(z)&{g_{e}}(z)\\{h_{o}}(z)&{g_{o}}(z)\end{pmatrix}}$
• ${\tilde {P}}(z)={\begin{pmatrix}{\tilde {h_{e}}}(z)&{\tilde {h_{o}}}(z)\\{\tilde {g_{e}}}(z)&{\tilde {g_{o}}}(z)\end{pmatrix}}$

Il vient assez facilement :

• ${\tilde {h}}(z)={\begin{matrix}\underbrace {{\tilde {h_{e}}}(z^{2})} \\1\end{matrix}}+z^{-1}{\begin{matrix}\underbrace {{\tilde {h}}_{o}(z^{2})} \\1\end{matrix}}$
• ${\tilde {g}}(z)={\begin{matrix}\underbrace {{\tilde {g_{e}}}(z^{2})} \\1\end{matrix}}+z^{-1}{\begin{matrix}\underbrace {{\tilde {g}}_{o}(z^{2})} \\-1\end{matrix}}$
• ${\tilde {P}}(z)={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}$

sachant que $\det {\tilde {P}}=-1$, et que pour $\det {\tilde {P}}=1$, on a les propriétés suivantes :

• ${\tilde {h}}_{e}(z)=g_{o}(z^{-1})$
• ${\tilde {h}}_{o}(z)=-g_{e}(z^{-1})$
• ${\tilde {g}}_{e}(z)=-h_{o}(z^{-1})$
• ${\tilde {g}}_{o}(z)=h_{e}(z^{-1})$

Ces propriétés montrent que pour passer de l’analyse à la synthèse (de $P$ à ${\tilde {P}}$, il suffit si $\det {\tilde {P}}=1$, de prendre la matrice des cofacteurs en changeant de signe.

De plus sachant que $P(z){\tilde {P}}(z^{-1})=I$ (l’inversion temporelle $z^{-1}$ est nécessaire pour compenser le délai introduit par le filtrage) :

• ${P}(z)={\frac {1}{\sqrt {2}}}\ {\begin{pmatrix}1&1\\1&-1\end{pmatrix}}$

Lifting primaire

L’élévation primaire (primary lifting) est aussi appelé update. Le lifting à proprement parler consiste à modifier le filtre $g$ en gardant la complémentarité avec $h$ à l’aide de la formule :

• $g_{new}(z)=g(z)+h(z)\ s(z^{2})$

où $s(z)$ est un polynôme de Laurent.

Soit la transformée en Z d’un filtre FIR :

• $h(z)=\sum \limits _{k=p}^{q}h[k]z^{-k}$.

Cette somme est aussi nommée polynôme de Laurent ou encore série de Laurent.

La matrice polyphase devient alors :

• $P_{new}(z)=P(z)\ {\begin{pmatrix}1&s(z)\\0&1\end{pmatrix}}$.

De la même façon pour ${\tilde {h}}$,

• ${\tilde {h}}_{new}(z)={\tilde {h}}(z)+{\tilde {g}}(z)\ {\tilde {s}}(z^{2})$,

où ${\tilde {s}}(z)$ est un polynôme de Laurent.

Dès lors,

• ${\tilde {P}}_{new}(z)={\begin{pmatrix}1&{\tilde {s}}(z)\\0&1\end{pmatrix}}\ {\tilde {P}}(z)$.

Lifting dual

L’élévation duale (lifting dual) est aussi appelé prédiction.

Les formules précédentes modifient la sous-bande passe-bas à l’aide de la sous-bande passe-haut. Le lifting dual consiste en l’opération inverse : modifier la sous-bande passe-bas à l’aide de la sous-bande passe-haut.

• $h_{new}(z)=h(z)+g(z)\ t(z^{2})$,
• $P_{new}(z)=P(z)\ {\begin{pmatrix}1&0\\t(z)&1\end{pmatrix}}$,

et

• ${\tilde {g}}_{new}(z)={\tilde {g}}(z)+{\tilde {h}}(z)\ {\tilde {t}}(z^{2})$,
• ${\tilde {P}}_{new}(z)={\begin{pmatrix}1&0\\t(z)&1\end{pmatrix}}\ {\tilde {P}}(z)$,

où $t$ est un polynôme de Laurent.

On a ainsi élevé (lifté) le niveau de sophistication de la transformation en ondelettes. On a de plus, pour avoir une transformation inversible :

• $t(z)=-{\tilde {t}}(z)$ et
• $s(z)=-{\tilde {s}}(z)$.

Factorisation des filtres

La démarche ici est en quelque sorte la démarche inverse afin de pouvoir passer de forme connue de pairs de filtres d’ondelettes à leur implémentation en termes de lifting d’ondelettes.

On peut réécrire :

• ${\tilde {g}}_{new}(z)={\tilde {g}}(z)+{\tilde {h}}(z)\ {\tilde {t}}(z^{2})$

en :

• ${\tilde {g}}(z)={\tilde {h}}(z)\ {\tilde {t}}(z^{2})+{\tilde {g}}_{new}(z)$,

qui est une forme de division avec reste (pour réaliser la division avec reste, on utilise l’algorithme d’Euclide) où ${\tilde {g}}_{new}$ est le reste.

Alors :

• ${\tilde {P}}(z)={\begin{pmatrix}1&0\\{\tilde {t}}(z)&1\end{pmatrix}}\ {\tilde {P}}_{new}(z)$.

En itérant cet exemple, on peut arriver à obtenir une matrice polyphase qui est de la forme :

• $P(z)={\begin{pmatrix}K_{1}&0\\0&K_{2}\end{pmatrix}}\ \prod \limits _{i=1}^{m}{\begin{pmatrix}1&s_{i}(z)\\0&1\end{pmatrix}}\ {\begin{pmatrix}1&0\\t_{i}(z)&1\end{pmatrix}}$,

où $K_{1}$ et $K_{2}$ sont deux constantes (différentes de zéro) que l’on peut éventuellement factoriser en quatre étapes de lifting.

Figure 2

Figure 2. Lifting, chaque voie (sous-bande) est modifiée par l’autre.

Exemple de la transformée lifting en ondelettes de Haar

On est déjà parti des filtres de la transformation en ondelettes de Haar et on a obtenu la matrice polyphase et sa forme duale. Il reste à factoriser pour avoir l’implémentation en lifting.

• ${\tilde {P}}(z)={\frac {1}{\sqrt {2}}}\ {\begin{pmatrix}1&1\\1&-1\end{pmatrix}}$

Lifting dual

On veut :

• ${\tilde {P}}(z)={\tilde {P}}_{new}(z)\ {\begin{pmatrix}1&0\\{\tilde {t}}(z)&1\end{pmatrix}}={\frac {1}{\sqrt {2}}}\ {\begin{pmatrix}1&1\\1&-1\end{pmatrix}}$,

• ${\tilde {P}}(z)={\begin{pmatrix}{\tilde {h_{e}}}^{new}(z)&{\tilde {h}}_{o}^{new}(z)\\{\tilde {g_{e}}}^{new}(z)&{\tilde {g}}_{o}^{new}(z)\end{pmatrix}}\ {\begin{pmatrix}1&0\\{\tilde {t}}(z)&1\end{pmatrix}}={\begin{pmatrix}{\tilde {h}}_{e}^{new}+{\tilde {h}}_{o}^{new}(z)\ {\tilde {t}}(z)&{\tilde {h}}_{o}^{new}(z)\\{\tilde {g}}_{e}^{new}+{\tilde {g}}_{o}^{new}(z)\ {\tilde {t}}(z)&{\tilde {g}}_{o}^{new}(z)\end{pmatrix}}$.

Par identification, il vient :

• $\left\lbrace {\begin{matrix}{\frac {1}{\sqrt {2}}}&=&{\tilde {h_{o}}}^{new}(z)\\-{\frac {1}{\sqrt {2}}}&=&{\tilde {g_{o}}}^{new}(z)\\{\frac {1}{\sqrt {2}}}&=&{\frac {1}{\sqrt {2}}}\ {\tilde {t}}(z)+{\tilde {h_{e}}}^{new}(z)\\{\frac {1}{\sqrt {2}}}&=&-{\frac {1}{\sqrt {2}}}\ {\tilde {t}}(z)+{\tilde {g_{e}}}^{new}(z)\end{matrix}}\right.$

Dans notre cas très simple, il n’est pas nécessaire d’utiliser l’algorithme d’Euclide (pour un exemple détaillé de l’utilisation de l’algorithme d’Euclide, voir le cas de l’ondelette de Daubechies D4 ci-après) et on peut prendre

Rappel : soit

• $-{\frac {1}{8}}z^{-1}+{\frac {3}{4}}-{\frac {1}{8}}z={\tilde {t}}(z)\left({\frac {1}{4}}+{\frac {1}{4}}z\right)+{\tilde {h}}_{e}^{new}(z)$.

On applique l’algorithme d’Euclide, soit $a(z)=b(z)\ q(z)+r(z)$.

Soient ici :

• $\left\lbrace {\begin{matrix}a_{0}(z)&=&a(z)&=&-{\frac {1}{8}}z^{-1}+{\frac {3}{4}}-{\frac {1}{8}}z\\b_{0}(z)&=&b(z)&=&{\frac {1}{4}}+{\frac {1}{4}}z\end{matrix}}\right.$, et :
• $\left\lbrace {\begin{matrix}a_{1}(z)&=&b_{0}(z)\\b_{1}(z)&=&a_{0}(z)\ \%\ b_{0}(z)\\q_{1}(z)&=&a_{0}(z)\ /\ b_{0}(z)\end{matrix}}\right.$,

où $\ \%\$ est l’opérateur modulo et $\ /\$ retourne le quotient entier. La procédure est itérative, plusieurs choix sont en général possible pour le choix de l’ordre du diviseur.

• $-{\frac {1}{8}}z^{-1}+{\frac {3}{4}}-{\frac {1}{8}}z=\left\lbrace {\begin{matrix}(-{\frac {1}{2}}z^{-1}+{\frac {7}{2}})&({\frac {1}{4}}+{\frac {1}{4}}z)&-z\\(-{\frac {1}{2}}z^{-1}-{\frac {1}{2}})&({\frac {1}{4}}+{\frac {1}{4}}z)&-1\\({\frac {7}{2}}z^{-1}-{\frac {1}{2}})&({\frac {1}{4}}+{\frac {1}{4}}z)&-z^{-1}\end{matrix}}\right.$
• ${\tilde {g}}_{e}^{new}(z)=0$,

d’où :

• $\left\lbrace {\begin{matrix}{\tilde {t}}(z)&=&-1\\{\tilde {h}}_{e}^{new}(z)&=&{\frac {2}{\sqrt {2}}}\end{matrix}}\right.$.

Alors,

• ${\tilde {P}}(z)={\frac {1}{\sqrt {2}}}{\begin{pmatrix}2&1\\0&-1\end{pmatrix}}\ {\begin{pmatrix}1&0\\-1&1\end{pmatrix}}$.

Lifting primaire

On désire réécrire ${\tilde {P}}(z)$ sous la forme :

• ${\tilde {P}}(z)={\begin{pmatrix}{\tilde {h}}_{e}^{new}(z)&{\tilde {h}}_{o}^{new}(z)\\{\tilde {g}}_{e}^{new}(z)&{\tilde {g}}_{o}^{new}(z)\end{pmatrix}}\ {\begin{pmatrix}1&{\tilde {s}}(z)\\0&1\end{pmatrix}}\ {\begin{pmatrix}1&0\\-1&1\end{pmatrix}}={\frac {1}{\sqrt {2}}}\ {\begin{pmatrix}2&1\\0&-1\end{pmatrix}}\ {\begin{pmatrix}1&0\\-1&1\end{pmatrix}}$

Par identification, il vient :

• $\left\lbrace {\begin{matrix}{\frac {2}{\sqrt {2}}}&=&{\tilde {h_{e}}}^{new}(z)\\0&=&{\tilde {g_{e}}}^{new}(z)\\{\frac {1}{\sqrt {2}}}&=&{\frac {2}{\sqrt {2}}}\ {\tilde {s}}(z)+{\tilde {h_{o}}}^{new}(z)\\-{\frac {1}{\sqrt {2}}}&=&0\ {\tilde {s}}(z)+{\tilde {g_{o}}}^{new}(z)\end{matrix}}\right.$

On prend :

• ${\tilde {s}}(z)={\frac {1}{2}}$ et ${\tilde {h}}_{o}^{new}(z)=0$, et
• ${\tilde {g}}_{o}^{new}(z)=-{\frac {1}{\sqrt {2}}}$

Alors :

• ${\tilde {P}}(z)={\frac {1}{\sqrt {2}}}\ {\begin{pmatrix}2&0\\0&-1\end{pmatrix}}\ {\begin{pmatrix}1&{\frac {1}{2}}\\0&1\end{pmatrix}}\ {\begin{pmatrix}1&0\\-1&1\end{pmatrix}}$, et
• ${P}(z)={\begin{pmatrix}1&0\\1&1\end{pmatrix}}\ {\begin{pmatrix}1&-{\frac {1}{2}}\\0&1\end{pmatrix}}\ {\begin{pmatrix}{\frac {1}{2}}&0\\0&-1\end{pmatrix}}\ {\sqrt {2}}$.

Ces opérations purement matricielles s’implémentent très facilement sous Scilab ou Matlab.

On peut de façon plus condensée (que l’écriture matricielle) écrire le pseudo code pour l’algorithme de calcul in-place :

• $x_{e}$ et $x_{o}$ représentent les coefficients pairs et impairs du signal (respectivement),
• $d$ représente les détails (c.à.d. les coefficients issus du filtrage passe-haut, donc les coefficients d’ondelettes),
• $s$ représente le signal grossier (smooth) issu du filtrage passe-bas et donc les coefficients d’échelle.

Alors :

${\begin{matrix}d&=&x_{o}-x_{e};\\s&=&x_{o}+d/2;\\s&=&2/{\sqrt {2}}*s;\\d&=&-1/{\sqrt {2}}*d;\end{matrix}}$

Pour le passage à une résolution supérieure on prend le code précédent que l’on réinitialise en commençant par :

${\begin{matrix}x_{o}&=&s(1:2:length(s));\\x_{e}&=&s(2:2:length(s));\end{matrix}}$.

La reconstruction se fait en inversant l’ordre des opérations (et leurs signes, sauf pour la normalisation où l’on prend l’inverse).

${\begin{matrix}d&=&-{\sqrt {2}}*d;\\s&=&1/{\sqrt {2}}*s;\\x_{o}&=&s-d/2;\\x_{e}&=&x_{o}-d;\end{matrix}}$.

Exemple de la transformée lifting en ondelettes de Haar entières

Description de la transformée lifting en ondelettes de Haar entières

Obtenir des coefficients d’ondelettes entiers peut-être un atout lorsque :

• des valeurs entières sont recommandées (notamment pour les images),
• pour certains processeurs embarqués ne traitant que les entiers,
• l’occupation mémoire est prépondérante (un entier occupe moins de place qu’un flottant).

Lors d’une étape de lifting que l’on a étudié on a utilisé une relation de ce type :

• $x_{new}(z)\longleftarrow x(z)+s(z)\ y(z)$

Puisque le signal $y(z)$ n’est pas modifié par cette étape de lifting alors on peut arrondir et réécrire l’étape du lifting.

• $x_{new}(z)\longleftarrow x(z)+\lfloor s(z)\ y(z)\rfloor$

où $\lfloor .\rfloor$ note une opération d’arrondi.

Ce qui est très fort, c’est que, quelle que soit l’opération d’arrondi utilisée, la transformation est inversible :

• $x(z)\longleftarrow x_{new}(z)-\lfloor s(z)\ y(z)\rfloor$

Il y a cependant une précaution à prendre qui concerne la mise à l’échelle (scaling), dans le cas où ces coefficients ne sont pas entiers. La solution dans ce cas consiste à transformer cette mise à l’échelle en 3 étapes supplémentaires de lifting suivant le modèle :

• $P(z)={\begin{pmatrix}K&0\\0&{\frac {1}{K}}\end{pmatrix}}={\begin{pmatrix}1&K-K^{2}\\0&1\end{pmatrix}}\ {\begin{pmatrix}1&0\\{\frac {1}{K}}&1\end{pmatrix}}\ {\begin{pmatrix}1&K-1\\0&1\end{pmatrix}}\ {\begin{pmatrix}1&1\\1&0\end{pmatrix}}$, ou
• $P(z)={\begin{pmatrix}K&0\\0&{\frac {1}{K}}\end{pmatrix}}={\begin{pmatrix}1&0\\-1&1\end{pmatrix}}\ {\begin{pmatrix}1&1-{\frac {1}{K}}\\0&1\end{pmatrix}}\ {\begin{pmatrix}1&0\\K&1\end{pmatrix}}\ {\begin{pmatrix}1&{\frac {1}{K^{2}}}-{\frac {1}{K}}\\0&1\end{pmatrix}}$

On rappelle :

• ${\tilde {P}}(z)={\frac {1}{\sqrt {2}}}{\begin{pmatrix}2&0\\0&-1\end{pmatrix}}\ {\begin{pmatrix}1&{\frac {1}{2}}\\0&1\end{pmatrix}}\ {\begin{pmatrix}1&0\\-1&1\end{pmatrix}}={\begin{pmatrix}{\sqrt {2}}&0\\0&-{\frac {1}{\sqrt {2}}}\end{pmatrix}}\ {\begin{pmatrix}1&{\frac {1}{2}}\\0&1\end{pmatrix}}\ {\begin{pmatrix}1&0\\-1&1\end{pmatrix}}$

Pour notre ondelette de Haar, on a un signe différent dans la matrice de normalisation, il suffit juste d’adapter les expressions précédentes avec par exemple pour la première (attention cependant lors de l’inversion) :

• $P(z)={\begin{pmatrix}K&0\\0&-{\frac {1}{K}}\end{pmatrix}}={\begin{pmatrix}1&K-K^{2}\\0&-1\end{pmatrix}}\ {\begin{pmatrix}1&0\\{\frac {1}{K}}&1\end{pmatrix}}\ {\begin{pmatrix}1&K-1\\0&1\end{pmatrix}}\ {\begin{pmatrix}1&1\\1&0\end{pmatrix}}$,

avec $K={\sqrt {2}}$.

Exemple de transformée lifting en ondelettes Daubechies(4)

Description de la transformée lifting en ondelettes Daubechies(4)

Daubechies(4) signifie que les filtres de cette ondelette possèdent 4 coefficients et $n\ =\ 2$ moments nuls. On a aussi :

• ${\tilde {h}}(z)=-z^{-1}\ g(-z^{-1})$, et
• ${\tilde {g}}(z)=z^{-1}\ h(-z^{-1})$.

On trouve son expression dans les tables ou dans [Daubechies] :

• $\left\lbrace {\begin{matrix}h_{0}&=&h[0]&=&{\frac {1+{\sqrt {3}}}{4{\sqrt {2}}}}\\h_{1}&=&h[1]&=&{\frac {3+{\sqrt {3}}}{4{\sqrt {2}}}}\\h_{2}&=&h[2]&=&{\frac {3-{\sqrt {3}}}{4{\sqrt {2}}}}\\h_{3}&=&h[3]&=&{\frac {1-{\sqrt {3}}}{4{\sqrt {2}}}}\end{matrix}}\right.$

On a les propriétés intéressantes suivantes :

• $\left\lbrace {\begin{matrix}h_{0}^{2}+h_{1}^{2}+h_{2}^{2}+h_{3}^{2}=1\\h_{3}\ h_{1}+h_{2}\ h_{0}=0\\h_{1}^{2}=-{\frac {h_{2}\ h_{1}\ h_{0}}{h_{3}}}\end{matrix}}\right.$, soit :
• $\left\lbrace {\begin{matrix}h[0]&=&0,482962913145\\h[1]&=&0,836516303738\\h[2]&=&0,224143868042\\h[3]&=&-0,129409522551\end{matrix}}\right.$

• $h(z)\ =\ h_{0}+h_{1}z^{-1}+h_{2}z^{-2}+h_{3}z^{-3}$, et
• $g(z)\ =\ -h_{3}z^{2}+h_{2}z^{1}-h_{1}+h_{0}z^{-1}$
• $P(z)\ =\ {\begin{pmatrix}h_{e}(z)&g_{e}(z)\\h_{o}(z)&g_{o}(z)\end{pmatrix}}$

On a alors pour $h$ :

• $h(z)\ =\ h_{e}(z^{2})+z^{-1}h_{o}(z^{2})$
• $h(z)\ =\ h_{0}+h_{2}z^{-2}+z^{-1}(h_{1}+h_{3}z^{-2})$, d’où
• $h_{e}(z)\ =\ h_{0}+h_{2}z^{-1}$, et
• $h_{o}(z)\ =\ h_{1}+h_{3}z^{-1}$

De la même façon pour $g$ :

• $g(z)\ =\ -h_{3}z^{2}-h_{1}+z^{-1}(h_{2}z^{2}+h_{0})$
• $g_{e}(z)\ =\ -h_{3}z-h_{1}$, et :
• $g_{o}(z)\ =\ h_{2}z+h_{0}$.

D’où :

• $P(z)={\begin{pmatrix}h_{0}+h_{2}z^{-1}&-h_{3}z-h_{1}\\h_{1}+h_{3}z^{-1}&h_{2}z+h_{0}\end{pmatrix}}$

Lifting primaire

On va écrire une étape de lifting primaire :

• $P(z)={\begin{pmatrix}1&s(z)\\0&1\end{pmatrix}}{\begin{pmatrix}h_{e}^{new}(z)&g_{e}^{new}(z)\\h_{o}^{new}(z)&g_{o}^{new}(z)\end{pmatrix}}$

Alors,

• $\left\lbrace {\begin{matrix}h_{o}^{new}(z)&=&h_{1}+h_{3}z^{-1}\\g_{o}^{new}(z)&=&h_{2}z+h_{0}\\h_{0}+h_{2}z^{-1}&=&s(z)(h_{1}+h_{3}z^{-1})+h_{e}^{new}(z)\\-h_{3}z-h_{1}&=&s(z)(h_{2}z+h_{0})+g_{e}^{new}(z)\end{matrix}}\right.$

On utilise alors la division euclidienne (plusieurs factorisations sont possibles suivant l’ordre dans lequel on choisit de prendre en compte diviseur et dividende) :

Le nombre de possibilités différentes est lié aux degrés (noté $\vert {.}\vert$) des polynômes de Laurent des diviseurs et dividendes. Le degré d’un polynôme de Laurent quelconque $h(z)$ défini par :

• $h(z)=\sum \limits _{k=p}^{q}h[k]z^{-k}$

est : $\vert {h}\vert =q-p$. Soit $a=b\ q+r$ l’expression de la division euclidienne des polynômes $a$ par $b$, alors

• si les degrés du diviseur et du dividende sont égaux, alors le nombre de possibilités est $4.3^{\vert {b}\vert -1}$,
• si maintenant $\vert {a}\vert =\vert {b}\vert +1$, alors le nombre de possibilités est $3^{\vert {b}\vert }$.

Par exemple :

ou alors :

etc.

On se limite à l’exploration de la première solution (les autres aboutiront aussi à des formulations différentes mais équivalentes).

On a alors :

• $s(z)={\frac {h_{2}}{h_{3}}}$, et
• $h_{e}^{new}(z)={\frac {h_{3}h_{0}-h_{2}h_{1}}{h_{3}}}$

On explicite alors $g_{e}^{new}(z)$ :

• ${\begin{matrix}g_{e}^{new}(z)&=&-h_{3}z-h1-{\frac {h_{2}}{h_{3}}}(h_{2}z+h_{0})\\&=&-({\frac {h_{3}^{2}+h_{2}^{2}}{h_{3}}})z-{\frac {h_{1}h_{3}+h_{2}h_{0}}{h_{3}}}\\&=&-({\frac {h_{3}^{2}+h_{2}^{2}}{h_{3}}})z\end{matrix}}$, d’où
• $P(z)={\begin{pmatrix}1&{\frac {h2}{h3}}\\0&1\end{pmatrix}}\ {\begin{pmatrix}{\frac {h_{3}h_{0}-h_{2}h_{1}}{h_{3}}}&-{\frac {h_{3}^{2}+h_{2}^{2}}{h_{3}}}z\\h_{1}+h_{3}z^{-1}&h_{2}z+h_{0}\end{pmatrix}}$

Lifting dual

Maintenant, le lifting dual :

• $P(z)={\begin{pmatrix}1&{\frac {h2}{h3}}\\0&1\end{pmatrix}}\ {\begin{pmatrix}1&0\\t(z)&1\end{pmatrix}}\ {\begin{pmatrix}h_{e}^{new}(z)&g_{e}^{new}(z)\\h_{o}^{new}(z)&g_{o}^{new}(z)\end{pmatrix}}={\begin{pmatrix}1&{\frac {h2}{h3}}\\0&1\end{pmatrix}}\ {\begin{pmatrix}{\frac {h_{3}h_{0}-h_{2}h_{1}}{h_{3}}}&-{\frac {h_{3}^{2}+h_{2}^{2}}{h_{3}}}z\\h_{1}+h_{3}z^{-1}&h_{2}z+h_{0}\end{pmatrix}}$

Alors,

• $\left\lbrace {\begin{matrix}h_{e}^{new}(z)&=&{\frac {h_{3}h_{0}-h_{2}h_{1}}{h_{3}}}\\g_{e}^{new}(z)&=&-{\frac {h_{3}^{2}+h_{2}^{2}}{h_{3}}}z\\h_{1}+h_{3}z^{-1}&=&t(z)({\frac {h_{3}h_{0}-h_{2}h_{1}}{h_{3}}})+h_{o}^{new}(z)\\h_{2}z+h_{0}&=&t(z)(-{\frac {h_{3}^{2}+h_{2}^{2}}{h_{3}}}z)+g_{o}^{new}(z)\end{matrix}}\right.$

Effectuons la division euclidienne suivante :

• .

Donc :

• $t(z)={\frac {h_{3}h_{1}}{h_{3}h_{0}-h_{2}h_{1}}}+{\frac {h_{3}^{2}}{h_{3}h_{0}-h_{2}h_{1}}}z^{-1}$ et
• $h_{o}^{new}(z)=0$, alors,
• ${\begin{matrix}g_{o}^{new}(z)&=&h_{2}z+h_{0}-\left({\frac {h_{3}h_{1}+h_{3}^{2}z^{-1}}{h_{3}h_{0}-h_{2}h_{1}}}\right)\ \left(-{\frac {h_{3}^{2}+h_{2}^{2}}{h_{3}}}z\right)\\&=&\left(h_{2}+{\frac {h_{1}(h_{3}^{2}+h_{2}^{2})}{h_{3}h_{0}-h_{2}h_{1}}}\right)z+{\frac {h_{3}(h_{3}^{2}+h_{2}^{2})}{h_{3}h_{0}-h_{2}h_{1}}}+h_{0}\end{matrix}}$.

Or,

• $h_{2}+{\frac {h_{1}(h_{3}^{2}+h_{2}^{2})}{h_{3}h_{0}-h_{2}h_{1}}}=0$,

d’où

• $g_{o}^{new}(z)={\frac {h_{3}(h_{3}^{2}+h_{2}^{2})}{h_{3}h_{0}-h_{2}h_{1}}}+h_{0}$.

Voilà :

• $P(z)={\begin{pmatrix}1&{\frac {h_{2}}{h_{3}}}\\0&1\end{pmatrix}}\ {\begin{pmatrix}1&0\\{\frac {h_{3}h_{1}}{h_{3}h_{0}-h_{2}h_{1}}}+{\frac {h_{3}^{2}}{h_{3}h_{0}-h_{2}h_{1}}}z^{-1}&1\end{pmatrix}}\ {\begin{pmatrix}{\frac {h_{3}h_{0}-h_{2}h_{1}}{h_{3}}}&-{\frac {h_{3}^{2}+h_{2}^{2}}{h_{3}}}z\\0&{\frac {h_{3}(h_{3}^{2}+h_{2}^{2})}{h_{3}h_{0}-h_{2}h_{1}}}+h_{0}\end{pmatrix}}$

On peut maintenant mettre en évidence la mise à l’échelle d’abord en réécrivant un peu les derniers coefficients obtenus à l’aide des formules sur les coefficients $h_{i},0\leq i\leq 3$ :

• $-{\frac {h_{3}^{2}+h_{2}^{2}}{h_{3}}}={\frac {h_{3}}{h_{3}h_{0}-h_{2}h_{1}}}$ et
• ${\frac {h_{3}(h_{3}^{2}+h_{2}^{2})}{h_{3}h_{0}-h_{2}h_{1}}}+h_{0}=h_{3}{\frac {h_{3}^{2}+h_{2}^{2}+h_{0}^{2}-{\frac {h_{2}h_{1}h_{0}}{h_{3}}}}{h_{3}h_{0}-h_{2}h_{1}}}={\frac {h_{3}}{h_{3}h_{0}-h_{2}h_{1}}}$,

donc,

• $P(z)={\begin{pmatrix}1&{\frac {h2}{h3}}\\0&1\end{pmatrix}}\ {\begin{pmatrix}1&0\\{\frac {h_{3}h_{1}}{h_{3}h_{0}-h_{2}h_{1}}}+{\frac {h_{3}^{2}}{h_{3}h_{0}-h_{2}h_{1}}}z^{-1}&1\end{pmatrix}}\ {\begin{pmatrix}{\frac {h_{3}h_{0}-h_{2}h_{1}}{h_{3}}}&{\frac {h_{3}}{h_{3}h_{0}-h_{2}h_{1}}}z\\0&{\frac {h_{3}}{h_{3}h_{0}-h_{2}h_{1}}}\end{pmatrix}}$

Mise à l’échelle

On peut donc introduire l’étape de mise à l’échelle (normalisation), en remarquant que :

• ${\begin{pmatrix}K&{\frac {1}{K}}z\\0&{\frac {1}{K}}\end{pmatrix}}={\begin{pmatrix}1&z\\0&1\end{pmatrix}}\ {\begin{pmatrix}K&0\\0&{\frac {1}{K}}\end{pmatrix}}$

d’où finalement :

• $P(z)={\begin{pmatrix}1&{\frac {h2}{h3}}\\0&1\end{pmatrix}}\ {\begin{pmatrix}1&0\\{\frac {h_{3}h_{1}}{h_{3}h_{0}-h_{2}h_{1}}}+{\frac {h_{3}^{2}}{h_{3}h_{0}-h_{2}h_{1}}}z^{-1}&1\end{pmatrix}}\ {\begin{pmatrix}1&z\\0&1\end{pmatrix}}\ {\begin{pmatrix}{\frac {h_{3}h_{0}-h_{2}h_{1}}{h_{3}}}&0\\0&{\frac {h_{3}}{h_{3}h_{0}-h_{2}h_{1}}}\end{pmatrix}}$,

c’est-à-dire :

• $P(z)={\begin{pmatrix}1&-{\sqrt {3}}\\0&1\end{pmatrix}}\ {\begin{pmatrix}1&0\\{\frac {\sqrt {3}}{4}}+{\frac {{\sqrt {3}}-2}{4}}z^{-1}&1\end{pmatrix}}\ {\begin{pmatrix}1&z\\0&1\end{pmatrix}}\ {\begin{pmatrix}{\frac {{\sqrt {3}}+1}{\sqrt {2}}}&0\\0&{\frac {{\sqrt {3}}-1}{\sqrt {2}}}\end{pmatrix}}$, et alors :
• ${\tilde {P}}(z)={\begin{pmatrix}{\frac {{\sqrt {3}}-1}{\sqrt {2}}}&0\\0&{\frac {{\sqrt {3}}+1}{\sqrt {2}}}\end{pmatrix}}\ {\begin{pmatrix}1&-z\\0&1\end{pmatrix}}\ {\begin{pmatrix}1&0\\-{\frac {\sqrt {3}}{4}}-{\frac {{\sqrt {3}}-2}{4}}z^{-1}&1\end{pmatrix}}\ {\begin{pmatrix}1&{\sqrt {3}}\\0&1\end{pmatrix}}$

Simplification de la mise en œuvre

On peut de façon plus condensée (que l’écriture matricielle) écrire le pseudo-code pour l’algorithme de calcul in situ :

• $x_{e}$ et $x_{o}$ représente les coefficients pairs et impairs du signal (respectivement),
• $d$ représente les détails (c.à.d. les coefficients issu du filtrage passe-haut, donc les coefficients d’ondelettes),
• $s$ représente le signal grossier (smooth) issu du fitlrage passe-bas et donc les coefficients d’échelle.

${\begin{matrix}s&=&x_{o}+{\sqrt {3}}x_{e};\\d&=&x_{e}-{\sqrt {3}}/4*s-({\sqrt {3}}-2)/4*[0\ s(1:1:length(s)-1)];\\s&=&s-[d(2:1:length(d))\ 0];\\d&=&({\sqrt {3}}+1)/{\sqrt {2}}*d;\\s&=&({\sqrt {3}}-1)/{\sqrt {2}}*s;\end{matrix}}$

Pour le passage à une résolution supérieure, on prend le code précédent que l’on réinitialise en commençant par :

${\begin{matrix}x_{o}&=&s(1:2:length(s));\\x_{e}&=&s(2:2:length(s));\end{matrix}}$

L’implémentation peut se faire facilement suivant l’exemple de la Figure 8.

Figure 8

Figure 8. Schéma d’une implémentation du lifting

Articles connexes

• Transformée en ondelettes discrète
• Transformée en cosinus discrète
• Compression par ondelettes

Références externes

• Ronan Le Page, Lifting en ondelettes, dont cet article est issu : avec l'implémentation en Scilab des algorithmes et une version pdf du document ici.
• l’excellent tutoriel de Clemens Valens (http://www.polyvalens.com/blog/wavelets/).
• articles de Wim Sweldens (disponibles sur son site)
• http://www-lmc.imag.fr/lmc-mosaic/Claire.Chauvin/these/index.html Les ondelettes comme fonctions de base dans le calcul des structures électroniques - Claire Chauvin (IMAG)
• http://www.ima.umn.edu/industrial/97_98/sweldens/fourth.html
• le livre Second Generation Wavelets and Applications by Maarten H. Jansen, Patrick J. Oonincx