Diskrete Wavelet-Transformation

Mit Wavelet-Transformation (WT, engl. wavelet transform) wird eine bestimmte Familie von linearen Zeit-Frequenz-Transformationen in der Mathematik und den Ingenieurswissenschaften (primär: Nachrichtentechnik, Informatik) bezeichnet. Die WT setzt sich zusammen aus der Wavelet-Analyse, welche den Übergang der Zeitdarstellung in die Spektral- bzw. Waveletdarstellung bezeichnet, und der Wavelet-Synthese, welche die Rücktransformation der Wavelettransformierten in die Zeitdarstellung bezeichnet.

Der Begriff Wavelet bezeichnet die für die Transformation benutzte Basisfunktion, mit welcher das zu analysierende Signal oder Bild (i.Allg. eine N-dimensionale Funktion) „verglichen“ wird. Die Wurzeln der Waveletschule liegen in Frankreich, wo auch der ursprünglich französische Begriff ondelette geprägt wurde, dessen englisches Pendant wavelet sich jedoch später als Bezeichnung durchgesetzt hat. Ins deutsche übersetzt bedeutet Wavelet soviel wie kleine Welle oder Wellchen und drückt den Umstand aus, dass man im Gegensatz zur Fourier-Transformation zeitlich lokalisierte Wellen bzw. Funktionen als Basis benutzt, wodurch die eingangs erwähnte Zeit- und Frequenzauflösung möglich wird. Die Wavelettransformierte unterliegt dem Abtasttheorem, was analog zur heisenbergschen Unschärferelation praktisch bedeutet, dass ein Ereignis nicht gleichzeitig beliebig genau in Zeit und Frequenz aufgelöst werden kann.

Die Wavelet-Transformation unterteilt sich in erster Linie in zwei Lager, nämlich die kontinuierliche Wavelet-Transformation, welche ihre Hauptanwendung in der Mathematik und der Datenanalyse hat, und die diskrete Wavelet-Transformation, welche eher in den Ingenieurswissenschaften zu finden ist und deren Anwendung im Bereich der Datenreduktion, Datenkompression und Signalverarbeitung liegt.

Funktionsweise

Die Wavelet-Transformation kann als Verbesserung der Short-Time-Fourier-Transformation (STFT) angesehen werden.

Schwächen der Short-Time-Fourier-Transformation

Bei der STFT wird das zu untersuchende Signal mit einer Fensterfunktion – etwa mit der Gaussschen Glockenkurve wie bei der Gabor-Transformation – verglichen. Für jeden Punkt der STFT wird das Fenster an den zu betrachtenden Zeitpunkt und an die zu betrachtende Frequenz (Modulation im Zeitbereich) verschoben. Die absolute Zeitdauer und Bandbreite des Fensters („Breite“ im Zeit- und Frequenzbereich) – und damit die Auflösung – ändert sich dadurch nicht.

Die Auflösungen im Zeit- und Frequenzbereich sind nur abhängig von der Form des Fensters. Auf Grund der Zeit-Frequenz-Unschärfe ist die Auflösung im Zeitbereich umgekehrt proportional zur Auflösung im Frequenzbereich. Es lässt sich also nicht gleichzeitig im Zeitbereich und im Frequenzbereich die bestmögliche Auflösung erzielen.

Enthält nun ein Signal Frequenzanteile sowohl bei hohen als auch bei niedrigen Frequenzen, möchte man bei niedrigen Frequenzen eine gute (absolute) Frequenzauflösung erzielen, da eine kleine absolute Frequenzänderung hier stark ins Gewicht fällt. Bei einer hohen Frequenz ist eine gute Zeitauflösung wichtiger, da eine vollständige Schwingung hier weniger Zeit beansprucht und sich die Momentanfrequenz daher schneller ändern kann.

Hat man beispielsweise ein Signal mit Frequenzanteilen bei 1 Hz und 1 kHz und möchte die Frequenz auf 10 % auflösen, so ist bei 1 Hz eine Frequenzauflösung von 0,1 Hz nötig. Bei 1 kHz entspricht dieses einer Auflösung von 0,01 % – eine so gute Auflösung ist hier nicht nötig.

Andererseits vollführt das Signal bei 1 kHz zehn vollständige Schwingungen in 10 ms. Um Frequenzänderungen in diesem Zeitraum auflösen zu können, ist eine Zeitauflösung besser als 10 ms nötig. Bei 1 Hz entspricht diese Zeitdauer nur einer hundertstel Schwingung. Eine so gute zeitliche Auflösung ist also hier nicht nötig.

