From e0b98f30ae4ca98de9605a63956c07238c13b12b Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Andreas=20M=C3=BCller?= <andreas.mueller@ost.ch>
Date: Mon, 6 Sep 2021 12:05:16 +0200
Subject: editorial edits ifs, crystal, typos in clifford

---
 buch/papers/ifs/teil3.tex | 66 +++++++++++++++++++++++++++++++----------------
 1 file changed, 44 insertions(+), 22 deletions(-)

(limited to 'buch/papers/ifs/teil3.tex')

diff --git a/buch/papers/ifs/teil3.tex b/buch/papers/ifs/teil3.tex
index cebb664..0ce12d8 100644
--- a/buch/papers/ifs/teil3.tex
+++ b/buch/papers/ifs/teil3.tex
@@ -6,6 +6,7 @@
 \section{Fraktale Bildkomprimierung
 \label{ifs:section:teil3}}
 \rhead{Fraktale Bildkomprimierung}
+\index{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 {\em Fractals Everywhere} einen wichtigen Beitrag zum Verständnis von Fraktalen geliefert hat.
 Das Ziel ist, ein IFS zu finden, welches das Bild als Attraktor hat.
@@ -23,17 +24,21 @@ Doch wie finden wir das PIFS, welches das Bild als Attraktor hat?
 
 \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.
+\index{Kompressionsverfahren}%
+Wir beschränken das Verfahren auf Graustufenbilder. Wie das Verfahren für Farbbilder verwendet werden kann, wird später erläutert.
+\index{Graustufenbild}%
 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 = f(x,y)\) zuweist.
 
 Wir suchen ein PIFS, welches das zu komprimierende Bild als Attraktor hat.
-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\}$. Diese sind als Raster im rechten Bild der Abbildung \ref{ifs:FIC} dargestellt.
+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\}$. Diese sind als Raster im rechten Bild der Abbildung \ref{ifs:FIC} dargestellt.
+\index{Range-Block}%
+\index{Domain-Block}%
 
-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 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.
-Zwei Beispiele wie solche Domain-, und Range-Block Paare aussehen können, sehen wir in Abbildung \ref{ifs:FIC}
+Zwei Beispiele, wie solche Domain- und Range-Block Paare aussehen können, sehen wir in Abbildung \ref{ifs:FIC}
 
 \subsubsection{Finden des ähnlichsten $D_j$}
 Zuerst brauchen wir die Transformation 
@@ -54,10 +59,10 @@ Zuerst brauchen wir die Transformation
 		\alpha_i \\
 		\beta_i \\
 		g_i
-	\end{pmatrix}
+	\end{pmatrix},
 \end{align*}
 um ein Element aus $D$ auf ein Element von $R$ abzubilden. 
-Das bestimmen der besten Transformation kann man in drei Schritte aufteilen.
+Das Bestimmen der besten Transformation kann man in drei Schritte aufteilen.
 
 \textbf{Schritt 1: }Wenn wir die Grauwerte ausser acht lassen, haben wir die affine Abbildung
 \begin{align}
@@ -74,9 +79,10 @@ Das bestimmen der besten Transformation kann man in drei Schritte aufteilen.
 	\begin{pmatrix}
 		\alpha_i \\
 		\beta_i
-	\end{pmatrix}.
+	\end{pmatrix}
 \label{ifs:affTrans}
 \end{align}
+zu finden.
 Da wir mit Pixeln arbeiten, ist die Auswahl der möglichen Abbildungen begrenzt.
 Wir sind auf folgende acht Abbildungen beschränkt:
 \begin{itemize}
@@ -85,25 +91,29 @@ Wir sind auf folgende acht Abbildungen beschränkt:
 	\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 $D_j$ um $1/2$ skalieren.
-Dies erreichen wir, indem wir alle disjunkten $2 \times 2$ Pixel Blöcke mit einem Pixel des Grautones deren Mittelwertes ersetzen.
+Dies erreichen wir, indem wir alle disjunkten $2 \times 2$\,Pixel Blöcke durch ein Pixel mit dem Grauton des Mittelwertes ersetzen.
+\index{Grauton}%
 
 \textbf{Schritt 2: }Es muss nicht nur eine geometrische Abbildung, sondern auch eine Abbildung für die Grautöne gewählt werden. Letztere lässt sich mit den Parametern $s_i$ und $g_i$ beschrieben.
