AN ALGORITHM FOR THE ANALYSIS OF FRACTAL-LIKE STRUCTURES AND MISCELLANEOUS APPLICATIONS

AN ALGORITHM FOR THE ANALYSIS OF FRACTAL-LIKE STRUCTURES AND MISCELLANEOUS APPLICATIONS

Abstract: In this paper we first introduce some new algorithms, most of them based on Box Counting methods and variations for 2D and 3D structures. To every image we associate a map which contains the essential information on the local fractal dimensions. We process a large variety of images , including landscapes, city areas, transport networks, medical images. In all these cases the associated map will reveal modified structures which do not fit in the general context. The conclusion is that the proposed algorithms can be used to find modified areas in the fractal-like structures. Applications can be found in military, medical, transport and civil domains.

Keywords: local fractal dimension, box counting method

INTRODUCTION

We give a brief introduction on what is usually known as Hausdorff dimension of a set embedded in the n-dimensional Euclidian space ([4])

Let and let be the Euclidian distance. The diameter of a subset is defined by . Let and let be an open cover of it. For every positive numbers and we define

is an open cover of

The -dimensional Hausdorff measure of is . It can be proved that there is a number such that if and if . The number is the Hausdorff dimension of and it can be zero, infinite or a a positive real number. We have also

.

We give in the following some basic properties of the Hausdorff dimension:

If then .

If then .

If is a countable set then .

If then is totally disconnected.

One of the most efficient algorithm to compute the Fractal Dimension is the Box Counting algorithm. [1,2,4] Let us consider a picture (structure). We cover the structure with a number of square boxes of size s. We count the number of the boxes which contain some part of the structure and let N(s) be this number. Clearly, if we increase the number of boxes or, equivalently, we decrease s to p, we obtain N(p). After this we make a diagram, on the Ox-axis we measure log(s) and on Oy-axis we measure log(N(s)). In this way we obtain several points for different values of s. The Box Counting Dimension of the structures is defined as the slope of the regression line defined by the points on the diagram. The Box Counting Dimension is a good approximation of the Hausdorff Dimension (Fractal Dimension).

THE ALGORITHMS

The usual Box Counting - type algorithms can be applied only to binary (black/white) images. In order to save the information we developped an extended Box Counting like algorithm version which can be apply directly on gray-levels images. The basic idea associate to every pixel a weight proportional its gray level. In this way we obtain a 3D-object on which we applied a 3D Box Counting algorithm and we obtain an approximation of the Fractal Dimension (a number between 0 and 3). We call this number the Weighted Fractal Dimension (WFD). [2]

Let A be a pixel on an image and let K be a neighbourhood of A. By using the 3D-Box-Counting Algorithm we compute the WFD of K. We repeat the process for every pixel in the image. In this way we obtain a matrix with inputs the WFD of every pixel respectively. We associate to every pixel a color acording to its WFD (The association between the WFD and the color is conventional and is a part of the algorithm). Finally, we generate a new image containing the level lines of the WFDs. We call this new image the Weighted Fractal Dimension Map (WFDM).

Example: We apply the above algorithms to the Mandelbrot set.

Mandelbrot set Spatial object associated WFDM of Mandelbrot set

to Mandelbrot set

APPLICATIONS

3.1. The analysis of medical images

The above algorithms can be used to analyze CT and MR medical images [2] in order to discover modified parts of human tissues. The WFDM shows the areas which require a further investigation. We present below some MR images of human brain and the associated WFDMs.

In the following example the algorithms reveal a very small modified area in a MR brain image.

Are these two images identical ? If not which one is modified ? 

The associated WFDM reveals a modified area on the right image

Zoom on the initial images

In the next example we apply a binary filter on the WFDM of a MR brain image to reveal the asymmetry of the tissue.

3.2. The analysis of military satellite images

In this section we apply the algorithms to analyze military satellite images to reveal military camps and military technique.

In the first example the associated WFDM of the Saudi Arabia King Khalid Military CY reveals (after a binary filer) military facilities in a desert landscape. [5]

In the second example we process satellite images of the Darunta military camp [6]

 

 

 

The associated WFDMs of the images strongly reveal the military objectives which are not obvious on the initial satellite picture.

The third example we have the images of a helicopter and of a soldier. On the initial images the two objectives are well hidden, but they become obvious on the WFDMs.

 

 

CONCLUSIONS

The Weighted Fractal Dimension Map method can be applied to a large variety of images and reveals details, modified areas, objects which do not fit in the background. The most important gain of this method is the possibility to use it to develop real-time automatic search and classification systems.

5. REFERENCES

1. P. Cristea, An Efficient Algorithm For Measuring Fractal Dimension Of Complex Sequences, Proceedings of IAFA2003, Bucharest, Romania, May 2003, p. 121-124.

2. Rodica Dragomir, M. Olteanu, M. Tanase, The Analysis Of CT and MR Brain Images using Box Counting Type Methods, Proceedings of IAFA2003, Bucharest, Romania, May 2003, p. 267-272.

3. B. Mandelbrot, The Fractal Geometry of Nature, Academic Press, 1975, New York.

4. H-O Peitgen, H. Jurgens, D. Saupe, Chaos and Fractals. New Frontiers of Science, Springer, 1992.

https://www.redtailcanyon.com/items/6165.aspx

https://www.globalsecurity.org/military/world/afghanistan/darunta.htm