1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
%
% teil3.tex -- Beispiel-File für Teil 3
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
\section{Fraktale Bildkomprimierung
\label{ifs:section:teil3}}
\rhead{Fraktale Bildkomprimierung}
Mit dem Prinzip dieser IFS ist es auch möglich Bilder zu Komprimieren.
Diese Idee hatte der Mathematiker Michael Barnsley, welcher mit seinem Buch Fractals Everywhere einen wichtigen beitrag zum verständnis von Fraktalen geiefert hat.
Das Ziel ist es ein IFS zu finden, welches das Bild als Attraktor hat.
In diesem Unterkapitel wollen wir eine Methode dafür anschauen.
Bis jetzt wurde in Zusammenhnag mit IFS immer erwähnt, dass die Transformationen auf die ganze Menge angewendet werden.
Dies muss jedoch nicht so sein.
Es gibt auch einen Attraktor, wenn die Transformationen nur Teile der Menge auf die ganze Menge abbilden.
Diese Eigenschaft wollen wir uns in der Fraktalen Bildkompression zunutze machen.
Sie ermöglicht uns Ähnlichkeiten zwischen kleineren Teilen des Bildes zunutze machen.
Es ist wohl nicht Falsch zu sagen, dass Ähnlichkeiten zur gesamten Menge, wie wir sie zum Beispiel beim Barnsley Fern gesehen haben, bei Bilder aus dem Alltag eher selten anzutreffen sind.
Doch wie Finden wir die richtigen Affinen Transformationen, welche als IFS das Bild als Attraktor haben?
\subsection{Titel
\label{ifs:subsection:malorum}}
In der Beschreibung des Verfahrens wird sich auf Graustufenbilder bezogen. Wie das Verfahren für Farbbilder verwendet werden kann, wird später erläutert.
In einem ersten Schritt teilen wir das Bild in disjunkte benachbarte $b \times b$ Pixel-Quadrate auf. Diese Blöcke nennen wir Range-Blöcke der Menge $R=\{R_0,R_1,...R_m\}$
Im nächesten Schritt teilen wir das Bild in alle möglichen $2b \times 2b$ Pixel-Quadrate auf. Diese sind die Domain-Blöcke der Menge $D = \{D_0,D_1,...D_n\}$.
Im dritten und letzten Schritt wird für jeden Range-Block $R_i$ ein Domain-Block $D_j$ gesucht, welcher ihm am ähnlichsten ist.
\subsubsection{Finden des ähnlichsten $D_j$}
Zuerst braucen wir die Transformation um ein Element aus $D$ auf ein Element von $R$ Abzubilden.
\begin{align*}
T(x,y,z) =
\begin{pmatrix}
a & b & 0 \\
c & d & 0 \\
0 & 0 & s
\end{pmatrix}
\begin{pmatrix}
x \\
y \\
z
\end{pmatrix}
+
\begin{pmatrix}
\alpha \\
\beta \\
g
\end{pmatrix}
\end{align*}
Diese Transformation bildet den Pixel $P$ auf Koordinate $(x,y)$ und Graustufe $z$ auf den Pixel $P'$ ab.
Da wir mit Pixeln arbeiten, sind die Transformationen in der Ebene Beschränkt.
Diese wird durch die Paramenter $a,b,c$ und $d$ bestimmt.
Mögliche Transfomrationen sind auf folgende Liste Beschränkt:
\begin{itemize}
\item Identische Transformation, keine änderung
\item Drehung um 90, 180 oder 270 Grad.
\item Spiegelung an der vertikalen, horizontalen und den Diagonalachsen.
\end{itemize}
$\alpha$ und $\beta$ verschieben den Pixel an die richtige Stelle.
Da wir ein $2b \times 2b$ Feld auf ein $b \times b$ Feld abbilden möcheen, müssen wir zuerst $G_j$ um $1/2$ skalieren.
Dies erreichen wir, indem wir alle disjunkten $2 \times 2$ px Blöcke mit einem Pixel des Grautones deren Mittelwertes ersetzen.
Skaliert und transformiert erhalten wir $\tilde{D_j}$
Die Parameter $s$ und $g$ beschreiben die Änderung des Grautones. $s$ verändert den Kontrast und $g$ verschiebt die Töne auf die richtige Helligkeit.
$s$ und $g$ werden mit der linearen Regression ermittelt.
\begin{align*}
z' = sz + g \\
f(\tilde{D_j}) \text{, Funktion um das Bild eins Blockes zu erhalten} \\
s = \frac{cov(f(R_i), f(\tilde{D_j}))}{var(\tilde{D_j})} \\
g = E(f(R_i)) - s E(f(\tilde{D_j}))
\end{align*}
Mit diesen Parameteren haben wir nun die Transformation vollständig bestimmt.
Um zu beurteilen ob der Domain-Block $D_j$ mit der gefundenen Transfromation $T$ dem Range-Block $R_i$ genügend ähnlich ist, berechnet man den quadratischen Abstand $e$.
\begin{align*}
e = d(f(R_i), f(T(D_j)))
\end{align*}
Dieser Abstand sollte so klein wie möglich sein.
Die beste Kombination von $D_j$ und $T_i$ ist also diese, welche den kleinsten Abstand zum Block $R_i$ hat, und somit am ähnlichsten ist.
Am Ende des Verfahrens haben wir also für jeden $R_i$ einen passenden $D_i$ mit der zugehörigen Abbildung $T_i$ gefunden.
\subsubsection{Rekonstruktion des Bildes}
Mit den Gefundenen Abbildungen lässt sich das Bild generieren.
Wir beginnen wie schon im letzten Kapitel mit einer beliebigen Startmenge.
In unserem Fall ist dieses ein Bild $f_0$ derselben Grösse.
Nun ersetzen wir jedes $R_i$ mit der Transformierten des zugehörigen Domain-Blocks $T(G_j)$.
Dies wird verkürzt als Operator $W$ geschrieben.
So erhalten wir ein neues Bild $f_1 = W(f_0)$.
Dieses Vorgehen führen wir iteriert aus bis wir von $f_n = W(f_{n-1})$ zu $f_{n-1}$ kaum mehr einen unterschied fesstellen. Die Iteration hat nun ihren Fixpunkt, das Bild, erreicht.
TODO Bilder Beispiel
TODO Performance und Kompressonsverhältnis
|
