Haar-Wavelet - LinkFang.de





Haar-Wavelet


Das Haar-Wavelet ist das erste in der Literatur bekannt gewordene Wavelet und wurde 1909 von Alfréd Haar vorgeschlagen.[1] Es ist außerdem das einfachste bekannte Wavelet und kann aus der Kombination zweier Rechteckfunktionen gebildet werden.

Vorteilhaft am Haar-Wavelet ist die einfache Implementierbarkeit der zugehörigen Wavelet-Transformation als schnelle Wavelet-Transformation (FWT). Der Nachteil des Haar-Wavelets ist, dass es unstetig und daher auch nicht differenzierbar ist.

Die Funktionen der Haar-Wavelet-Basis

Skalierungsfunktion

Die Skalierungsfunktion bzw. „Vater-Wavelet“-Funktion der Haar-Wavelet-Basis ist die Indikatorfunktion des Intervalls [math][0,1)[/math].

[math]\phi(x)=\chi_{[0,1)}(x)=\begin{cases}1&0\le x\lt1\\0&\mbox{sonst}\end{cases}[/math]

Sie erfüllt die Funktionalgleichung

[math]\phi(x)=\phi(2x)+\phi(2x-1)=\sqrt2\left(a_0\phi(2x)+a_1\phi(2x-1)\right)[/math] mit [math]a_0=a_1=\frac1{\sqrt2}[/math].

Waveletfunktion

Die Waveletfunktion ist die „zusammengeschobene“ Differenz zweier aufeinanderfolgender Skalierungsfunktionen:

[math]\psi(x)=\phi(2x)-\phi(2x-1)=\sqrt2\left(b_0\phi(2x)+b_1\phi(2x-1)\right)=\begin{cases}1&0\le x\lt1/2\\-1&1/2\le x\lt1\\0&\mbox{sonst}\end{cases}[/math],

wobei [math](b_0,b_1)=(\tfrac1{\sqrt2},-\tfrac1{\sqrt2})[/math].

Die Schreibweise mit Vorfaktor sorgt dafür, dass die Matrix

[math] H=\begin{pmatrix}a_0&a_1\\b_0&b_1\end{pmatrix} =\frac1{\sqrt2}\,\begin{pmatrix}1&1\\1&-1\end{pmatrix} [/math]

eine orthogonale Matrix ist. Dies ist Teil der Bedingungen, die orthogonale Wavelets erfordern.

Multiskalenanalyse

Diese Funktion erzeugt die Multiskalenanalyse der Stufenfunktionen. In dieser wird jeder Funktion [math]f \in L^2(\R)[/math] mit „endlicher Energie“ auf jeder Skala [math]J\in\Z[/math] die folgende Projektion zugewiesen:

[math]f\mapsto P_J(f)[/math] mit [math] P_J(f)(x)=\sum_{n\in\Z}\left(\int_0^1 f\left(2^{-J}(n+t)\right)\,\mathrm dt\right)\cdot\phi(2^Jx-n) [/math].

Die Differenz zwischen zwei Skalen lässt sich dann durch das „Mutter-Wavelet“ bzw. die eigentliche Waveletfunktion ausdrücken:

[math] P_{J+1}(f)(x)-P_J(f)(x) =\sum_{n\in\Z}\left(\int_0^1 f\left(2^{-J-1}(2n+t)\right)\, \mathrm dt-\int_0^1 f\left(2^{-J-1}(2n+1+t) \right)\, \mathrm dt\right)\cdot\psi(2^Jx-n) [/math].

Mit [math]\phi_{j,k}(x)={\sqrt2\,}^j\phi({2\,}^jx-k)[/math] und [math]\psi_{j,k}(x)={\sqrt2\,}^j\psi({2\,}^jx-k)[/math] als Funktionen im Hilbertraum [math]L^2(\R)[/math] gilt

  • alle diese Funktionen haben [math]L^2[/math]-Norm 1,
  • [math]\phi_{j,k}[/math] ist senkrecht zu [math]\phi_{j,l}[/math] bei k≠l,
  • [math]\psi_{i,k}[/math] ist senkrecht zu [math]\psi_{j,l}[/math] bei i≠j oder k≠l,
  • die [math]\psi_{i,k}[/math] bilden eine Hilbertbasis von [math]L^2(\R)[/math].

Schnelle Haar-Wavelet-Transformation

Gegeben sei ein diskretes Signal f, welches durch eine endliche oder quadratsummierbare Folge

[math]f=(\dots,f_{-2},f_{-1},f_0,f_1,f_2,f_3,\dots)[/math]

