Iterated function system

An iterated function system ( IFS ) is a set of functions that have the same space as a domain of definition and value and are closed under linkage. So ${\displaystyle {\mathcal {F}}}$ ${\displaystyle M}$

${\displaystyle {\mathcal {F}}\circ {\mathcal {F}}\subset {\mathcal {F}}\;}$d. H. ${\displaystyle \;\forall f,g\in {\mathcal {F}}:\;f\circ g\in {\mathcal {F}}.}$

Iterated function systems are mostly used to construct fractals , which are then also referred to as IFS fractals . Well-known representatives of this class of fractals are the Sierpinski triangle and the Koch curve as well as the limit sets of Lindenmayer systems .

• 

  Sierpinski triangle

• 

  Koch curve

• 

  Sierpinski carpet

• 

  Dragon fractal

This type of fractal construction was invented by John Hutchinson in 1981 and later popularized by Michael F. Barnsley with his book Fractals Everywhere . There Barnsley also gave the collage set , which forms the basis of fractal image compression . However, this way of efficiently coding images using data structures has never really caught on and is now essentially only examined as a hybrid method in combination with a wavelet transformation .

Invariant, self-similar sets

In order to be able to derive properties for an IFS, the set of functions must meet additional requirements. Usually, when one speaks of IFS , these prerequisites are tacitly taken for granted. These requirements are

1. that the IFS is finitely generated, i.e. it contains a finite number of functions from which the others can be composed by repeated (iterated) linking,
2. that the space is a complete metric space with metric , and ${\displaystyle M}$ ${\displaystyle d}$
3. that every function of the IFS is contractive , with condition 1. it is sufficient to demand this from the producer.

Under these circumstances there is an invariant, self-similar set . ${\displaystyle X\subseteq M}$

• The subset is invariant if it is mapped into itself again by every function of the IFS. ${\displaystyle X}$
• The subset is self-similar when each point in the image set of a function . ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle F(X)}$ ${\displaystyle F\in {\mathcal {F}}}$

Self-similar sets usually do not have an integral Hausdorff dimension and are then also referred to as fractals, hence the designation IFS fractal . One could also further define the concept of self-similarity by requiring the existence of an IFS.

Existence and uniqueness of the invariant set

From a mathematical point of view, the theory of iterated function systems , as the terminology suggests, is a direct application of Banach's fixed point theorem , whereby several functions are considered instead of one and, instead of a clear fixed point, an invariant, mostly fractal, subset of the Room results. The two-dimensional unit square with the Euclidean distance is usually chosen for illustration . ${\displaystyle M}$ ${\displaystyle M=[0,1]\times [0,1]}$

So we start with a finite set of functions of a compact metric space in itself: ${\displaystyle (M,d)}$

${\displaystyle {\mathcal {F}}_{1}:=\{\phi _{1},\dots ,\phi _{r}\colon M\to M\},}$

which we assume that there is a constant of contraction with ${\displaystyle 0<c<1}$

${\displaystyle \forall x,y\in M,\phi \in {\mathcal {F}}_{1}:\;d(\phi (x),\phi (y))\leq c\,d(x,y)}$

By iteration , we proceed to an IFS , be it ${\displaystyle {\mathcal {F}}_{1}}$ ${\displaystyle {\mathcal {F}}}$

${\displaystyle {\mathcal {F}}_{n+1}:={\mathcal {F}}_{1}\circ {\mathcal {F}}_{n}:=\{\phi \circ F:\;\phi \in {\mathcal {F}}_{1},\;F\in {\mathcal {F}}_{n}\}}$

and finally get

${\displaystyle {\mathcal {F}}:=\bigcup _{n=1}^{\infty }{\mathcal {F}}_{n}}$.

