Dekorrelation

Nächstes: Quantisierung Letztes: Das Drei-Phasen-Kompressions-Modell

Dekorrelation

Wie bereits angedeutet soll die Dekorrelation des Bildsignals durch eine Wavelet-Zerlegung implementiert werden. Es stellt sich natürlich die berechtigte Frage, ob nicht durch ein anderes Verfahren eine noch ,,bessere`` Zerlegung der Eingangsgröße möglich ist. Tatsächlich gibt es ein solches Verfahren:
Wenn die Korrelation der vorliegenden Daten genau bekannt ist, kann mit Hilfe der sogenannten Karhunen-Loève-Darstellung eine in gewisser Hinsicht optimale Basis gefunden werden. Das Verfahren beruht auf der Berechnung der Eigenvektoren der Korrelationsmatrix. Die Gründe, die gegen dieses Verfahren sprechen, sind jedoch so gravierend, daß für praktische Zwecke eine weniger optimale Lösung mit Hilfe von Wavelets vorgezogen wird:

Die benötigte Korrelationsmatrix ist in der Regel unbekannt .
Der Aufwand für die Berechnung der Eigenvektoren beträgt , was bereits bei einem Bild mit Pixeln einen beachtlichen Rechenaufwand mit sich bringt ().
Selbst wenn die optimale Basis bekannt ist, benötigt die Berechnung der Transformation quadratischen Aufwand.
Die Basis ist abhängig von den konkreten Eingangsgrößen.

Die Wavelet-Transformation kann hingegen mit linearem Aufwand implementiert werden. Hierzu bedient man sich in der Regel sogenannter QMF-Systeme, wobei QMF für Quadratic Mirror Filter steht. Ein solches System untergliedert sich in einen Hochpaß-Filter

und einen Tiefpaß-Filter T, welche sich jeweils durch eine finite Folge

bzw.

beschreiben lassen. Die Filterung eines (eindimensionalen) Signals erfolgt in dieser Darstellung durch Faltung der entsprechenden Filterkoeffizienten

mit dem Eingangssignal

, d.h. das gefilterte Signal

ergibt sich zu

Im Fall des QMF-Systems sind die Koeffizienten

des Hochpaß-Filters durch die den Tiefpaß-Filter beschreibenden

bereits festgelegt (vgl. MRA):

Beschreibt das Paar

die Rücktransformation, so gilt für das zugehörige Paar von (Vorwärts-) Transformations-Filtern

Die effektive Ausführung der Wavelet-Transformation besteht nun in der simultanen Filterung des Eingangssignals mit

und

und anschließendem downsampling um den Faktor 2 der Ausgangssignale.
Die daraus abgeleitete Anwendung auf ein zweidimensionales (Bild-) Signal läßt sich wie folgt beschreiben:

Das Eingangssignal (Original-Bild) wird in x-Richtung (horizontal) simultan mit dem Hochpaß und dem Tiefpaß gefiltert. Die resultierenden Bilder und erlauben aufgrund der Wahl der Filter eine Rekonstruktion des Originals.
Da die Bandbreite von und bzgl. der x-Achse nur noch halb so groß ist wie die des Ausgangssignals, kann die Hälfte der Spalten von und verlustfrei entfernt werden (downsampling). Seien und die Ergebnisse des Sampling-Vorgangs.
und werden in y-Richtung (vertikal) simultan mit und gefiltert. Die resultierenden Bilder seien .
weisen in y-Richtung nur noch eine halb so große Bandbreite wie bzw. auf, d.h. die Hälfte der Zeilen kann jeweils entfernt werden. Damit erhält man vier Bilder .

Die vier erhaltenen Bildern können visuell folgendermaßen interpretiert werden:

entspricht einer geglätteten und verkleinerten Version des Originalbildes (gewissermaßen eine Darstellung des Originals bei verringerter Auflösung)
in treten besonders die horizontalen Bildelemente hervor
in dominieren die vertikalen Bildelemente
betont die diagonalen Strukturen des Original-Bildes

Das nachstehende Blockdiagramm verdeutlicht nochmals einen einzelnen Durchlauf der Wavelettransformation. Das Verfahren kann rekursiv auf die verkleinerte Version des Originalbildes angewendet werden; theoretisch kann die Transformationssequenz durchlaufen werden, bis das Ausgangsbild zu einem einzelnen Punkt zusammengeschrumpft ist. Praktisch wird dies kaum gemacht, da meist bereits vorher eine hinreichende Kompressionsrate erreichbar ist.

Anmerkung: Die Einschränkung der Rekursion auf das verkleinerte Originalbild ist nicht zwingend; es kann durchaus erwünscht sein andere ,,Teilbilder`` in die Rekursion enzubeziehen.

Abbildung 1: Schematischer Ablauf einer Wavelettransformation

Es sollen an dieser Stelle noch einige Details erwähnt werden, die bei der Implementierung des obigen Verfahrens zu beachten sind:

Das Entfernen der Zeilen bzw. Spalten reduziert die Größe des Eingangsbildes jeweils um den Faktor 2. Insbesondere bei mehrfacher Iteration des Vorgangs kann es sich als sehr störend erweisen, wenn das Bildformat nicht als Zweierpotenz darstellbar ist oder eine hinreichend große Zweierpotenz als Faktor enthält. Auch in diesem Sinne ist es anzustreben, daß das Transformationsschema nur möglichst selten zu durchlaufen ist. Gegebenenfalls sollte das Original-Bild im Format entsprechend angepaßt werden, um das obige Verfahren möglichst direkt übernehmen zu können.
Die eigentliche Filterung des Signals wird wie bereits gesagt durch Faltung der Filterkoeffizienten mit dem Eingangssignal realisiert:

Das Eingangssignal ist hierbei eine (evtl. endliche) Folge Gemäß der obigen Faltungsvorschrift können aber negative Indizes, also nicht vorhandene Komponenten , auftreten. Ist die Folge endlich, ergibt sich am ,,Ende`` des Tupels ein analoges Problem mit zu großen Indizes. Die Randpunkte des Signals müssen deshalb gesondert betrachtet werden. Einige mit relativ geringem Aufwand realisierbaren Möglichkeiten sind:
- Entfernen der Randpunkte-die Randpunkte werden ersatzlos abgeschnitten
- Fortsetzung durch Spiegelung-das Signal wird durch die Festlegung (ggf. am anderen Rand analog) fortgesetzt
- Fortsetzung durch erzwungene Periodizität-besitzt das Signal nur eine endliche Ausdehnung, wird es an den Rändern wieder angefügt
Die Realisierung der Filterung bzw. Faltung erfordert eine hinreichend gute Rechengenauigkeit. Als Hinweis mögen einige Filterkoeffizienten des Tiefpaßfilters dienen, welche bei Verwendung des Daubechies-Wavelets auftreten:

Treten hier größere Rundungsfehler auf, kann dies merkliche Qualitätsverluste bei den Ausgangsdaten nach sich ziehen - nicht zuletzt bei rekursiver Anwendung des Transformationsschemas.

Nä<`;chstes: Quantisierung Letztes: Das Drei-Phasen-Kompressions-Modell

Rainer Steinwandt