For faster navigation, this Iframe is preloading the Wikiwand page for
Lifting en ondelettes.
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) moments nuls, produit une transformée dont les propriétés sont similaires à une ondelette à moments nuls supérieur à .
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).
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.
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 les coefficients d’ondelettes et par les coefficients d’échelle obtenus par la transformation.
Pour une ondelette particulière (c.à.d. un couple de filtres ou dans l’implémentation par banc de filtres) caractérisée en outre par (disons) 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 moments nuls pour le filtre dual, le schéma d’implantation par lifting permet d’obtenir facilement des ondelettes de moments et 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 passe par les deux filtres complémentaires (passe-bas) et (passe-haut), en sortie on peut sous-échantillonner par 2 et on obtient alors respectivement des coefficients d’ondelettes et des coefficients d’échelle .
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 et passage par les filtres de synthèse et , puis par simple addition pour obtenir le signal .
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 :
Attention aux notations utilisées ci-dessus :
dans certaines références, on trouve souvent et .
dans les expressions des filtres, le coefficient souligné correspond à l’indice .
Les filtres doivent en outre satisfaire les formules suivantes :
On a besoin de construire la matrice polyphase ainsi que sa matrice duale (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 :
, où désigne les échantillons pairs (even) et les échantillons impairs (odd) (moyen mnémotechnique : even a un nombre de lettres pair, odd a un nombre de lettres impair).
Il vient assez facilement :
sachant que , et que pour , on a les propriétés suivantes :
Ces propriétés montrent que pour passer de l’analyse à la synthèse (de à , il suffit si , de prendre la matrice des cofacteurs en changeant de signe.
De plus sachant que (l’inversion temporelle est nécessaire pour compenser le délai introduit par le filtrage) :
L’élévation primaire (primary lifting) est aussi appelé update. Le lifting à proprement parler consiste à modifier le filtre en gardant la complémentarité avec à l’aide de la formule :
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.
,
,
et
,
,
où 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 :
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 :
en :
,
qui est une forme de division avec reste (pour réaliser la division avec reste, on utilise l’algorithme d’Euclide) où est le reste.
Alors :
.
En itérant cet exemple, on peut arriver à obtenir une matrice polyphase qui est de la forme :
,
où et 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.
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
.
On applique l’algorithme d’Euclide, soit .
Soient ici :
, et :
,
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.
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 :
Puisque le signal n’est pas modifié par cette étape de lifting alors on peut arrondir et réécrire l’étape du lifting.
où 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 :
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 :
, ou
On rappelle :
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) :
,
avec .
Exemple de transformée lifting en ondelettes Daubechies(4)
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é ) des polynômes de Laurent des diviseurs et dividendes. Le degré d’un polynôme de Laurent quelconque défini par :
est : . Soit l’expression de la division euclidienne des polynômes par , alors
si les degrés du diviseur et du dividende sont égaux, alors le nombre de possibilités est ,
si maintenant , alors le nombre de possibilités est .
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 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 :
This browser is not supported by Wikiwand :( Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience. Please download and use one of the following browsers:
Your input will affect cover photo selection, along with input from other users.
X
Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?
Oh no, there's been an error
Please help us solve this error by emailing us at support@wikiwand.com
Let us know what you've done that caused this error, what browser you're using, and whether you have any special extensions/add-ons installed.
Thank you!