Schnelle Wavelet-Transformation

Die schnelle Wavelet-Transformation, englisch fast wavelet transform, ist ein effizientes Verfahren zur Berechnung einer diskreten Wavelet-Transformation. Sie kann mit der Anwendung der schnellen Fourier-Transformation zur Berechnung der Koeffizienten einer Fourier-Reihe verglichen werden.

Konstruktion

Analyse-Filterbank, ${\displaystyle g=a^{-},h=b^{-}}$

Rekursive Anwendung einer Analyse-Filterbank

Ein gegebenes kontinuierliches Signal ${\displaystyle f}$ wird zunächst durch orthogonale Projektion auf einen Unterraum ${\displaystyle V_{-J}}$ einer orthogonalen Multiskalenanalyse in eine zeitdiskrete Koeffizientenfolge ${\displaystyle s^{(-J)}}$ umgewandelt. Je größer ${\displaystyle J}$ ist, desto genauer ist die dadurch erzielte Approximation. In vielen Fällen ist es ausreichend,

${\displaystyle s_{n}^{(-J)}:=2^{-J/2}\,f(n/2^{J})}$

zu setzen. Nun wird rekursiv aus jedem Tiefpasssignal ${\displaystyle s^{(k)}}$ ein neues Tiefpasssignal

${\displaystyle s^{(k+1)}={\frac {1}{\sqrt {2}}}(\downarrow 2)(a_{-}*s^{(k)})}$

und das Hochpasssignal

${\displaystyle d^{(k+1)}={\frac {1}{\sqrt {2}}}(\downarrow 2)(b_{-}*s^{(k)})}$

erzeugt. Zusammen bilden diese eine Analyse-Filterbank, die Operationen darin werden weiter unten erklärt.

Nach ${\displaystyle M}$ Schritten der Rekursion ergeben sich die Folgen

${\displaystyle d^{(-J+1)},\dots ,d^{(-J+M)}}$   und   ${\displaystyle s^{(-J+M)}}$.

Das Ziel dieser Transformation ist, dass die ${\displaystyle d^{(k)}}$ „dünn“ besetzt sind und sich daher gut komprimieren lassen.

Sind die Filter ${\displaystyle a}$ und ${\displaystyle b}$ ausreichend frequenzselektiv, war das Ausgangssignal bandbeschränkt und wurde dem WKS-Abtasttheorem entsprechend die erste Koeffizientenfolge ${\displaystyle s_{n}^{(-J)}}$ gewonnen, so enthält das erste Tiefpassergebnis alle Signalbestandteile bis zur halben Nyquist-Frequenz, das Hochpassergebnis die darüberliegenden, beide Male mit einer der Bandbreite entsprechenden Abtastrate.

Analyse und Synthese

Der Fischgrätenzerlegung in der Multiskalenanalyse entspricht eine aus dem Tiefpass ${\displaystyle a}$ und dem Hochpass ${\displaystyle b}$ zusammengesetzte zeitdiskrete Filterbank, es wird ein zeitdiskretes Signal ${\displaystyle x}$ aufgeteilt in ein hohes Band ${\displaystyle b^{-}*x}$ und ein tiefes Band ${\displaystyle a^{-}*x}$ (Faltung von Folgen). Danach werden beide Signale heruntergetaktet (englisch downsampling) zu

${\displaystyle s=(\downarrow 2)(a^{-}*x)}$   und   ${\displaystyle d=(\downarrow 2)(b^{-}*x)}$.

Mit ${\displaystyle a^{-}}$ sei dabei die zeitinvertierte Folge

${\displaystyle a^{-}=\{\dots ,a_{2},a_{1},a_{0},a_{-1},a_{-2},\dots \}}$

bezeichnet. Das Heruntertakten einer Folge bedeutet, dass eine neue Folge aus den Gliedern mit geradem Index gebildet wird,

${\displaystyle (\downarrow 2)(y)=\{\dots ,y_{-4},y_{-2},y_{0},y_{2},y_{4},\dots \}}$.

Alle diese Operationen zusammengefasst ergibt sich eine gliedweise Berechnungsvorschrift der Analyse-Filterbank

${\displaystyle s_{n}=\sum _{k}a_{k}\cdot x_{2n+k}}$   und   ${\displaystyle d_{n}=\sum _{k}b_{k}\cdot x_{2n+k}}$.

Aus der Orthogonalität ergibt sich, dass das Ausgangssignal ${\displaystyle x}$ zurückgewonnen werden kann, zuerst werden die Tiefpass- und Hochpassanteile ${\displaystyle s}$ und ${\displaystyle d}$ in der Abtastrate hochgerechnet, dies wird als Upsampling bezeichnet, mit den Skalierungs- und Waveletmasken gefaltet und dann addiert,

${\displaystyle 2x=a*(\uparrow 2)s+b*(\uparrow 2)d}$

oder koeffizientenweise

${\displaystyle 2x_{n}=\sum _{k}a_{n-2k}\cdot s_{k}+\sum _{k}b_{n-2k}\cdot d_{k}}$.

Der Übergang von ${\displaystyle x}$ zu ${\displaystyle (s,d)}$ heißt Analyse, der inverse Synthese. Es ist ersichtlich, dass die Transformierte ${\displaystyle (s,d)}$ eines endlichen Signals nun etwa genauso viele Samples wie das Signal ${\displaystyle x}$ selbst hat, also genauso viel Information enthält.

Erweiterungen

Es ist nicht erforderlich, dass die Folgen in der Analyse-Filterbank mit denen in der Synthese-Filterbank wie oben übereinstimmen, nur ist dann nicht garantiert, dass die Kombination beider Filterbänke das Ausgangssignal rekonstruiert. Ist dies doch der Fall, spricht man von vollständiger Rekonstruktion (englisch perfect reconstruction) oder von Biorthogonalität der Wavelet-Basen.