2D-Wavelet-Transformation mittels Haar-Wavelet
Die zu transformierenden Daten werden in jedem Schritt in nebeneinander stehende 2-Tupel aufgeteilt und anschließend Mittelwert und Abweichung berechnet. Bei der Standard-Dekomposition werden erst alle Zeilen und danach alle Spalten transformiert, was die Implementierung stark vereinfacht. Dagegen wird bei der Nonstandard-Dekomposition die Transformation von Zeilen und Spalten abwechselnd vorgenommen, was bedingt, dass das Bild gleich viele Spalten und Zeilen haben muss. Allerdings ist dieses Verfahren effizienter, da es weniger Zuweisungen braucht.
| Original-Matrix |
| 10 | 14 | 7 | 5 |
| 16 | 12 | 13 | 19 |
| 14 | 12 | 1 | 5 |
| 8 | 2 | 3 | 3 |
|
|
|
|
Standard-Dekomposition |
Nonstandard-Dekomposition |
| 1. Schritt |
| 12 | 6 | -2 | 1 |
| 14 | 16 | 2 | -3 |
| 13 | 3 | 1 | -2 |
| 5 | 3 | 3 | 0 |
|
| 12 | 6 | -2 | 1 |
| 14 | 16 | 2 | -3 |
| 13 | 3 | 1 | -2 |
| 5 | 3 | 3 | 0 |
|
|
Der erste Schritt bei Standard- und Nonstandard-Dekomposition ist gleich: Es werden zunächst die Zeilen transformiert.
Beispiel: Die erste Zeile [10 14 7 5] wird in 2-Tupel aufgeteilt von denen jeweils Mittelwert und Abweichung berechnet werden. Das Tupel [10 14] ergibt als Mittelwert (10+14)/2=12, das Tupel [7 5] den Mittelwert 6. Als Abweichung ergibt sich für [10 14] (10-14)/2=-2 und für [7 5] (7-5)/2=1.
|
| 2. Schritt |
|
| 13 | 11 | 0 | -1 |
| 9 | 3 | 2 | -1 |
| -1 | -5 | -2 | 2 |
| 4 | 0 | -1 | -1 |
|
|
Bei der Standard-Dekomposition werden im Weiteren nur noch die Mittelwerte der Zeilen transformiert, während bei der Nonstandard-Dekomposition die ganze Spalte transformiert wird.
Beispiel: Bei der Standard-Dekomposition wird nur noch das Tupel der Mittelwerte [12 6] aus der ersten Zeile zu Mittelwert (12+6)/2=9 und Abweichung (12-6)/2=3 umgeformt. Bei der Nonstandard-Dekomposition wird die erste Spalte [12 14 13 5] zu [13 9 -1 4] transformiert.
|
| 3. Schritt |
| 12 | 1 | 0 | -1 |
| 6 | 3 | 2 | -1 |
| -3 | 2 | -2 | 2 |
| 2 | 2 | -1 | -1 |
|
| 12 | 1 | 0 | -1 |
| 6 | 3 | 2 | -1 |
| -3 | 2 | -2 | 2 |
| 2 | 2 | -1 | -1 |
|
|
Nachdem bei der Standard-Dekomposition alle Zeilen umgeformt worden sind, werden nun sämtliche Spalten transformiert. Bei der Nonstandard-Dekomposition wird nun der zweite Schritt der Zeilentransformation durchgeführt, d.h. es wird nur noch die vordere Hälfte jeder Zeile verwendet.
Beispiel: Aus der ersten Spalte [9 15 8 4] werden in der Standard-Dekomposition die Werte [12 6 -3 2]. Die Nonstandard-Dekomposition ergibt für die vordere Hälfte erste Zeile [13 11] die Werte [12 1].
|
| 4. Schritt |
| 9 | 2 | 1 | -1 |
| 3 | -1 | -1 | 0 |
| -3 | 2 | -2 | 2 |
| 2 | 2 | -1 | -1 |
|
| 9 | 2 | 1 | -1 |
| 3 | -1 | -1 | 0 |
| -3 | 2 | -2 | 2 |
| 2 | 2 | -1 | -1 |
|
|
Die letzte Umformung ist für beide Verfahren gleich: Die ersten beiden Werte jeder Spalte werden transformiert. Daraus ergibt sich der absolute Mittelwert 9 der Matrix. Alle anderen Werte sind die berechneten Abweichungen von diesem absoluten Mittelwert.
Man kann erkennen, dass die Beträge der Werte durch die Transformation deutlich abgenommen haben. Während der ursprüngliche Mittelwert 9 war, liegt er bei der umgeformten Matrix etwas über 2.
|
Bei der Transformation entsteht eine Matrix, die genau die gleiche Dimension hat, wie das ursprüngliche Bild (allerdings normalerweise mit Fließkommawerten). Die umgeformte Matrix hat die Eigenschaft, dass nicht mehr jedes Pixel für sich allein beschrieben ist, sondern die Farbe eines Pixels sich aus sehr vielen Werten der Matrix zusammensetzt. Kleinere Werte verändern das Motiv nicht so stark wie große Werte. Deshalb kann man sie wegfallen lassen um die Anzahl der zu speichernden Elemente zu verringern, ohne dass die Information des Bildes stark verfälscht wird.
Basisfunktionen und Rekonstruktion
Bilddaten, die durch eine n×m-Matrix definiert sind, liegen in einem n×m-dimensionalen Raum. Dieser Raum lässt sich durch ebenso viele linear unabhängige Basisfunktionen aufspannen. Die Bilddaten kann man durch Linearkombinationen dieser Basisfunktionen ausdrücken.
Bei der hier vorgestellten Methode werden zweidimensionale Haar-Wavelets als Basisfunktionen benutzt. Das Standard- und das Nonstandard-Dekompositions-Verfahren haben verständlicherweise unterschiedliche Basisfunktionen, da die Rekonstruktion die Umkehrfunktion der Transformation ist.
Bei der Rekonstruktion werden die Elemente der transformierten Daten mit den Basisfunktionen mutlipliziert und anschließend addiert. Im obigen Beispiel würde bei der Standard-Rekonstruktion wie bei der Nonstandard-Rekonstruktion wieder die ursprüngliche Matrix
| 10 | 14 | 7 | 5 |
| 16 | 12 | 13 | 19 |
| 14 | 12 | 1 | 5 |
| 8 | 2 | 3 | 3 |
entstehen, da keine Kompression angewendet wurde.
Normalisierung und Orthogonalisierung
Um die Größe der Daten zu reduzieren, müssen Informationen beim Speichern weggelassen werden. Um unwichtigere Elemente entfernen zu können, müssen die Werte der transformierten Matrix nach ihrem Informationsgehalt sortiert werden.
Eine Normierung der Koeffizienten ermöglicht eine Vergleichbarkeit zwischen den Werten bezogen auf ihre Energie. Das bedeutet, dass, wenn die Elemente der transformierten Matrix normiert wurden, die Koeffizienten mit größerem Einfluss auf das Signal auch einen größeren Betrag haben als Koeffizienten, die nur wenig Einfluss haben.
Aus der Gleichung
ergibt sich, dass mit einer orthonormalen Basis ein zu komprimierendes Signal in seine Komponenten zerlegt werden und anschließend wieder eindeutig rekonstruiert werden kann.
Um diese Eigenschaften nutzen zu können, muss die verwendete Basis normiert werden und orthogonal sein, wie es bei den benutzten Haar-Wavelets der Fall ist. [3]
