\graphicspath{{fractalDimension/}}
\section{Fractal Dimension}
Many people are familiar with the term dimension when it is applied to classical geometric objects such as the line, plane, or cube.  It is well known that a line is one dimensional, a plane is two dimensional, and a cube has three dimensions.
When we consider the dimension of objects from nature such as trees, clouds, and mountains, 
we usually say that they are three-dimensional.  They are, in 
fact, real objects that reside in our three-dimensional world.  However, when we apply the
techniques of fractal geometry to these objects, we get dimension values that are 
fractions.  The fractal dimension of the branching structure of a tree is not three but some number between two and three.
This fractional dimension value can sometimes be more useful in describing the structure of 
an object than our conventional concept of dimension.

We now present one of the many definitions for the notion of dimension that is useful for characterizing the forms of natural objects as well as purely mathematical ones. It will be shown that this definition of dimension provides a convenient method of measuring fractal forms and produces the same dimension values that we would expect to see for classical geometric shapes.

\subsection{The Hausdorff Dimension}
We choose the Hausdorff dimension, $D_H$, for our measure of fractal objects. The Hausdorff dimension of a set embedded in a Euclidean space is defined as
\begin{equation}
D_H = \lim_{\epsilon\rightarrow0} \frac{\ln M(\epsilon)}{\ln(\frac{1}{\epsilon})}
\label{eq:hausdim}
\end{equation}  
where $M(\epsilon)$ is the number of hypercubes (a hypercube is a generalization which includes line segments, squares, cubes, etc.) with sides of length $\epsilon$ that are needed to cover the set in the space.

We will attempt to clarify this using the simple example of a line segment. Consider a line segment of unit length which is the set of points on the interval $[0,1]$ in $R'$,  and measures of length $\epsilon = \frac{1}{2^n}$ where $n = 1, 2,... .$ The number of measures, $M(\epsilon)$ needed to cover the unit interval is $2^n$. Substituting these values into our definition we arrive at
\begin{equation}
D_H = \lim_{\epsilon\rightarrow0} \frac{\ln 2^n}{\ln 2^n}\qquad .
\end{equation}
This gives us our expected value for the dimension of a line segment, 1.

We can also show that the Hausdorff dimension of a square is 2 as we would expect. Consider the unit square $[0,1]\times[0,1]$ in the plane, and measuring squares with sides of length $\epsilon = \frac{1}{2^n}$. To cover the unit square, we need $M(\epsilon) = 2^{2n}$ measuring squares.

\begin{figure}[htbp]
\centering
\includegraphics[scale=0.15]{squaredimension}
\caption{A unit square covered by 16 squares with sides of length $1/4$}
\label{fig:squaredimension}
\end{figure}

This leaves us with
\begin{equation}
D_H = \lim_{\epsilon\rightarrow0} \frac{\ln 2^{2n}}{\ln 2^n}\qquad .
\end{equation}
Since as $\epsilon\rightarrow0 \qquad n\rightarrow\infty$, we can rewrite the 
equation as follows 
\begin{equation}
D_H = \lim_{n\rightarrow\infty} \frac{\ln 2^{2n}}{\ln 2^n} = 2\qquad .
\end{equation}
Taking this limit, 
\begin{equation}
D_H = \frac{2n\ln 2}{n\ln 2} = 2
\end{equation}
Which leaves us with a dimension of 2 for our unit square.

Figure \ref{fig:squaredimension} shows a unit square covered by $M = 16$
squares with sides of length $\epsilon = 1/4$.  For this example we can
observe that $n = 2$. Substituting into Equation \ref{eq:hausdim} easily
yields $D_H = 2$. 

This method can be used to compute the dimensions of objects with more degrees of freedom such as cubes and hypercubes. But so far we have only shown that the Hausdorff dimension gives us the values that we would expect to see for familiar geometric objects. We will now show that the fractal dimension can be useful in characterizing some less common mathematical objects.

\subsubsection{The Koch Curve}
The Koch Curve was introduced as part of the discussion of L-Systems in Section \ref{sec:lsys:graphint} on page \pageref{sec:lsys:graphint}.
It is an example of a fractal structure that is strictly self-similar. It is composed of an infinite number of copies of itself. Figure \ref{fig:kochcurve}
shows the Koch curve. In order to construct it we begin with a line segment. This segment is then divided into three pieces of equal length. The middle piece is replaced with the top two legs of an equilateral triangle and the base of this triangle is removed. The result is a curve consisting of 4 line segments each $\frac{1}{3}$ the length of the original line. This procedure is repeatedly applied to the remaining line segments. The limiting object is a self-similar structure called the Koch curve.

\begin{figure}[htbp]
\centering
\includegraphics[scale=0.5]{kochcurve}
\caption{The Koch Curve}
\label{fig:kochcurve}
\end{figure}

To compute the dimension of the Koch curve we use an approach similar to that used with the line segment. Assume that the original construction step is a line segment of unit length. After $n$ steps the number of segments is $M(\epsilon) = 4^n$ each with length $\epsilon = \frac{1}{3^n}$. Substituting into Equation \ref{eq:hausdim} we obtain a value for the fractal dimension of the Koch curve to be
\begin{equation}
D_H = \frac{\ln 4}{\ln 3} \approx 1.26
\end{equation}

