3. 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 = {f1, f2, ..., fN}, que l'on assimile au lissage de notre signal à l'échelle la plus fine considérée : s0 = f, sa transformée en ondelettes dyadique lui associe une suite de N lg(N) coefficients. On calcule tout d'abord s1 = Hs0, puis s2 = Hs1, s3 = Hs2, 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 : d1 = Gs0, puis d2 = Gs1, d3 = Gs
… pour nos abonnés, l'article se prolonge sur 8 pages…
