Theoretische und methodische Grundlagen des Visual Computing – Wavelets

Haar-Wavelets

Level-1-Haar-Transformation: Sei \(N \in \natural \) gerade.
Dann ist die Level-1-Haar-Transformation definiert als \(\H _1\colon \real ^N \to \real ^N\), \(\vec {f} \mapsto (\vec {a^{(1)}} \;|\; \vec {d^{(1)}})\) mit dem ersten Trend \(\vec {a^{(1)}} := (a_m)_{m=1}^{N/2}\) mit \(a_m := \frac {1}{\sqrt {2}} (f_{2m-1} + f_{2m})\) und
der ersten Fluktuation \(\vec {d^{(1)}} := (d_m)_{m=1}^{N/2}\) mit \(d_m := \frac {1}{\sqrt {2}} (f_{2m-1} - f_{2m})\).
\(\H _1\) ist invertierbar mit \((\H _1)^{-1}\colon \real ^N \to \real ^N\),
\((\vec {a^{(1)}} \;|\; \vec {d^{(1)}}) = \vec {f} = \frac {1}{\sqrt {2}} (a_1 + d_1, a_1 - d_1, \dotsc , a_{N/2} + d_{N/2}, a_{N/2} - d_{N/2})\).

Eigenschaften:

kleine Fluktuation: Die Fluktuationswerte sind größenordnungsmäßig oft deutlich kleiner als die Originalwerte.
Energieerhaltung: \(E_{(\vec {a^{(1)}} \;|\; \vec {d^{(1)}})} = E_{\vec {f}}\) für alle \(\vec {f} \in \real ^N\) mit \(E_{\vec {f}} := \sum _{n=1}^N f_n^2\)
Energieverdichtung: Der Großteil der Energie von \((\vec {a^{(1)}} \;|\; \vec {d^{(1)}})\) ist in \(\vec {a^{(1)}}\) enthalten.

Haar-Transformation höherer Levels: Sei \(2^n \;|\; N\). Die Level-\(n\)-Haar-Transformation ist rekursiv definiert durch \(\H _n\colon \real ^N \to \real ^N\), \(\vec {f} \mapsto (\vec {a^{(n)}} \;|\; \vec {d^{(n)}} \;|\; \dotsb \;|\; \vec {d^{(1)}})\) mit
\((\vec {a^{(n-1)}} \;|\; \vec {d^{(n-1)}} \;|\; \dotsb \;|\; \vec {d^{(1)}}) := \H _{n-1}(\vec {f})\) und \((\vec {a^{(n)}} \;|\; \vec {d^{(n)}}) := \H _1(\vec {a^{(n-1)}})\) (mit einem anderen \(N\)).

Level-1-Haar-Wavelets: Die Level-1-Haar-Wavelets sind für ein Signal der Länge \(N\) definiert durch \(\vec {W_1^{(1)}} := \frac {1}{\sqrt {2}} (1, -1, 0, \dotsc , 0)\), \(\vec {W_2^{(1)}} := \frac {1}{\sqrt {2}} (0, 0, 1, -1, 0, \dotsc , 0)\), …,
\(\vec {W_{N/2}^{(1)}} := \frac {1}{\sqrt {2}} (0, \dotsc , 0, 1, -1)\). Es gilt \(d_m = \vec {f} \cdot \vec {W_m^{(1)}}\) für \(m = 1, \dotsc , N/2\).

Level-1-Skalierungssignale: Die Level-1-Skalierungssignale sind für ein Signal der Länge \(N\) definiert durch \(\vec {V_1^{(1)}} := \frac {1}{\sqrt {2}} (1, 1, 0, \dotsc , 0)\), \(\vec {V_2^{(1)}} := \frac {1}{\sqrt {2}} (0, 0, 1, 1, 0, \dotsc , 0)\), …,
\(\vec {V_{N/2}^{(1)}} := \frac {1}{\sqrt {2}} (0, \dotsc , 0, 1, 1)\). Es gilt \(a_m = \vec {f} \cdot \vec {V_m^{(1)}}\) für \(m = 1, \dotsc , N/2\).

Rekonstruktion von \(\vec {f}\): Es gilt \(\vec {f} = \vec {A^{(1)}} + \vec {D^{(1)}}\) mit
\(\vec {A^{(1)}} = \sum _{m=1}^{N/2} a_m \vec {V_m^{(1)}} = \sum _{m=1}^{N/2} (\vec {f} \cdot \vec {V_m^{(1)}}) \vec {V_m^{(1)}}\) und \(\vec {D^{(1)}} = \sum _{m=1}^{N/2} d_m \vec {W_m^{(1)}} = \sum _{m=1}^{N/2} (\vec {f} \cdot \vec {W_m^{(1)}}) \vec {W_m^{(1)}}\).

