Fractals: a deterministic and recursive algorithm to reproduce it (Part II)

Abstract:

Fern fractal estimation thru recursive and deterministic algorithm.

A fractal can be described as fixed point of a Markov process: given the proper contractive maps it's easy to generate it.

The question is: given the contractive maps, is it possible to generate the fractal using a pure deterministic approach?

Problem

We already observed that the iteration of the contractive maps starting from a fixed point that lyes on the border of the fractal returns points of the convex hull of the fractal.

• What's happen if we recursively apply such schema to the points obtained from the the above procedure?
• Is it possible recreate the markov process (or at least approximate it) removing any probabilistic aspects?

The below algorithm, given the contractive maps of the fractal, returns at each iteration better approximation of it.

At each iteration it considers the fractal as better approximation of the contour of the original image.

The Algorithm (by practical means)

1. Consider a fixed point $P_0$ of a contractive map $\tau_1$ that lyes on the convex hull of the fractal.
2. Choose randomly a point $P_i$ of the fractal and apply the above contractive map until the distance to $P_0$ is negligible.
3. Map the point calculated at step 2 using sequentially all the contractive maps.
4. Map each point obtained from point 3 the former step with $\tau_1$ till the distance to $P_0$ is negligible.
5. If[ITERATIONS< K]:
1. K--;
2. For each point obtained from point 4 go to point 3.

To explain how it works I plotted the list of points got using $K=1$ iterations of the algorithm:

Bigger is $K$, more accurate will be the result.
The above procedure works only if the contractive map $\tau_1$ has a fixed point that lyes on the convex hull of the fractal!!

Results:

I iterated the algorithm with $K=4$ times. At each iteration the algorithm returns a deeper description of the contour of the fractal (...even though definition of contour for a fractal doesn't make any sense, it gives at least a practical meaning):

Results of the Recursive Algorithm iterated with K=1,2,3,4. 

If we try to overlap the results obtained with the original fern we get:

Original Fern, and the overlap with the results obtained using the recursive algorithm (K=4).

Conclusion and next steps
I showed how to depict the IFS generated thru the markovian process as a recursive and completely deterministic process.
We noticed also, that in the fractal there are special points (as for instance $P_0$) that play a crucial role to describe the IFS.

The question now is the following:
is it possible leverage such special points and the above recursive algorithm to estimate the parameters of the contractive maps?
... I will show you a procedure that partially answer the question and some other example of the algorithm above described!
Stay Tuned.
Cristian

Fractal parameters estimation thru contour analysis - Part I

Introduction
I really love fractals theory. Nothing fascinates me as the amazing structures generated by a chaotic processes that describe (hyperbolic) fractals.
It's fairly easy to draw a fractal image:

• The input
• A small set of very easy function (linear transformations)
• A probability to choose one of the aforementioned functions.
• The process
• Choose randomly a starting point.
• Choose randomly one of the above functions according to the above defined probability.
• Map the starting point using the above selected function.
• iterate as long as you want :)
• Admire the meaning of the life!
• just plot the points

Wherever you are, whatever decision you make, despite the chaos, the overall picture will be always the same. More you will move, more clear the picture will be!

When I approached for the first time fractals,  after the reading of the great Barnley's book (Fractals Everywhere) I opened the laptop and I wrote the routine to draw my first IFS!
...By mistake I also plotted the lines that join the points:

...It's quite a messy, isn't it?
Sometimes it's better to give up to connect the points, just relax and wait until everything will be clear. If we focus on every single detail we risk to lose what really counts!

What is a fractal (Iterated Fractal System)?
There are many formal definitions to describe an IFS, in my opinion the most effective describe a fractal as the fixed point of the Markov process (mentioned above).
The process converges to the fractal :)

The powerful of the fractal
In literature there are plenty articles in which fractals are used to solve complex problems (financial analysis, stock exchange preditictions, description of biological processes,...).
Also in Computer Science fractals fond a good collocation, think about the image compression: the ivy leaf image takes around 25MB of space, all the information to obtain it thru the IFS takes less 1KB!!
The problem 
Given the ivy leaf image, what are the parameters of the Markov process to generate it?
A bit more formally what we have to estimate is:

