3.3.4 Algorithme à trous

L'algorithme à trous est un algorithme très général et valable pour toute interpolation embo^tée. En effet, à partir d'une interpolation linéaire, on peut montrer qu'il est possible de calculer de manière exacte la transformée en ondelettes d'une fonction connaissant ses coefficients d'interpolation à l'échelle 1 d'échantillonnage. Cette hypothèse s'écrit :

où est la fonction originale, et les valeurs initiales, produit scalaire de avec la base échantillonnée au pas 1. Dans la théorie classique d'échantillonnage, la fonction est égale à . Les coefficients de l'approximation lissée du signal à l'échelle s'écrivent :

Si engendre une base d'interpolation embo^tée, on a :

Le calcul de devient donc :

On a donc une convolution avec le filtre symétrique et avec un pas entre éléments de créant des trous, d'où le nom de l'algorithme.

Les coefficients en ondelettes à l'échelle sont obtenus par :

Si l'ondelette est choisie comme étant le résultat de la différence de deux interpolations, alors les coefficients en ondelettes sont donnés par :

Une seule convolution est donc effectuée par échelle.

La reconstruction est effectuée en sommant tous les coefficients en ondelettes obtenus et l'approximation à la dernière échelle du signal (notée ) :

Cependant, le calcul de la transformée en ondelettes du signal reconstruit (par la méthode donnée par l'équation (1.49)) ne donne pas les mêmes coefficients en ondelette que la transformée du signal original. Par conséquent, on applique un algorithme itératif à la transformée inverse afin qu'au bout de quelques itérations, la transformée du signal original soit égale à celle du signal reconstruit. Il est possible d'utiliser l'algorithme d'inversion de Van Cittert pour reconstruire le signal.

L'avantage de l'algorithme à trou par rapport à l'algorithme de Mallat est qu'il permet le calcul de la transformée sur l'ensemble des abcisses. En revanche, cet avantage est aussi un inconvénient puisque la relation signal original - signal transformé n'est pas bi-univoque, ce qui implique que la reconstruction du signal original à partir de ces coefficients et signaux transformés n'est pas exacte.