From dfb9b5075e428e41f02cdf2d758a02899eea7e1e Mon Sep 17 00:00:00 2001 From: Alain Date: Fri, 4 Jun 2021 18:55:37 +0200 Subject: New Chapter IFS --- buch/papers/ifs/images/koch0-eps-converted-to.pdf | Bin 0 -> 5087 bytes buch/papers/ifs/images/koch1-eps-converted-to.pdf | Bin 0 -> 5141 bytes buch/papers/ifs/images/koch2-eps-converted-to.pdf | Bin 0 -> 5210 bytes buch/papers/ifs/images/koch8-eps-converted-to.pdf | Bin 0 -> 103521 bytes buch/papers/ifs/images/sierpinski.PNG | Bin 0 -> 293448 bytes buch/papers/ifs/images/sierpinski1.PNG | Bin 0 -> 11571 bytes buch/papers/ifs/images/sierpinski2.PNG | Bin 0 -> 12811 bytes buch/papers/ifs/images/sierpinski3.PNG | Bin 0 -> 14204 bytes buch/papers/ifs/images/sierpinski6.PNG | Bin 0 -> 30626 bytes buch/papers/ifs/main.tex | 19 ---- buch/papers/ifs/teil2.tex | 128 +++++++++++++++++----- buch/papers/ifs/teil3.tex | 46 +++----- 12 files changed, 114 insertions(+), 79 deletions(-) create mode 100644 buch/papers/ifs/images/koch0-eps-converted-to.pdf create mode 100644 buch/papers/ifs/images/koch1-eps-converted-to.pdf create mode 100644 buch/papers/ifs/images/koch2-eps-converted-to.pdf create mode 100644 buch/papers/ifs/images/koch8-eps-converted-to.pdf create mode 100644 buch/papers/ifs/images/sierpinski.PNG create mode 100644 buch/papers/ifs/images/sierpinski1.PNG create mode 100644 buch/papers/ifs/images/sierpinski2.PNG create mode 100644 buch/papers/ifs/images/sierpinski3.PNG create mode 100644 buch/papers/ifs/images/sierpinski6.PNG (limited to 'buch/papers/ifs') diff --git a/buch/papers/ifs/images/koch0-eps-converted-to.pdf b/buch/papers/ifs/images/koch0-eps-converted-to.pdf new file mode 100644 index 0000000..078c399 Binary files /dev/null and b/buch/papers/ifs/images/koch0-eps-converted-to.pdf differ diff --git a/buch/papers/ifs/images/koch1-eps-converted-to.pdf b/buch/papers/ifs/images/koch1-eps-converted-to.pdf new file mode 100644 index 0000000..81dcf18 Binary files /dev/null and b/buch/papers/ifs/images/koch1-eps-converted-to.pdf differ diff --git a/buch/papers/ifs/images/koch2-eps-converted-to.pdf b/buch/papers/ifs/images/koch2-eps-converted-to.pdf new file mode 100644 index 0000000..b7c7de7 Binary files /dev/null and b/buch/papers/ifs/images/koch2-eps-converted-to.pdf differ diff --git a/buch/papers/ifs/images/koch8-eps-converted-to.pdf b/buch/papers/ifs/images/koch8-eps-converted-to.pdf new file mode 100644 index 0000000..0bafd03 Binary files /dev/null and b/buch/papers/ifs/images/koch8-eps-converted-to.pdf differ diff --git a/buch/papers/ifs/images/sierpinski.PNG b/buch/papers/ifs/images/sierpinski.PNG new file mode 100644 index 0000000..1e57bf1 Binary files /dev/null and b/buch/papers/ifs/images/sierpinski.PNG differ diff --git a/buch/papers/ifs/images/sierpinski1.PNG b/buch/papers/ifs/images/sierpinski1.PNG new file mode 100644 index 0000000..91195f9 Binary files /dev/null and b/buch/papers/ifs/images/sierpinski1.PNG differ diff --git a/buch/papers/ifs/images/sierpinski2.PNG b/buch/papers/ifs/images/sierpinski2.PNG new file mode 100644 index 0000000..df57c13 Binary files /dev/null and b/buch/papers/ifs/images/sierpinski2.PNG differ diff --git a/buch/papers/ifs/images/sierpinski3.PNG b/buch/papers/ifs/images/sierpinski3.PNG new file mode 100644 index 0000000..055818f Binary files /dev/null and b/buch/papers/ifs/images/sierpinski3.PNG differ diff --git a/buch/papers/ifs/images/sierpinski6.PNG b/buch/papers/ifs/images/sierpinski6.PNG new file mode 100644 index 0000000..7990497 Binary files /dev/null and b/buch/papers/ifs/images/sierpinski6.PNG differ diff --git a/buch/papers/ifs/main.tex b/buch/papers/ifs/main.tex index 48c38f9..8ae0fad 100644 --- a/buch/papers/ifs/main.tex +++ b/buch/papers/ifs/main.tex @@ -8,25 +8,6 @@ \begin{refsection} \chapterauthor{Alain Keller} -Ein paar Hinweise für die korrekte Formatierung des Textes -\begin{itemize} -\item -Absätze werden gebildet, indem man eine Leerzeile einfügt. -Die Verwendung von \verb+\\+ ist nur in Tabellen und Arrays gestattet. -\item -Die explizite Platzierung von Bildern ist nicht erlaubt, entsprechende -Optionen werden gelöscht. -Verwenden Sie Labels und Verweise, um auf Bilder hinzuweisen. -\item -Beginnen Sie jeden Satz auf einer neuen Zeile. -Damit ermöglichen Sie dem Versionsverwaltungssysteme, Änderungen -in verschiedenen Sätzen von verschiedenen Autoren ohne Konflikt -anzuwenden. -\item -Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren -Übersicht wegen, aber auch um GIT die Arbeit zu erleichtern. -\end{itemize} - \input{papers/ifs/teil0.tex} \input{papers/ifs/teil1.tex} \input{papers/ifs/teil2.tex} diff --git a/buch/papers/ifs/teil2.tex b/buch/papers/ifs/teil2.tex index bfd1684..a3d5ee1 100644 --- a/buch/papers/ifs/teil2.tex +++ b/buch/papers/ifs/teil2.tex @@ -3,38 +3,106 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Teil 2 +\section{Fraktale mit IFS \label{ifs:section:teil2}} \rhead{Teil 2} -Sed ut perspiciatis unde omnis iste natus error sit voluptatem -accusantium doloremque laudantium, totam rem aperiam, eaque ipsa -quae ab illo inventore veritatis et quasi architecto beatae vitae -dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit -aspernatur aut odit aut fugit, sed quia consequuntur magni dolores -eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam -est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci -velit, sed quia non numquam eius modi tempora incidunt ut labore -et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima -veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam, -nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure -reprehenderit qui in ea voluptate velit esse quam nihil molestiae -consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla -pariatur? +Wollen wir nun eine bestimmte Art anschauen, wie man Fraktale machen kann. +Zur veranschaulichung dieser Methode nehmen wir das Sierpinski Dreieck. +\begin{figure} + \label{ifs:sierpinski10} + \centering + \includegraphics[width=0.5\textwidth]{papers/ifs/images/sierpinski} + \caption{Sierpinski-Dreieck} +\end{figure} +Wenn man das Dreieck genau anschaut, erkennt man schnell, dass es aus drei kleineren Kopien seiner selbst besteht. +Es ist also ein Selbstähnliches Konstrukt. +Diese Eigenschaft wollen wir uns zunutze machen. -\subsection{De finibus bonorum et malorum -\label{ifs:subsection:bonorum}} -At vero eos et accusamus et iusto odio dignissimos ducimus qui -blanditiis praesentium voluptatum deleniti atque corrupti quos -dolores et quas molestias excepturi sint occaecati cupiditate non -provident, similique sunt in culpa qui officia deserunt mollitia -animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis -est et expedita distinctio. Nam libero tempore, cum soluta nobis -est eligendi optio cumque nihil impedit quo minus id quod maxime -placeat facere possimus, omnis voluptas assumenda est, omnis dolor -repellendus. Temporibus autem quibusdam et aut officiis debitis aut -rerum necessitatibus saepe eveniet ut et voluptates repudiandae -sint et molestiae non recusandae. Itaque earum rerum hic tenetur a -sapiente delectus, ut aut reiciendis voluptatibus maiores alias -consequatur aut perferendis doloribus asperiores repellat. +Wir definieren das Dreieck mit kantenlänge 1 als Menge $X$. +Ausserdem bestimmen wir drei Funktionen, welche die gesamte Menge auf eine ihrer kleineren Kopien abbildet +\begin{align*} + f_1(x,y) + = + \begin{pmatrix} + \frac{1}{2} & 0 \\ + 0 & \frac{1}{2} \\ + \end{pmatrix} + \begin{pmatrix} + x\\ + y\\ + \end{pmatrix} + ,\quad + f_2(x,y) + = + \begin{pmatrix} + \frac{1}{2} & 0 \\ + 0 & \frac{1}{2} \\ + \end{pmatrix} + \begin{pmatrix} + x\\ + y\\ + \end{pmatrix} + + + \begin{pmatrix} + \frac{1}{2} \\ + 0 + \end{pmatrix} + , \quad + f_3(x,y) + = + \begin{pmatrix} + \frac{1}{2} & 0 \\ + 0 & \frac{1}{2} \\ + \end{pmatrix} + \begin{pmatrix} + x\\ + y\\ + \end{pmatrix} + + + \begin{pmatrix} + \frac{1}{4} \\ + \frac{1}{2} + \end{pmatrix}\\ +\end{align*} +$f_1$ bildet das Dreieck auf das Teilstück unten links ab, $f_2$ auf das Teilstück unten rechts und $f_3$ auf das obere Teilstück. +Wendet man alle drei Funktionen auf das Sierpinski-Dreieck an, entsteht also wieder ein Sierpinski-Dreieck. +\begin{align*} + X = \bigcup\limits_{i = 1}^{3} f_i(X) +\end{align*} +Man kann sogar noch einen Schritt weiter gehen, und sagen: Wenn wir die Funktionen auf eine beliebige Startmenge anwenden, konvergeiert die Menge gegen das Sierpinski-Dreieck. +\begin{figure} + \label{ifs:sierpconst} + \centering + \subfigure[]{ + \label{ifs:sierpconsta} + \includegraphics[width=0.25\textwidth]{papers/ifs/images/sierpinski1}} + \subfigure[]{ + \label{ifs:sierpconstb} + \includegraphics[width=0.25\textwidth]{papers/ifs/images/sierpinski2}} + \subfigure[]{ + \label{ifs:sierpconstc} + \includegraphics[width=0.25\textwidth]{papers/ifs/images/sierpinski3}} + \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} +\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 bei unendlich Iterationen gegen null. + +\subsection{Iterierte Funktionensysteme +\label{ifs:subsection:bonorum}} +In diesem Unterkapitel wollen wir die Erkenntniss, wie wir aus einer beliebigen Menge ein Sierpinski-Dreieck genereieren können, verallgemeinern. +TODO TEXT +$S_1_...,S_n$ sind Kontraktionen auf die 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$. Dann existiert eine eindeutige kompakte Menge $F$ für die gilt +\begin{equation} + F = \bigcup\limits_{i = 1}^{m} S_i(F) +\end{equation} +TODO Text diff --git a/buch/papers/ifs/teil3.tex b/buch/papers/ifs/teil3.tex index 23fabbc..bba6e32 100644 --- a/buch/papers/ifs/teil3.tex +++ b/buch/papers/ifs/teil3.tex @@ -3,38 +3,24 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Teil 3 +\section{Fraktale Bildkomprimierung \label{ifs:section:teil3}} -\rhead{Teil 3} -Sed ut perspiciatis unde omnis iste natus error sit voluptatem -accusantium doloremque laudantium, totam rem aperiam, eaque ipsa -quae ab illo inventore veritatis et quasi architecto beatae vitae -dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit -aspernatur aut odit aut fugit, sed quia consequuntur magni dolores -eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam -est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci -velit, sed quia non numquam eius modi tempora incidunt ut labore -et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima -veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam, -nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure -reprehenderit qui in ea voluptate velit esse quam nihil molestiae -consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla -pariatur? +\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. -\subsection{De finibus bonorum et malorum +\subsection{Titel \label{ifs:subsection:malorum}} -At vero eos et accusamus et iusto odio dignissimos ducimus qui -blanditiis praesentium voluptatum deleniti atque corrupti quos -dolores et quas molestias excepturi sint occaecati cupiditate non -provident, similique sunt in culpa qui officia deserunt mollitia -animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis -est et expedita distinctio. Nam libero tempore, cum soluta nobis -est eligendi optio cumque nihil impedit quo minus id quod maxime -placeat facere possimus, omnis voluptas assumenda est, omnis dolor -repellendus. Temporibus autem quibusdam et aut officiis debitis aut -rerum necessitatibus saepe eveniet ut et voluptates repudiandae -sint et molestiae non recusandae. Itaque earum rerum hic tenetur a -sapiente delectus, ut aut reiciendis voluptatibus maiores alias -consequatur aut perferendis doloribus asperiores repellat. +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. + + -- cgit v1.2.1