ONDELETTES

3. Des algorithmes rapides

L'une des raisons essentielles du succès rencontré par les méthodes fondées sur la transformation de Fourier tient dans l'existence d'algorithmes rapides de calcul qui lui sont associés (la fameuse F.F.T. [Fast Fourier Transform]). Or il s'est avéré que les transformations en ondelettes discrètes, pour peu que l'ondelette soit convenablement choisie, sont naturellement associées à des algorithmes qui peuvent être encore plus efficaces que les algorithmes de F.F.T.

Pour saisir le fonctionnement de ces algorithmes, il nous faut revenir à la multirésolution, brièvement évoquée plus haut, en se limitant au cas de transformations en ondelettes dites dyadiques, c'est-à-dire conservant une certaine redondance. Le cas des décompositions en bases d'ondelettes sera évoqué un peu plus loin. Les coefficients d'ondelettes d'un signal sont obtenus à partir d'une série de lissages du signal, à des résolutions de plus en plus grossières. La remarque clé (faite initialement dans un contexte de codage du signal de parole, puis en traitement d'images) est que ces lissages peuvent être effectués de façon récursive, en utilisant de façon systématique un unique opérateur de lissage, que l'on peut noter H. H transforme une suite de nombres en une autre suite, lissée. Plus précisément, partant d'un signal échantillonné, c'est-à-dire d'une série de N nombres f = {f₁, f₂, ..., f_N}, que l'on assimile au lissage de notre signal à l'échelle la plus fine considérée : s₀ = f, sa transformée en ondelettes dyadique lui associe une suite de N lg(N) coefficients. On calcule tout d'abord s₁ = Hs₀, puis s₂ = Hs₁, s₃ = Hs₂, et ainsi de suite, jusqu'à l'échelle la plus grande. On montre que les coefficients d'ondelettes eux aussi s'obtiennent suivant une règle similaire, en utilisant un autre opérateur que l'on peut noter G : d₁ = Gs₀, puis d₂ = Gs₁, d₃ = Gs₂,...

Le fait d'effectuer des opérations identiques à toutes les résolutions est en lui-même remarquable si l'on songe que le but de cet algorithme est de manipuler des ondelettes dont la taille croît proportionnellement à l'échelle. Cela devrait logiquement se traduire par des coûts en temps de calcul de plus en plus élevés quand l'échelle devient grande. Or il n'en est rien. Il est facile de démontrer que le nombre d'opérations élémentaires (additions et multiplications) effectuées par les opérateurs H et G est proportionnel à N, le nombre d'échantillons du signal de départ. Comme le nombre d'échelles est proportionnel au logarithme de N (cela résulte du fait que les échelles sont en progression géométrique et de ce que l'échelle maximale à considérer ne peut être supérieure à la longueur du signal), nous aboutissons à un nombre d'opérations élémentaires proportionnel à N lg(N). On dit que l'on a un algorithme de complexité N lg(N).

Des considérations tout à fait similaires conduisent à des algorithmes efficaces de reconstruction d'un signal à partir de ses coefficients d'ondelettes, eux aussi de complexité N lg(N). Ces algorithmes font également appel aux mêmes opérateurs G et H.

Dans le cas d'une transformation en ondelettes sans redondance, le nombre de coefficients d'ondelettes calculés est alors égal à N exactement. La procédure est strictement la même que plus haut, à ceci près que les opérateurs H et G sont légèrement différents (en fait un peu plus simples) et que le nombre d'opérations qu'ils effectuent est maintenant fonction décroissante de l'échelle (en fait, inversement proportionnel à l'échelle). De là, on montre que les algorithmes correspondants de décomposition en base d'ondelettes et de reconstruction sont de complexité N (au lieu de N lg(N) comme[...]