Ruler or Compass Dimension

Written by Paul Bourke
October 1998

Introduction

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 refered to as fractals and they have what is known as a fractal dimension between 1 and 2. Dimension measured in this way is refered to as the Hausdorff Besicovitch dimension.

Perhaps the most often quoted example is "How long is the coast of Britian?". 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

N(l) = c l^-D

where c is some constant. Taking logs of both sides

log(N(l)) = log(c) - D log(l)

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.

The software requires a representation of the curve, this is as a file of (x,y) coordinates. The file format is straightforward, it is a series of x,y pairs as either integers of floating point numbers, each number and each pair are separated by any "white space" character (tab, space, carriage return. linefeed, etc). The first few lines of such a file format are shown on the right.

   17.3205 100
   25.9808 105
   34.641  100
   34.641   90
   43.3013  95
   51.9615  90
   51.9615 100
     :      :
     :      :

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
- 1/512'th of the diagonal length, or
- the length of the shortest line segment
which ever occurs first.

As the software reduces the ruler it graphically shows the results. The diagrams below are screen snapshots for the first 6 rulers analysing Browsian (1/f²) noise. The black line is the curve being analysed, the blue lines are the ruler lines, and the red lines are the compass radii.

Ruler 1 (longest)	Ruler 2
Ruler 3	Ruler 4
Ruler 5	Ruler 6

The graph of log(l) vs log(N(l)) for the above analysis is given below. The expected dimension is 1.5 (Hurst exponent H = 0.5, D = 2 - H) Before the software is used to compute the fractal dimension of curves we don't know the dimension of, it should be tested with curves for which we do know the dimension.
A few examples are given below.

Expected: D = 1	Expected: D = 1
Expected: D = log(4)/log(3) = 1.26....	Expected: D = log(8)/log(4) = 1.5

References

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