## Fractal Dimension CalculatorWritten by Paul BourkeFebruary 2003
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). 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)
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)
Repeat for a cube....N(s) = (1/s)
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) 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.
FDC is a Mac OSX application that 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. If you have any problems with these demo version please contact the author. To obtain the full version with offset sampling enabled the shareware fee of US$30 is payable, preferably through PayPal. Note than from Lion onward you may need to install X-Windows separately, it is recommended you use XQuartz. Also, you will need a 3 button mouse since the right mouse button is used for the menus. This can be achieved by enabling the secondary mouse button on the Apple mice.
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 range
The 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.
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 particularly sensitive to this.
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 trade-off 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
## Ruler or Compass DimensionWritten by Paul BourkeOctober 1998 Update June 2017, see below for an implementation for vector data.
While this application is not generally available, if it is of interest then please contact the author by email. The author is also available for consulting and bespoke software development in this area.
A "standard" method of estimating the length of a curve on a plane is to count how many ruler lengths it takes to move from the start of the curve to the end. Since the ruler has a finite length, the details of the curve that are smaller than the ruler get skipped over and therefore the length we measure is normally less than the real length. This is illustrated below for two rulers (red) of different length being used to estimate the length of the curve in black. Intuitively we believe that as our ruler gets shorter, our estimate of the real length improves and increases. The estimate of the length on the right image above is closer to the true length because it follows the curve more closely. This improved estimate as the ruler length decreases is certainly true for many curves (1 dimensional objects) but it is not true for others. Such curves are referred to as fractals and they have what is known as a fractal dimension between 1 and 2. Dimension measured in this way is referred to as the Hausdorff Besicovitch dimension. Perhaps the most often quoted example is "How long is the coast of Britain?". One could measure the length using a map and a compass set to say a 50km radius. A better estimate would be achieved by using smaller and smaller compass radii, each one revealing more and more detail. One could go further and have someone walk around the coast, they would still make decisions on how closely they followed the beach. As one became more and more "precise" one would find more and more detail about which to become precise about. As with most fractals in the real world this process and therefore the fractal nature of the object is only appropriate over some limited range of scales. There are many such examples in nature where the relationship between the measured length and the ruler length is not linear, ie: 1 dimensional. The outline of mountain ranges, clouds, and Brownian motion are another examples. The ruler or compass dimension of a curve is computed from the relationship between the length of a ruler and the number of rulers required to measure the length of the curve. This is given by ^{-D}where c is some constant. Taking logs of both sides
So if we plot log(N(l)) against log(l) for a range of values of l, the slope will be an estimate of the fractal dimension D. Implementation
The software described here estimates the length of a curve by measuring it with successively shorter ruler lengths. The results when plotted as described above give an estimate of the fractal dimension of the curve.
Note: only continuous curves are possible in this implementation.
The range of line lengths is varied
in powers of sqrt(2) from half the diagonal length of the
bounding box of the curve to either
As the software reduces the ruler it graphically shows the results.
The diagrams below are screen snapshots for the first 6 rulers
analysing Brownian (1/f
The above are applied to image representation of curves, this can be limiting for many datasets that might have both large scale and fine grain detail thus requiring very large image resolutions to effectively be represented as an image. There are other problems in the reliability of the compass dimension estimates arising from rasterisation of vector data. The software described here (vcompassdim) computes the compass dimension for vector data in 2D. Usage: vcompassdim [options] filename Options -w n Size of output image files, default: do not create The data is conveyed to the software through a text file consisting of x,y pairs, each number and pairs can be separated by any white space character but usually it is a space between x and y and a carriage return before the next pair. The first few lines of an example data file might be as follows 17.3205 90 17.3205 100 25.9808 105 34.641 100 34.641 90 43.3013 95 51.9615 90 51.9615 100 60.6218 105 51.9615 110 51.9615 120 60.6218 125 : : : As per the early fractal dimension estimators, before applying to real data the code should be carefully tested against curves with known dimension. One such curve is the Koch curve with a fracal dimension of log(4)/log(3) = 1.26. A vector form of that curve is generated and the graph of log(l) vs log(N(l)) and linear curve fit shown below.
As a visual check the software optionally outputs an image for every compass length. As example is shown below, the black line is the curve read from the data file, the blue lines are the rulers following the curve, and the red circles are the compass arcs.
Another example might be to apply to a space filling curve, where the compass dimension should approach 2. An example is below.
The software writes the log(l) and log(N(l)) as text in 4 columns as follows l N(l) log(l) log(N(l)) 857.369 7 6.75387 1.94591 606.251 21 6.40729 3.04452 428.684 26 6.06072 3.2581 303.126 55 5.71415 4.00733 214.342 116 5.36757 4.75359 151.563 242 5.021 5.48894 107.171 363 4.67443 5.8944 75.7814 810 4.32785 6.69703 53.5855 2186 3.98128 7.68983 37.8907 3280 3.63471 8.0956 26.7928 6561 3.28813 8.7889 18.9454 19683 2.94156 9.88751 13.3964 24907 2.59499 10.1229 9.47268 59049 2.24841 10.9861 6.69819 68890 1.90184 11.1403 4.73634 118098 1.55526 11.6793 And finally the compass dimension is the slope as shown below.
Andrew Harrison. Fractals In Chemistry, Oxford Chemistry Primers. Oxford Science Publications, 1995 T.G. Smith Jr., W.B. Marks, G.D. Lang, W.H. Sheriff Jr., and E.A. Neal. A Fractal Analysis of Cell Images. Journal of Neuroscience Methods, Vol 27, pp 173-180, 1989 Heinz-Otto Peitgen. Fractals in the Classroom, Part 1. Springer-Verlag, 1991, pp 240 Heinz-Otto Peitgen, Dietmer Saupe. The Science of Fractal Images. Springer-Verlag, pp 61, 1985
## LacunarityWritten by Paul BourkeApril 2004
Lacunarity was initially introduced as a means of further classifying fractals and textures which had the same fractal dimension and a very different visual appearance. Lacunarity is a measure of how the fractal fills space, if the fractal is dense the lacunarity is small, the lacunarity increases with coarseness. Method 1: (Voss)
Let P(m,r) be the probability that a box of size r contains m black pixels.
Define M
and
then
Method 2:
Calculate the mean M(r) and variance V(r) of the number of black pixels in each box size r.
Notes
- These two definitions give identical results.
- The object being studied is assumed to be made up of black pixels, all
non object pixels are white.
- The value for a 1 pixel box (r = 1) reduces to the ratio of the white to
black pixels, most easily derived from the equations for method 1.
- Only include those boxes which are totally enclosed within the boundary
of the image.
- As the number of occupied pixels (black) tends to 0 the lacunarity
tends to infinity, so sparse data will generally have higher lacunarity
curves.
- If lacunarity is plotted as log(L(r)) vs log(r) then fractals will
have straight line plots, in other words, they have similar appearance
across scales.
Texture Description and Segmentation through Fractal Geometry. J.M. Keller, S. Chen, R.M. Crowover. Computer Vision, Graphics, and Image Processing, 45, 150-166 (1989) Characterisation and measurement to scaling phenomena in disordered systems. R. Voss, R. Pynn and A Skjeltorp, (Ed), New York, 1986. Fractal Methods and Results in Cellular Morphology. G.D. Lange and W.B. Marks. J. Neurosci, 69, 1123-1126 (1996) Lacunarity calculation in the true fractal limit. D.A.Fabio, A. Reis, and R. Riera. J. Phys. A. Math, 27, 1827-1835 (1994) Three-dimensional image analysis and fractal characterization of kidney arterial vessels. M. Sernetz, J. Wubbeke, and P. Wiezek. Physica A, 191: 13-16. (1992)
## Multifractal spectrumWritten by Paul BourkeJanuary 2004
Let N(r) be the total number of boxes (non overlapping)
of size length r covering the object.
Let M
The multifractal dimension D(q) is given by
q ranges from -infinity (concentrates on less dense regions) and +infinity (concentrates on dense regions). For q = 0 this reduces to standard box dimension.
Consider all circles of radius r that have their center on the object.
Let M
The multifractal dimension D(q) is given by
ReferencesMultifractal Characterization of Soil Particle-Size Distributions. A.N.D. Posadas, D. Gimenez, M. Bittelli, C.M.P. Vaz, and M. Flury. Soil Sci. Soc. Am. J. 65:1361–1367 (2001) Direct Determination of the f(alpha) Singularity Spectrum. A. Chhabra and R.V. Jensen. Physical Review Letters, 62, March 1989, #12 Multifractal features of random walks on random fractals. A. Bunde, S. Havlin, H.E. Roman. Physical Reviewm A 42, 6274 (1990) Multifractal phenomena in physics and chemistry. H.E. Stanley and P. Meakin. Nature, 335, 405 (1988) Measuring the strangeness of strange attractors. P. Grassberger and I. Procaccia. Physica, Amsterdam, 9D, 189 (1983) Scaling in financial prices: IV Multifractal Concentration. M.B. Mandelbrot. Quantitative Finance, Vol 1, 641-649 (2001) Are Neurons multifractals. E. Fernandez, J.A. Bolen, et al. Journal of Neuroscience Methods, 89, 151-157 (1999) Physical mechanisms underlying neurite outgrowth: a quantitative analysis of neuronal shape. Caserta, F., et al. Physical Review Letters, 1990. 64(1): p. 95-9
## Recurrence plotsWritten by Paul BourkeJanuary 1998
Recurrence plots are used to reveal non-stationarity of a series as well as to indicate the degree of aperiodicity. They were first proposed by Eckmann et al around 1986 in order to study phase space orbits. For example, for a stationary system the recurrence plot should generally be homogeneous along the diagonal. Consider a series x with N terms
_{0}, x_{1}, x_{2}, x_{3}, x_{4},
x_{5}, .... x_{i}, ..... x_{N-1}
Form all the vectors y _{i} = ( x_{i}, x_{i+d}, x_{i+2d}, .... )
D >= 2 and d >= 1
This is normally referred to as The recurrence plot is formed by comparing all embedded vectors with each other, and drawing points when the distance between two vectors is below some threshold. More precisely, we draw a point at coordinate (i,j) if the i'th and j'th embedded vectors are less than some distance r apart, eg: a point is drawn if _{i} - y_{j}|| < r
i is plotted along the horizontal axis, j on the vertical axis.
The correlation integral is just the "density" of points on a recurrence plot, that is, the number of points divided by the total number of points in the plot. _{i} - y_{j}|| < r) / N^{2}
Note, the formulation includes the points along the diagonal where i = j. Determining the slope of the correlation integral as a function of log(r) gives the correlation dimension. This is most efficiently computed from a colour recurrence plot where, in general, all the distances have been computed and one simply need to step through a range of radii and count the number of cells with a distance less than the radius.
The usefulness of this result stems from an observation that the fractal
dimension of an attractor of a chaotic system exhibits self similarity.
It can be shown that the topological dimension of an embedding is the
same as the topological dimension of the underlying attractor as long
as the embedding dimension is large enough. Unfortunately there is no
straightforward way to determine what "large enough" is except by
computing the correlation dimension for a number of different embedding
dimensions. Further examples
Source code
The following illustrative C source was used to generate the diagrams shown above
Understanding Non-linear Dynamics. Daniel Kaplan and Leon Glass. Springer-Verlag Recurrence Plots of Dynamical Systems. Eckman, J.P., et. al. Europhys. Lett. 4, 973 (1 November 1987). Characterization of Strange Attractors. Grassberger, P., Procaccia, I. Phys. Rev. Lett. 50, 346 (31 January 1983).
## Self SimilarityWritten by Paul BourkeOctober 2002, updated June 2007
Fractals usually possess what is called self similarity across scales. That is, as one zooms in or out the geometry/image has a similar (sometimes exact) appearance. The following will illustrate various types of self similarity as well as present some real world examples. Exact self similarityThe self similarity may be exact, this normally only occurs in mathematically defined fractals where the realities/constraints on structures by the physical world don't apply. The following example is the well known Koch snowflake curve created by starting with a single line segment and on each iteration replacing each line segment by four others shaped as follows . As one successively zooms in the resulting shape is exactly the same no matter how far in the zoom is applied.
A far more common type of self similarity is an approximate one, that is, as one looks at the object at different scales one sees structures that are recognisably similar but not exactly so. An example of this in a mathematically defined system can be readily demonstrated by almost all the patterns seen in the Mandelbrot set. The following show three successive zooms and at each level a structure similar but not exactly the same as the whole Mandelbrot set can be found.
Note that in the above example the self similar structure occurs at discrete levels of scale while other systems like the Koch curve the self similarity occurs at all scales. Statistical self similaritySometimes the self similarity is isn't visually obvious but there may be numerical or statistical measures that are preserved across scales. One obvious measure might be the fractal dimension, in the example below of 1/f noise. the fractal dimension is constant as one zooms in.
Consider the following image, is it on the scale of a large piece of rugged terrain photographed from an aeroplane, or the side of a mountain, or a patch of dirt on the scale of a few meters, or a magnification of the surface of a rough rock? Whichever it is, it could also easily be imagined to be any one of the others. So one could start at the large scale view from the air and apply successive zooms down to a microscopic scale, the surface maintains self similarity across those scales.
As with most fractal structures found in nature, the self similarity only occurs over a range of scales. In the above example, there is no self similarity as we zoom out to see the whole planet, or zoom in to microscopic scales. Example 2 - Fern leaf
In the case of the self similarity found in the fern, not only is there a limit to the range of scales at which the self similarity occurs but it also occurs at only at a few discrete scales.
Branching structures such as roots, capillaries, river networks often exhibit self similarity across scales. In some cases, a young tree may be self similar in time, namely, as it grows. A Bonsai tree is a good example (if a little artificial) of this. The trees below, besides the fact that you can see them in their context and thus scale, could easily be imagined to be anywhere in size from a small shrub of 10cm, as they are at about 1m tall, and even as small trees of 10 to 20m in height, or large trees of 100m. They would all pass for possible trees across that large range of scales.
Tropical leaf |