1. Measure of fractal dimension

1.1 Principles

Fractalyse implements different methods (box counting, radius mass, correlation...) to measure fractal dimension which corresponds to different dimensions (Hausdorff, Minkowski, correlation...). The process of the measure is split in two part :

  • the counting method
  • the estimation module.

1.1.1 The counting method

Counting method goes step by step following an iteration principle. At each iteration step, the method involved counting the number of black pixels contained in a counting window. From one step to the next, the size of the counting window is enlarged. By doing that, we artificially change the level of analysis of the image. So, for each method we have two elements varying according to the counting step (iteration step) (i):

  • the number of counted elements (which is roughly the number of black pixels present in the window) (N)
  • the size of either the counting window or the reference element (ε).

Then, we obtain a series of points that can be represented on a Cartesian graph. The Y-axis corresponds to the number of counted elements (N) and the X-axis corresponds to the size of the counting window or to the size of the reference element ε, with ε increasing from step to step.

image ville-> [Counting method] -> courbe-> [Estimation module] ->D=1.7
ImageCurveFractal dimension

1.1.2 The estimation module

Mathematically, the series of points is a curve (named the empirical curve). The next stage is to fit this empirical curve with another one, the estimated curve. If the empirical curve follows a fractal law, the estimated curve has the form of a power law (parabolic or hyperbolic), and D represents the fractal dimension.

N = εD or N = ε-D

1.2 The counting methods

Now, there is seven methods to measure fractal dimension.
  • grid
  • radius mass
  • dilation
  • correlation
  • gaussian convolution
  • box-counting (testing)
  • network (testing)

1.2.1 Grid method

This is the most used method to estimate fractal dimension. The image is covered by a quadratical grid and the grid distance ε is then varied. Following the logic described earlier, for each value ε, the number of squares N(ε) containing any occupied point is counted. Usually, the value set of ε follows a power of 2.

Parameters : centre and size of the square zone to study

You can choose the centre by selecting a pixel of the image then click on the button "Cursor", or directly capturing the coordinates. You can also use the barycentre of the image. The size of the square define also the value set of ε, for example size 16 corresponds to the set (1, 2, 4, 8), size 72 corresponds to the set (1, 3, 9, 18, 36) and size 216 corresponds to the set (1, 3, 9, 27, 54, 108). Values sets are mixed with power of 2 and power of 3.

1.2.2 Radius mass method

This method refers to a specific point known as the counting centre and gives the law of distribution of the occupied sites around this point. A circle is drawn around this point, and the radius r is gradually increased. At each step, the total number of occupied points N(ε) inside the circle is counted. In this method, ε equals to 2.r+1.

Parameters : counting centre and form of the counting window (circle or square)
You can choose the counting centre by the same way as Grid method.

1.2.3 Correlation method

Each point of the image is surrounded with a small squared window. The number of occupied points inside each window is enumerated. This allows the mean number of points per window of that given size to be calculated. The same operation is applied for windows of increasing sizes. The X-axis of the graph represents the size of the side of the counting window ε = (2i+1). The Y-axis represents the mean number of counted points per window. (Because the theory underlying the correlation analysis considers the simultaneous presence of two points at a certain distance, i.e. the mean distance between a pair of built-up pixels, the correlation dimension is a second order fractal dimension. In a multi-fractal theoretical framework, this correlation dimension should be extended to a series of three, four or more points). In principle it is possible to choose any shape for the window, such as circle, hexagon, etc. However, since pixels are square-like, the choice of a square helps to avoid rounding errors.

Parameters : maximum window size (ε).

1.2.4 Dilation method

This method is based on the algorithm introduced by Minkowski and Bouligand to establish the dimension of an object using the measure theory approach. In this analysis each occupied point is surrounded by a square of size ε, the surface of which is considered to be completely occupied. The size of these squares is then gradually enlarged, and we measure the total surface A(ε) covered at each stage. As the squares are enlarged, any details smaller than ε are overlooked and we gradually obtain an approximation of the original form. Because more and more squares overlap, the total occupied surface for a particular value ε is less than what it would be if the same number of occupied points that make up the original form were surrounded individually. By dividing this total surface by the surface of a test square (ε2), we get an approximation of the number of elements N(ε) necessary to cover the whole.

