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 Great Britain. In actuality, it is impossible to precisely measure the length of the coastline. The tide is always coming in or going out which means that the coastline itself is constantly changing. Therefore, any ordinary measurement is meaningless.

Fractal Dimension allows us to measure the degree of complexity by evaluating how fast our measurements increase or decrease as our scale becomes larger or smaller.

We will discuss two types of fractal dimension: self-similarity dimension and box-counting dimension. There are many different kinds of dimension. Other types include topological dimension, Hausdorff dimension, and euclidean dimension. It is important to note that not all types of dimension measurement will give the same answer to a single problem. However, our dimension measurements will give the same answer.

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).

To the Next Page

To the Table of Contents

To Eric's Home

Copyright Eric Green, 1998