dargestellt ist. Ihm ist als kontinuierliches Signal die Treppenfunktion

[math]F(x) = \dots+ f_{-1}\phi_{0,-1}(x)+ f_0\phi_{0,0}(x)+ f_1\phi_{0,1}(x)+ f_2\phi_{0,2}(x)+ \dots[/math]

zugeordnet.

Vorwärtstransformation

Aus dem diskreten Signal wird durch paarweises „Senkrechtstellen“ ein vektorwertiges Signal, die sogenannte Polyphasenzerlegung, erzeugt:

[math]f_p=\left(\dots,\left({f_{-2}\atop f_{-1}}\right),\left({f_0\atop f_1}\right),\left({f_2\atop f_3}\right),\dots\right)[/math].

Dieser wird nun gliedweise mit der Haar-Transformationsmatrix [math]H:=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}[/math] multipliziert

[math]\left({s\atop d}\right)=:Hf_p=\left(\dots,\left({s_{-1}\atop d_{-1}}\right),\left({s_0\atop d_0}\right),\left({s_1\atop d_1}\right),\dots\right)[/math],

dabei ist [math]s_k=\frac{f_{2k+1}+f_{2k}}{\sqrt2}[/math] und [math]d_k=\frac{f_{2k+1}-f_{2k}}{\sqrt2}[/math].

Rücktransformation

Wir erhalten ein Mittelwertsignal s und ein Differenzsignal d, aus denen durch einfache Umkehr der vorgenommenen Schritte das Ausgangssignal zurückgewonnen werden kann:

[math]f_{2k}=\frac{s_k-d_k}{\sqrt2}[/math] und [math]f_{2k+1}=\frac{s_k+d_k}{\sqrt2}[/math]

Ist die Schwankung von Glied zu Glied im Ausgangssignal durch ein kleines ε>0 beschränkt, so ist die Schwankung in s durch √2⋅ε beschränkt, also immer noch klein, die Größe der Glieder in d jedoch durch ε/√2. Ein glattes Signal wird also in ein immer noch glattes Signal halber Abtastfrequenz und in ein kleines Differenzsignal zerlegt. Dies ist der Ausgangspunkt für die Wavelet-Kompression.

Rekursive Filterbank

Wir können den Vorgang wiederholen, indem wir s zum Ausgangssignal erklären und mit obigem Vorgehen zerlegen, wir erhalten eine Folge von Zerlegungen [math]s^0:=f,\; (s^1,d^1),\; (s^2, d^2, d^1),\;\dots,(s^T,d^T,\dots,d^2,d^1)[/math], [math]s^k[/math] hat ein [math]2^k[/math]-tel der ursprünglichen Abtastfrequenz und eine durch 2k/2⋅ε beschränkte Schwankung, [math]d^k[/math] hat ebenfalls ein [math]2^k[/math]-tel der ursprünglichen Abtastfrequenz und durch 2k/2−1⋅ε beschränkte Glieder.

Interpretation

Als diskretes Signal f wird meist eine reelle Folge (fn) über Z mit endlicher Energie betrachtet,

[math]\sum_{n=-\infty}^\infty\,|f_n|^2 \lt \infty[/math].

Unter diesen gibt es einige sehr einfache Folgen δn, Kronecker- oder Dirac-Delta genannt, eine für jedes n[math]\in[/math]Z. Für deren Folgenglieder gilt, dass das jeweils n-te den Wert 1 hat, [math]\delta^n_n=1[/math], und alle anderen den Wert 0, [math]\delta^n_k=0[/math] bei k≠n.

Jetzt können wir jedes Signal trivial als Reihe im Signalraum schreiben

[math]f=\sum_{n=-\infty}^\infty\,f_n\cdot\delta^n[/math]

oder als Summe zweier Reihen

[math]f=\sum_{n=-\infty}^\infty\,f_{2n}\cdot\delta^{2n} +\sum_{n=-\infty}^\infty\,f_{2n+1}\cdot\delta^{2n+1}[/math].

In vielen praktisch relevanten Signalklassen, z. B. bei überabgetasteten bandbeschränkten kontinuierlichen Signalen, sind Werte benachbarter Folgenglieder auch benachbart, d. h. im Allgemeinen liegen f2n und f2n+1 dicht beisammen, relativ zu ihrem Absolutbetrag. Dies wird in der obigen Reihen aber überhaupt nicht berücksichtigt. In Mittelwert und Differenz von f2n und f2n+1 käme deren Ähnlichkeit stärker zum Ausdruck, der Mittelwert ist beiden Werten ähnlich und die Differenz klein. Benutzen wir die Identität

