5.6 Fraktale Kompression

Iterierte Funktionssysteme sind in der Lage, mit wenigen Regeln komplexe, natürlich aussehende Bilder zu erzeugen. Hierbei wird eine Folge von Punkten im R ² durch fortgesetzte Anwendung von affinen Transformationen durchlaufen. Jede Transformation ist definiert durch eine 2 × 2 - Deformationsmatrix A , einen Translationsvektor b und eine Anwendungswahrscheinlichkeit p , wodurch ein Punkt $\overline{x}$ abgebildet wird auf A$\overline{x}$ + b . Zum Beispiel erzeugen folgende 4 Regeln das Blatt eines Farns:

Button Start führt 10.000 Iterationen aus.
Mit gedrückter Maustaste
kann Zoom-Bereich festgelegt werden.

Eine alternative Sichtweise zur Definition eines fraktalen Bildes verlangt die Selbstähnlichkeit von Teilen des Bildes mit dem Ganzen.

Beispielsweise sei ein Rechteck R gesucht, so daß sich sein Inhalt, jeweils auf ein Viertel verkleinert, im linken oberen, linken unteren und rechten unteren Quadranten wiederfindet. Beginnend mit einem beliebigen Rechteckinhalt werden die 3 Quadranten so lange als skalierte Versionen des Gesamtrechtecks ersetzt, bis wir nahe am Fixpunkt dieser Iterationen angelangt sind. Das Ergebnis ist das sogenannte Sierpinsky-Dreieck.

Sierpinsky-Dreieck

Im Gegensatz zu einem Pixelbild mit fester Auflösung in horizontaler und vertikaler Richtung läßt sich in ein fraktal erzeugtes Bild beliebig reinzoomen, da sein Inhalt durch eine auflösungsunabhängige Rechenvorschrift definiert ist.
Ziel der fraktalen Kompression ist es, in einer gegebenen Bildvorlage Selbstähnlichkeiten zu erkennen und diese durch ein System von affinen Transformationen zu beschreiben. Beim Entpacken können dann die Auswirkungen dieser Transformationen in beliebiger Detaillierung berechnet werden.

Zur fraktalen Kompression eines S/W -Bildes G werden zunächst die schwarzen Bildteile durch rechteckige, disjunkte Domain-Blöcke D₁,D₂,...,D_n überdeckt. Dann wird zu jedem Domain-Block D_i ein zu ihm selbstähnlicher Range-Block R_i gesucht, d.h. ein Teilbereich R_i des Bildes G und eine affine, kontraktive Abbildung w_i mit

d.h., das durch w_i erzeugte Abbild des Inhaltes von R_i liegt sehr nah (im Sinne einer geeigneten Metrik) am Inhalt von D_i .

Domain-Block D_i wird angenähert durch w_i(R_i)

In einer praktischen Implementierung sind alle D_i Teile einer rechteckigen Kachelung von G . Wegen der Kontraktivität der affinen Abbildungen sind die Regionen R_i (ggf. überlappende) Rechtecke mit jeweils doppelter Kantenlänge. Bei der Wahl der w_i beschränkt man sich auf jeweils eine der 8 elementaren Verformungen mithilfe von Spiegelungen an den x -, y - und Diagonal-Achsen sowie Rotationen um 0, 90, 180 und 270 Grad.

Die 8 möglichen Transformationsmatrizen

Map # D_x D_y R_x R_y Symmetrie

1 0 0 0 0 0

2 4 4 0 0 0

3 8 8 0 0 2

4 12 12 0 0 0

Ausgangsbild, Domain-Blöcke, Range-Blöcke, 4 affine Abbildungen

Bild G und eine Überdeckung mit Domainblöcken

Suche nach geeigneten Range-Blöcken

Zuordnung von Range- und Domainblöcken

Koordiantensystem zur Referenz einer linken unteren Reckteck-Ecke

Map # D_x D_y R_x R_y Symmetrie

1 0 2.5 0 2 0

2 1 2.5 0 2 0

3 2 2 2 2 0

4 3 2 2 2 0

5 2 3 2 2 0

6 3 3 2 2 0

7 2 1 2 0 0

8 3 1 2 0 0

9 3 0 2 0 0

Beschreibung eines Schwarzweißbildes durch 9 affine Abbildungen
von Range-Blöcken mit Koordinanten R_x,R_y
auf Domain-Blöcke mit Koordinanten D_x,D_y .

Eine einfache Methode zur Bestimmung des Attraktors A eines IFS (iterierten Funktionensystems) ist der Escape-Time-Algorithmus:

Da alle Domain-Blöcke D₁,...,D_n eine Überdeckung der schwarzen Bildteile von R ergeben, hat jedes x $\in$ D=D₁$\bigcup$D₂$\bigcup$...$\bigcup$D_n durch die für seine Domain zuständige Abbildung w_i : R_i $\rightarrow$ D_i ein eindeutiges Urbild f (x) : = w_i^{- 1}(x) .
Sei eine maximale Iterationszahl MAX_ITER vorgegeben.

Färbe alle Pixel des (vorläufigen) Attraktors A schwarz.
Für jedes Pixel x ₀ tue:
x = x ₀
for (z = 0; ((z++ < MAX_ITER) && (x $\in$ D)); x = f(x));
if (x $\not\in$ D) färbe x weiß (d.h. gehört nicht zum Attraktor)

Auswirkungen der ersten 4 Iterationen des Escape-Time-Algorithmus

Bei Grauwertbildern wird der Helligkeitswert als 3. Dimension geführt, und die affinen Abbildungen haben die Form:

wobei die Koeffizienten a_i,b_i,c_i,d_i Transformationen beschreiben gemäß der 8 möglichen Symmetrien mit einem Kontraktivitätsfaktor s = ${\frac{1}{2}}$ . P ist eine feste Konstante unterhalb des Kontraktivitätsfaktors s , Q_i eine individuelle Helligkeitsverschiebung. Der Grauwert z wird daher abgebildet auf

Die Domain-Blöcke D_i bilden nun eine Partition des Rechtecks R ; die Range-Blöcke mit doppelter Kantenlänge beginnen mit ihrer linken unteren Ecke an endlich vielen, dafür vorgesehenen Gitterpunkten. Zur Bestimmung des Attraktors werden, ausgehend von einem beliebigen Rechteckinhalt, immer wieder die lokalen Abbildungen w_i auf ihre Range-Blöcke R_i angewendet und berechnen ein Update der zugehörigen Domain-Blöcke.

13 14 15 16

9 10 11 12

5 6 7 8

1 2 3 4

Partitionierung des Bildes in Domain-Blöcke

einige Anfangspositionen der Range-Blöcke

Map R_x R_y Symmetrie Q

1 0 8 0 -7

2 0 8 6 29

3 0 4 4 50

4 0 8 0 -4

5 0 8 0 -7

6 3 4 2 50

7 3 5 5 -16

8 0 6 3 50

9 0 8 0 -7

10 2 5 0 58

11 0 8 2 48

12 0 8 1 32

13 0 8 0 -7

14 0 5 5 -12

15 0 8 5 23

16 0 8 0 -7

Beispiel für fraktale Beschreibung eines Grauwertbildes
durch 16 affine Abbildungen

jan.fif, 26.592 KBytes fraktal komprimiert Original-Auflösung 696 x 924 x 24 Kompression 72:1

Vergrößerung eines Ausschnitts einer JPEG-Komprimierung ausgehend vom selben Original mit Kompressionsrate 71:1