The Barnsley Fern

At the end of the chapter on Iterated Function Systems, we introduced two separate attractors: the Sierpinski triangle, and a uniform two-dimensional square, shown below with their corresponding Hutchinson operator.

Hutchinson Operator Attractor
Sierpinsky Triangle Chaos Game
Square Chaos Game

As a reminder, the Hutchinson operator is a set of functions that act on a point in space, , and return another another point at a new location. These functions are meant to be used over and over again in some fashion, and as you continually iterate through them, some shape will eventually be drawn. This shape is known as an attractor, and the entire system is called an iterated function system due to the iterative nature of drawing the attractor.

In these cases, each function will move the point to be halfway between its original position and the position of , , , and for , , , and , respectively. Even though , , and are the same for both attractors, the addition of drastically changes the final result! It is surprising that two seemingly identical sets of functions can look so different in the end, and this leads us to a somewhat challenging question: given a set of functions, is there any way to predict what the attractor will be without iterating through the functions?

In general, the answer is no. You must sample the function set in some fashion to get find the resulting attractor.

This feels somewhat unsettling to me. After all, each individual function is simple, so why is the result so difficult to predict? In this chapter, I hope to provide a slightly more satisfying answer by introducing another iterated function system with beautiful attractor, known as the Barnsley fern [1]:

Hutchinson Operator Attractor
Barnsley Chaos Game

At first glance, this set of functions looks like an incomprehensible mess of magic numbers to create a specific result, and in a sense, that is precisely correct. That said, we will go through each function and explain how it works, while also providing a simple chaos game implementation in code. By the end of this chapter, we do not hope to provide a general strategy for understanding all iterated function systems, but we hope to at least make this one set of functions a bit more understandable.

Individual affine transforms

The first thing to note about the Barnsley set of functions is that each one is an affine transformation. Though it is not a hard rule, most iterated function systems use affine transforms, so this notation is common. In fact, the Sierpinski operators can also be written in an affine form:

Non-affine Affine

The affine variant performs the same operation by scaling the and component of by and then adding half of either , , or for , , or , respectively. Each of these transforms involves some linear component (scaling or shearing) with an additional translation.

As an important side-note: in both the Barnsley and Sierpinski function systems, the coefficients of the transformation matrix are all less than 1. This property is known as contractivity, and an iterated function system can only have an attractor if the system is contractive. Upon reflection, this makes sense. If the matrix elements were greater than 1, the point could tend towards infinity after successive iterations of the function.

Now let's hop into disecting the Barnsley fern by seeing how each transform affects a random distribution of points:

Function Operation

This operation moves every point to a single line.

This operation moves every point up and to the right.

This operation rotates every point to the left.

This operation flips every point and rotates to the right.

At this stage, it might be clear what is going on, but it's not exactly obvious. Essentiallg, each operation corresponds to another part of the fern:

  • creates the stem.
  • creates successively smaller ferns moving up and to the right.
  • creates the leaves on the right.
  • creates the leaves on the left.

The easiest way to make sense of this is to show the operations on the Barnsley fern, itself, instead of a random distribution of points.

Function Operation

Here, the self-similar nature of the fern becomes apparent. Each operation is effectively moving a point on one part of the fern to a point on another part of the fern.

In the final construction, it is clear that fewer points are necessary on some parts than others. The stem, for example, does not need many points at all. Meanwhile, the bulk of the fern seems to be generated by , so we probably want the majority of the points to choose that function when iterating through he set. To account for this, each function is also given a probability of being chosen:

Function Probability
0.01
0.85
0.07
0.07

Playing around a bit...

One big advantage of using affine transformations to construct an attractor is that mathematicians and programmers can leverage their knowledge of how these transformations work to also modify the resulting image. Here are a few examples of ferns that can be generated by modifying constituent functions:

Function Operation

where

Turning stems to leaves

where

Changing fern tilt

where

Plucking left leaves

where

Plucking right leaves

As an important note: the idea of modifying a resulting image by twiddling the knobs of an affine transform is the heart of many interesting methods, including fractal image compression where a low resolution version of an image is stored along with a reconstructing function set to generate high-quality images on-the-fly [2][3]. If this seems mystifying, don't worry! We'll definitely come back to this soon, I just wanted to briefly mention it now so it's on everyone's mind as we move forward.

Video Explanation

Here is a video describing the Barnsley fern:

Example Code

Similar to the chapter on iterated function systems, the example code here will show a chaos game for the construction of an attractor; however, in this case the attractor will be the Barnsley fern instead of the Sierpinski triangle. The biggest differences between the two code implementations is that the Barnsley implementation must take into account the varying probabilities for choosing each function path and that we will be choosing an initial point that is on the attractor this time (namely ).

using DelimitedFiles

# This is a function that reads in the Hutchinson operator and corresponding
#     probabilities and outputs a randomly selected transform
# This works by choosing a random number and then iterating through all 
#     probabilities until it finds an appropriate bin
function select_array(hutchinson_op, probabilities)

    # random number to be binned
    rnd = rand()

    # This checks to see if a random number is in a bin, if not, that 
    #     probability is subtracted from the random number and we check the
    #     next bin in the list
    for i = 1:length(probabilities)
        if (rnd < probabilities[i])
            return hutchinson_op[i]
        end
        rnd -= probabilities[i]
    end
end

# This is a general function to simulate a chaos game
# n is the number of iterations
# initial_location is the the starting point of the chaos game
# hutchinson_op is the set of functions to iterate through
# probabilities is the set of probabilities corresponding to the likelihood
#     of choosing their corresponding function in hutchinson_op
function chaos_game(n::Int, initial_location, hutchinson_op, probabilities)

    # Initializing the output array and the initial point
    output_points = zeros(n,2)

    # extending point to 3D for affine transform
    point = [initial_location[1], initial_location[2], 1]

    for i = 1:n
        output_points[i,:] .= point[1:2]
        point = select_array(hutchinson_op, probabilities)*point
    end

    return output_points

end

barnsley_hutchinson = [[0.0 0.0 0.0;
                        0.0 0.16 0.0;
                        0.0 0.0 1.0],
                       [0.85 0.04 0.0;
                        -0.04 0.85 1.60;
                        0.0 0.0 1.0],
                       [0.20 -0.26 0.0;
                        0.23 0.22 1.60;
                        0.0 0.0 1.0],
                       [-0.15 0.28 0.0;
                        0.26 0.24 0.44;
                        0.0 0.0 1.0]]

barnsley_probabilities = [0.01, 0.85, 0.07, 0.07]
output_points = chaos_game(10000, [0,0],
                           barnsley_hutchinson, barnsley_probabilities)
writedlm("out.dat", output_points)

Bibliography

1.
Barnsley, Michael F, Fractals everywhere, Academic press, 2014.
3.
Saupe, Dietmar and Hamzaoui, Raouf, A review of the fractal image compression literature, ACM, 1994.

License

Code Examples

The code examples are licensed under the MIT license (found in LICENSE.md).

Text

The text of this chapter was written by James Schloss and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.

Images/Graphics

results matching ""

    No results matching ""