Haar-Wavelet

Die Skalierungsfunktion bzw. „Vater-Wavelet“-Funktion der Haar-Wavelet-Basis ist die Indikatorfunktion des Intervalls ${\displaystyle [0,1)}$.

${\displaystyle \phi (x)=\chi _{[0,1)}(x)={\begin{cases}1&0\leq x<1\\0&{\mbox{sonst}}\end{cases}}}$

Sie erfüllt die Funktionalgleichung

${\displaystyle \phi (x)=\phi (2x)+\phi (2x-1)={\sqrt {2}}\left(a_{0}\phi (2x)+a_{1}\phi (2x-1)\right)}$ mit ${\displaystyle a_{0}=a_{1}={\frac {1}{\sqrt {2}}}}$.

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

${\displaystyle \psi (x)=\phi (2x)-\phi (2x-1)={\sqrt {2}}\left(b_{0}\phi (2x)+b_{1}\phi (2x-1)\right)={\begin{cases}1&0\leq x<1/2\\-1&1/2\leq x<1\\0&{\mbox{sonst}}\end{cases}}}$,

wobei ${\displaystyle (b_{0},b_{1})=({\tfrac {1}{\sqrt {2}}},-{\tfrac {1}{\sqrt {2}}})}$.

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

${\displaystyle H={\begin{pmatrix}a_{0}&a_{1}\\b_{0}&b_{1}\end{pmatrix}}={\frac {1}{\sqrt {2}}}\,{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}$

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

Diese Funktion erzeugt die Multiskalenanalyse der Stufenfunktionen. In dieser wird jeder Funktion ${\displaystyle f\in L^{2}(\mathbb {R} )}$ mit „endlicher Energie“ auf jeder Skala ${\displaystyle J\in \mathbb {Z} }$ die folgende Projektion zugewiesen:

${\displaystyle f\mapsto P_{J}(f)}$ mit ${\displaystyle P_{J}(f)(x)=\sum _{n\in \mathbb {Z} }\left(\int _{0}^{1}f\left(2^{-J}(n+t)\right)\,\mathrm {d} t\right)\cdot \phi (2^{J}x-n)}$.

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

${\displaystyle P_{J+1}(f)(x)-P_{J}(f)(x)=\sum _{n\in \mathbb {Z} }\left(\int _{0}^{1}f\left(2^{-J-1}(2n+t)\right)\,\mathrm {d} t-\int _{0}^{1}f\left(2^{-J-1}(2n+1+t)\right)\,\mathrm {d} t\right)\cdot \psi (2^{J}x-n)}$.

Mit ${\displaystyle \phi _{j,k}(x)={{\sqrt {2}}\,}^{j}\phi ({2\,}^{j}x-k)}$ und ${\displaystyle \psi _{j,k}(x)={{\sqrt {2}}\,}^{j}\psi ({2\,}^{j}x-k)}$ als Funktionen im Hilbertraum ${\displaystyle L^{2}(\mathbb {R} )}$ gilt

• alle diese Funktionen haben ${\displaystyle L^{2}}$-Norm 1,
• ${\displaystyle \phi _{j,k}}$ ist senkrecht zu ${\displaystyle \phi _{j,l}}$ falls ${\displaystyle k\not =l}$,
• ${\displaystyle \psi _{i,k}}$ ist senkrecht zu ${\displaystyle \psi _{j,l}}$ falls ${\displaystyle i\not =j}$ oder ${\displaystyle k\not =l}$,
• die ${\displaystyle \psi _{i,k}}$ bilden eine Hilbertbasis von ${\displaystyle L^{2}(\mathbb {R} )}$.

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

${\displaystyle 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)}$.

Dieser wird nun gliedweise mit der Haar-Transformationsmatrix ${\displaystyle H:={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}$ multipliziert

${\displaystyle \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)}$,

dabei ist ${\displaystyle s_{k}={\frac {f_{2k+1}+f_{2k}}{\sqrt {2}}}}$ und ${\displaystyle d_{k}={\frac {f_{2k+1}-f_{2k}}{\sqrt {2}}}}$.

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

${\displaystyle f_{2k}={\frac {s_{k}-d_{k}}{\sqrt {2}}}}$ und ${\displaystyle f_{2k+1}={\frac {s_{k}+d_{k}}{\sqrt {2}}}}$