Theorem: If all functions in are contractive , there is an invariant subset , which is the fixed point equation ${\displaystyle \phi _{1},\dots ,\phi _{r}}$ ${\displaystyle {\mathcal {F}}_{1}}$ ${\displaystyle X}$ ${\displaystyle X=\bigcup _{i=1}^{r}\phi _{i}(X)}$ Fulfills. For these applies: There is exactly one fixed point for each . The invariant set is the topological closure of the set of all fixed points ${\displaystyle F\in {\mathcal {F}}}$ ${\displaystyle X}$ ${\displaystyle \{x\in M|\;\exists F\in {\mathcal {F}}:\,x=F(x)\}}$. If there is any point, then applies to the distance of this point ${\displaystyle y\in M}$ ${\displaystyle d(X,F(y))\leq c_{F}\,d(X,y)}$for each . ${\displaystyle F\in {\mathcal {F}}}$ The estimate applies if there is a -fold concatenation of the output functions. ${\displaystyle c_{F}\leq c^{m}}$ ${\displaystyle F}$ ${\displaystyle m}$ ${\displaystyle F\in {\mathcal {F}}_{m}}$ Thus, by iteration of a limited initial set ${\displaystyle X}$ ${\displaystyle X_{0}\subset M,\quad X_{n+1}=\bigcup _{i=1}^{r}\phi _{i}(X_{n})}$ can be approximated as well as desired.

The proof of the theorem takes place by constructing a new space from the metric space , whose “points” are exactly the compact subsets of . A metric can then be defined (the Hausdorff metric ) with respect to which this space is complete and the mapping is a contraction. This makes Banach's fixed point theorem applicable. ${\displaystyle (M,d)}$ ${\displaystyle M}$ ${\displaystyle X\mapsto \bigcup _{i=1}^{r}\phi _{i}(X)}$

Approximation of the limit set

Chaos game

The shape of the fractal set can be visualized by a so-called chaos game . Here, a fixed point is first of identified and applied to this in random order the defining features. As an algorithm, this can look like this: ${\displaystyle X}$ ${\displaystyle {\vec {x}}}$ ${\displaystyle {\vec {x}}=\phi _{1}({\vec {x}})}$

• Example 100 times in succession to ${\displaystyle {\vec {x}}:=\phi _{1}({\vec {x}})}$
• Repeat as often as you like
  • Pick one at random ${\displaystyle i\in \left\{1,\dots ,r\right\}}$
  • Way to ${\displaystyle {\vec {x}}:=\phi _{i}({\vec {x}})}$
  • Draw the point . ${\displaystyle x}$

Annotation:

1. In the first, blind, iterations it is irrelevant which function is selected, since the distance to the fractal set is reduced in each step . Is z. B. the contraction constant and the basic set the unit square, which is displayed with 1024 × 1024 pixels , the error has already dropped below the pixel size after 12 blind iterations. ${\displaystyle X}$ ${\displaystyle c=0{,}5}$ ${\displaystyle M}$
2. In general, better representations will be achieved if the probability of each function being called is roughly proportional to the volume of . ${\displaystyle \phi _{i}}$ ${\displaystyle \phi _{i}(M)}$

Recursion

Another possibility of representation, preferably for the affine fractals, is the recursive approximation of the set . This is usually explained clearly using a photocopier: You make various reductions in an initial image, fix this on a new sheet according to the instructions and then use this as the initial image for the next step. ${\displaystyle X}$

The turtle graphic used to construct the L-systems also follows a similar idea.

As an algorithm, you need a recursively callable function that realizes the assignment for any set . The implementation requires a stack memory in which the current coordinate system is recorded as affine coordinate transformations. This results in the algorithm ${\displaystyle F(n)=\bigcup _{i=1}^{r}\phi _{i}(F(n-1))}$ ${\displaystyle F(0)}$

The Koch fractal in recursion depths 0 to 5

${\displaystyle Figur(n)}$:

• If ${\displaystyle n=0}$
  • draw the basic figure (e.g. a line, a letter, a black rectangle)
• otherwise:
  • For up ${\displaystyle i:=1}$ ${\displaystyle r}$
    • Put the current coordinate system on the stack
    • Transform the current coordinate system accordingly ${\displaystyle \phi _{i}}$
    • Calls out ${\displaystyle Figur(n-1)}$
    • Recover coordinate system from stack

Fractal:

• Calls (10 as an example) ${\displaystyle Figur(10)}$

Examples of iterated function systems

Affine images

Let the generating functions of the IFS be affine maps of the two-dimensional unit square in itself. Each function is given by a 2 × 2 matrix and a displacement vector . ${\displaystyle \phi _{k}}$ ${\displaystyle A_{k}}$ ${\displaystyle b_{k}}$

The Koch fractal is z. B. generated by the following system of 2 functions:

