Iterated function system
An iterated function system ( IFS) is a set of functions that have the same space M as a definition and range of values and are closed under join. so
Iterated function systems are mostly used for the construction of fractals, which are then referred to as IFS fractals. Well-known representatives of this class of fractals are the Sierpinski gasket and the Koch curve as well as the marginal amounts of Lindenmayer systems.
Koch curve
Dragon Fractal
This type of Fraktalkonstruktion in 1981 by John Hutchinson invented and later popularized by Michael F. Barnsley with his book Fractals Everywhere. There Barnsley also stated the collage theorem, which forms the basis of fractal image compression. This type of encoding images efficiently by means of data structures, however, has never been able to show off and is now investigated essentially only as a hybrid method combined with wavelet transform.
- 4.1 Affine pictures
Invariant, self-similar sets
In order to derive for an IFS properties that set of functions required to meet additional requirements. Usually, when IFS is spoken, these conditions are tacitly accepted as a given. These conditions are
Under these circumstances, there is an invariant, self-similar set X ⊆ M.
- The subset X is invariant if it is imaged by each function of the IFS back in on itself.
- The subset X is self-similar if every point of X in the image set F ( X) is a function.
Self-similar volumes usually do not have integer Hausdorff dimension and are then referred to as a fractal, hence the designation IFS fractal. One could also define going on the notion of self-similarity by requiring the existence of an IFS.
Existence and uniqueness of the invariant quantity
Mathematically, it is in the theory of iterated function systems, as well as the terminology suggests, a direct application of the Banach fixed point theorem, where several functions are considered instead of one and, rather than a unique fixed point, an invariant, mostly fractal, subset of space M results. To illustrate the two-dimensional unit square is usually selected with the Euclidean distance.
So we start with a finite set of functions of a compact metric space into itself:
Of which we assume that there is a contraction with constant
By iteration, we put an IFS continues, it is
And finally obtain
Sentence: Are all functions in contractionary, so there is an invariant subset of X which the fixed point equation
Met. In this economy:
- There is exactly one fixed point for each. The invariant set X is the topological closure of the set of all fixed points
- If y ∈ M be an arbitrary point, then for the distance of this point
- Thus, X by iteration of a limited initial amount
The proof of the theorem is effected by constructing a new space of the metric space whose "points" are exactly the compact subsets of. Then one can define a metric ( Hausdorff metric ), with respect to the this space completely and the mapping is a contraction. Thus, the Banach fixed point theorem is applicable.
Approximation of the limit amount
Chaos game
The shape of the fractal set X can be visualized by a so-called chaos game. First, a fixed point of is identified and applied to this in random order the defining features. For the algorithm, this may look like this:
- Way to 100 times in succession
- Repeat as often as Randomly choose an i in {1, ..., r }
- Way to
- Draw the point x
Note: 1) It is immaterial in the first, blind, iterations, which function is chosen because is reduced in each step the distance to the fractal set X. If, for example, the contraction constant c = 0.5 and the basic set M the unit square, which is represented with 1024x1024 pixels, so has dropped already after 12 iterations of the blind fault beneath the pixel size.
2) It will generally provide better representations when the probability of call, each of the functions is roughly proportional to the volume of.
Recursion
Another way of presentation, preferably for the affine fractals, the recursive approximation of the set X. This is most clearly explained by means of a photocopier: you make various reductions of the original image, this fixed -to-rule on a new sheet and then used this as a starting image the next step.
The turtle graphics that is used to construct the L- systems, follows a similar idea.
For the algorithm, you need to use a recursively callable function which implements the assignment in any amount. The implementation requires a stack memory in which the respective current coordinate system is taken as affine coordinate transformations. This results in an algorithm
Figure ( s):
- If n = 0 Draw the base figure (eg, a route, a letter, a black rectangle )
- For i: = 1 to r Put current coordinate system on the stack from
- Transform the current coordinate system according to
- Calls figure ( n -1)
- Body coordinate system from the stack restores
Fractal:
- Calls figure ( 10) to (10 for example)
Examples of iterated function systems
Affine
The generating functions of the IFS are affine transformations of the two-dimensional unit square into itself? K Each function is given by a 2 × 2 matrix Ak and a displacement vector bk.
The Koch fractal is, for example, generated by the following system of two functions:
- ,
The classical method for the generation of the Koch curve is used by 4 functions
The right-angled Sierpinski triangle generated by
Collagen
The basis for the enthusiasm for such IFS fractals the collage theorem of Barnsley. It states that every compact set - any shape - can be approximated with arbitrary precision 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, which map the entire space on each one of a finite number of points.
2 Every compact set K has an ε - net for every ε > 0, ε is thus covered by finitely many balls of radius.
More illustratively: Do we have a 100 × 100 - pixel image a figure of 500 black pixel points, so we can reduce the image size by a factor of 100 to the size of a pixel and then re-paint with this one black dot the figure by him in any the associated 500 pixel map. This procedure is far from optimal, where the easy storage of the positions of the pixels 500 would be easier. But if we supply their needs for the same purpose with only five figures, a data reduction would be achieved.
We are also not limited to simple black and white images. In a grayscale image, the degree of blackening can be regarded as the third coordinate of the point, the result is a compact surface in the three-dimensional space, to which again the Collage theorem can be applied. With systematic method for constructing an IFS fractal with as few functions, the fractal image compression and fractal sound compression is concerned.