\graphicspath{{ifs/}}
\section{Iterated Function Systems}
\label{sec:ifs}

Iterated function systems (IFS's) are used to generate fractal images from a very small input data set.  Figure \ref{fig:fern} shows an image that bears a striking resemblance to the fern \emph{asplenium resiliens}, also known as the black spleenwort.  This image was created by Michael Barnsley, and is completely described by a set of only 28 numbers.  Iterated function systems use a very small data set to produce highly detailed images that are very provocative to their audiences.  In order to understand what these numbers are, and how they're used, some mathematical background is needed.

\begin{figure}
\centering
\includegraphics{fern.png}
\caption{Barnsley's famous fern fractal}
\label{fig:fern}
\end{figure}

\subsection{Affine Transformations}

Iterated function systems are based on affine transformations.  An affine transformation in $\mathbb{R}^2$ is just a class of mapping from one image to another.  Given an image, an affine transformation may rotate, scale, mirror, skew, and translate an image relative to the origin.  Linear algebra tells us that any such transformation on points $(x,y)$ in $\mathbb{R}^2$ can be represented like this:
\begin{displaymath}
w\left( \left[ \begin{array}{c}
x\\
y\\
\end{array} \right] \right)
=
\left[ \begin{array}{cc}
a&b\\
c&d\\
\end{array} \right]
\left[ \begin{array}{c}
x\\
y\\
\end{array} \right]
+
\left[ \begin{array}{c}
e\\
f\\
\end{array} \right]
\end{displaymath}
The matrix $A = \left[\begin{array}{cc}a&b\\c&d\end{array}\right]$ will apply rotation, scaling, mirroring, and skewing, and the additional $\left[\begin{array}{c}e\\f\end{array}\right]$ vector will translate the result.  

\subsection{Contraction Mappings}

A contraction mapping is a special kind of affine transformation.  As the name suggests, for an affine transformation to be a contraction mapping, it is necessary for it to make the image ``smaller''.  To state this more mathematically, it must be true that the distance between any two points after transformation must be less than or equal to their distance before transformation.

\subsection{Example: Sierpinski Gasket}
\label{sec:IFS:sierpinski}
An iterated function system is just a set of contraction mappings.  Each of these mappings requires 6 numbers to quantify exactly, using the above definition.  One additional number must be attached to each mapping, but we will explain this number later.  The fern example mentioned above uses just 4 contraction mappings to fully describe the fractal.

How are the contraction mappings used?  We will demonstrate using a simple example with three contraction mappings:
\begin{enumerate}
\item Scale the entire image to half size 
\begin{displaymath}
w_1\left( \left[ \begin{array}{c}
x\\
y\\
\end{array} \right] \right)
=
\left[ \begin{array}{cc}
0.5&0\\
0&0.5\\
\end{array} \right]
\left[ \begin{array}{c}
x\\
y\\
\end{array} \right]
+
\left[ \begin{array}{c}
0\\
0\\
\end{array} \right]
\end{displaymath}
\item Scale the entire image to half size, and translate 0.5 units along the y-axis
\begin{displaymath}
w_2\left( \left[ \begin{array}{c}
x\\
y\\
\end{array} \right] \right)
=
\left[ \begin{array}{cc}
0.5&0\\
0&0.5\\
\end{array} \right]
\left[ \begin{array}{c}
x\\
y\\
\end{array} \right]
+
\left[ \begin{array}{c}
0\\
0.5\\
\end{array} \right]
\end{displaymath}
\item Scale the entire image to half size, and translate 0.5 units along the y-axis and 0.5 units along the x-axis
\begin{displaymath}
w_3 \left( \left[ \begin{array}{c}
x\\
y\\
\end{array} \right] \right)
=
\left[ \begin{array}{cc}
0.5&0\\
0&0.5\\
\end{array} \right]
\left[ \begin{array}{c}
x\\
y\\
\end{array} \right]
+
\left[ \begin{array}{c}
0.5\\
0.5
\end{array} \right]
\end{displaymath}
\end{enumerate}

For this example, the process starts with the image shown in the upper left of Figure \ref{fig:sierpinski}.  Next, apply each contraction mapping $w_i$ to the image, and remember the result.  Finally, combine these three results into one new image (upper right).  Now, using this resulting image, repeat the process.  Each repetition is called an iteration, and the first few iterations are shown in the lower left.  If this process is repeated indefinitely, the image will eventually look like the Sierpinski gasket, shown in the lower right.  The resulting image is known as the attractor of the IFS.

\begin{figure}
\centering
\begin{tabular}{cc}
\includegraphics{deterministic1.png}&\includegraphics{deterministic2.png}\\
\includegraphics{deterministic3.png}&\includegraphics{deterministic4.png}\\
\end{tabular}
\caption{Steps along the way to creating the famous Sierpinski gasket, also known as the Sierpinski triangle.  Upper left is the starting image, upper right shows the first iteration, lower left shows 2 iterations, and lower right shows as many iterations as can be printed.}
\label{fig:sierpinski}
\end{figure}

The original image is eventually scaled down so far that its features are no longer distinguishable.  For this reason, one can start with any original image, and the process will always result in the same Sierpinski triangle [Barnsley 1988]!  The essence of the final image is completely described by the three contraction mappings, and is not affected by the starting image.  The necessity that affine transformations must be contraction mappings is now obvious: otherwise, the image would expand without limit.

\subsection{The Non-Deterministic Rendering Algorithm}

The process described above is very time-consuming.  Computers can help, but there are still many calculations that must be done, and the process is still slow.  Fortunately, there is a simpler method which is less CPU-intensive and results in the same image, called the random iteration algorithm.  This is where the extra number for each contraction mapping comes in.  A probability, $p_i$, is associated with each contraction mapping $i$, such that the sum of the probabilities of all mappings is 1.  Barnsley suggests that the probability $p_i$ of the affine transformation defined by matrix $A_i$ should be calculated using this formula:
\begin{displaymath}
p_i \approx \frac{\displaystyle \left|\mathrm{det} A_i\right|}{\displaystyle \sum_{i=1}^N \left|\mathrm{det} A_i\right|}
\end{displaymath}
where N is the number of mappings.

To carry out the random iteration algorithm, first select a starting point.  Now, randomly select one of the contraction mappings, weighted by the probability.  Apply this contraction mapping to the point, and plot the result.  Using the resulting point, select a new mapping randomly, and repeat the process.  If this process is repeated indefinitely, the resulting image will be exactly the same as above [Barnsley 1988].  

In practice, the process is repeated for a set number of iterations.  The more iterations, the more accurately the resulting image will represent the attractor of the IFS.  With the careful selection of probability values, a clear approximation of the image can be rendered with fewer iterations.  Since this randomized algorithm is much faster and easier to program than the deterministic method shown above, most fractal representation programs use it to render IFS's.

\subsection{Fractint}

Fractint is a very useful program for rendering many types of fractals.  Among its many specialties, it can render images from a user-specified or built-in IFS.  One such built-in IFS is the Barnsley Fern, depicted in Figure 1.

Fractint takes as input a file with the extension ``.IFS''.  This file can contain one or more IFS, specified as follows:

\vspace{1em}

\begin{tabular}{lccccccc}
\multicolumn{8}{l}{\texttt{ifs name} \{}\\
 &$a_1$&$b_1$&$c_1$&$d_1$&$e_1$&$f_1$&$p_1$\\
 &$a_2$&$b_2$&$c_2$&$d_2$&$e_2$&$f_2$&$p_2$\\
 &\multicolumn{7}{l}{\ldots}\\
 &$a_n$&$b_n$&$c_n$&$d_n$&$e_n$&$f_n$&$p_n$\\
\multicolumn{8}{l}{\}}\\
\end{tabular}

\vspace{1em}

Using Fractint, one can generate an amazing array of figures, suggestive of dragons (Figure \ref{fig:dragon}), trees (Figure \ref{fig:mytree}), and even fanciful symbolic structures (Figure \ref{fig:ifsjohn}).  The recursive structures that result can mimic nature's self-similarity, as shown by the fern and tree examples, among many more.  Also, abstract but captivating structures can be generated.  Many beautiful examples of IFS's are included with Fractint.  For more information about Fractint, see Appendix B, page \pageref{program:fractint}.

\begin{figure}[htbp]
\centering
\includegraphics{dragon.png}
\caption{A Fractint built-in IFS that looks like a dragon.}
\label{fig:dragon}
\end{figure}

\begin{figure}[htbp]
\centering
\includegraphics{mytree.png}
\caption{An IFS reminiscent of a tree, created by the authors using FDESIGN and Fractint}
\label{fig:mytree}
\end{figure}

\begin{figure}[htbp]
\centering
\includegraphics{john.png}

\vspace{1em}

\includegraphics{johnzoom.png}
\caption{Another IFS created with FDESIGN.  The lower image is a zoom-in of the outlined part of the upper image.  In the fractal structure approximated by this image, the name ``JOHN'' repeats down to infinity.  John created this image after seeing a similar image designed by the authors of Fractint.}
\label{fig:ifsjohn}
\end{figure}

\subsection{FDESIGN}

It is not very easy to design an IFS by hand.  Each contraction mapping vaguely specifies that a copy of the ``whole image'' is to be rotated like so and placed like so, but all of the contraction mappings pull and tug at each other.  If a small change is made to just one number of the fern fractal, the stem may become detached, or the branches will no longer attach to the main stem.  As such, the process of designing or modifying an IFS is largely trial and error, with the latter occurring frequently.

Enter FDESIGN.  FDESIGN was written in 1990 for computers with Intel 8087 math coprocessors by Doug Nelson.  It is amazing that this 12 year old program will still run, and it is very interesting that it is still the most useful program of its kind that the authors could find.  Given today's processor speeds, FDESIGN can render an IFS very quickly.

FDESIGN allows the user to visually indicate contraction mappings, and watch the IFS render as the mappings are added and modified.  Mappings are represented by the action they take on a triangle.  First, the user draws a starting triangle, used as a base for all transformations.  Then, one draws what happens to this triangle after it undergoes the desired contraction mapping.  By observing the starting and ending positions of the three vertices of the triangles, FDESIGN can uniquely determine the parameters for the contraction mapping.  This is done by solving a system of equations (Barnsley pp 53).

John used FDESIGN to create the ``JOHN'' fractal in Figure \ref{fig:ifsjohn}.  Once he created the contraction mappings, he directed FDESIGN to export the IFS into a format recognized by Fractint and rendered the image shown.  By loading the IFS code provided into FDESIGN, the reader can see the triangles that were used to construct the system.  There are 13 different contraction mappings in this IFS.  One can see them visually in Figure \ref{fig:ifsjohn}, each in a different color.  In essence, John used the triangles to specify that the entire image was to appear in each of 13 places so that they spelled out his name.

Though FDESIGN is a powerful tool, it is not trivial to design a meaningful IFS.  One must be aware of the meaning of the triangles, and what it means to combine all of the contraction mappings at once.  Fortunately, FDESIGN comes with numerous examples, and the interface allows the user to experiment with modifications to the examples.  For more information about FDESIGN, see Appendix B, page \pageref{program:fdesign}

Iterated Function Systems can create stunning visual effects, as seen above.  Because of their recursive nature, they can be made to mimic figures found in nature.  They can be used to provoke interesting emotions in people, because they explore our fascination with the concept of infinity.  For example, the ``JOHN'' fractal is extremely interesting because the name seems to be made of itself, with an infinite number of levels that we can never quite understand.  This is why Iterated Function Systems evoke emotion, because they intrigue our senses and make us ponder the infinite.



