The Barnsley Fern
At the end of the chapter on Iterated Function Systems, we introduced two separate attractors: the Sierpinski triangle, and a uniform twodimensional square, shown below with their corresponding Hutchinson operator.
Hutchinson Operator  Attractor 

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 

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:
Nonaffine  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 sidenote: 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 selfsimilar 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 highquality images onthefly [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
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 AttributionShareAlike 4.0 International License.
Images/Graphics
 The image "IFS triangle 1" was created by James Schloss and is licensed under the Creative Commons AttributionShareAlike 4.0 International License.
 The image "IFS square 3" was created by James Schloss and is licensed under the Creative Commons AttributionShareAlike 4.0 International License.
 The image "Simple Barnsley fern" was created by James Schloss and is licensed under the Creative Commons AttributionShareAlike 4.0 International License.
 The video "Affine random transform 0" was created by James Schloss and is licensed under the Creative Commons AttributionShareAlike 4.0 International License.
 The video "Affine random transform 1" was created by James Schloss and is licensed under the Creative Commons AttributionShareAlike 4.0 International License.
 The video "Affine random transform 2" was created by James Schloss and is licensed under the Creative Commons AttributionShareAlike 4.0 International License.
 The video "Affine random transform 3" was created by James Schloss and is licensed under the Creative Commons AttributionShareAlike 4.0 International License.
 The video "Affine fern transform 0" was created by James Schloss and is licensed under the Creative Commons AttributionShareAlike 4.0 International License.
 The video "Affine fern transform 1" was created by James Schloss and is licensed under the Creative Commons AttributionShareAlike 4.0 International License.
 The video "Affine fern transform 2" was created by James Schloss and is licensed under the Creative Commons AttributionShareAlike 4.0 International License.
 The video "Affine fern transform 3" was created by James Schloss and is licensed under the Creative Commons AttributionShareAlike 4.0 International License.
 The video "Fern twiddle 0" was created by James Schloss and is licensed under the Creative Commons AttributionShareAlike 4.0 International License.
 The video "Fern twiddle 1" was created by James Schloss and is licensed under the Creative Commons AttributionShareAlike 4.0 International License.
 The video "Fern twiddle 2" was created by James Schloss and is licensed under the Creative Commons AttributionShareAlike 4.0 International License.
 The video "Fern twiddle 3" was created by James Schloss and is licensed under the Creative Commons AttributionShareAlike 4.0 International License.