Autre exemple l'ondelette Daubechies(4) version lifting

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] :

$$\begin{array}{ccc} h_0 = h[0] &=& \frac{1+\sqrt{3}}{4\sqrt{... ...}}\\ h_3 = h[3] &=& \frac{1-\sqrt{3}}{4\sqrt{2}} \end{array}$$

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

$$\begin{array}{l} h_0^2+h_1^2+h_2^2+h_3^2=1 \\ h_3h_1+h_2h_0=0\\ h_1^2=-\frac{h_2h_1h_0}{h_3} \end{array}$$

soient

$$\begin{array}{ccc} h[0]&=&.482962913145\\ h[1]&=&.836516303738\\ h[2]&=&.224143868042\\ h[3]&=&-.129409522551 \end{array}$$

$$h(z)=h_0 + h_1 z^{-1} + h_2 z^{-2} + h_3z^{-3}$$

et

$$g(z)=-h_3 z^2 + h_2 z^{1} - h_1 + h_0z^{-1}$$

$$P(z)=\left( \begin{array}{cc} h_e(z) & g_e(z)\\ h_o(z) & g_o(z) \end{array}\right)$$

$${h}(z)={h}_e(z^2) + z^{-1} {h}_o(z^2)$$

$${h}(z)={h}_0+h_2z^{-2} + z^{-1} (h_1+h_3z^{-2})$$

d'où

$${h}_e(z)=h_0+h_2z^{-1}$$

et

$${h}_o(z)=h_1+h_3 z^{-1}$$

de la même façon pour ${g}$

$$g(z)=-h_3z^2-h_1 + z^{-1} ( h_2z^2+h_0)$$

$${g}_e(z)=-h_3z-h_1$$

et

$${g}_o(z)=h_2z+h_0$$

d'où

$${P}(z)=\left( \begin{array}{cc} h_0+h_2z^{-1} & -h_3z-h_1\\ h_1+h_3 z^{-1}& h_2z+h_0 \end{array}\right)$$

On va écrire une étape de lifting primaire :

$$P(z)=\left( \begin{array}{cc} 1 & s(z)\\ 0 & 1 \end{array}\... ...g_e^{new}(z)\\ h_o^{new}(z) & g_o^{new}(z) \end{array}\right)$$

Alors,

$$\left\lbrace \begin{array}{l} h_o^{new}(z)=h_1+h_3z^{-1}\\ ... ...\\ -h_3z-h_1=s(z) (h_2z+h_0) +g_e^{new}(z) \end{array}\right.$$

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

Par exemple :

$$\begin{array}{rl\vert c} h_2z^{-1} &+h_0 & h_3z^{-1}+h_1\\ ... ... \\ \cline{1-2} 0 &+ \frac{h_3h_0-h_2h_1}{h_3} & \end{array}$$

ou alors

$$\begin{array}{rl\vert c} h_0 &+h_2z^{-1} &h_1+h_3z^{-1}\\ \... ...cline{1-2} 0 &+ \frac{h_2h_1-h_3h_0}{h_1}z^{-1} & \end{array}$$

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_3h_0-h_2h_1}{h_3}$$

on explicite alors $g_e^{new}(z)$ :

$$\begin{array}{lll} g_e^{new}(z) & = & -h_3z-h1-\frac{h_2}{h_... ...3+h_2h_0}{h_3}\\ & = &-(\frac{h_3^2+h_2^2}{h_3})z \end{array}$$

d'où

$$P(z)=\left( \begin{array}{cc} 1 & \frac{h2}{h3}\\ 0 & 1 \en... ...^2+h_2^2}{h_3}z\\ h_1+h_3z^{-1} & h_2z+h_0 \end{array}\right)$$

Maintenant, le lifiting dual :

$$P(z)=\left(\begin{array}{cc} 1 & \frac{h2}{h3}\\ 0 & 1 \end... ...^2+h_2^2}{h_3}z\\ h_1+h_3z^{-1} & h_2z+h_0 \end{array}\right)$$

alors,

