aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/ifs
diff options
context:
space:
mode:
authorfabioviecelli <80270098+fabioviecelli@users.noreply.github.com>2021-09-08 09:23:56 +0200
committerfabioviecelli <80270098+fabioviecelli@users.noreply.github.com>2021-09-08 09:23:56 +0200
commit910a4f556d89d75ee07384a2a3fb963334552264 (patch)
tree53f346e2de59d4bf1365535b709f0a2e8ebffba1 /buch/papers/ifs
parentErgänzungen (diff)
parenteditorial edits clifford (diff)
downloadSeminarMatrizen-910a4f556d89d75ee07384a2a3fb963334552264.tar.gz
SeminarMatrizen-910a4f556d89d75ee07384a2a3fb963334552264.zip
Merge remote-tracking branch 'upstream/master'
Diffstat (limited to '')
-rw-r--r--buch/papers/ifs/teil0.tex9
-rw-r--r--buch/papers/ifs/teil1.tex55
-rw-r--r--buch/papers/ifs/teil2.tex81
-rw-r--r--buch/papers/ifs/teil3.tex66
4 files changed, 126 insertions, 85 deletions
diff --git a/buch/papers/ifs/teil0.tex b/buch/papers/ifs/teil0.tex
index af2105e..2a803d6 100644
--- a/buch/papers/ifs/teil0.tex
+++ b/buch/papers/ifs/teil0.tex
@@ -5,8 +5,13 @@
%
\section{Einleitung \label{ifs:section:teil0}}
\rhead{Was ist ein Iteriertes Funktionsschema}
-Mit der Hilfe von Iterierten Funktionsschemata (IFS) können mit nur wenigen affinen Funktionen komplexe Bilder beschrieben werden.
+Mit der Hilfe von iterierten Funktionsschemata (IFS) können mit nur wenigen affinen Funktionen komplexe Bilder beschrieben werden.
+\index{iterierte Funktionsschemata}%
+\index{Funktionschemata, iterierte}%
+\index{affine Funktion}%
In der Regel sind diese Bilder Fraktale.
-Wie es dazu kommt, und wie man mit IFS auch Bilder komprimieren kann, wollen wir in diesem Kapitel untersuchen.
+\index{Fraktal}%
+Wie es dazu kommt und wie man mit IFS auch Bilder komprimieren kann, wollen wir in diesem Kapitel untersuchen.
+\index{Bildkompression}%
diff --git a/buch/papers/ifs/teil1.tex b/buch/papers/ifs/teil1.tex
index caba120..08e1cbf 100644
--- a/buch/papers/ifs/teil1.tex
+++ b/buch/papers/ifs/teil1.tex
@@ -11,20 +11,27 @@ Bevor wir die IFS ansehen, schauen wir uns Fraktale genauer an.
In diesem Kapitel orientieren wir uns an den Eigenschaften, welche Kenneth Falconer in seinem Buch {\em Fractal Geometry} \cite{ifs:fractal-geometry} beschreibt.
Von einem Fraktal $F$ können wir folgende Eigenschaften erwarten:
\begin{enumerate}
- \item $F$ hat eine unendlich feine Struktur
+ \item $F$ hat eine unendlich feine Struktur.
\item $F$ kann nicht mit der klassischen Geometrie beschrieben werden.
\item Oftmals hat $F$ eine Form von Selbstähnlichkeit.
+\index{Selbstähnlichkeit}%
Man spricht von einer selbstähnlichen Menge, wenn sich diese Menge überdecken lässt mit echten Teilmengen, die zur ganzen Menge ähnlich sind.
- \item Die `fraktale Dimension' ist grösser als die topologische Dimension.
+ \item Die ``fraktale Dimension'' ist grösser als die topologische Dimension.
+\index{Dimension, topologische}%
+\index{topologische Dimension}%
+\index{fraktale Dimension}%
+\index{Dimension, fraktale}%
\item Viele Fraktale lassen sich auf eine simple Art definieren. Es genügen zum Beispiel nur wenige Funktionen, welche rekursiv ausgeführt werden, um ein Fraktal zu definieren.
\end{enumerate}
-\subsection{Koch Kurve
+\subsection{Koch-Kurve
\label{ifs:subsection:lilkoch}}
-Diese Eigenschaften möchten wir nun am Beispiel der Koch Kurve näher anschauen.
-In Abbildung \ref{ifs:kochkurve8} sehen wir die Koch Kurve. Sie besteht aus lauter kleineren Kopien von sich selbst.
+\index{Kochsche Kurve}%
+\index{Schneeflockenkurve}%
+Diese Eigenschaften möchten wir nun am Beispiel der Koch-Kurve näher anschauen.
+In Abbildung \ref{ifs:kochkurve8} sehen wir die Koch-Kurve. Sie besteht aus lauter kleineren Kopien von sich selbst.
Der Konstruktionsvorgang ist in Abbildung \ref{ifs:kochconst} dargestellt.
Gestartet wird mit einer einzelnen Strecke der Länge $a$.
-Diese wird in ersten Schritt durch vier gleich langen Streckenabschnitte der Länge $\frac{a}{3}$ ersetzt.
+Diese wird im ersten Schritt durch vier gleich langen Streckenabschnitte der Länge $\frac{a}{3}$ ersetzt.
In \ref{ifs:kochconstb} ist die Anordnung dieser vier Streckenabschnitte ersichtlich.
Dieser Schritt wird nun für jeden der resultierten Streckenabschnitten wiederholt.
Die Kurve besteht also aus vier kleineren Kopien der ganzen Kurve, was auch unter Selbstähnlichkeit bekannt ist.
@@ -33,7 +40,7 @@ Die Kurve besteht also aus vier kleineren Kopien der ganzen Kurve, was auch unte
\begin{figure}
\centering
\includegraphics{papers/ifs/images/koch8}
- \caption{Koch Kurve}
+ \caption{Koch-Kurve}
\label{ifs:kochkurve8}
\end{figure}
@@ -48,23 +55,24 @@ Die Kurve besteht also aus vier kleineren Kopien der ganzen Kurve, was auch unte
\subfigure[]{
\label{kochconstc}
\includegraphics[width=0.32\textwidth]{papers/ifs/images/koch2}}
- \caption{(a) Start (b) 1. Iteration (c) 2. Iteration}
+ \caption{(a) Start, (b) 1.~Iteration, (c) 2.~Iteration}
\label{ifs:kochconst}
\end{figure}
Die resultierende Kurve hat ein paar interessante Eigenschaften.
Die Länge der Kurve der jeweiligen Iteration lässt sich mit
\begin{align*}
- l_0 = a ,\quad l_1 = a \frac{4}{3} ,\quad l_2 = a \left( \frac{4}{3}\right)^2 , \quad \cdots , \quad
+ l_0 = a ,\quad l_1 = a \frac{4}{3} ,\quad l_2 = a \left( \frac{4}{3}\right)^2 , \dots , \quad
l_n = a \cdot \left( \frac{4}{3}\right)^n \quad
\Rightarrow \quad
\lim_{n\to\infty} a \left( \frac{4}{3}\right)^n = \infty
\end{align*}
berechnen.
In jedem Schritt wird die Länge um den Faktor $\frac{4}{3}$ verlängert. Daraus resultiert, dass die Länge gegen $\infty$ divergiert.
+\index{divergiert}%
-Die Fläche zwischen der Strecke von $O$ nach $(1,0)$ und der Kurve lässt sich folgendermassen berechnen
+Die Fläche zwischen der Strecke von $O$ nach $(1,0)$ und der Kurve lässt sich folgendermassen berechnen:
\begin{align*}
A_0 &= 0 \\
A_1 &= \left( \frac{a}{3}\right)^2 \frac{\sqrt{3}}{4} = a^2 \frac{\sqrt{3}}{36}\\
@@ -72,36 +80,39 @@ Die Fläche zwischen der Strecke von $O$ nach $(1,0)$ und der Kurve lässt sich
A_3 &= A_1 + A_2 + 4^2 \left( \frac{a}{3^2}\right)^2 \frac{\sqrt{3}}{4} = A_1 + \frac{4}{9} A_1 + \left( \frac{4}{9}\right)^2 A_1.
\end{align*}
Wir sehen, dass mit jedem Schritt die neu dazugekommene Fläche um $\frac{4}{9}$ kleiner ist.
-Die Gesamtfläche ist daher gegeben durch die konvergierende geometrische Reihe,
+Die Gesamtfläche ist daher gegeben durch die konvergierende geometrische Reihe
\begin{align*}
- A_n = A_1 \sum_{i = 0}^{n-1} \left( \frac{4}{9}\right)^n = a^2 \frac{\sqrt{3}}{36} \sum_{i = 0}^{n-1} \left( \frac{4}{9}\right)^n \\
+ A_n = A_1 \sum_{i = 0}^{n-1} \left( \frac{4}{9}\right)^n = a^2 \frac{\sqrt{3}}{36} \sum_{i = 0}^{n-1} \left( \frac{4}{9}\right)^n
\end{align*}
mit dem Grenzwert
\begin{align*}
\lim_{n\to\infty} a^2 \frac{\sqrt{3}}{36} \sum_{i = 0}^{n-1} \left( \frac{4}{9}\right)^n = \frac{\sqrt{3}}{20} a^2.
\end{align*}
-Wie wir sehen ist die Koch-Kurve ein Objekt mit endlicher Fläche, aber unendlichem Umfang.
+Wie wir sehen, ist die Koch-Kurve ein Objekt mit endlicher Fläche, aber unendlichem Umfang.
Zu guter Letzt bestimmen wir die Dimension der Kurve.
Es gibt viele verschiedene Methoden die Dimension zu definieren. Diese können dann auch unterschiedliche Resultate liefern.
Vor allem im Zusammenhang mit Fraktalen findet man in der Literatur unterschiedliche Arten.
-Da die Kochsche Kurve selbstähnlich ist, ist die Ähnlichkeits-Dimension \cite{ifs:fractal-geometry} die angemessene Messzahl für die Dimension.
-Die Ähnlichkeits-Dimension $D$ ist das Verhältnis der Logarithmen der Anzahl Kopien $N$ des Originales und deren Skalierungsfaktor $\epsilon$
+Da die Kochsche Kurve selbstähnlich ist, ist die Ähnlichkeitsdimension \cite{ifs:fractal-geometry} die angemessene Masszahl für die Dimension.
+Die Ähnlichkeitsdimension $D$ ist das Verhältnis der Logarithmen der Anzahl Kopien $N$ des Originales und deren Skalierungsfaktor $\varepsilon$
\begin{align*}
- D = - \frac{\log N}{\log \epsilon }.
+ D = - \frac{\log N}{\log \varepsilon }.
\end{align*}
-Die Ähnlichkeits-Dimension stimmt für viele gewöhnliche Geometrische Objekte mit der intuitiven Vorstellung von Dimension überein.
-Zum Beispiel besteht ein Dreieck aus $N = 4$ Kopien mit halber ($\epsilon = 1/2$) Kantenlänge $l$, Abbildung \ref{ifs:trinagle}.
+Die Ähnlichkeitsdimension stimmt für viele gewöhnliche geometrische Objekte mit der intuitiven Vorstellung von Dimension überein.
+Zum Beispiel besteht das Dreieck
+von Abbildung \ref{ifs:trinagle}
+aus $N = 4$ Kopien mit halber ($\varepsilon = 1/2$) Kantenlänge $l$.
Somit hat das Dreieck die Dimension $D = 2$.
-Die Koch Kurve besteht aus $N = 4$ Kopien mit Kantenlänge $\epsilon =l \cdot 1/3$.
-Ihre Ähnlichkeits-Dimension ist somit
+
+Die Koch Kurve besteht aus $N = 4$ Kopien mit Kantenlänge $\varepsilon =l \cdot 1/3$.
+Ihre Ähnlichkeitsdimension ist somit
\begin{align*}
- D = - \frac{\log N }{\log \epsilon } = - \frac{\log 4 }{\log 1/3 } \approx 1.2619.
+ D = - \frac{\log N }{\log \varepsilon } = - \frac{\log 4 }{\log 1/3 } \approx 1.2619.
\end{align*}
Wie wir nun sehen, besitzt die Koch-Kurve alle oben beschriebenen Eigenschaften von Fraktalen.
-Dies muss jedoch nicht bei allen Fraktalen der Fall sein. Sonst wäre die Frage nach einer `richtigen' Definition einfach zu beantworten.
+Dies muss jedoch nicht bei allen Fraktalen der Fall sein. Sonst wäre die Frage nach einer ``richtigen'' Definition einfach zu beantworten.
\begin{figure}
\centering
\begin{tikzpicture}
diff --git a/buch/papers/ifs/teil2.tex b/buch/papers/ifs/teil2.tex
index d0110ed..360a2c0 100644
--- a/buch/papers/ifs/teil2.tex
+++ b/buch/papers/ifs/teil2.tex
@@ -8,7 +8,8 @@
\rhead{Teil 2}
Wollen wir nun eine bestimmte Art anschauen, wie man Fraktale erzeugen kann.
Im Beispiel auf Seite \pageref{ifs:trinagle} haben wir ein Dreieck aus 4 skalierten Kopien zusammengefügt.
-Lässt man die Kopie im Zentrum des Dreiecks weg, entsteht die Grundlage des sogenannten Sierpinski-Dreieck in Abbildung \ref{ifs:sierpinski10}.
+Lässt man die Kopie im Zentrum des Dreiecks weg, entsteht die Grundlage des sogenannten Sierpinski-Dreiecks in Abbildung \ref{ifs:sierpinski10}.
+\index{Sierpinski-Dreieck}%
\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{papers/ifs/images/sierpinski}
@@ -16,7 +17,7 @@ Lässt man die Kopie im Zentrum des Dreiecks weg, entsteht die Grundlage des sog
\label{ifs:sierpinski10}
\end{figure}
Es besteht aus drei kleineren Kopien von sich selbst.
-Es ist also ein Selbstähnliches Gebilde.
+Es ist also ein selbstähnliches Gebilde.
Diese Eigenschaft wollen wir uns zunutze machen.
@@ -73,7 +74,7 @@ Wendet man alle drei Funktionen auf das Sierpinski-Dreieck an
X = \bigcup\limits_{i = 1}^{3} f_i(X),
\end{align*}
entsteht also wieder ein Sierpinski-Dreieck.
-Man kann sogar noch einen Schritt weiter gehen, und sagen: Wenn wir die Funktionen auf eine beliebige Startmenge anwenden, konvergiert die Menge gegen das Sierpinski-Dreieck.
+Man kann sogar noch einen Schritt weiter gehen und sagen: Wenn wir die Funktionen auf eine beliebige Startmenge anwenden, konvergiert die Menge gegen das Sierpinski-Dreieck.
\begin{figure}
\centering
\subfigure[]{
@@ -88,19 +89,21 @@ Man kann sogar noch einen Schritt weiter gehen, und sagen: Wenn wir die Funktion
\subfigure[]{
\label{ifs:sierpconstd}
\includegraphics[width=0.25\textwidth]{papers/ifs/images/sierpinski6}}
- \caption{Konstruktion eines Sierpinski-Dreiecks mit einem Schwarzen Quadrat als Start\\
- (a) 1. Iteration (b) 2. Iteration (c) 3. Iteration (d) 5. Iteration}
+ \caption{Konstruktion eines Sierpinski-Dreiecks mit einem schwarzen Quadrat als Start\\
+ (a) 1.~Iteration, (b) 2.~Iteration, (c) 3.~Iteration, (d) 5.~Iteration}
\label{ifs:sierpconst}
\end{figure}
Im Beispiel der Abbildung \ref{ifs:sierpconst} sehen wir, wie das Bild nach jeder Iteration dem Sierpinski-Dreieck ähnlicher wird.
-Der `Abstand' zum Original wird immer kleiner, und konvergiert gegen null.
+Der `Abstand' zum Original wird immer kleiner und konvergiert gegen null.
\subsection{Iterierte Funktionensysteme
\label{ifs:subsection:IteratedFunktionensysteme}}
+\index{iterierte Funktionssysteme}%
In diesem Abschnitt wollen wir die Erkenntnis, wie wir aus einer beliebigen Menge ein Sierpinski-Dreieck generieren können, verallgemeinern.
$S_1,\dots,S_n$ sind Kontraktionen auf einer Menge $D \subset \mathbb{R}^n$. Es gilt
+\index{Kontraktion}%
\begin{align}
|S_i(x) - S_i(y)| \leq c_i|x - y|
\end{align}
@@ -124,10 +127,37 @@ Wird diese Transformation iterativ ausgeführt, das heisst $S^0(E) = E, S^k(E) =
\end{equation}
In Worte gefasst bedeutet das, dass jede Gruppe von Kontraktionen iterativ ausgeführt gegen eine eindeutige Menge konvergiert.
Diese Menge ist auch als Attraktor eines IFS bekannt.
+\index{Attraktor}%
Der Beweis für die Existenz eines eindeutigen Attraktors ist in \cite{ifs:fractal-geometry} beschrieben.
\subsection{Beispiel: Barnsley-Farn}
+\begin{figure}
+ \centering
+ \makebox[\textwidth][c]{
+ \includegraphics[width=1.4\textwidth]{papers/ifs/images/farn}}
+ \caption{Barnsley-Farn}
+ \label{ifs:farn}
+\end{figure}%
+\begin{figure}
+ \centering
+ \includegraphics[width=\textwidth]{papers/ifs/images/farncolor2}
+ \caption{Vier Transformationen des Barnsley-Farn in unterschiedlichen Farben}
+ \label{ifs:farncolor}
+\end{figure}%
+\begin{figure}
+ \centering
+ \includegraphics[width=\textwidth]{papers/ifs/images/chaosspiel.pdf}
+ %\subfigure[]{
+ % \label{ifs:farnNoWeight}
+ % \includegraphics[width=0.45\textwidth]{papers/ifs/images/farnnotweight}}
+ %\subfigure[]{
+ % \label{ifs:farnrightWeight}
+ % \includegraphics[width=0.45\textwidth]{papers/ifs/images/farnrightwight}}
+ \caption{(a) Chaosspiel ohne Gewichtung, (b) $S_4$ zu wenig gewichtet}
+ \label{ifs:farnweight}
+\end{figure}%
Der Barnsley-Farn, Abbildung \ref{ifs:farn}, ist ein Beispiel eines Fraktals, welches mit einem IFS generiert werden kann.
+\index{Barnsley-Farn}%
Wie man schnell erkennen kann, besteht der Farn aus Blättern, welche eine grosse Ähnlichkeit zum ganzen Farn haben.
Die vier affinen Transformationen
\begin{align}
@@ -185,7 +215,7 @@ Die vier affinen Transformationen
\begin{pmatrix}
0 \\
0.44
- \end{pmatrix},\\
+ \end{pmatrix},
\label{ifs:farnFormel}
\end{align}
welche für die Konstruktion des Farns benötigt werden, sind in der Abbildung \ref{ifs:farncolor} farblich dargestellt.
@@ -211,6 +241,7 @@ Weitere Iterationen hätten in dieser Darstellungsgrösse kaum mehr einen Unters
Die zweite Methode ist das Chaosspiel \cite{ifs:chaos}.
+\index{Chaosspiel}%
Bis jetzt wurde immer davon gesprochen, die Transformationen auf die gesamte Menge anzuwenden.
Bei komplizierteren IFS welche viele Iterationen brauchen, bis man den Attraktor erkennen kann, ist die erste Methode ziemlich rechenintensiv.
Beim Chaosspiel werden die Transformationen nicht auf die Menge angewendet, sondern nur auf einen einzelnen Punkt.
@@ -220,41 +251,13 @@ Es wird bei jedem Iterationsschritt nur eine Transformation $S_i$, welche zufäl
Da, wie wir beim Barnsley-Farn gut sehen, nicht jede Transformation gleich viel des Bildes ausmacht, werden diese beim Chaosspiel gewichtet.
Je mehr eine Transformation kontrahiert, desto weniger Punkte braucht es, um die resultierende Teilabbildung darzustellen.
Im Fall des Barnsley-Farns wird $S_1$ in $1\%$, $S_2$ in $85\%$ und $S_3$ und $S_4$ in $7\%$ der Iterationen ausgeführt.
-Wir sehen auch in Abbildung \ref{ifs:farncolor} gut, dass der rote Stiel, $S_1$, viel weniger Punkte braucht als der grüne Hauptteil des Blattes, $S_2$.
+Wir sehen auch in Abbildung \ref{ifs:farncolor} gut, dass der rote Stiel, erzeugt von $S_1$, viel weniger Punkte braucht als der grüne Hauptteil des Blattes, erzeugt von $S_2$.
-In Abbildung \ref{ifs:farnNoWeight} wurden die vier gleich stark gewichtet.
-Man sieht, dass trotzt gleich vieler Iterationen wie in Abbildung \ref{ifs:farn}, der Farn nicht so gut abgebildet wird.
+In Abbildung \ref{ifs:farnweight}(a) wurden die vier Transformationen gleich stark gewichtet.
+Man sieht, dass trotz gleich vieler Iterationen wie in Abbildung \ref{ifs:farn}, der Farn nicht so gut abgebildet wird.
-Am besten sieht man den Effekt einer schlechten Gewichtung in Abbildung \ref{ifs:farnrightWeight}.
+Am besten sieht man den Effekt einer schlechten Gewichtung in Abbildung \ref{ifs:farnweight}(b).
Hier wurde $S_4$, welches für das rechte untere Teilblatt zuständig ist, mit nur $1\%$ statt $7\%$ gewichtet.
Man sieht, wie sich der Mangel an Punkten auf die anderen Abbildungen das Farnblattes auswirkt.
In jeder Kopie des ganzen Farns fehlen die Punkte für dieses rechte untere Teilblatt.
-
-
-\begin{figure}
- \centering
- \makebox[\textwidth][c]{
- \includegraphics[width=1.4\textwidth]{papers/ifs/images/farn}}
- \caption{Barnsley-Farn}
- \label{ifs:farn}
-\end{figure}
-\begin{figure}
- \centering
- \includegraphics[width=\textwidth]{papers/ifs/images/farncolor2}
- \caption{Vier Transformationen des Barnsley-Farn in unterschiedlichen Farben}
- \label{ifs:farncolor}
-\end{figure}
-
-\begin{figure}
- \centering
- \includegraphics{papers/ifs/images/chaosspiel.pdf}
- %\subfigure[]{
- % \label{ifs:farnNoWeight}
- % \includegraphics[width=0.45\textwidth]{papers/ifs/images/farnnotweight}}
- %\subfigure[]{
- % \label{ifs:farnrightWeight}
- % \includegraphics[width=0.45\textwidth]{papers/ifs/images/farnrightwight}}
- \caption{(a) Chaosspiel ohne Gewichtung (b) $S_4$ zu wenig gewichtet}
- \label{ifs:farnweight}
-\end{figure}
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.