[math]ac+bd=\frac12 (a+b)(c+d)+\frac12 (a-b)(c-d)[/math]

um benachbarte Glieder der ersten Reihe bzw. korrespondierende Glieder in der zweiten Zerlegung zusammenzufassen in (skalierten) Mittelwerten und Differenzen:

[math]f=\sum_{n=-\infty}^\infty\, \frac{f_{2n}+f_{2n+1}}{\sqrt2}\cdot\frac{\delta^{2n}+\delta^{2n+1}}{\sqrt2} +\sum_{n=-\infty}^\infty\, \frac{f_{2n}-f_{2n+1}}{\sqrt2}\cdot\frac{\delta^{2n}-\delta^{2n+1}}{\sqrt2}[/math]

Jetzt führen wir neue Bezeichnungen ein:

  • die neuen Basisfolgen
[math]a^n:=\frac{\delta^{2n}+\delta^{2n+1}}{\sqrt2}[/math] und [math]b^n:=\frac{\delta^{2n}-\delta^{2n+1}}{\sqrt2}[/math]
  • mit den neuen transformierten Koeffizienten
[math]s_n:=\frac{f_{2n}+f_{2n+1}}{\sqrt2}[/math] und [math]d_n:=\frac{f_{2n}-f_{2n+1}}{\sqrt2}[/math].

Wir erhalten somit die Zerlegung der Haar-Wavelet-Transformation

[math]f=\sum_{n=-\infty}^\infty\,s_n\cdot a^n+\sum_{n=-\infty}^\infty\,d_n\cdot b^n[/math].

und mittels des unendlichen euklidischen Skalarproduktes können wir schreiben

[math]s_n= \langle f,\,a^n \rangle[/math] und [math]d_n= \langle f,\,b^n \rangle[/math].

Die letzten drei Identitäten beschreiben eine „Conjugate Quadrature Filterbank (CQF)“, welche so auch für allgemeinere Basisfolgen an und bn definiert werden kann. Die Basisfolgen an entstehen alle durch Verschiebung um das jeweilige 2n aus a0, die bn durch Verschiebung aus b0. Weiteres dazu im Artikel Daubechies-Wavelets.

Nun enthält die Folge s=(sn) eine geglättete Version des Ausgangssignals bei halber Abtastrate, man kann also auch s nach dieser Vorschrift zerlegen und dieses Vorgehen über eine bestimmte Tiefe rekursiv fortsetzen. Aus einem Ausgangssignal s0:=f werden also nacheinander die Tupel

[math](s^1,d^1)[/math], [math](s^2,d^2,d^1)[/math], [math](s^3,d^3,d^2,d^1)[/math], …

Ist f endlich, also fast überall Null, mit Länge N, dann haben die Folgen in der Zerlegung im Wesentlichen, d. h. bis auf additive Konstanten, die Längen

[math]\left( \tfrac N2, \tfrac N 2 \right)[/math], [math]\left( \tfrac N4, \tfrac N4, \tfrac N2 \right)[/math], [math]\left( \tfrac N8, \tfrac N8, \tfrac N4, \tfrac N2 \right)[/math], …

so dass die Gesamtzahl wesentlicher Koeffizienten erhalten bleibt. Die Folgen in der Zerlegung eignen sich meist besser zur Weiterverarbeitung wie Kompression oder Suche nach bestimmtem Merkmalen als das rohe Ausgangssignal.

Modifikationen

Die Polyphasenzerlegung des Ausgangssignals kann auch zu einer anderen Blockgröße s als 2 erfolgen, von der entsprechenden Haar-Matrix ist zu fordern, dass sie eine orthogonale Matrix ist und ihre erste Zeile nur aus Einträgen 1/√s besteht. Diese Anforderung erfüllen die Matrizen der diskreten Kosinustransformation und die der Walsh-Hadamard-Transformation.

Die Haar-Wavelet-Transformation entspricht einer diskreten Kosinustransformation zur Blockgröße s=2, welche im Bild=Pixelrechteck nacheinander in horizontaler und vertikaler Richtung angewandt wird.

Literatur

  • Alfréd Haar: Zur Theorie der orthogonalen Funktionensysteme, Mathematische Annalen 69, 331–371, 1910, Online , insbesondere Kapitel 3 (ab S. 361).

Weblinks

 Commons: Haar-Wavelet  – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

  1. Alfred Haar: Zur Theorie der orthogonalen Funktionensysteme. In: Mathematische Annalen. 69, Nr. 3, 1910, S. 331–371. doi:10.1007/BF01456326 .

Kategorien: Wavelet

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Haar-Wavelet (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.