Quelltext der Seite Haar-Wavelet

[[Datei:Haar wavelet.svg|mini|Haar-Wavelet]]
Das '''Haar-Wavelet''' ist das erste in der Literatur bekannt gewordene [[Wavelet]] und wurde 1909 von [[Alfréd Haar]] eingeführt.<ref>{{cite journal |last=Haar |first=Alfred |title=Zur Theorie der orthogonalen Funktionensysteme |journal=[[Mathematische Annalen]] |volume=69 |year=1910 |issue=3 |pages=331–371 |doi=10.1007/BF01456326 }}</ref> Es ist außerdem das einfachste bekannte Wavelet und kann aus der Kombination zweier [[Rechteckfunktion|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 [[Stetige Funktion|unstetig]] und daher auch nicht [[Differentialrechnung|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<1\\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<1/2\\-1&1/2\le x<1\\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> falls <math>k\not=l</math>,
* <math>\psi_{i,k}</math> ist senkrecht zu <math>\psi_{j,l}</math> falls <math>i\not=j</math> oder <math>k\not=l</math>,
* die <math>\psi_{i,k}</math> bilden eine [[Hilbertraumbasis|Hilbertbasis]] von <math>L^2(\R)</math>.

== Schnelle Haar-Wavelet-Transformation ==
Gegeben sei ein [[Digitales Signal|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 <math>s</math> und ein Differenzsignal <math>d</math>, 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 <math>\epsilon>0</math> beschränkt, so ist die Schwankung in <math>s</math> durch <math>\sqrt{2}\epsilon</math> beschränkt, also immer noch klein, die Größe der Glieder in <math>d</math> jedoch durch <math>\epsilon/\sqrt{2}</math>. 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 <math>2^{k/2}\epsilon</math> beschränkte Schwankung, <math>d^k</math> hat ebenfalls ein <math>2^k</math>-tel der ursprünglichen Abtastfrequenz und durch <math>2^{-k/2}\epsilon</math> beschränkte Glieder.

=== Interpretation ===
Als [[Digitales Signal|diskretes Signal]] <math>f</math> wird meist eine reelle Folge <math>(f_n)</math> über <math>Z</math> mit endlicher Energie betrachtet,
: <math>\sum_{n=-\infty}^\infty\,|f_n|^2 < \infty</math>.

Unter diesen gibt es einige sehr einfache Folgen ''δ<sup>n</sup>'', Kronecker- oder Dirac-Delta genannt, eine für jedes <math>n\in Z</math>. Für deren Folgenglieder gilt, dass das jeweils <math>n</math>-te den Wert <math>1</math> hat, <math>\delta^n{}_n=1</math>, und alle anderen den Wert <math>0</math>, <math>\delta^n{}_k=0</math> falls <math>k\not= n</math>.

Jetzt können wir jedes Signal trivial als [[Reihe (Mathematik)|Reihe]] im [[Hilbertraum|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.&nbsp;B. bei [[Überabtastung|überabgetasteten]] [[Bandbreite|bandbeschränkten]] kontinuierlichen Signalen, sind Werte benachbarter Folgenglieder auch benachbart, d. h. im Allgemeinen liegen <math>f_{2n}</math> und <math>f_{2n+1}</math> dicht beisammen, relativ zu ihrem Absolutbetrag. Dies wird in der obigen Reihen aber überhaupt nicht berücksichtigt. In Mittelwert und Differenz von <math>f_{2n}</math> und <math>f_{2n+1}</math> 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 [[Skalarprodukt]]es 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 <math>a^n</math> und <math>b^n</math> definiert werden kann. Die Basisfolgen <math>a^n</math> entstehen alle durch Verschiebung um das jeweilige <math>2n</math> aus <math>a^0</math>, die <math>b^n</math> durch Verschiebung aus <math>b^0</math>. Weiteres dazu im Artikel [[Daubechies-Wavelets]].

Nun enthält die Folge <math>s=(s^n)</math> eine geglättete Version des Ausgangssignals bei halber [[Abtastrate]], man kann also auch <math>s</math> nach dieser Vorschrift zerlegen und dieses Vorgehen über eine bestimmte Tiefe rekursiv fortsetzen. Aus einem Ausgangssignal <math>s^0=f</math> 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 <math>f</math> endlich, also fast überall Null, mit Länge <math>N</math>, dann haben die Folgen in der Zerlegung im Wesentlichen, d.&nbsp;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 <math>1/\sqrt{s}</math> besteht. Diese Anforderung erfüllen die Matrizen der [[Diskrete Kosinustransformation|diskreten Kosinustransformation]] und die der [[Walsh-Hadamard-Transformation]].

Die Haar-Wavelet-Transformation entspricht einer [[Diskrete Kosinustransformation|diskreten Kosinustransformation]] zur Blockgröße <math>s=2</math>, welche im Bild=Pixelrechteck nacheinander in horizontaler und vertikaler Richtung angewandt wird.

== Siehe auch ==
* [[Viola-Jones-Methode]]

== Literatur ==
* [[Alfréd Haar]]: ''Zur Theorie der orthogonalen Funktionensysteme'', Mathematische Annalen '''69''', 331–371, 1910, [[doi:10.1007/BF01456927]], insbesondere Kapitel 3 (ab S. 361).

== Weblinks ==
{{Commonscat|Haar wavelet|Haar-Wavelet}}

== Einzelnachweise ==
<references />

[[Kategorie:Wavelet]]