|
|
Introduction to Fractal
Theory
What is a fractal? In the most generalized terms, a fractal
demostrates a limit. Fractals model complex physical processes and
dynamical systems. The underlying principle of fractals is that a
simple process that goes through infinitely many iterations becomes
a very complex process. Fractals attempt to model the complex
process by searching for the simple process underneath.Most fractals
operate on the principle of a feedback loop. A simple operation is
carried out on a piece of data and then fed back in again. This
process is repeated infinitely many times. The limit of the process
produced is the fractal.
Almost all fractals are at least partially self-similar. This
means that a part of the fractal is identical to the entire fractal
itself except smaller.Fractals can look very complicated. Yet,
usually they are very simple processes that produce complicated
results. And this property transfers over to Chaos Theory. If
something has complicated results, it does not necessarilly mean
that it had a complicated input. Chaos may have crept in (in
something as simple as round-off error for a calculation), producing
complicated results.
Fractal Dimensions are used to measure the complexity of
objects. We now have ways of measuring things that were
traditionally meaningless or impossible to measure.
Finally, Fractal research is a fairly new field of interest.
Thanks to computers, we can now generate and decode fractals with
graphical representations. One of the hot areas of research today
seems to be Fractal Image Compression. Many web sites devote
themselves to discussions of it. The main disadvantage with Fractal
Image Compression and Fractals in general is the computational power
needed to encode and at times decode them. As personal computers
become faster, we may begin to see mainstream programs that will
fractally compress images. Self-Similarity
An object is self-similar only if you can break the object
down into an arbitrary number of small pieces, and each of those
pieces is a replica of the entire structure. Some examples of
self-similarity follow. The red outlining indicates a few of the
self-similarities of the object.
Below are some
examples of "classic" fractals.
Fractal Dimension
Everyone knows the dimension of a line, a square, and a cube.
They are one, two, and three respectively. And, we can measure the
distance, area, and volume of those objects as well. However, what
is the dimension of the inside of a kidney or the brain, and how do
we measure their surface area? How about a piece of brocolli or
cauliflower? This is where fractal dimension can help us out.
Fractal Dimension allows us to measure the complexity of an
object.The classic example of this is trying to measure the
coastline of
Before explaining dimension measuring algorithms, we must
explain how a power law works. Essentially, data behave with a power
law relationship if they fit the following equation: y=c*x^d where c
is a constant. One way to determine if data fit a power law
relationship is to plot the log(y) versus the log(x). If the plot is
a straight line, then it is a power law relationship with slope d.It
turns out that the methods we are going to discuss for measuring
fractal dimension rely heavily on the power law. Self-Similarity
Dimension
To
Measure the Self-Similar Dimension, the picture must be
self-similar. The power law holds and in this case is a
= 1/(s^D) where
a is the number of pieces, s is the reduction factor, and D is the
self-similar dimension measure. For
example, if a line is broken into three pieces, each is going to be
one-third the length of the original. Therefore a=3, s=(1/3), and
D=1. In another
example, if a square is broken into four pieces, each side is going
to be one-half the original length of the side. Therefore a=4,
s=(1/2), and D=2.
For the Sierpinski
Gasket, the original triangle is cut in half, and there are
three pieces. Therefore a=3, s=(1/2), and D=1.5850. Box-Counting Dimension To
calculate the box-counting dimension, we need to place the picture
on a grid. The x-axis of the grid is s where s=1/(width of the
grid). For example, if the grid is 240 blocks tall by 120 blocks
wide, s=1/120. Then, count the number of blocks that the picture
touches. Label this number N(s). Now, resize the grid and repeat the
process. Plot the values found on a graph where the x-axis is the
log(s) and the y-axis is the log(N(s)). Draw in the line of best fit
and find the slope. The box-counting dimension measure is equal to
the slope of that line. The Box-counting dimension is much more
widely used than the self-similarity dimension since the
box-counting dimension can measure pictures that are not
self-similar (and most real-life applications are not self-similar. Iterated Function
Systems
Note: This page uses animated GIFs. You must use a graphical
web browser which supports 89a GIFs. If you would like to view each
frame of the animation at your own pace, please click on the
animation. Clicking on the animation will link you to another page
where each frame will be displayed as its own graphic. Fractals
can be formed using Iterated Function Systems. To begin thinking
about the topic, let us consider the Cantor Set.The Cantor Set is
formed using the following algorithm: 1.
Begin
with the set [0,1]. 2.
Divide
the existing segments into thirds. 3.
Remove
the middle third. 4.
Go
to step #2. 5.
The
picture below should help visualize the process. The solid line at
the start of the animation represents the set [0,1]. Each iteration
is shown in following frames of the animation. The green highlight
indicates the "middle third" which is to be removed. If
this process were to be repeated indefinitely, the cantor set would
be produced. Obviously, the cantor set cannot be precisely
represented with a finite number of pixels on the screen, so a very
poor approximation will have to suffice. However, this "poor
approximation" will give you a good idea what the cantor set
look like (as an uneven spacing of discrete values). Notice how the
points tend to cluster. This is one characteristic of the cantor
set. Next, let us
focus our attention on the Sierpinski Gasket. As usual, the picture
below shows the building of the fractal. We start with an
equilateral triangle (although the actual shape does not really
matter as we shall see later). The
Sierpinski Gasket can be formed as follows: 1.
Begin
with an equilateral triangle (although, we can begin with any figure
as we will see later). 2.
Divide
the triangle into four equal-sized triangles. 3.
Remove
the middle triangle. 4.
Go
to Step #2. The above
method will form a Sierpinski Gasket. However, it is not an Iterated
Function System yet. Let us express this as an Iterated Function
System. 1.
Begin
with an equilateral triangle (again, this is arbitrary) 2.
Reduce
the image by one-half. 3.
Make
three copies of the reduced image. 4.
Align
them in the shape of an equilateral triangle. 5.
Translate
the top copy to the left above the lower-left copy. 6.
Go
to step #2. The following
is produced by the above iterated function system: After seeing a
few examples, we are now ready to more precisely define an iterated
function system. An initial image is transformed by a set of affine
transformations (functions) producing a new image. The new image is
then transformed by the same affine transformations producing
another new image. Thus, each time the image is transformed, an
iteration occurs. If the transformation is contractive--that is, the
transformation brings points closer together--, then the image will
begin to converge. After infinitely many iterations, assuming a
contractive transformation, the image will converge to what is
called an attractor. Chaos and Randomness
to Generate IFS
As we have seen from the section on Iterated Function
Systems, the Barnsley Fern is impossible to generate by drawing
triangles. There are too many triangles to draw and too many
transformation to be applied. There must be another way!Instead of
using and transforming triangles, let us transform points. It is
computationally much easier to draw and transform a point than a
triangle. To best describe this, let us use the Sierpinski
Gasket as our example again. We begin with an imaginary triangle
and label its vertices 1, 2, & 3. Pick a random point. Now,
generate a random integer between 1 and 3. The next point is the
midpoint between the first point and the generated random number
vertex. Continue generating random integers and plotting the
midpoints. After a thousand or so iterations, we will see a
Sierpinski Gasket! A
more algorithmic approach to this would be 1.
Pick
the total number of iterations to perform and call it i.
9.
Here
are two books which are very helpful for learning more about
fractals: Peitgen,
Heinz-Otto, Hartmut Jurgens & Dietmar Saupe, Chaos and
Fractals: New Frontiers of Science, Fisher, Yuval,
Fractal Image Compression: Theory and Application, |
