Fractal Dimension CalculatorWritten by Paul BourkeFebruary 2003
Introduction FDC estimates the fractal dimension of an object represented as a black and white image where the object to be analysed is assumed to be made up of the black pixels. This is accomplished by an algorithm called "box-counting". The application provided here is a upgrade to a very popular application written for the Macintosh back in the early 90's. This upgrade is provided for Mac OS-X (as a UNIX application) and Linux. An earlier application (no longer available) along with the documentation can be found here, in what follows it will be assumed the documentation for the earlier version has been read. Brief theory
Consider a line, if we subdivide the line in half then it takes two bits to recreate the original line. If we subdivide the line into 4 pieces it takes 4 of them to cover the line. We can write this generally, if we have a line segment of length "s' then the number of segments that will cover the original line is given by N(s) = (1/s)1. Consider a square, if we subdivide it into smaller squares each with 1/2 the side length then it takes 4 of these smaller pieces to form the original square. If we subdivide the square into smaller squares each with 1/4 of the side length then it takes 16 of them to form the original square. As above we can write an expression for the number of pieces we need of size "s" to cover the original square, it is N(s) = (1/s)2. Repeat for a cube....N(s) = (1/s)3. The exponents 1, 2, and 3 in the above examples are fundamental to our concept of the dimension involved. This can be generalised to N(s) = (1/s)D where D is the dimension, an integer as above but it need not be. If we take logarithms of both sides we have log(N(s)) = D log(1/s), in order words we can estimate the dimension by plotting log(N(s)) against log(1/s) the slope of which is the dimension, if it isn't an integer then it's a fractional (fractal) dimension. Screen dumpsA side goal for this project was to see to what extent graphical software could be written and which would compile on multiple UNIX based system including Mac OS-X. The aim was to create a single source version rather than have any special case code for any particular platform. To this end, all the graphics are created using OpenGL and the GLUT interface, all dialogs and user IO is implemented with the Forms (xforms) library. So, it is assumed that OpenGL and X are available, a fairly common situation.
Download FDC can be freely downloaded for evaluation. It is fully functional except that offset sampling (a critical feature for good estimates of the fractal dimension) isn't enabled. This allows prospective users to check the application runs on their system and performs as expected before investing in a version which will compute more reliable estimates of the fractal dimension. To obtain the full version with offset sampling enabled the shareware fee of US$30 is payable, preferably through PayPal.
Running FDC FDC can be run in either graphical mode where the user chooses options and gets graphical feedback on the process or it can be run quietly. FDC will present a window with the current image (it will be empty, white), from here you can use the right mouse button (control click on a Mac with only a single mouse button) to show the menus from where you can open a TGA file (24 or 32 bit), set options, start and stop the processing, display the graph, and save the results for further analysis. The full list of command line options for FDC can be viewed by typing "fdc -h", at the time of writing they are as follows.
Usage: fdc [options]
General options
-h this text (help)
-i s load input TGA file
-bw invert image
-q quiet, command line mode
-p start processing immediately
Box options
-n n number of offset samples, default: 10
-b1 n start box size (default: -1)
-b2 n end box size (default: 6)
-bf n box reduction factor (default: 1.2)
Region options
-sl left boundary (default: 0)
-sr right boundary (default: image width)
-sb bottom boundary (default: 0)
-st top boundary (default: image height)
So for example the command line to run the analysis on the image "snowflake.tga" (supplied in the FDC distribution) quietly with the results written to standard output, using box sizes that range from 200 to 8 in factor steps of 1.2 with 100 offset samples might be as follows. fdc -q -i snowflake.tga -b1 200 -b2 8 -n 100 -bf 1.2 > snowflake.dat The results in "snowflake.dat" will be something like the text on the left below. Where the first column is the box size (s), the second column is the minimum number of covering boxes (N), the third column is log(1/s), and the last column is log(N). The estimate of the fractal dimension is the slope of this graph. If the application is run in graphical mode, at the end of the processing the graph window will look something like the image on the right.
The processing will generally run faster if the options and graph window are hidden. It will run significantly faster if run in "quiet" mode using the "-q" command line option. This is particularly important if a large number of offsets are being used. Box size rangeThe default range of box sizes is usually optimal but not always so. They should only be changed when you have some experience and understanding of the processes involved. The following graph is the result of performing the box counting where the box size ranged from being 5 times the width (or height) of the image to 1 pixel. For successful choice of the box size range it is important to understand the regions of the graph illustrated here. 
Testing The following are some shapes for which the exact fractal dimension is known, these can test the convergence and the dimension estimated using this software. Note that for the examples below which have a fractal dimension one doesn't expect a perfect match to theoretical because the image is only an approximation to the real fractal form. Note that since FDC assumes the object doesn't exist outside the image area, the estimates for the Sierpinski Carpet are particulary sensitive to this.
Advanced topic: regional analysis
It is possible to analyse just a portion of the image.
For example fdc -sr 700 -sl 400 -sb 300 -st 600 -i gasket.tga 
It is anticipated that in normal operation the area of interest will be chosen in an image editing page prior to analysing the fractal dimension. The ability to process just a region of the image is intended to be used with automatic scripts to estimate the fractal dimension locally across the image, for example, when the dimension is expected to vary across the image. The approach that might be used is to slide a rectangular region across the image estimating the dimension at each position, these estimates can then be combined to form an image showing the dimensional variation. This is similar to a sliding window used in signal processing to calculate the fourier spectrum variation of a time series. There are two variables involved, the width of the window and the distance between two successive window positions. Typically there is significant overlap between the windows. The image below is formed by analysing a gasket (image size 840 by 950) with a window width of 200 and a window step size of 20. 
The colour scale is a blue to green to red colour ramp where blue is 1 and red is 2. The correct dimension in this case is 1.585 hence the green appearance. The white region is where the window didn't intersect with any part of the image.
The window size and stepping are chosen based upon a tradeoff between temporal resolution and reliability of the dimension estimate. A large window gives good estimates but low resolution (ability to detect local variations in the dimension), while a small window gives good resolution but poorer estimates. In the example above there are good estimates but low resolution. In the example below a window of 50 is used with the same stepping size of 20, here there is better resolution but poorer estimates. 
Please note that the above colour plots of the sliding window dimension estimates is not part of the FDC package. FDC creates the data for the above but it is up to user to turn that data into a suitable form for visual inspection. Applications of this software
Using Box Counting Techniques for Measuring Shape of Colonies of Filamentous Micro-organisms
Viscosity of Venusian Lava Flows: Constraints from Fractal Dimension
and Chemical Composition
The Box-Counting: Critical Study
Fractal Properties of the Thyrotropic Feedback Control
Implications of a Nonlinear Model Compared with Empirical Data
Measuring Ocular Redness: First order (luminance & chromaticity)
measurements provide more information than second order (spatial
structure) measurements.
Incident Detection by Fractal Dimension Analysis of Loop Detection Data
+plus issue 15
Advances in the implementation of the box-counting method of fractal
dimension estimation References
Texture Description and Segmentation through Fractal Geometry
The Fractal Geometry of Nature
Fractals and Disordered Systems
The Infinite Number of Generalised Dimensions of Fractals and Strange Attractors
Determination of Fractal Dimension for Geometrical Multifractals
| |||||||||||||||||||||||