Ist die Schwankung von Glied zu Glied im Ausgangssignal durch ein kleines ${\displaystyle \epsilon >0}$ beschränkt, so ist die Schwankung in ${\displaystyle s}$ durch ${\displaystyle {\sqrt {2}}\epsilon }$ beschränkt, also immer noch klein, die Größe der Glieder in ${\displaystyle d}$ jedoch durch ${\displaystyle \epsilon /{\sqrt {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.

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

Als diskretes Signal ${\displaystyle f}$ wird meist eine reelle Folge ${\displaystyle (f_{n})}$ über ${\displaystyle Z}$ mit endlicher Energie betrachtet,

${\displaystyle \sum _{n=-\infty }^{\infty }\,|f_{n}|^{2}<\infty }$.

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

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

${\displaystyle f=\sum _{n=-\infty }^{\infty }\,f_{n}\cdot \delta ^{n}}$

oder als Summe zweier Reihen

${\displaystyle f=\sum _{n=-\infty }^{\infty }\,f_{2n}\cdot \delta ^{2n}+\sum _{n=-\infty }^{\infty }\,f_{2n+1}\cdot \delta ^{2n+1}}$.

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

${\displaystyle ac+bd={\frac {1}{2}}(a+b)(c+d)+{\frac {1}{2}}(a-b)(c-d)}$

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

${\displaystyle f=\sum _{n=-\infty }^{\infty }\,{\frac {f_{2n}+f_{2n+1}}{\sqrt {2}}}\cdot {\frac {\delta ^{2n}+\delta ^{2n+1}}{\sqrt {2}}}+\sum _{n=-\infty }^{\infty }\,{\frac {f_{2n}-f_{2n+1}}{\sqrt {2}}}\cdot {\frac {\delta ^{2n}-\delta ^{2n+1}}{\sqrt {2}}}}$

Jetzt führen wir neue Bezeichnungen ein:

• die neuen Basisfolgen

${\displaystyle a^{n}:={\frac {\delta ^{2n}+\delta ^{2n+1}}{\sqrt {2}}}}$ und ${\displaystyle b^{n}:={\frac {\delta ^{2n}-\delta ^{2n+1}}{\sqrt {2}}}}$

• mit den neuen transformierten Koeffizienten

${\displaystyle s_{n}:={\frac {f_{2n}+f_{2n+1}}{\sqrt {2}}}}$ und ${\displaystyle d_{n}:={\frac {f_{2n}-f_{2n+1}}{\sqrt {2}}}}$.

Wir erhalten somit die Zerlegung der Haar-Wavelet-Transformation

${\displaystyle f=\sum _{n=-\infty }^{\infty }\,s_{n}\cdot a^{n}+\sum _{n=-\infty }^{\infty }\,d_{n}\cdot b^{n}}$.

und mittels des unendlichen euklidischen Skalarproduktes können wir schreiben

${\displaystyle s_{n}=\langle f,\,a^{n}\rangle }$ und ${\displaystyle d_{n}=\langle f,\,b^{n}\rangle }$.

Die letzten drei Identitäten beschreiben eine „Conjugate Quadrature Filterbank (CQF)“, welche so auch für allgemeinere Basisfolgen ${\displaystyle a^{n}}$ und ${\displaystyle b^{n}}$ definiert werden kann. Die Basisfolgen ${\displaystyle a^{n}}$ entstehen alle durch Verschiebung um das jeweilige ${\displaystyle 2n}$ aus ${\displaystyle a^{0}}$, die ${\displaystyle b^{n}}$ durch Verschiebung aus ${\displaystyle b^{0}}$. Weiteres dazu im Artikel Daubechies-Wavelets.

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

${\displaystyle (s^{1},d^{1})}$, ${\displaystyle (s^{2},d^{2},d^{1})}$, ${\displaystyle (s^{3},d^{3},d^{2},d^{1})}$, …

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

${\displaystyle \left({\tfrac {N}{2}},{\tfrac {N}{2}}\right)}$, ${\displaystyle \left({\tfrac {N}{4}},{\tfrac {N}{4}},{\tfrac {N}{2}}\right)}$, ${\displaystyle \left({\tfrac {N}{8}},{\tfrac {N}{8}},{\tfrac {N}{4}},{\tfrac {N}{2}}\right)}$, …

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.