\subsection{Box Dimension}
\label{sec:dimension:boxcounting}
A convenient way of estimating the fractal dimension of nearly any arbitrary structure is the box-counting method.  In fact, not only can this method be used to estimate the dimension of classical geometric shapes and all of the fractals discussed so far, but it can be used to find dimension values for all kinds of data sets, not just mathematically defined objects. It is possible to compute the fractal dimension of a mountain or tree given a digital image of the object. For structures in the plane, the method of computing the box-counting dimension is to cover the object with a grid of square cells with sides of length $r$.
Next, count the number of squares $N(r)$ that contain at least part of the structure. Repeat this for varying lengths $r$. We can then plot on double logarithmic axes the number $N$ cells versus the box-size $r$.
Using common regression techniques, we can fit a straight line to our data points, which corresponds to the relation,
\begin{equation}
N(r) \propto r^{-D_B}
\end{equation}
where $D_B$ is the box-counting dimension. This assumes that as the box-size $r$ varies, the number of cells $N$ needed to cover the image varies proportional to $r^{-D_B}$. Since we are plotting this relationship on a $log$/$log$ plot, $D_B$ is simply the negative value of the slope of our plot line.

The data points used to generate the following plots were generated by a box-counting program written for this project.  The program
divides the image into a number of squares of a certain size and then counts the number of squares that contain part of the image (a black pixel).
This process is repeated for varying square sizes. Next, the $log$ of each count value and square size is output in a text format that is readable by
Microsoft Excel.  At this point Excel is used to plot the $log$/$log$ graph, and linear regression is used to fit a line to the data points.  The
negative slope of this line is taken as the box counting dimension $D_B$.
The program runs on Microsoft Windows systems and accepts 512 X 512 pixel, monochromatic images in the Device Independent Bitmap (DIB) format.
It could, however be easily modified to accept images of various dimensions.  For more information please refer to the source code located in 
Section \ref{source:boxcounting} on page \pageref{source:boxcounting}.

\subsubsection{Example: The Sierpinski Gasket}
Figure \ref{fig:sierpinskidim} contains an image of the Sierpinski Gasket which was discussed in Section \ref{sec:IFS:sierpinski} on page \pageref{sec:IFS:sierpinski}.  The fractal dimension
of the gasket can be computed analytically.  It consists of three pieces, each identical to the whole, except scaled down by a factor of $1/2$.  This means that $M(\epsilon) = 3$ and $\epsilon = 1/2$. By substituting into Equation \ref{eq:hausdim} we can see that the Hausdorff dimension for this object is 
$D_H = \frac{\ln 3}{\ln 2} \approx 1.58$.  Table \ref{tab:sierpinski} shows the data produced by running our box-counting program on the image, and figure \ref{fig:sierpinskiplot} shows a plot of these data points.  As you can see, this technique estimates the dimension as $1.67$.

\begin{figure}[hbtp]
\centering
\includegraphics[scale=0.35]{sierpinski}
\caption{The Sierpinski Gasket}
\label{fig:sierpinskidim}
\end{figure}

\begin{figure}[htbp]
\begin{center}
\includegraphics{sierpinski9plot}
\end{center}
\caption{Plot of box-counting measurements for the Sierpinski Gasket. This graph shows the box size $r$ as a function of the number of boxes $n$ needed to cover the image. The slope is shown as -1.6715}
\label{fig:sierpinskiplot}
\end{figure}

\begin{table}[htbp]
\begin{center}
\begin{tabular}{|l|l|}
\hline
$log(r)$&$log(n)$\\
\hline
$0$&4.59405\\
\hline
$0.30103$&4.081311\\
\hline
$0.60206$&3.596487\\
\hline
$0.90309$&3.118926\\
\hline
$1.20412$&2.631444\\
\hline
$1.50515$&2.149219\\
\hline
$1.80618$&1.643453\\
\hline
$2.10721$&1.113943\\
\hline
$2.40824$&0.60206\\
\hline
$2.70927$&0\\
\hline
\end{tabular}
\end{center}
\caption{This table contains the data points generated using our box-counting program on the Sierpinski Gasket.}
\label{tab:sierpinski}
\end{table}

\subsubsection{Example: The Koch Curve}
Figure \ref{fig:kochplot} shows the $log$/$log$ plot of box-counting data for the Koch Curve.  The same program used for the Sierpinski Gasket was used to analyze this image.  The slope of the curve is -1.2806. 
This gives us a box-counting dimension which is very close to the fractal dimension determined analytically earlier.

\begin{equation}
D_H = \frac{\ln 4}{\ln 3} \approx 1.26
\end{equation}

\begin{figure}[hbtp]
\centering
\includegraphics[scale=0.35]{kochplot}
\caption{Plot of box counting measurements for the Koch Curve.  The box-counting dimension is $D_B = 1.2806$}
\label{fig:kochplot}
\end{figure}

For many self-similar structures, such as natural objects and fractal art, it may not be possible to analytically determine dimension. However the box dimension can be used as an appropriate estimator for the Hausdorff dimension. This gives us the ability to apply fractal analysis techniques to a wide range of natural phenomena.






















