Wavelet-Transformation

Als Wavelet-Transformation (WT, englisch wavelet transform) wird eine Familie von linearen Zeit-Frequenz-Transformationen in der Mathematik und den Ingenieurwissenschaften (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 der das zu analysierende Signal oder Bild – im Allgemeinen 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 so viel 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. Wie alle linearen Zeit-Frequenz-Transformationen unterliegt auch die Wavelettransformierte der Unschärferelation der Nachrichtentechnik, d. h. ein Ereignis kann nicht gleichzeitig beliebig genau in Zeit und Frequenz lokalisiert werden. Es gibt immer nur einen Kompromiss aus guter zeitlicher Auflösung oder guter Auflösung im Frequenzbereich.

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 Ingenieurwissenschaften zu finden ist und deren Anwendung im Bereich der Datenreduktion, Datenkompression und Signalverarbeitung liegt^[1].

Wichtige Anwendungen der Wavelet-Transformation sind die Wavelet-Kompression für die Bildkompression oder Videokompression, die Signalverarbeitung und die Lösung von Differentialgleichungen.

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

Bei der STFT wird eine Fensterfunktion auf das zu untersuchende Signal angewendet – etwa die Gaußsche Glockenkurve wie bei der Gabor-Transformation. 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 – ändern sich dadurch nicht.

Die Auflösungen im Zeit- und Frequenzbereich sind nur abhängig von der Form des Fensters. Aufgrund 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.

Für ein Signal mit Frequenzanteilen bei 1 Hz und 1 kHz, für welches die Frequenz auf 10 Prozent genau aufgelöst werden soll, ist bei 1 Hz eine Frequenzauflösung von 0,1 Hz nötig. Bei 1 kHz entspricht dieses einer Auflösung von 0,01 Prozent – 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. Gewünscht ist bei niedrigen Frequenzen also 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.

Wie bei der STFT wird eine Fensterfunktion auf das zu untersuchende Signal angewendet. 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.

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

W ψ x ( a , b ) = 1 a ∫ − ∞ ∞ ψ ( t − b a ) ¯ x ( t ) d t . {\displaystyle {\mathcal {W}}_{\psi }x(a,b)={\frac {1}{\sqrt {a}}}\int _{-\infty }^{\infty }{\overline {\psi \left({\frac {t-b}{a}}\right)}}x(t)\;dt.}

Dabei ist

• x ( t ) {\displaystyle x(t)} : die zu transformierende Funktion, beispielsweise ein Audio- oder Bildsignal
• ψ ( t ) {\displaystyle \psi (t)} : Wavelet-Funktion (engl. mother wavelet) welche je nach Anwendung verschieden gewählt werden kann
• b {\displaystyle b} : Translationsparameter, zur Abtastung der Daten x ( t ) {\displaystyle x(t)} in der zeitlichen bzw. räumlichen Dimension
• a {\displaystyle a} : Skalierungsparameter, welcher die Daten über verschiedene Frequenzbereiche scannt

Mit der aus dem Mother-Wavelet ψ ( t ) {\displaystyle \psi (t)} abgeleiteten Wavelet-Familie

ψ a b = 1 a ψ ( t − b a ) {\displaystyle \psi _{ab}={\frac {1}{a}}\psi \left({\frac {t-b}{a}}\right)}

lässt sich die kontinuierliche Wavelet-Transformation kompakt als Skalarprodukt

W ψ x ( a , b ) = ⟨ ψ a b , x ⟩ {\displaystyle {\mathcal {W}}_{\psi }x(a,b)=\langle \psi _{ab},x\rangle }

schreiben.

Ein Wavelet ψ ( t ) {\displaystyle \psi (t)} ist eine quadratintegrierbare Funktion, welche relativ frei wählbar ist. Im Allgemeinen stellt man eine weitere technische Voraussetzung an ein Wavelet, die Zulässigkeitsbedingung:

∫ − ∞ ∞ | ψ ^ ( ω ) | 2 | ω | d ω < ∞ {\displaystyle \int _{-\infty }^{\infty }{\frac {|{\hat {\psi }}(\omega )|^{2}}{|\omega |}}d\omega <\infty }

Dabei bezeichnet ψ ^ ( ω ) {\displaystyle {\hat {\psi }}(\omega )} die Fourier-Transformierte von ψ ( t ) {\displaystyle \psi (t)} . Die Zulässigkeitsbedingung wird für den Beweis einiger zentraler Sätze und Eigenschaften benötigt, weshalb sie häufig in die Definition eines Wavelets mit eingeschlossen wird.

Eine unmittelbare Folgerung der Zulässigkeit ist, dass die Fouriertransformierte des Wavelets an der Stelle 0 verschwindet:

ψ ^ ( ω = 0 ) = 0 {\displaystyle {\hat {\psi }}(\omega =0)=0}

Des Weiteren folgt daraus, dass das erste Moment des Wavelets, also sein Mittelwert, verschwindet:

∫ − ∞ ∞ ψ ( t ) d t = 0 {\displaystyle \int _{-\infty }^{\infty }\psi (t)\;dt=0}

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

x ( t ) = 1 c ϕ ψ ∫ 0 ∞ d a a ∫ − ∞ ∞ d b W ψ x ( a , b ) 1 a ϕ ( t − b a ) , {\displaystyle 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 ϕ ψ = ∫ 0 ∞ d ω ω ϕ ^ ( ± ω ) ¯ ψ ^ ( ± ω ) d ω . {\displaystyle c_{\phi \psi }=\int _{0}^{\infty }{\frac {d\omega }{\omega }}{\overline {{\hat {\phi }}(\pm \omega )}}{\hat {\psi }}(\pm \omega )\;d\omega .}

Dabei ist ϕ ( t ) {\displaystyle \phi (t)} die duale Wavelet-Funktion zu ψ ( t ) {\displaystyle \psi (t)} .

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

K ψ ( a , b ) = ⟨ ψ a b , ψ ⟩ {\displaystyle K_{\psi }(a,b)=\langle \psi _{ab},\psi \rangle }

den Kern des Wavelets ψ {\displaystyle \psi } .

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

( K ψ ∗ W ψ x ) ( a , b ) = ∫ 0 ∞ d a ′ a ′ ∫ − ∞ ∞ d b ′ 1 a ′ K ψ ( a a ′ , b − b ′ a ′ ) ( W ψ x ) ( a , b ) . {\displaystyle (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 ) {\displaystyle \xi (t)} ein Gauss’sches weißes Rauschen mit Varianz 1, so ist dessen Autokorrelation gegeben durch ⟨ ξ ( t ) ξ ( t ′ ) ⟩ = δ ( t , t ′ ) {\displaystyle \langle \xi (t)\xi (t')\rangle =\delta (t,t')} . Die Korrelation im Waveletraum ist dann (ohne Ausführung der Rechnung)

⟨ ( W ψ ξ ( a ′ , b ′ ) ¯ W ψ ξ ( a , b ) ⟩ = 1 a ′ K ψ ( 1 a ′ , b − b ′ a ′ ) , {\displaystyle \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.

Die Diskrete Wavelet-Transformation (DWT, engl. discrete wavelet transform) ist gegeben durch

W ψ x ( m , n ) = ∫ − ∞ ∞ ψ m , n ( t ) x ( t ) d t . {\displaystyle {\mathcal {W}}_{\psi }x(m,n)=\int _{-\infty }^{\infty }\psi _{m,n}(t)x(t)\;dt.}

Dabei ist

• x ( t ) {\displaystyle x(t)} : die zu transformierende Funktion, beispielsweise ein Audio- oder Bildsignal
• ψ ( t ) {\displaystyle \psi (t)} : Wavelet-Funktion (engl. mother wavelet) welche je nach Anwendung verschieden gewählt werden kann

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

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 ( N log ⁡ N ) {\displaystyle O(N\log N)} (vgl. schnelle Fourier-Transformation) auf O ( N ) {\displaystyle O(N)} reduziert.

Zur Berechnung der Wavelet-Transformation eines Bildes braucht man eigentlich gar keine Wavelets oder Skalierungsfunktionen. Die komplette Transformation besteht dann lediglich aus der sogenannten Faltung des Ausgangssignals mit geeigneten Filtern. Ein Filter h {\displaystyle h} stellt dabei einen Vektor von reellen Zahlen (den sogenannten Filter-Koeffizienten) mit n {\displaystyle n} Einträgen dar. Die Faltung von Signal und Filter ist mathematisch definiert als

y ( n ) = ∑ i = 0 N − 1 h ( i ) x ( n − i ) {\displaystyle y(n)=\sum _{i=0}^{N-1}h(i)x(n-i)}

Dabei ist

• x ( n ) {\displaystyle x(n)} : die zu transformierende Funktion, beispielsweise ein Audio- oder Bildsignal
• y ( n ) {\displaystyle y(n)} : das Ausgangssignal nach der Faltung
• h ( i ) {\displaystyle h(i)} : der verwendete Filter
• N {\displaystyle N} : die Länge des Filters
• n {\displaystyle n} : die Position des Signals

Man braucht lediglich geeignete Hochpass-Filter und Tiefpass-Filter, um die Schnelle Wavelet-Transformation durchzuführen. Aus den gegebenen Filtern lassen sich dann die zugehörige Wavelet-Funktion und Skalierungsfunktion berechnen. Die Skalierungsfunktion ϕ {\displaystyle \phi } wird rekursiv aus dem Tiefpass-Filter h 0 {\displaystyle h_{0}} berechnet durch

ϕ ( t ) = 2 ∑ k = 0 N h 0 ( k ) ϕ ( 2 t − k ) {\displaystyle \phi (t)=2\sum _{k=0}^{N}h_{0}(k)\phi (2t-k)}

Die Wavelet-Funktion ω {\displaystyle \omega } kann aus dem Hochpass-Filter h 1 {\displaystyle h_{1}} und der Skalierungsfunktion bestimmt werden:^[2]

ω ( t ) = 2 ∑ k = 0 N h 1 ( k ) ω ( 2 t − k ) {\displaystyle \omega (t)=2\sum _{k=0}^{N}h_{1}(k)\omega (2t-k)}

Die Wavelet-Paket-Transformation ist eine Ausweitung der Schnellen Wavelet-Transformation (FWT), indem nicht nur der Tiefpasskanal, sondern auch der Hochpasskanal weiter mittels der Wavelet-Filterbank aufgespalten wird. 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 Hochpasskanal 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 man dieses Verfahren für die aufgespaltenen Kanäle fort, so entsteht eine Variante eines Beste-Basis-Verfahrens.

• Diskrete Kosinustransformation
• Diskrete Fourier-Transformation
• Fourier-Transformation
• Stationäre Wavelet-Transformation
• Schnelle Wavelet-Transformation
• Laplace-Transformation

• Yves Meyer: Wavelets and Operators. Cambridge University Press, Cambridge 1992, 1995.

• Wavelets for Kids – Einführung (englisch)
• The engineer’s ultimate guide to wavelet analysis von Robi Polikar (englisch) – 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
• The Wavelet Transform

1. ↑ Strutz: Bilddatenkompression. SpringerVieweg, 2009
2. ↑ Christoph Esser, Universität Mannheim: Wavelet Transformation von Standbildern