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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
%
% 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 geliefert 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, wie sie in \cite{ifs:Rousseau2012} beschrieben ist.
Bis jetzt wurde in Zusammenhang mit IFS immer erwähnt, dass die Transformationen, welche das IFS bilden, auf die gesamte Menge.
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 Farn 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{das Kompressionsverfahren
\label{ifs:subsection:malorum}}
Wir beschränken das Verfahren für Graustufenbilder. Wie das Verfahren für Farbbilder verwendet werden kann, wird später erläutert.
Ein Graustufenbild kann man als Pixelraster mit einer x und y Achse verstehen.
Jedem dieser Pixel wird ein Grauwert zugeordnet.
Ein Bild ist also eine Funktion, die jedem Pixel einen Grauwert $z$ zuweist
\begin{align*}
z = f(x,y).
\end{align*}
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ächsten 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 brauchen wir die Transformation
\begin{align*}
T_i(x,y,z) =
\begin{pmatrix}
a_i & b_i & 0 \\
c_i & d_i & 0 \\
0 & 0 & s_i
\end{pmatrix}
\begin{pmatrix}
x \\
y \\
z
\end{pmatrix}
+
\begin{pmatrix}
\alpha_i \\
\beta_i \\
g_i
\end{pmatrix}
\end{align*}
um ein Element aus $D$ auf ein Element von $R$ Abzubilden.
Wenn wir die Grauwerte ausser acht lassen, haben wir die affine Abbildung
\begin{align}
t_i(x,y) =
\begin{pmatrix}
a_i & b_i \\
c_i & d_i
\end{pmatrix}
\begin{pmatrix}
x \\
y
\end{pmatrix}
+
\begin{pmatrix}
\alpha_i \\
\beta_i
\end{pmatrix}.
\label{ifs:affTrans}
\end{align}
Da wir mit Pixeln arbeiten, ist die Auswahl der möglichen Abbildungen begrenzt.
Wir sind auf folgende acht Abbildungen 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}
Da wir ein $2b \times 2b$ Feld auf ein $b \times b$ Feld abbilden möchten, 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.
Die Parameter $s_i$ und $g_i$ beschreiben die Änderung des Grautones. $s$ verändert den Kontrast und $g$ verschiebt die Töne auf die richtige Helligkeit, sie bilden die lineare Funktion
\begin{align*}
z' = s_i z + g_i.
\end{align*}
Für die Bestimmung dieser Parameter führen wir zuerst die Bildfunktionen $f_{R_i}$ und $\tilde{f_{R_i}}$ ein.
$f_{R_i}$ ist die Bildfunktion des Range-Blockes $R_i$ und $\tilde{f_{R_i}}$ ist die Bildfunktion des zuerst Skalierten und dann mit \ref{ifs:affTrans} transformierten Domain-Blocks $D_j$.
$s$ und $g$ werden mit der einfachen linearen Regression ermittelt.
Wir suchen $s_i$ und $g_i$ so das
\begin{align*}
f_{R_i} = s_i \tilde{f_{R_i}} + g_i = \bar{f_{R_i}}.
\end{align*}
Die Parameter lassen sich mit
\begin{align*}
s = \frac{\operatorname{cov}(f_{R_i}), f(\tilde{f_{R_i}}))}{\operatorname{var}(\tilde{f_{R_i}})} \\
g = E(f_{R_i}) - s E(f(\tilde{f_{R_i}}))
\end{align*}
berechnen.
Mit diesen Parametern haben wir nun die Transformation vollständig bestimmt.
Um zu beurteilen wie ähnlich der Domain-Block $D_j$ mit der gefundenen Transformation $T$ dem Range-Block ist, berechnet man den quadratischen Abstand
\begin{align*}
e = d(f_{R_i}, \bar{f_{R_i}}).
\end{align*}
Dieser Abstand sollte so klein wie möglich sein.
Wir bestimmen die Parameter $s$ und $g$ für jede der acht möglichen affinen Abbildungen und das mit jedem Domain-Block.
Die Kombination von $D_j$ und $T_i$, welche den kleinsten Abstand $e$ hat, ist die beste.
Diese Schritte führen wir für jeden Range-Block $R_i$ aus.
Am Ende des Algorithmus haben wir für jeden Range-Block den zugehörigen Domain-Block und Transformation 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 feststellen. Die Iteration hat nun ihren Attraktor, das Bild, erreicht.
\subsubsection{Farbbilder}
Dieses Verfahren mit Graustufenbilder lässt sich ganz einfach auf Farbbilder erweitern.
Jeder Pixel eines Farbbildes besteht aus einem Rot, Grün und Blauwert (RGB).
Teilt man ein Bild in die drei Farbkanäle auf, das heisst, es wird nur noch ein Farbwert benutzt, erhält man drei Bilder, welche wie ein Graustufenbild sind.
Nun wendet man auf jeden dieser Farbkanalbilder den Algorithmus an, und fügt nach der Rekonstruktion die Kanäle wieder zusammen.
\subsubsection{Performance des Verfahren}
Dieser Grundalgorithmus der fraktalen Bildkompression ist recht langsam und skaliert auch schlecht für grössere Bilder.
Dies resultiert aus eigenen Experimenten.
Man kann die Laufzeit zwar verbessern indem man die Domain-Blöcke auch disjunkt macht, und für weniger detailreiche Bilder ein grösseres $b$ wählt, jedoch wird er auch so nicht so schnell wie zum Beispiel das JPEG-Verfahren.
Es wurden bessere Algorithmen der fraktalen Bildkompression entwickelt, doch auch diese können, vor allem in der Laufzeit, noch nicht mit herkömmlichen Komprimierungsverfahren mithalten.
\subsection{Beispiel}
Wir Verwenden dafür den oben beschriebenen Algorithmus, welcher uns für jeden Range-Block die benötigten Parameter liefert.
Mit diesen lässt sich das Bild im Anschluss wieder Rekonstruieren.
Die Range-Blöcke wurden $4\times4$ gewählt und die Dommain dementsprechend $8\times8$.
Um etwas Zeit bei der Komprimierung zu ersparen, wurden nur disjunkte Domain-Blöcke gebraucht.
Als erstes Beispiel wählen wir das 360x360px Bild von Rapperswil in Abbildung \ref{ifs:original}.
Das Startbild ist ein mittelgraues 360x360px Bild, Abbildung \ref{ifs:bild0}.
Es kann jedoch ein beliebiges Startbild
Nun lassen wir das IFS laufen.
Wie wir in Abbildung \ref{ifs:rappirecoa} sehen, ist schon nach der ersten Iteration das Bild schon erkennbar.
Nach der fünften Iteration , Abbildung \ref{ifs:rappirecoc} gibt es fast keinen Unterschied mehr zur letzten Iteration, wir können die Rekonstruktion beenden.
\begin{figure}
\centering
\includegraphics[width=0.4\textwidth]{papers/ifs/images/original}
\caption{Original Bild von Rapperswil}
\label{ifs:original}
\end{figure}
\begin{figure}
\centering
\includegraphics[width=0.4\textwidth]{papers/ifs/images/rapperswil}
\caption{Startbild}
\label{ifs:bild0}
\end{figure}
\begin{figure}
\centering
\subfigure[]{
\label{ifs:rappirecoa}
\includegraphics[width=0.32\textwidth]{papers/ifs/images/rapperswil01}}
\subfigure[]{
\label{ifs:rappirecob}
\includegraphics[width=0.32\textwidth]{papers/ifs/images/rapperswil001}}
\subfigure[]{
\label{ifs:rappirecoc}
\includegraphics[width=0.32\textwidth]{papers/ifs/images/rapperswil04}}
\caption{(a) 1. Iteration (b) 2. Iteration (c) 5. Iteration}
\label{ifs:rappireco}
\end{figure}
|
