# Digital Image Processing (EEE F435)
### Assignment on Fractal Dimension
*Supervised by Prof. R. Venkateswaran*
<br><br>
<b>Group number: 35</b>
|Member Name|ID|
|--|--|
|Nihal Jain|2017A7PS0325H|
|Praneetha Vaddamanu|2017AAPS0319H|
|Shifa Saima|2017B2A81303H|

<div style="page-break-after: always;"></div>

### 1. Fractal Dimension

- *What is fractal dimension?*

A <i>fractal dimension</i> is a ratio providing a statistical index of complexity comparing how detail in a pattern changes with the scale at which it is measured. In general, fractal dimensions help to show how scaling changes a model or modeled object.

- *What does it measure?*

Fractal dimension is a measure of how *complex* a figure is, which is sometimes intuitively explained as how *rough* it is, when zooming in on the figure extensively. In another sense, it captures a notion of <i>how many points</i> lie in a given set. Even though a plane and a line have uncountable points each, a plane is <i>larger</i> than a line, whereas something like the *Vicsek fractal* that we will see subsequently, lies somewhere in between. Fractal dimension captures this notion nicely. The mathematical formulation of the fractal dimension specifies this idea clearly.

Mathematically,
$$
D = \frac{\ln{N}}{\ln{S}}
$$
where $D$ is the fractal dimension, $N$ is the number of the auto-similar parts in which an object can be subdivided and $S$ is the scaling, that is, the factor needed to observe $N$ auto-similar parts.

As an example, for the <i>Vicsek Fractal</i>, $N = 5$ and $S = 3$. So, $D_{Vicsek} = \frac{\ln{5}}{\ln{3}} \approx 1.4649$.

<p align="center" width="100%">
<img src="https://i.imgur.com/DpZcdtT.png" height=300px>
</p>
<p align="center" width="100%">
<em>Fig 1. Vicsek Fractal.</em>
</p>

<div style="page-break-after: always;"></div>

### 2. Box Counting Method

The <i>box counting</i> method is a technique for approximating the fractal dimension of an object. In essence, it can be viewed as zooming in or out of the image, to observe how detail changes with scale. However, in this technique, rather than changing the magnification of the image itself, we alter the size of the element used to inspect the image, by varying the <i>box width</i>.

Fractal dimension can be approximated by the box counting method using the relation given below :

$$
D = \frac{\ln{N_{boxes}}}{\ln{1/r}}
$$
where $D$ is the fractal dimension, $N_{boxes}$ is the number of boxes containing some portion of the object, and $r$ is the side length of a box.

On plotting a graph between $\ln{N_{boxes}}$ on the y-axis, and $\ln{1/r}$ on the x-axis, we can hence estimate the fractal dimension $D$ as the <i>slope</i> of the graph.

We demonstrate the box counting method using a sample image of the Vicsek fractal, the fractal dimension of which as shown previously is **1.4649**.

First, we attempt to do this by **hand-counting** the number of boxes containing a portion of the image, for varying box widths.

|<img src="https://i.imgur.com/nI4gRcx.png" height=150px><font size=2px>Box width = 60px<br>Box count = 36</font>|<img src="https://i.imgur.com/8OvJwub.png" height=150px><font size=2px>Box width = 100px<br>Box count = 21</font>|<img src="https://i.imgur.com/bb1FWBr.png" height=150px><font size=2px>**Box width = 140px<br>Box count = 12**</font>|<img src="https://i.imgur.com/y9FWC6g.png" height=150px><font size=2px>**Box width = 180px<br>Box count = 8**</font>|
|:---:|:---:|:---:|:---:|

Now, the points on the $\ln{N_{boxes}}$ vs ${\ln{1/r}}$ graph would be plotted as:

$(-4.094, 3.584), (-4.605, 3.045), (-4.942, 2.485), (-5.193, 2.079)$

We find the slope $m$ of the best-fit line through these points, using the *least squares regression* method (hand calculation shown in the next section), which comes out to be **1.374**.

<div style="page-break-after: always;"></div>

`MATLAB` code used for automating the box counting method, with relevant documentation:

|<img src="https://i.imgur.com/x7jAGsL.png" height=600px width=1000px>|<img src="https://i.imgur.com/DvQITrf.png" height=600px width=1000px>|
|---|---|

<div style="page-break-after: always;"></div>

On running the program for box widths varying from 1px to 200px, with an increment of 7px in box width for every iteration, we obtain the following graph.

<p align="center" width="100%">
<img src="https://i.imgur.com/FbuGkWk.png" height=300px>
</p>
<p align="center" width="100%">
<em>Fig 2. Box counting estimation for fractal dimension</em>
</p>

The solid black points represent our observations and the green line is a best fit line estimation for the observed points. This line is obtained using least squares linear regression. The fractal dimension is roughly approximated as the slope of this best fit line. The slope obtained of this line is 1.440.

Hence, our revised estimate for fractal dimension is **1.440**, which is much closer to the actual value of 1.4649 than the estimate we had obtained by hand calculation.

### 3. Role of Regression in Box Counting

- *In measuring fractal dimension using box counting method, why is regression/correlation method used to find the fractal value?*

As described above, it is estimated that $\ln{N_{boxes}}$ and $\ln{1/r}$, follow a linear relation and clearly, the slope of this line gives a measure of the fractal dimension $D$. From the data obtained using the box counting method, the linear relation, and hence the slope of the line giving the required fractal dimension, is generally estimated using <b>least squares linear regression</b> method.

- *How have you used it in your fractal dimension calculation?*

In our experiments, for any object, we obtained a set of data points for the $\ln{N_{boxes}}, \ln{1/r}$ plot by varying the box width $r$ and for each box configuration, estimating $N_{boxes}$, the number of boxes that contain the object. After sampling several such data points, we performed linear regression using least squares method to obtain the linear relation that satisify the observed data. The slope of this line was taken to be an appoximation for the fractal dimension $D$ of the given object.

<div style="page-break-after: always;"></div>

- *Show a hand calculation.*

Following the data obtained above, we can estimate the fractal dimension using linear regression by the least squares method.

Once again, the data obtained by box counting for four samples obtained by hand is tabulated below.

|$boxwidth$ $(r)$|$N_{boxes}$|$x = \ln{\frac{1}{r}}$|$y = \ln{N_{boxes}}$|
|:--:|:--:|:--:|:--:|
|60|36|-4.094|3.584|
|100|21|-4.605|3.045|
|140|12|-4.942|2.485|
|180|8|-5.193|2.079|

We are interested in the slope of the line that best fits these sample points. Using least squares linear regression, we obtain the required line as follows:

Let the line be $Y = mX + c$.

Then from statistics, we know the following relations:

$$
m = \frac{N\sum{(xy)} - \sum{x}\sum{y}}{N\sum{x^2} - (\sum{x})^2}
$$
$$
c = \frac{\sum{y} - m\sum{x}}{N}
$$

For the above data, we obtain, the following values:
$$
\sum{(xy)} = -51.772 \\ \sum{x}\sum{y} = -210.809 \\ \sum{x^2} = 89.357 \\ (\sum{x})^2 = 354.720 \\ \sum{x} = -18.834, \sum{y} = 11.193
$$

Plugging in these values and $N=4$ into the above formulas, we obtain,

$$
m = 1.374 \\
c = 9.2677
$$

Therefore, we see, by hand calculation we get a loose estimate of the fractal dimension of the Vicsek Fractal as the slope ($m$) as **1.374**. Our `MATLAB` code gives a better estimate as **1.440**.