-Wir suchen einen linearen Zusammenhang zwischen den Grautönen des Domain-, und Range-Block. $s_i$ verändert den Kontrast und $g_i$ verschiebt die Grautöne auf die richtige Helligkeit, sie bilden die lineare Funktion
+Wir suchen einen linearen Zusammenhang zwischen den Grautönen des Domain- und Range-Block. $s_i$ verändert den Kontrast und $g_i$ verschiebt die Grautöne auf die richtige Helligkeit, sie bilden die lineare Funktion
+\index{Helligkeit}%
 \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 \eqref{ifs:affTrans} transformierten Domain-Blocks $D_j$.
+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 \eqref{ifs:affTrans} transformierten Domain-Blocks $D_j$.
 
 Wir suchen $s_i$ und $g_i$ so das der quadratische Abstand zwischen 
 \begin{align*}
-	\bar{f_{R_i}} = s_i \tilde{f_{R_i}} + g_i
+	\bar{f}_{R_i} = s_i \tilde{f}_{R_i} + g_i
 \end{align*}
 und $f_{R_i}$ am kleinsten ist.
 Dies ist ein klassisches Problem der linearen Regression. Die Parameter lassen sich mit
+\index{lineare Regression}%
+\index{Regression, lineare}%
 \begin{align*}	
-	s_i = \frac{\operatorname{cov}(f_{R_i}, \tilde{f_{R_i}})}{\operatorname{var}(\tilde{f_{R_i}})} \\
-	g_i = E(f_{R_i}) - s E(\tilde{f_{R_i}})
+	s_i = \frac{\operatorname{cov}(f_{R_i}, \tilde{f}_{R_i})}{\operatorname{var}(\tilde{f}_{R_i})} \\
+	g_i = E(f_{R_i}) - s E(\tilde{f}_{R_i})
 \end{align*}
 berechnen.
 Die Varianz und Kovarianz erstrecken sich über die Grauwerte der Pixel der Blöcke.
@@ -111,13 +121,15 @@ 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 Fehler
 \begin{align*}
-	e = d(f_{R_i}, \bar{f_{R_i}}).
+	e = d(f_{R_i}, \bar{f}_{R_i})
+=
+E(|f_{R_i} - \bar{f}_{R_i}|^2)
 \end{align*}
 $e$ sollte so klein wie möglich sein.
 
 \textbf{Schritt 3: }
 Somit haben wir die zwei Schritte um eine Transformation $T_i$ zu finden.
-Wir führen den zweiten Schritt für jede der acht möglichen affinen Abbildungen vom ersten Schritt aus, und bestimmen den jeweilig resultierenden Fehler $e$.
+Wir führen den zweiten Schritt für jede der acht möglichen affinen Abbildungen vom ersten Schritt aus und bestimmen den jeweilig resultierenden Fehler $e$.
 Es resultieren acht $T_j$ mit ihren jeweiligen Fehlern.
 
 Um den besten Domain-Block zu finden, führen wir die drei Schritte für jeden Domain-Block aus.
@@ -129,11 +141,12 @@ Am Ende des Algorithmus haben wir für jeden Range-Block den zugehörigen Domain
 \begin{figure}	
 	\centering
 	\includegraphics[width=\textwidth]{papers/ifs/images/FIC}
-	\caption{Domain-, und Range-Block Paare in Grün und Rot}
+	\caption{Domain- und Range-Block Paare in Grün und Rot}
 	\label{ifs:FIC}
 \end{figure}
 
 \subsubsection{Rekonstruktion des Bildes}
+\index{Rekonstruktion}%
 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.
@@ -143,22 +156,31 @@ 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}
+\index{Farbbild}%
 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).
+Jeder Pixel eines Farbbildes besteht aus einem Rot-, Grün- und Blauwert (RGB).
+\index{Rotwert}%
+\index{Grünwert}%
+\index{Blauwert}%
+\index{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. 
+\index{Farbkanal}%
+Nun wendet man auf jedes dieser Farbkanalbilder den Algorithmus an und fügt nach der Rekonstruktion die Kanäle wieder zusammen. 
 
 \subsubsection{Performance des Verfahren}
 Experimentelle Beobachtungen haben gezeigt, dass dieser Grundalgorithmus der fraktalen Bildkompression recht langsam ist und auch schlecht für grössere Bilder skaliert.
-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.
+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.
+\index{JPEG}%
+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}
+Als Beispiel wählen wir das 360$\times$360 Pixel Bild von Rapperswil in Abbildung \ref{ifs:original}.
+\index{Rapperswil}%
 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 Domain 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 360$\times$360 Pixel Bild von Rapperswil in Abbildung \ref{ifs:original}.
+
 Das Startbild ist ein mittelgraues 360$\times$360 Pixel Bild, Abbildung \ref{ifs:bild0}.
 Es kann jedoch ein beliebiges Startbild sein.
 Nun lassen wir das PIFS laufen.
-- 
cgit v1.2.1

