Mass Fractal Analysis of Minimal Spanning Tree Graphs
using 2-d Wavelet Packet Analysis

by

Cameron L. Jones

It is now possible to use the power of two dimensional Wavelet Packet Analysis (2-d WPA) to measure the mass fractal dimension, D_f of minimal spanning tree graphs. The following example shows how this can be accomplished using S-Plus and S+ Wavelets. S-Plus code is available for drawing the minimal spanning tree, and the output graph is then manipulated using PaintShop Pro and WinLab in order to generate an image data set which can be input into the S-Plus operating environment.

REQUIREMENTS: A minimal spanning tree (mst) is a graph theoretic method which connects a set of points together using the shortest path. Full details are available in the papers by Jones et al. (1996). In the original application, the mst was used to generate a histogram showing the relative distribution of the edge (or line) lengths which made up the mst graph. This statistic was difficult to work with, and therefore a superior descriptive index was developed. This approach was an extension from previous work which had shown how 2-d WPA could be used to measure the mass fractal dimension of binary images or the self-affine fractal dimension of grey-scale images. Here it is shown how 2-d WPA can be used to measure the mass fractal dimension of the mst graph.

REQUIREMENTS: The following software is needed:

S-Plus for Windows: http://www.mathsoft.com/splus.html

S+Wavelets: http://www.mathsoft.com/splsprod/wavelets.html

WinLab: http://www.coast.net/cgi-bin/WebZip?path=/SimTel/win3/graphics/wlabv30.zip

PaintShop Pro: http://www.visitorinfo.com/software/paint.htm

S-Plus Minimal Spanning Tree (dotmst): http://www.swin.edu.au/chem/bio/fractals/mst01.htm

S-Plus 2-d WPA: http://www.swin.edu.au/chem/bio/s+code/wpafrac1.htm

EXAMPLE: The following data set called: "five10.txt" was used as the raw data input to the S-Plus program called: "fracmst". Clicking on these hypertext links will download the sample data as well as the S-Plus code needed to operate this sotware function. Instructions for adding this new function to the S-Plus library of functions can be found in Jones (1996).

The following screen capture shows how S-Plus and the program: "dotmst" were used to generate the mst for this dataset.

The image was copied to the clipboard from within S-Plus and then PaintShop Pro was opened. Paste the contents of the clipboard into PaintShop Pro, and use the cropping tool to cut out the mst from within the graph. Then select cut and close this window. Next, select File, then New, then New Image. Change the width and Height fileds to 300 x 200 and the image type should be changed to 2 colors (1 bit). Now with this window as the dominant screen, select Edit, then paste the contents of the clipboard as a new selection. This drops the mst into the 300 x 200 frame. Then select Copy and open WinLab, and select Paste as new image. Then from Image, select change depth to 8 bits per pixel. Then from Image, select convert to greyscale. Then select Save as and save into *.RAW image file format. You can download the RAW image from here.

This image was resized to 300 x 200 pixel resolution (above), and then it was saved into RAW file format and opened in S-Plus (see below). Note that the perspective in the S-Plus window has skewed the image, although during image-processing the pixel aspect ratio is correct.

Once the image has been opened in S-Plus, the 2-d WPA program which operates on images of 300 x 200 pixel resolution is needed. Once this is run, the program will prompt you to enter the file name for the image file. This is the file created in RAW format. In the following example, the screen contents have been copied to the clipboard and pasted into this document for clarity.

Input Wavelet Transform Filter to use for analysis:

Choose from the following

list:

DAUBLETS: haar(d2) d4 d6 d8 d10 d12 d14 d16 d18 d20

SYMMLETS: s8 s10 s12 s14 s16 s18 s20

COIFLETS: c6 c12 c18 c24 c30

Your choice is: s12

The following list shows selected wavelet packet best basis energies and their corresponding coefficient index positions in square brackets (i.e. [*]).

[1] 1.037418e+008 9.176008e+007 8.579729e+007 8.512876e+007 7.373475e+007

[6] 6.214246e+007 6.812129e+006 5.641391e+005 9.085219e+004 2.749035e+004

[11] 1.456491e+004 8.578879e+003 6.839260e+003 5.484134e+003 4.425714e+003

[16] 3.507931e+003 2.643080e+003 1.963104e+003 1.418426e+003 9.404844e+002

[21] 5.852387e+002 3.185767e+002 1.451815e+002 4.977111e+001 1.056591e+001

[26] 2.535290e-001 3.996592e-042 3.996592e-042 0.000000e+000

Examine the list of Wavelet Packet Coefficient Energies. Take particular note of the

Coefficient Index Position number where the energy falls below 1.

For binary images of 300x200 pixel size,the 'Fmin'size to include in the least squares regression is the one that returns the highest r^2 value (i.e. closest to 1)

Coefficient Energies <500 are highlighted in RED.

Warning: Data values <=0 omitted from logarithmic plot

Enter the number of the last valueyou want included in the regression:

The next image shows the first sample graph showing all the data.

The user is then prompted to select cut-off values for including in the least squares linear regression. In this example, the correct cut-off is "24", although several values on either side of this number were trialled before the value which returned the highest r2 value was discovered.

Enter the number of the last value you want included in the regression: 24

Call: lm(formula = log10(y2) ~ log10(x2))

Residuals:

Min 1Q Median 3Q Max

-0.9212 -0.2557 0.005603 0.1504 1.101

Coefficients:

Value Std. Error t value Pr(>|t|)

(Intercept) 8.9371 0.2039 43.8261 0.0000

log10(x2) -1.4915 0.0654 -22.8186 0.0000

Residual standard error: 0.4416 on 22 degrees of freedom

Multiple R-Squared: 0.9595

F-statistic: 520.7 on 1 and 22 degrees of freedom, the p-value is 1.11e-016

Correlation of Coefficients:

(Intercept)

log10(x2) -0.897

The Hurst Exponent,H is estimated from: (slope)+1=H, and the Fractal

Dimension,D is determined from: 2-H=D.

The slope is the log10(x2) value which was -1.4915.

The following graph plots all data points up to and including value "24".

It is expected that other data which is amenable to mst analysis can be quantified using the mass fractal dimension evaluated using 2-d WPA.