Haar-Wavelets/Skalierungssignale höherer Levels: Seien \(\alpha _1 := \alpha _2 := \beta _1 := -\beta _2 := \frac {1}{\sqrt {2}}\). Mit \(\vec {V_m}^{(0)} := (0, \dotsc , 0, 1, 0, \dotsc , 0)\) gilt \(\vec {V_m^{(1)}} = \alpha _1 \vec {V_{2m-1}^{(0)}} + \alpha _2 \vec {V_{2m}^{(0)}}\) und \(\vec {W_m^{(1)}} = \beta _1 \vec {V_{2m-1}^{(0)}} + \beta _2 \vec {V_{2m}^{(0)}}\). Definiert man \(\vec {V_m^{(n)}} := \alpha _1 \vec {V_{2m-1}^{(n-1)}} + \alpha _2 \vec {V_{2m}^{(n-1)}}\) und \(\vec {W_m^{(n)}} := \beta _1 \vec {V_{2m-1}^{(n-1)}} + \beta _2 \vec {V_{2m}^{(n-1)}}\), so erhält man die Level-\(n\)-Haar-Wavelets/-Skalierungssignale. Es gilt \(d_m^{(n)} = \vec {f} \cdot \vec {W_m^{(n)}}\) und \(a_m^{(n)} = \vec {f} \cdot \vec {V_m^{(n)}}\).

2D-Wavelet-Transformation

2D-Wavelet-Transformation: Gegeben sei ein Bild \(G \in \real ^{M \times N}\) mit \(M, N\) gerade. Dann berechnet sich die 2D-Wavelet-Transformation für den ersten Level wie folgt:

Führe die Level-1-1D-Wavelet-Transformation für jede Zeile von \(G\) durch, um so ein neues Bild zu erhalten.
Führe auf dem neuen Bild die Level-1-1D-Wavelet-Transformation für jede Spalte durch.

Man erhält so \(G \mapsto \smallpmatrix {A^{(1)}&V^{(1)}\\H^{(1)}&D^{(1)}}\), wobei \(H^{(1)}, D^{(1)}, A^{(1)}, V^{(1)} \in \real ^{N/2 \times M/2}\) und

\(A^{(1)}\) Trends entlang Zeilen und Spalten,
\(H^{(1)}\) Trends entlang Zeilen und Fluktuationen entlang Spalten,
\(V^{(1)}\) Fluktuationen entlang Zeilen und Trends entlang Spalten und
\(D^{(1)}\) Fluktuationen entlang Zeilen und Spalten enthält.

Für höhere 2D-Wavelet-Transformationen höherer Levels führe diese Prozedur für \(A^{(1)}\) durch.

Daubechies-Wavelets

Daubechies-Wavelets: Die Daubechies-Wavelet-Transformation Daub4 ist für den Level 1 definiert durch \(D_1\colon \real ^N \to \real ^N\), \(\vec {f} \mapsto (\vec {a^{(1)}} \;|\; \vec {d^{(1)}})\), wobei \(a_m^{(1)} := \vec {f} \cdot \vec {V_m^{(1)}}\) und \(d_m^{(1)} := \vec {f} \cdot \vec {W_m^{(1)}}\) für \(m = 1, \dotsc , N/2\) und \(\vec {V_1^{(1)}} := (\alpha _1, \dotsc , \alpha _4, 0, \dotsc , 0)\), \(\vec {V_2^{(1)}} := (0, 0, \alpha _1, \dotsc , \alpha _4, 0, \dotsc , 0)\), …, \(\vec {V_{N/2-1}^{(1)}} := (0, \dotsc , 0, \alpha _1, \dotsc , \alpha _4)\) \(\vec {V_{N/2}^{(1)}} := (\alpha _3, \alpha _4, 0, \dotsc , 0, \alpha _1, \alpha _2)\) mit \(\alpha _1 := \frac {1 + \sqrt {3}}{4\sqrt {2}}\), \(\alpha _2 := \frac {3 + \sqrt {3}}{4\sqrt {2}}\), \(\alpha _3 := \frac {3 - \sqrt {3}}{4\sqrt {2}}\), \(\alpha _4 := \frac {1 - \sqrt {3}}{4\sqrt {2}}\). Dabei sei außerdem \(\vec {V_m^{(n)}} := \sum _{i=1}^{4} \alpha _i \vec {V_{2m-2+i}^{(n-1)}}\) und
\(\vec {W_m^{(n)}} := \sum _{i=1}^{4} \beta _i \vec {V_{2m-2+i}^{(n-1)}}\) mit \(\beta _1 := \alpha _4\), \(\beta _2 := -\alpha _3\), \(\beta _3 := \alpha _2\), \(\beta _4 := -\alpha _1\) für \(n \in \natural \).

Eigenschaften:

konstante Energie: \(\sum _{i=1}^4 \alpha _i^2 = 1\), \(\sum _{i=1}^4 \beta _i^2 = 1\)
Mittelwert/Differenz: \(\sum _{i=1}^4 \alpha _i = \sqrt {2}\), \(\sum _{i=1}^4 \beta _i = 0\)
Rekonstruktion: \(\vec {f} = \vec {A^{(k)}} + \sum _{n=1}^k \vec {D^{(n)}}\) mit \(\vec {A^{(n)}} := \sum _{m=1}^{N/2^n} (\vec {f} \cdot \vec {V_m^{(n)}}) \vec {V_m^{(n)}}\)
und \(\vec {D^{(n)}} := \sum _{m=1}^{N/2^n} (\vec {f} \cdot \vec {W_m^{(n)}}) \vec {W_m^{(n)}}\)