Man wünscht sich also bei niedrigen Frequenzen eine gute Frequenzauflösung unter Inkaufnahme einer schlechten Zeitauflösung und bei hohen Frequenzen eine gute Zeitauflösung bei schlechterer Frequenzauflösung. Die Short-Time-Fourier-Transformation leistet dieses nicht.

Zusammenfassung der Funktionsweise

Wie bei der STFT wird das zu untersuchende Signal mit einer Fensterfunktion verglichen. Anstatt allerdings das Fenster zu verschieben und zu modulieren (Verschiebung im Frequenzbereich) (wie bei der STFT), wird das Fenster verschoben und skaliert. Durch die Skalierung ergibt sich, wie durch die Modulation, ebenfalls eine Frequenzverschiebung, allerdings wird gleichzeitig mit einer Frequenzerhöhung die Zeitdauer („Breite“ im Zeitbereich) des Fensters verringert. Dadurch ergibt sich bei höheren Frequenzen eine bessere zeitliche Auflösung. Bei niedrigen Frequenzen wird die Frequenzauflösung besser, dafür wird die Zeitauflösung schlechter.

Kontinuierliche Wavelet-Transformation

Die kontinuierliche Wavelet-Transformation (CWT, engl. continuous wavelet transform) ist gegeben durch

$\mathcal{W}_\psi x(a,b) = \frac{1}{a} \int_{-\infty}^{\infty} \overline{\psi\left(\frac{t-b}{a}\right)} x(t) \; dt.$

Diese lässt sich durch die Einführung der Wavelet-Familie

$\left\{ \psi_{ab} = \frac{1}{a} \psi\left(\frac{t-b}{a}\right) \ : \ (a,b) \in\mathbb R_+\!\times \mathbb R \right\}$

kompakt als Skalarprodukt

$\mathcal{W}_\psi x(a,b) = \langle \psi_{ab} , x \rangle$

auffassen, wodurch auch sofort die Linearität der WT folgt.

Eigenschaften von Wavelets

Die wichtigste Eigenschaft eines Wavelets ist seine Admissibilität

$\int_{-\infty}^{\infty} \frac{ |\hat{\psi}(\omega)|^2 }{ |\omega| }d\omega < \infty$

aus welcher folgt, dass die Fouriertransformierte des Wavelets an der Stelle 0 verschwindet

$\hat{\psi}(\omega=0) = 0,$

was bedeutet, dass das Wavelet einen Bandpass-Charakter haben muss. Des weiteren folgt daraus, dass das erste Moment des Wavelets, also sein Mittelwert, verschwindet:

$\int_{-\infty}^{\infty} \psi (t) \; dt = 0,$

Wavelet-Synthese

Die ursprüngliche Funktion x(t) kann, bis auf eine additive Konstante, wieder aus der Wavelettransformierten zurückgewonnen werden mit der Rekonstruktionsformel

$x(t) = \frac{1}{c_{\phi\psi}} \int_{0}^{\infty} \!\frac{da}{a} \int_{-\infty}^{\infty} \!\!\! db\; \mathcal{W}_\psi x(a,b) \frac{1}{a} \phi\left(\frac{t-b}{a}\right),$

mit

$c_{\phi\psi} = \int_{0}^{\infty} \frac{d\omega}{\omega} \overline{\hat{\phi}(\pm\omega)} \hat{\psi}(\pm\omega) \; d\omega.$

Reproduzierender Kern

Als Reproduzierender Kern (engl. reproducing kernel) wird die Wavelettransformierte des Wavelets selbst bezeichnet. Somit bezeichnet

$K_\psi(a,b) = \langle \psi_{ab} , \psi \rangle$

den Kern des Wavelets ψ.

Das Attribut reproduzierend trägt der Kern, weil sich die Wavelettransformierte unter der Faltung mit dem Kern reproduziert, d. h. die Wavelettransformierte ist invariant unter der Faltung mit dem Kern. Diese Faltung ist gegeben durch