• ${\displaystyle \phi _{1}{\binom {x}{y}}={\frac {1}{\sqrt {3}}}{\begin{pmatrix}\cos 30^{\circ }&\sin 30^{\circ }\\\sin 30^{\circ }&-\cos 30^{\circ }\end{pmatrix}}\,{\binom {x}{y}}}$,
• ${\displaystyle \phi _{2}{\binom {x}{y}}=-{\frac {1}{\sqrt {3}}}{\begin{pmatrix}-\cos 30^{\circ }&\sin 30^{\circ }\\\sin 30^{\circ }&\cos 30^{\circ }\end{pmatrix}}{\binom {x}{y}}+{\frac {1}{\sqrt {3}}}{\binom {\cos 30^{\circ }}{\sin 30^{\circ }}}}$

The classic method for generating the Koch curve uses 4 functions

• ${\displaystyle \phi _{1}(x,y)=\left({\frac {x}{3}},{\frac {y}{3}}\right)}$
• ${\displaystyle \phi _{2}(x,y)=\left({\frac {2+x-{\sqrt {3}}y}{6}},{\frac {{\sqrt {3}}x+y}{6}}\right)}$
• ${\displaystyle \phi _{3}(x,y)=\left({\frac {3+x+{\sqrt {3}}y}{6}},{\frac {{\sqrt {3}}-{\sqrt {3}}x+y}{6}}\right)}$
• ${\displaystyle \phi _{4}(x,y)=\left({\frac {2+x}{3}},{\frac {y}{3}}\right)}$

The right-angled Sierpinski triangle is generated by

• ${\displaystyle \phi _{1}(x,y)=\left({\frac {x}{2}},{\frac {y}{2}}\right)}$
• ${\displaystyle \phi _{2}(x,y)=\left({\frac {x+1}{2}},{\frac {y}{2}}\right)}$
• ${\displaystyle \phi _{3}(x,y)=\left({\frac {x}{2}},{\frac {y+1}{2}}\right)}$

Collages

The basis for the enthusiasm for such IFS fractals was the Barnsley collage theorem . It says that every compact quantity - every shape - can be approximated as precisely as desired by an IFS fractal. The basis for this are the following observations:

1. Every finite set is an IFS fractal. The associated functions are those constant functions that map the entire space to one of the finitely many points. 2. Every compact set has a -net for every one , so it is covered by a finite number of spheres from the radius . ${\displaystyle K}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ⇒ The IFS fractal of the center of the sphere contains the initial quantity in an environment ${\displaystyle \varepsilon }$

More clearly: If we have a figure of 500 black pixel points in a 100 × 100 pixel image, we can reduce the image by a factor of 100 to the size of one pixel and then use this one black point to paint the figure again by placing it on each of the associated 500 pixels. This approach is by far not optimal; simply saving the positions of the 500 pixels would be easier here. But if we could manage with only five figures for the same purpose, a data reduction would be achieved.

We are also not limited to simple black and white images. In the case of a grayscale image , the degree of blackening can be understood as the third coordinate of the point, resulting in a compact area in three-dimensional space, to which the collage theorem can be applied again. The fractal image compression and the fractal sound compression deal with systematic procedures for the construction of an IFS fractal with as few functions as possible .

Web links

Commons : Iterated systems of functions  - collection of images, videos and audio files

• Informative page about fractals and IFS for beginners with numerous illustrations
• A collection of fractal art by Paul Bourke
• Colored expansions of the chaos game fractal flames , under math the theory.
• On history and generalizations: Cabrelli, Molter: Generalized Self-Similarity ...
  • 1957 Self-similar functions examined by Bajraktarevic and de Rham
  • 1981 Hutchinson investigated self-similar quantities and curves
  • 1986 Barnsley defined fractal functions

Individual evidence

1. ^ John E. Hutchinson: Fractals and self similarity . In: Indiana University Mathematics Journal . tape 30 , no. 5 , 1981 ( semanticscholar.org [PDF; 483 kB ]).
2. ^ Michael Barnsley: Fractals Everywhere . Academic Press, 1988, ISBN 978-0-12-079062-3 .
3. ^ Mario Peruggia: Discrete Iterated Function Systems . Taylor & Francis, CRC Press, 1993, ISBN 978-0-429-06536-1 , pp. ix, xi , doi : 10.1201 / 9781439864708 .