• A set of functions: $\{ \tau_1, \cdots,\tau_N \}$, where $\tau_i(p_0)=A_1 \cdot p_0 +Q_1$, where:

$ A= \begin{bmatrix}\alpha & \beta\\ \gamma & \delta \end{bmatrix} Q= \begin{bmatrix} \epsilon\\ \zeta \end{bmatrix} $

• We need also the estimate the probability to choose each $\tau_j$

The combination of the collage theorem and the box counting approach is the most common technique to solve the problem.
When I was student I approached the problem from a different angle. I have to say that the results obtained were partials but I still think that something more can be done :)
Before to start we need one more notion: the contractive maps (have a look at Banach Theorem)
Under certains conditions the iteration  $\tau_j$ led to a fixed point:

Example of contractive map applied to an ellipsoid.
It converges to a fixed pointed.

First conjecture:

• An IFS is characterised by a fixed point that lies on its convex hull.
• From a fixed point that lies on the border of the IFS, the iterations of the contractive maps that generate the fractal return the convex hull of the fractal.

The ivy leaf IFS is generated by 4 contractive maps. Each color describes the map used to generate the point.

The above animated gif shows the meaning of the conjecture.

An experimental evidence about the fact that at least one fixed point lies on the convex hull of the fractal can be obtained changing the params of the maps:

The light blue points depict the fixed point of the maps used to plot the fractals.

Despite the changes in the maps, the fixed point on top of the leaf still lays on the convex hull of the fractal.

In the next post I'll show you a nice recursive algorithm I found to obtain different levels of convex hull for an IFS.

Stay tuned

Cristian.

Think different part 1: IFS fractals to generate points in a convex polygon

Sometime datasets assume strange shapes, and often to make easier our computations, we simulate the set of points using approximation of well-known statistic distributions, mixture models, and so on, but as we know the world often is more complex than expected, and an analytical density function is tricky to find out.

Let me show, a different approach, to simulate points belonging to really irregular convex polygons.

The method I propose is based on a kind of Markovian Process, better known under the name of Iterated Function System (IFS). The IFS are famous thanks to the “collage theorem” of Prof. M. F. Barnsley that allows amazing image compressions and description of complex phenomena. (I really suggest a deep reading of  the book “Fractal everywhere” that you can buy clicking on the Amazoon panel).

Just to remark the powerful of the IFS fractals, I plotted the famous fern obtained with 4 affine transformations ( I’ll explain below how IFS works).

The sequence of images shows how a fern can be built following the underlying process.

IFS to generate the fern. To different transformation has been assigned a different color.  

IFS: how it works

To generate an IFS fractal you just need a set of affine contractive transformations and for each transformation an associated probability (…of course the sum of the probabilities associated to the transformations must be equal to one!).

So for a given set of affine contractive transformation {a,b,c,d} and the respective probability set {pr_a, pr_b, pr_c, pr_d} you initialize the process from an arbitrary point of the space “P_t0”, and you find the next point of the process applying to it a transformation chosen among the mentioned set with the associated probability.

That's it!

Generate points in a convex Polygon.

The process to generate a set of points in a convex polygon is based on the above process, but, instead of using a generic affine transformation, we can use only homothetic contractive transformations.

Procedure:

• Find a set of homothetic affine transformations of the polygon having fixed point in the vertexes of the polygon.

Homothetic transformations with fixed points on vertexes of the polygon

• Assign equal probability to each transformation
• Trigger the Process starting from a point inside the polygon.

Actually the above procedure works properly also with non concave objects (like straight line):

The above procedure applied to find points belonging to a segment

Here you are some examples of set for the above procedures.

The set of points obtained for the former polygon. (Changing the contraction factor, you can obtain different coverages).

Others examples:

As you can see, some points fall above the polygons: Why?
Because I initialized the process from point outside the polygon, but the final effect doesn't change

In the next post we will discuss about the Probability Density Function  (PDF) for the points obtained with this procedure and the relation between the PDF and contractive factor.

Stay Tuned!

cristian