Fast Algorithms for Discrete and Continuous
Olivier Rioul, Pierre Duhamel · 1992
Several algorithms are reviewed for computing var- ious types of wavelet transforms: the Mallat algorithm, the trous algorithm and their generalizations by Shensa. The goal is 1) to develop guidelines for implementing discrete and contin- uous wavelet transforms efficiently, 2) to compare the various algorithms obtained and give an idea of possible gains by providing operation counts. The computational structure of the algorithms rather than the mathematical relationship between transforms and algorithms, is focused upon. Most wavelet trans- form algorithms compute sampled coefficients of the continuous wavelet transform using the filter bank structure of the discrete wavelet transform. Although this general method is already efficient, it is shown that noticeable computational savings can be obtained by applying known convolution techniques (such as the FFT) in a suitable manner. The modified algorithms are termed because of their ability to reduce the compu- tational complexity per computed coefficient from L to log L (within a small constant factor) for large filter lengths L. For short filters, we obtain smaller gains: fast running FIR filter- ing techniques allow one to achieve typically 30% save in computations. This is still of practical interest when heavy computation of wavelet transforms is required, and the resulting algorithms remain easy to implement. Index Terms-Discrete wavelet transform, continuous wavelet transform, octave-band filter banks, computational complexity, Fourier transform, FIR filtering algorithms.