aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/ifs
diff options
context:
space:
mode:
Diffstat (limited to 'buch/papers/ifs')
-rw-r--r--buch/papers/ifs/images/Makefile9
-rw-r--r--buch/papers/ifs/images/chaosspiel.tex37
-rw-r--r--buch/papers/ifs/images/farnnotweight-eps-converted-to.pdfbin166218 -> 6074235 bytes
-rw-r--r--buch/papers/ifs/images/farnrightwight-eps-converted-to.pdfbin59191 -> 6450743 bytes
-rw-r--r--buch/papers/ifs/teil1.tex8
-rw-r--r--buch/papers/ifs/teil2.tex43
-rw-r--r--buch/papers/ifs/teil3.tex17
7 files changed, 81 insertions, 33 deletions
diff --git a/buch/papers/ifs/images/Makefile b/buch/papers/ifs/images/Makefile
new file mode 100644
index 0000000..c6d3fb5
--- /dev/null
+++ b/buch/papers/ifs/images/Makefile
@@ -0,0 +1,9 @@
+#
+# Makefile
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+chaosspiel.pdf: chaosspiel.tex \
+ farnnotweight-eps-converted-to.pdf \
+ farnrightwight-eps-converted-to.pdf
+ pdflatex chaosspiel.tex
diff --git a/buch/papers/ifs/images/chaosspiel.tex b/buch/papers/ifs/images/chaosspiel.tex
new file mode 100644
index 0000000..7c69ad3
--- /dev/null
+++ b/buch/papers/ifs/images/chaosspiel.tex
@@ -0,0 +1,37 @@
+%
+% tikztemplate.tex -- template for standalon tikz images
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+% add image content here
+
+\begin{scope}[xshift=-3.6cm]
+%\clip (-3.3,-3) rectangle (3.3,3);
+\node at (0,0) {
+\includegraphics[width=6.8cm]{farnnotweight-eps-converted-to.pdf}
+};
+\node at (0.2,-5.7) {(a)};
+\end{scope}
+
+\begin{scope}[xshift=3.6cm]
+%\clip (-3.3,-3) rectangle (3.3,3);
+\node at (0,0) {
+\includegraphics[width=6.8cm]{farnrightwight-eps-converted-to.pdf}
+};
+\node at (0.2,-5.7) {(b)};
+\end{scope}
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/papers/ifs/images/farnnotweight-eps-converted-to.pdf b/buch/papers/ifs/images/farnnotweight-eps-converted-to.pdf
index 35bff32..f5e4093 100644
--- a/buch/papers/ifs/images/farnnotweight-eps-converted-to.pdf
+++ b/buch/papers/ifs/images/farnnotweight-eps-converted-to.pdf
Binary files differ
diff --git a/buch/papers/ifs/images/farnrightwight-eps-converted-to.pdf b/buch/papers/ifs/images/farnrightwight-eps-converted-to.pdf
index 3652e8f..fa69d77 100644
--- a/buch/papers/ifs/images/farnrightwight-eps-converted-to.pdf
+++ b/buch/papers/ifs/images/farnrightwight-eps-converted-to.pdf
Binary files differ
diff --git a/buch/papers/ifs/teil1.tex b/buch/papers/ifs/teil1.tex
index 7ce546a..caba120 100644
--- a/buch/papers/ifs/teil1.tex
+++ b/buch/papers/ifs/teil1.tex
@@ -15,7 +15,7 @@ Von einem Fraktal $F$ können wir folgende Eigenschaften erwarten:
\item $F$ kann nicht mit der klassischen Geometrie beschrieben werden.
\item Oftmals hat $F$ eine Form von 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.
\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
@@ -64,7 +64,7 @@ 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.
-Die Fläche 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}\\
@@ -100,8 +100,8 @@ Ihre Ähnlichkeits-Dimension ist somit
\begin{align*}
D = - \frac{\log N }{\log \epsilon } = - \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.
+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.
\begin{figure}
\centering
\begin{tikzpicture}
diff --git a/buch/papers/ifs/teil2.tex b/buch/papers/ifs/teil2.tex
index 49c1cf3..d0110ed 100644
--- a/buch/papers/ifs/teil2.tex
+++ b/buch/papers/ifs/teil2.tex
@@ -8,7 +8,7 @@
\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, Abbildung \ref{ifs:sierpinski10}.
+Lässt man die Kopie im Zentrum des Dreiecks weg, entsteht die Grundlage des sogenannten Sierpinski-Dreieck in Abbildung \ref{ifs:sierpinski10}.
\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{papers/ifs/images/sierpinski}
@@ -93,22 +93,22 @@ Man kann sogar noch einen Schritt weiter gehen, und sagen: Wenn wir die Funktion
\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}}
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 der Menge $D \subset \mathbb{R}^n$. Es gilt
+$S_1,\dots,S_n$ sind Kontraktionen auf einer Menge $D \subset \mathbb{R}^n$. Es gilt
\begin{align}
|S_i(x) - S_i(y)| \leq c_i|x - y|
\end{align}
für jedes i mit einem $c_i < 1$.
-Der Banachsche Fixpunktsatz besagt, dass für solche Kontraktionen ein Eindeutiges $A$ existiert, für das $S_i(A) = A$ gilt.
+Man kann zeigen, dass für solche Kontraktionen ein eindeutiges $A$ existiert, für das $S_i(A) = A$ gilt.
Den Beweis kann man in \cite{ifs:Rousseau2012} nachlesen.
-Hat man nicht nur eine sondern mehrere Kontraktionen, dann existiert eine eindeutige kompakte Menge $F$ für die gilt
+Hat man nicht nur eine sondern mehrere Kontraktionen, dann existiert eine eindeutige kompakte Menge $F$, für die gilt
\begin{equation}
F = \bigcup\limits_{i = 1}^{m} S_i(F).
\end{equation}
@@ -117,12 +117,12 @@ Weiter definieren wir die Transformation S auf kompakte Mengen $E$ ohne die leer
S(E) = \bigcup\limits_{i = 1}^m S_i(E).
\label{ifs:transformation}
\end{equation}
-Wird diese Transformation Iterativ ausgeführt, das heisst $S^0(E) = E, S^k(E) = S(S^{k-1}(E))$, gilt
+Wird diese Transformation iterativ ausgeführt, das heisst $S^0(E) = E, S^k(E) = S(S^{k-1}(E))$, gilt
\begin{equation}
F = \bigcap\limits_{k = 1}^{\infty} S^k(E).
\label{ifs:ifsForm}
\end{equation}
-In Worte gefasst bedeutet das, dass jede Gruppe von Kontraktionen iterativ ausgeführt, gegen eine eindeutige Menge konvergiert.
+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.
Der Beweis für die Existenz eines eindeutigen Attraktors ist in \cite{ifs:fractal-geometry} beschrieben.
@@ -155,7 +155,7 @@ Die vier affinen Transformationen
\begin{pmatrix}
0 \\
1.6
- \end{pmatrix}\\
+ \end{pmatrix},\\
& {S_3(x,y)}
=
\begin{pmatrix}
@@ -188,7 +188,7 @@ Die vier affinen Transformationen
\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.
+welche für die Konstruktion des Farns benötigt werden, sind in der Abbildung \ref{ifs:farncolor} farblich dargestellt.
Das gesamte Farnblatt ist in der schwarzen Box.
Auf diese werden die Transformationen angewendet.
$S_1$ erstellt den Stiel des Farnblattes (rot).
@@ -198,12 +198,12 @@ Sie verkleinert und dreht das gesamte Bild und stellt es auf das Ende des Stiels
$S_3$ bildet das gesamte Blatt auf das blaue Teilblatt unten links ab.
$S_4$ spiegelt das Blatt und bildet es auf das magentafarbene Teilblatt ab.
\subsection{Erzeugung eines Bildes zu einem IFS}
-Es gibt zwei verschiedene Methoden um das Bild zu einem IFS zu erzeugen.
+Es gibt zwei verschiedene Methoden, um das Bild zu einem IFS zu erzeugen.
Die erste Methode ist wahrscheinlich die intuitivste.
-Wir beginnen mit einem Startbild, zum Beispiel ein Schwarzes Quadrat, und bilden dieses mit den affinen Transformationen des IFS ab.
-Das neue Bild, dass entsteht, ist die nächste Iterierte.
+Wir beginnen mit einem Startbild, zum Beispiel ein schwarzes Quadrat, und bilden dieses mit den affinen Transformationen des IFS ab.
+Das neue Bild, das entsteht, ist die nächste Iterierte.
Dieses wird wieder mit den Transformationen abgebildet.
-Wir wiederholen den letzten schritt, bis wir zufrieden mit der neusten Iterierten sind.
+Wir wiederholen den letzten Schritt, bis wir zufrieden mit der neusten Iterierten sind.
Diesen Vorgang haben wir beim Sierpinski-Dreieck in Abbildung \ref{ifs:sierpconst} gebraucht.
In Abbildung \ref{ifs:sierpinski10} ist die zehnte Iterierte zu sehen.
@@ -219,8 +219,8 @@ 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-Fern 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$, einiges weniger Punkte braucht als der grüne Hauptteil des Blattes, $S_2$.
+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$.
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.
@@ -248,12 +248,13 @@ In jeder Kopie des ganzen Farns fehlen die Punkte für dieses rechte untere Teil
\begin{figure}
\centering
- \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}}
+ \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 1d39c6f..cebb664 100644
--- a/buch/papers/ifs/teil3.tex
+++ b/buch/papers/ifs/teil3.tex
@@ -8,12 +8,13 @@
\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 {\em 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.
+Das Ziel ist, 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.
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.
Ein IFS, wie wir es in \ref{ifs:subsection:IteratedFunktionensysteme} definiert haben, wird uns also nicht weiter helfen.
-Anders sieht es mit Partitionierten IFS (PIFS) \cite{ifs:pifs} aus.
+Anders sieht es mit partitionierten IFS (PIFS) \cite{ifs:pifs} aus.
+
In \ref{ifs:transformation} wurde definiert, dass die Kontraktionen $S_i$ bei IFS auf die gesamte Menge $E$ angewendet werden.
Bei einem PIFS wird der Attraktor in disjunkte Teilmengen aufgeteilt.
Für jede dieser Teilmengen $R_i$ braucht es dann eine grössere Teilmenge, welche mit einer affinen Transformation eine zu $R_i$ ähnliche Menge bildet.
@@ -55,7 +56,7 @@ Zuerst brauchen wir die Transformation
g_i
\end{pmatrix}
\end{align*}
-um ein Element aus $D$ auf ein Element von $R$ Abzubilden.
+um ein Element aus $D$ auf ein Element von $R$ abzubilden.
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
@@ -83,7 +84,7 @@ Wir sind auf folgende acht Abbildungen beschränkt:
\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.
+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.
\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.
@@ -136,7 +137,7 @@ Am Ende des Algorithmus haben wir für jeden Range-Block den zugehörigen Domain
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)$.
+Nun ersetzen wir jedes $R_i$ mit der Transformierten des zugehörigen Domain-Blocks $T(D_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.
@@ -157,12 +158,12 @@ Wir verwenden dafür den oben beschriebenen Algorithmus, welcher uns für jeden
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$360px Bild von Rapperswil in Abbildung \ref{ifs:original}.
-Das Startbild ist ein mittelgraues 360$\times$360px Bild, Abbildung \ref{ifs:bild0}.
+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.
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.
+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}