$$\left\lbrace \begin{array}{l} h_e^{new}(z)=\frac{h_3h_0-h_2h... ... (-\frac{h_3^2+h_2^2}{h_3}z) + g_o^{new}(z) \end{array}\right.$$

$$\begin{array}{rc\vert c} h_1 &+h_3z^{-1} &\frac{h_3h_0-h_2h_... ...1} & \\ & -( h_3z^{-1}) & \\ \cline{1-2} & 0 & \end{array}$$

donc

$$t(z)=\frac{h_3h_1}{h_3h_0-h_2h_1} + \frac{h_3^2}{h_3h_0-h_2h_1}z^{-1}$$

et

$$h_o^{new}(z)=0$$

alors,

$$\begin{array}{ll} g_o^{new}(z)&=h_2z+h_0-\left(\frac{h_3h_1+... ...ght) z + \frac{h_3(h_3^2+h_2^2)}{h_3h_0-h_2h_1}+h_0 \end{array}$$

Or

$$h_2 +\frac{h_1(h_3^2+h_2^2)}{h_3h_0-h_2h_1}=0$$

d'où

$$g_o^{new}(z)=\frac{h_3(h_3^2+h_2^2)}{h_3h_0-h_2h_1}+h_0$$

Voilà :

$$P(z)=\left(\begin{array}{cc} 1 & \frac{h_2}{h_3}\\ 0 & 1 \e... ... \frac{h_3(h_3^2+h_2^2)}{h_3h_0-h_2h_1}+h_0 \end{array}\right)$$

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\le i\le 3$) :

$$\frac{h_3(h_3^2+h_2^2)}{h_3h_0-h_2h_1}+h_0=h_3 \frac{h_3^2 +h_2^2 + h_0^2-\frac{h_2h_1h_0}{h_3}}{h_3h_0-h_2h_1}$$

d'où

$$\frac{h_3(h_3^2+h_2^2)}{h_3h_0-h_2h_1}+h_0=\frac{h_3}{h_3h_0-h_2h_1}$$

et

$$P(z)= \left(\begin{array}{cc} 1 & \frac{h2}{h3}\\ 0 & 1 \en... ...2}{h_3} z \\ 0 & \frac{h_3}{h_3h_0-h_2h_1} \end{array}\right)$$

On a aussi

$$-\frac{h_3^2+h_2^2}{h_3}= \frac{h_3}{h_3h_0-h_2h_1}$$

$$P(z)= \left(\begin{array}{cc} 1 & \frac{h2}{h3}\\ 0 & 1 \en... ...h_2h_1} z \\ 0 & \frac{h_3}{h_3h_0-h_2h_1} \end{array}\right)$$

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

$$\left(\begin{array}{cc} K & \frac{1}{K} z \\ 0 & \frac{1}{K... ...\begin{array}{cc} K & 0 \\ 0 & \frac{1}{K} \end{array}\right)$$

d'où finalement

$$P(z)= \left(\begin{array}{cc} 1 & \frac{h2}{h3}\\ 0 & 1 \en... ...{h_3} & 0 \\ 0 & \frac{h_3}{h_3h_0-h_2h_1} \end{array}\right)$$

c'est-à-dire

$$P(z)= \left(\begin{array}{cc} 1 & -\sqrt{3}\\ 0 & 1 \end{ar... ...2}} & 0 \\ 0 & \frac{\sqrt{3}-1}{\sqrt{2}} \end{array}\right)$$

et alors :

$$\tilde{P}(z)= \left(\begin{array}{cc} \frac{\sqrt{3}-1}{\sqr... ...eft(\begin{array}{cc} 1 & \sqrt{3}\\ 0 & 1 \end{array}\right)$$

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ésente les coefficients pairs et impairs du signal (respectivement), $d$ représente les détails (i.e. 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{array}{l} s=x_o+\sqrt{3}x_e;\\ d=x_e-\sqrt{3}/4*s-(\... ...qrt{3}+1)/\sqrt{2}*d;\\ s=(\sqrt{3}-1)/\sqrt{2}*s; \end{array}$$

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{array}{l} x_o=s(1:2:length(s));\\ x_e=s(2:2:length(s));\\ \end{array}$$

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

Figure 8: Schéma d'une implémentation du lifting