Lifting en ondelettes

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 ${\displaystyle \ \gamma \ }$ les coefficients d’ondelettes et par ${\displaystyle \ \lambda \ }$ les coefficients d’échelle obtenus par la transformation.

Pour une ondelette particulière (c.à.d. un couple de filtres ${\displaystyle (h,\ g)}$ ou ${\displaystyle ({\tilde {h}},\ {\tilde {g}})}$ dans l’implémentation par banc de filtres) caractérisée en outre par (disons) ${\displaystyle \ 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 ${\displaystyle \ {\tilde {n}}\ }$ moments nuls pour le filtre dual, le schéma d’implantation par lifting permet d’obtenir facilement des ondelettes de moments ${\displaystyle \ n\ }$ et ${\displaystyle \ {\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 ${\displaystyle \left(\ X\ \right)}$ passe par les deux filtres complémentaires ${\displaystyle \left[\ {\tilde {h}}\ \right]}$ (passe-bas) et ${\displaystyle \left[\ {\tilde {g}}\ \right]}$ (passe-haut), en sortie on peut sous-échantillonner par 2 ${\displaystyle \left[\ \downarrow 2\ \right]}$ et on obtient alors respectivement des coefficients d’ondelettes ${\displaystyle \left(\ \gamma \ \right)}$ et des coefficients d’échelle ${\displaystyle \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 ${\displaystyle \left[\ \uparrow 2\ \right]}$ et passage par les filtres de synthèse ${\displaystyle \left[\ h\ \right]}$ et ${\displaystyle \left[\ g\ \right]}$, puis par simple addition pour obtenir le signal ${\displaystyle \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.

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 :

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

Attention aux notations utilisées ci-dessus :

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

Les filtres doivent en outre satisfaire les formules suivantes :

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

On a besoin de construire la matrice polyphase ${\displaystyle {\tilde {P}}}$ ainsi que sa matrice duale ${\displaystyle {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 :

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

• ${\displaystyle {\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}}}$
• ${\displaystyle {\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}}}$
• ${\displaystyle {\tilde {P}}(z)={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}$

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

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

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

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

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

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

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

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

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

• ${\displaystyle 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 :

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

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

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

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

Dès lors,

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

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.

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

et

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

où ${\displaystyle 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 :

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

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 :

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

en :

• ${\displaystyle {\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ù ${\displaystyle {\tilde {g}}_{new}}$ est le reste.

Alors :

• ${\displaystyle {\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 :

• ${\displaystyle 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ù ${\displaystyle K_{1}}$ et ${\displaystyle 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.

On veut :

• ${\displaystyle {\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}}}$,

• ${\displaystyle {\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 :

• ${\displaystyle \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

• ${\displaystyle -{\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 ${\displaystyle a(z)=b(z)\ q(z)+r(z)}$.

Soient ici :

• ${\displaystyle \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 :
• ${\displaystyle \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ù ${\displaystyle \ \%\ }$ est l’opérateur modulo et ${\displaystyle \ /\ }$ 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.

• ${\displaystyle -{\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.}$
• ${\displaystyle {\tilde {g}}_{e}^{new}(z)=0}$,

d’où :

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

Alors,

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

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

• ${\displaystyle {\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 :

• ${\displaystyle \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 :

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

Alors :

• ${\displaystyle {\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
• ${\displaystyle {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 :

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

Alors :

${\displaystyle {\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 :

${\displaystyle {\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).

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

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 :

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

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

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

où ${\displaystyle \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 :

• ${\displaystyle 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 :

• ${\displaystyle 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
• ${\displaystyle 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 :

• ${\displaystyle {\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) :

• ${\displaystyle 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 ${\displaystyle K={\sqrt {2}}}$.

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

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

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

• ${\displaystyle \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 :

• ${\displaystyle \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 :
• ${\displaystyle \left\lbrace {\begin{matrix}h[0]&=&0,482962913145\\h[1]&=&0,836516303738\\h[2]&=&0,224143868042\\h[3]&=&-0,129409522551\end{matrix}}\right.}$

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

On a alors pour ${\displaystyle h}$ :

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

De la même façon pour ${\displaystyle g}$ :

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

D’où :

• ${\displaystyle 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}}}$

On va écrire une étape de lifting primaire :

• ${\displaystyle 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,

• ${\displaystyle \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é ${\displaystyle \vert {.}\vert }$) des polynômes de Laurent des diviseurs et dividendes. Le degré d’un polynôme de Laurent quelconque ${\displaystyle h(z)}$ défini par :

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

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

• si les degrés du diviseur et du dividende sont égaux, alors le nombre de possibilités est ${\displaystyle 4.3^{\vert {b}\vert -1}}$,
• si maintenant ${\displaystyle \vert {a}\vert =\vert {b}\vert +1}$, alors le nombre de possibilités est ${\displaystyle 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 :

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

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

• ${\displaystyle {\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ù
• ${\displaystyle 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}}}$

Maintenant, le lifting dual :

• ${\displaystyle 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,

• ${\displaystyle \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 :

• ${\displaystyle 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
• ${\displaystyle h_{o}^{new}(z)=0}$, alors,
• ${\displaystyle {\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,

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

d’où

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

Voilà :

• ${\displaystyle 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 ${\displaystyle h_{i},0\leq i\leq 3}$ :

• ${\displaystyle -{\frac {h_{3}^{2}+h_{2}^{2}}{h_{3}}}={\frac {h_{3}}{h_{3}h_{0}-h_{2}h_{1}}}}$ et
• ${\displaystyle {\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,

• ${\displaystyle 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}}}$