Parameters : number of dilation

1.2.5 Gaussian convolution

When the image is reduced to a single curve, we can apply another counting method: the gaussian convolution. Contrary to the other methods, the gaussian convolution is applied on a curve and not on an image. At each iteration step, the curve is more and more smoothed. In this case, the structuring element (which increases at each iteration step) is the variance of the gaussian function used to smooth the curve. The X-axis represent the variance of the gaussian function and Y-axis the length of the curve (expressed in number of pixels) divided by the variance.

Parameters : number of step and maximal variance (in pixel).

1.2.6 Box method (testing)

This method consist in finding the least number of square of size ε needed to cover all black pixels. The algorithm converge to the minimum in infinite time, so the results are only approximation of the best coverage. It is a generalized version of grid method.

1.2.7 Network method (testing)

1.3 The estimation module

The next stage of the process is to fit the empirical curve (in blue) from counting method, with another one, the estimated curve (in red). If the empirical curve follows a fractal law, the estimated curve has the form of a power law (parabolic or hyperbolic) N = εD or N = ε-D. Because an image is not a pure fractal (it is not a continuous function but a discrete and finite one), it is only possible to approximate the fractal law. It explains why Fractalyse propose some option to approximate the empirical curve :

  • non linear regression
  • linear logarithmic regression
  • non linear differentiate regression (only with radial and correlation methods)

1.3.1 Nonlinear regression

In this method, we can approximate the empirical curve with four different equations : the fractal law N(ε) = εD and three others wich permit to measure also the fractal law deviation

  • N(ε) = a.εD
  • N(ε) = εD+c
  • N(ε) = a.εD+c

D is the fractal dimension.
c corresponds to the point of origin on the Y-axis.
a is called the “pre-factor of shape”. It gives a synthetic indication of the local deviations from the estimated fractal law.
Default is last equation.

To ensure that Fractalyse finds the best approximation, the software can performs the estimation with two different methods. The first one is based on the use of partial derivate whereas the second one is based on evolutionary strategies (that is, genetic algorithms). In most cases, the two methods give exactly the same results.
Default method is partial derivate, but you can use both by checking "ES estimation".
Last option is the error function. Default is least square method : ferr = (femp - festim)2, but you can choose normalized least square : ferr = (femp-festim)2 / femp2 by checking "Normalized estim." (testing only).

1.3.2 Linear logarithmic regression

In this method, the curve is transformed by logarithmic transformation. Then the power law become linear equation :

log(N(ε)) = log(εD) => log(N(ε)) = D.log(ε)

In the software, we used log(N(ε)) = D.log(ε)+c

1.3.3 Nonlinear differenciate regression

This method has been added to compare results with non linear regression.

1.3.4 Quality of estimation

The quality of the estimation is quantified using a correlation ratio. If the fit between the two curves (empirical and estimated ones) is bad, two conclusions are possible: either the pattern under study is not of a fractal nature or it is of a multi-fractal nature. In the second case, the empirical curve has to be divided into several portions, each of them corresponding to a different estimated curve (i.e. according to the considered portion of curve, the non linear regression gives different values for the three parameters a and D and c).

Correlation ratio : 1 ( y i y i ˆ ) 2 ( y i y ˉ ) 2 1 - sum (y_{i}-hat y_{i})^{2} over sum (y_{i}-bar y)^2

1.3.5 Other curves

  • Curve of the scaling behaviour : α(ε) = d log(N(ε)) / d log(ε)
  • Error curve : difference between empirical and estimated curve fdiff = femp - festim
  • Objective curve

2. Other features

2.1 Border extraction

2.2 Cluster counting

2.3 Tentacularity