$( K_\psi * \mathcal{W}_\psi x )(a,b) = \int_{0}^{\infty} \!\frac{da'}{a'} \int_{-\infty}^{\infty} \!\!\! db'\; \frac{1}{a'} K_\psi\left(\frac{a}{a'},\frac{b-b'}{a'}\right) (\mathcal{W}_\psi x)(a,b).$

Dies ist keine gewöhnliche Faltung, da sie nicht kommutativ ist; sie ist jedoch assoziativ.

Eine weitere wichtige Bedeutung erhält der Reproduzierende Kern daher, dass er die minimale Korrelation zwischen zwei Punkten (a,b) und (a',b') im Waveletraum angibt. Dies lässt sich zeigen, indem man die Autokorrelation von weißem Rauschen im Waveletraum betrachtet. Bezeichnen wir mit ξ(t) ein Gauss’sches weißes Rauschen mit Varianz 1, so ist dessen Autokorrelation gegeben durch $\langle \xi(t)\xi(t') \rangle = \delta(t,t')$. Die Korrelation im Waveletraum ist dann (ohne Ausführung der Rechnung)

$\langle (\overline{\mathcal{W}_\psi\xi(a',b')} \mathcal{W}_\psi\xi(a,b) \rangle = \frac{1}{a'} K_\psi \left( \frac{1}{a'},\frac{b-b'}{a'} \right),$

also gerade gegeben durch den reproduzierenden Kern.

Diskrete Wavelet-Transformation

• Die Diskrete Wavelet-Transformation oder DWT ist eine Wavelet-Transformation, die zeit- und frequenzdiskret durchgeführt wird.
• Es wurde gezeigt, dass die Informationen trotz Reduktion auf eine diskrete Teilmenge $\{(a,b)=(\alpha^k,l\,\beta\,\alpha^{-k}):\;k,l\in\mathbb Z\}\subset\mathbb R_+\times \mathbb R$, bei α > 1,β > 0, vollständig erhalten bleibt.
• Eine DWT lässt sich sehr effizient als eine Reihe von zeitdiskreten Filtern implementieren, die kontinuierliche Wavelet-Transformation wird praktisch auf diese Weise berechnet.

Schnelle Wavelet-Transformation

• Die schnelle Wavelet-Transformation (engl. fast wavelet transform, FWT) ist ein Algorithmus, der mit Hilfe der Theorie der Multiskalenanalyse die diskrete Wavelet-Transformation implementiert. Dabei wird das Bilden des inneren Produkts des Signals mit jedem Wavelet durch das sukzessive Zerteilen des Signals in Frequenzbänder ersetzt. Dadurch wird die Komplexität der Wavelet-Transformation von O(NlogN) (vgl. schnelle Fourier-Transformation) auf O(N) reduziert.

Wavelet-Paket-Transformation und Beste-Basis-Algorithmen

Die Wavelet-Paket-Transformation ist eine Ausweitung der schnellen Wavelet-Transformation (FWT), indem nicht nur das Tiefpasskanal, sondern auch das Bandpasskanal weiter mittels der Wavelet-Filterbank aufgespalten werden. Dieses kann dazu dienen, aus einer üblichen 2-Kanal-DWT wie z. B. den Daubechies-Wavelets eine M-Kanal-DWT zu erhalten, wobei M eine Potenz von 2 ist, der Exponent wird Tiefe des Paket-Baums genannt. Dieses Verfahren wird in der Breitbanddatenübertragung als Alternative zur schnellen Fourier-Transformation angewandt.

Wird in einem Rekursionsschritt der FWT ein weißes Rauschen als Eingangssignal transformiert, so ist das Ergebnis aufgrund der orthogonalen Natur der DWT wieder ein weißes Rauschen, wobei die Energie (=Quadratsumme der Samples) gleichmäßig auf Tief- und Bandpasskanal verteilt wird. Nimmt man eine möglichst hohe Abweichung von diesem Verhalten, d. h. eine möglichst vollständige Konzentration der Signalenergie auf einen der beiden Kanäle, als Entscheidungskriterium, ob der Eingangskanal aufgespalten werden soll und setzt dieses Verfahren für die aufgespaltenen Kanäle fort, so entsteht eine Variante eines Beste-Basis-Verfahrens.

Wichtige Anwendungen

• Bildkompression und Videokompression: Wavelet-Kompression
• Lösung von Differentialgleichungen
• Signalverarbeitung

Geschichte

• Erstes Wavelet (Haar-Wavelet) von Alfred Haar (1909)
• Seit den 1950er-Jahren: Jean Morlet und Alex Grossman
• Seit den 1980er-Jahren: Yves Meyer, Stéphane Mallat, Ingrid Daubechies, Ronald Coifman, Victor Wickerhauser

Siehe auch

• Diskrete Kosinustransformation
• Diskrete Fourier-Transformation
• Fourier-Transformation

Weblinks

• Wavelets for Kids – Einführung, engl. – pdf
• The engineer’s ultimate guide to wavelet analysis von Robi Polikar – engl. – Erklärung der Wavelet-Transformation mit Motivation, die für Leute mit Kenntnis der Fourier-Transformation gut verständlich ist
• Linksammlung zu Wavelets
• Wavelet Digest Home Page