Fractals and their applications

Fractal definition

In mathematics, fractals are special subsets of Euclidean space that have a complex, often self-similar structure. Unlike ordinary shapes, the outlines of which degenerate into fragments of a straight line with sufficient zooming, fractals retain their complex structure at any scale.

Also, the accepted metrics of space are not always suitable for fractals: 1 for straight lines, 2 for planes, 3 for volumetric space. Some fractals occupy an intermediate position between spaces. For example, a polygonal chain, each fragment of which is the same polygonal chain, contains an infinite number of links, that is, it cannot be described as a sum of straight lines, at the same time it cannot yet be called a two-dimensional shape with an area because its second metric is incomplete.

Unusual properties of fractals, or rather their complex internal dependencies, are used in mathematics, physics, information processing — compression algorithms and steganography. In addition, fractals have found application in art as their non-trivial structure is highly aesthetic.

Generation of fractals

Fractals retain their complex structure at any scale, i.e. they can be infinitely zoomed in and detailed. The space of the real world has limitations, some basic indivisible values: pixels for display on the monitor, atoms and smaller elementary particles for the physical world, or, if we go further, values comparable to Planck length 10^(-35), at which modern physical theories stop working. Hence, we can conclude that generating true fractals with an infinitely complex structure is impossible in real world. Any visualization of fractals is done with a certain degree of accuracy.

Fractals have an inhomogeneous and unpredictable structure. Therefore, to generate an image of a detailed fractal, it is necessary to calculate values of functions describing it, in a huge number of points — thousands, millions and more. This explains the fact that active research of fractals began in the second half of the 20th century, when computers capable of such calculations appeared.

There are different types of fractals and approaches to their generating. We will consider two popular approaches — iterated function systems and an escape-time algorithm.

Iterated function systems

Fractals are closely related to iterated function systems, which are often used for analytical representation and graphing. One of the types of iteration functions are affine transformations.

Iterated function systems are related to the concept of contraction mapping. Its essence: after applying a contraction map to a set of points, the distance between any two points does not increase, that is,

, where d is the distance between points; x, y — points; f -contractive mapping.

There are two subtypes of fractals generated by iterated function systems:

1. Fractals formed from geometric shapes, fragments of which are iteratively replaced with similar shapes of a smaller size. These include Sierpiński triangle, Koch snowflake, Menger sponge, etc. (Fig. 1–3)

Figure 1 — Sierpiński triangle | Figure 2 — Koch snowflake

Figure 3 — Menger sponge

2. Fractals made by points corresponding to the values of functions. Most often, such fractals are made on a plane, and the following system of functions is used to set the fractal

All functions f must be contraction maps. An initial point is selected and the functions described by the system are iteratively applied to it, with each function being used with a preset probability pi. All values obtained are marked on the coordinate plane, forming a fractal.

Barnsley fern

Barnsley fern is one of the most famous fractals described by a system of equations. Its author — Michael Barnsley — is one of the most famous researchers of properties of fractals. He also suggested using some properties of fractals to compress information, in particular, images. This approach is discussed in the following sections in detail.

Barnsley investigated the fractal properties that occur in nature, especially in plants. For example, fern leaves have a fractal structure. Barnsley found a system of iterated functions that allow generating such a fern.

This system is represented in the following way (coefficients may differ slightly in different sources):

Which generates the following fractal (Fig. 4):

Figure 4 — Barnsley fern

The image shows that the branches of fern are smaller copies of the entire fern.

Escape time algorithm

The escape time algorithm and the fractals generated by it are closely related to the concept of a recurrence relation. Recurrence relation is represented by formula

, i.e. the next elements of the sequence are calculated based on the previous. Recurrence relations are a special case of recursive functions — when the solution to a problem depends on the solution of the same problem for other input data. Such algorithms can be executed only if there are such input data, the solution of the problem for which is possible without another recursion. In case with recurrence relation this means that to calculate the sequence, function F and k of the first members of sequence must be known

, based on which

can be calculated, etc.

The escape time algorithm allows visualizing the behavior of the series given by the recurrent formula. It is usually used for functions of a complex variable and sequences of the type

Although in the general case, the “depth” of the recurrent connection is not limited.

The essence of the escape time algorithm is as follows:

1) A fragment of the coordinate plane is assigned to the image, with each pixel corresponding to a point on it.

2) For each point (this can be the initial value of sequence or one of parameters of the function), it is determined whether the corresponding sequence exhibits some property in a finite number of n steps.

3) Pixels are colored according to the revealed properties.

The accuracy of fractal generating depends on the number of n iterations, since the desired property can manifest itself both on the first and on a millionth or more of its elements. For small n, the graph will display an approximate view of the fractal; the boundaries are detailed with an increase in n.

The escape time algorithm has two variations:

• Two-color (each pixel is colored in one of two colors, depending on whether the property was detected or not);
• Multicolor (each pixel is colored in one of several colors, depending not only on the fact of detecting a property, but also in how many steps the property was found).

The most famous escape time fractals are Mandelbrot and Julia fractals. The property that forms fractals is the behavior of a recurrent series with

, the following cases are possible:

1. Elements of the series tend to a specific value (attractor)

2. Elements of the series loop around multiple values

3. Elements of the series tend to infinity

4. The behavior is chaotic and does not fit the described cases.

Usually, points are divided according to whether the corresponding series retains a finite value (case 1–2) or goes to infinity (case 3).

Mandelbrot fractal

Mandelbrot fractals are a visualization of Mandelbrot set — a set of complex numbers c for which the series corresponding to the recurrence relation

does not tend to infinity with the initial value

The set was discovered by Fatou at the beginning of the 20th century, then it was studied and visualized by Mandelbrot already in the 70s, when sufficiently powerful computers became available. Figure 5 shows a classic Mandelbrot fractal, Figure 6 is a zoomed copy of one of its fragments. All fractals were generated using [2].

Figure 5 — Mandelbrot fractal | Figure 6 — Mandelbrot fractal zoomed

The function

is considered the most canonical for Mandelbrot set, however, in this way it is possible to make a fractal for any function of a complex variable. In this case, the most difficult task is to determine the condition that the series generated by the function tends to infinity; for the canonical Mandelbrot set, the proof is the appearance in the series of the element

However, this condition may differ for functions of a different nature.

Figures 7–9 depict the so-called Multibrot fractals, their Mandelbrot sets are given by a function

, where k is a positive integer.

Figure 7 — Mandelbrot-3 fractal | Figure 8 — Mandelbrot-3 fractal zoomed

Figure 9 — Mandelbort-5 fractal | Figure 10 — Carlson fractal

Julia Fractals

Julia fractals correspond to Julia sets which are closely related to Mandelbrot sets. In the case of Mandelbrot set, analyzed points are used as a parameter of function F(z), and the series begins with the value

In the case of Julia the parameters F(z) are fixed, and the point under study c is the beginning of the series

This difference leads to the emergence of fractals of a completely different kind. In fact, Julia set is only a border between areas with different behavior (series generated by elements of some areas have a finite limit, while series generated by elements of others — infinite), in the context of fractals, they usually speak of a filled Julia set, which includes areas with stable behavior.

The classical Julia set, similarly to the Mandelbrot set, corresponds to the formula

, and if С1 belongs to Mandelbrot set, then Julia set will be connected. Mandelbrot set is the domain of definition of Julia set. The most “exotic” fractals occur when С1 lies on the boundary of Mandelbrot set (Fig. 11–12).

Figure 11 — Julia fractal, c belongs to Mandelbrot set | Figure 12 — Julia fractal, c lies on border

As in the case of Mandelbrot, Julia fractals are also not limited by the formula

and can be generated for an arbitrary function (Fig. 13–14).

Figure 13 — Julia-3 fractal | Figure 14 — Julia-11 fractal

Mandelbrot and Julia fractals use two fundamentally different approaches to constructing the series under study, first determine the parameter of the function at a fixed initial value, others determine the initial value at a fixed parameter. No less interesting are multidimensional fractals corresponding to functions with several parameters, but their visualization is difficult.

Fractal Compression

There is a number of algorithms, the so-called fractal image compression, which is not directly related to the mathematical concept of a fractal, but deal exclusively with the similarity of image areas. These algorithms are closely related to systems of iteration functions and the concept of a fixed point. Point x is fixed for function f if

Algorithms of this family are used to compress images in grayscale; to compress a color image, it is necessary to separately compress each of its color channels.

The main idea of fractal compression algorithms is to present an image in the form of a system of equations describing the relationship between its fragments. In addition, each fragment of the image is described by an affine transformation over another fragment of the image.

The image is divided into range and domain blocks. As a rule, range blocks are half the size of domain blocks, for example, range blocks are 8x8 pixels and domain blocks are 16x16. Range blocks do not overlap and completely cover the image. Domain blocks can overlap and include fragments of several range blocks.

Domain blocks are compressed to the size of range blocks by simply averaging neighboring pixels, and they form a code book. Then, for each range block we need to find a domain block which can be transformed to the original block using a simple affine transformation.

As a rule, blocks are represented as vectors and use a fairly simple transformation of the following type:

, where

R — range block;

D — compressed domain block;

1 — unit vector equal in length to the range block;

s — scale;

o — offset.

It is often impossible to find a domain block, transformation over which will allow you to accurately restore the range block. Therefore, the block is chosen that gives the best approximation, i.e. such

, at which the reconstruction error will be minimal

Imperfection of mapping, as well as limited accuracy of representation of s and o, lead to compression losses.

For any D, R pair it is easy to calculate the optimal values of s and o, but finding the optimal D remains a nontrivial problem. In the first versions of the algorithm, the search was performed with a simple brute-force search, which was very inefficient. There are numerous approaches that allow you to optimize the search, some of them will be discussed below.

As a result, each range block Ri corresponds to three values — (o, s, k), where k is the number of the selected domain block in the code book (in fact, its coordinates in the image). The compressed image is an array of triplets of coefficients.

The decoder knows the relations between the blocks of the image, but not the blocks themselves, it also knows code book formation rules, but not the book itself. Therefore, it is very important that the coefficients k determine the position of the domain block in the image, and not in the code book, which can be sorted to optimize the search.

Image recovery algorithm:

1. An arbitrary Img image is selected that coincides in size with the original (it can be monochrome, structured or noise — this does not affect the result).
2. The image is divided into range and domain blocks similar to the compression algorithm.
3. A code book is built from domain blocks.
4. The range blocks of the image are replaced with the corresponding k blocks from the code book, transformed using s and o.
5. Steps 3–4 are repeated until the image stops changing. This will mean that a fixed point has been reached and an image has been found that corresponds to the system of equations.

Recovery usually takes about 10 iterations. Such an unusual decompression process, starting from an arbitrary state of the system and leading to the same result, is possible due to the fact that used transformations map large fragments to smaller ones. At the same time, each iteration changes not only the range blocks, making them more similar to the original image, but also the domain blocks they are included in, such a complex connection of the entire image allows each iteration of the algorithm to bring it closer to the original.

The main disadvantage of fractal compression algorithms is the computationally complex search for optimal domain blocks. The easiest way to speed up a search is to look for a block that gives not the best possible accuracy, but sufficient accuracy, i.e. if an acceptable block was found, the search stops. Many approaches have been developed for both search optimization and to reduce compression loss. Summary of such approaches is presented below.

1. Expansion of the code book due to greater overlap of domain blocks, including rotations and reflections of domain blocks.
2. Use of multiple orthogonal feature vectors and corresponding o coefficients instead of one.
3. Dynamic resizing of blocks — first a match is found for large blocks, if the required accuracy is not achieved, the block is split. In this case, not only square blocks can be used, but also rectangular or polygonal blocks.
4. Using search trees.
5. Using different classification methods.
6. Split and merge approach — range blocks with similar properties are combined into groups, which simplifies further analysis. Not only square, but also rectangular and triangular blocks can be used.
7. Start searching for a suitable domain near the range block.

The ideas behind fractal image compression are very different from other popular approaches. A number of fractal compression algorithms were patented, which prevented its widespread adoption.

Fractal Watermarking

Steganography deals with the problem of hiding one piece of information (stegomessage) inside another (container). Fractal compression principles are also used in steganography, including digital watermarking.

The image is divided into two disjoint areas — R and D. Area R is divided into range blocks, area D — into domain blocks. A code book is compiled from domain blocks, which is then divided into two disjoint halves D0, D1. In the simplest case, D0 and D1 can be built from non-overlapping image fragments, for example, D0 from the upper left quarter, and D1 from the lower right. It is very important that D0 and D1 do not contain the same blocks.

Data will be embedded into range blocks, one bit per block. When information is embedded, the range block is replaced with a transformed domain block taken from D0 or D1 depending on the embedded bit. The coefficients o and s are used for embedding, but are not transmitted. To find the optimal domain block, the same methods can be used as in fractal compression. However, using not the best, but only an acceptable block of the domain block, is unsafe, because steganogram may not be correctly extracted.

When extracting a stegomessage, the image is divided into areas in the same way as during embedding, a code book is built and divided into two parts. Then, for each range block, an optimal domain block is searched for (if the container was not distorted, then the range block can be obtained from domain block without loss), if the found block belongs to D0, then a zero bit is extracted, if it belongs to D1, the hidden bit is 1.

Fractal watermarking algorithms should solve both the problems relevant to fractal compression — search optimization and distortion reduction, and a new one — construction of D0 and D1 code books. On the one hand, both should contain a variety of domain blocks that allow displaying range blocks with minimal distortion, regardless of the embedded message; on the other hand, both books should not contain completely identical, and in some cases, very similar blocks, which will make extraction impossible.

Study of dependence of Julia fractal shape on parameters

The classic Julia fractal is represented by the formula

and is actually determined by c parameter, while fractals with close c values have a similar shape. Partly an exception is the values of c located on the boundary of Mandelbrot set, for which even a slight change leads to noticeable changes in Julia fractals.

We have experimentally investigated the changes that emerge in the appearance of Julia fractals when the parameter c changes. For this, using the program [2], a large sample of Julia fractals (about 15 thousand) was generated, c changed with a step of 0.01 in the ranges shown in Table 1.

Table 1. Ranges of used parameters of Julia fractals

Selected areas almost completely cover Mandelbrot set.

Display area vertically [-1.5; 1.5], horizontally [-1; 1], this is enough to display Julia set (Fig. 15).

Figure 15. — Examples of fractals used

Fractals were presented in two-color black and white (gray compression artifacts were ignored), image size 200x200 pixels.

The analysis was carried out as follows:

1. each pair of fractals was assigned the value

— the distance between their parameters on the complex plane;

2. The percentage of pixels that differ in these fractals was calculated;

3. The average percentage for each distance was calculated.

The results are presented in the graph (Fig. 16).

Figure 16 — Dependence of changes in Julia fractals on the distance between c parameters

The graph shows that for distance (0; 0.6] the dependence is close to linear, then sharp variations begin, and after 1 there is a drop. This is due to the fact that Mandelbrot set is rather small and with increasing distance

number of pairs of connected Julia fractals decreases.

The image covers an area larger than any of the generated fractals, and some areas along the edges of the image remain unchanged (their points do not belong to any of the studied sets), this distorts the measurement results. To eliminate this effect, we defined the area of the image in which all the generated fractals lie (Fig. 17) and in which, accordingly, all changes take place.

Figure 17 — Changing area of Julia fractals

It makes up about 60% of the image area. Taking this fact into account, the dependence of distortions on distance is shown in Fig. 18.

Figure 18 — Dependence of changes in Julia fractals on the distance between c parameters in view of unchangeable areas

We also analyzed how often Julia set for different c include points of the plane under consideration. The results are shown in Fig. 19. The darker the pixel, the more often it enters Julia set. Obviously, points with coordinates close to zero are more often included in Julia set. Also, the frequency of occurrence changes gradually without sharp variations.

Figure 19 — Frequency of belonging of points of the plane to Julia sets

Bottom line

Fractals are significantly different from “simple” shapes because of their infinitely complex and often unpredictable structure. They are used in both science and art. One of the main tools for studying fractals is computer visualization thereof. The mathematical properties of fractals have found application in information processing — in image compression and steganography.

Fractals have widely different forms, determined by coefficients of formulas by which they are defined. We are considering the possibility of using fractals in steganography and cryptography as secret system keys. Experiments have shown that the shape of Julia fractals changes smoothly enough when c parameter changes without sharp variations. That is, the fractal image can be approximately reconstructed if approximate coefficients are known. In the future, we plan to investigate in practice the possibility of application of fractal images in various fields.

References

1. Michael F. Barnsley, Hawley Rising. Fractals Everywhere.
2. https://github.com/mbilotta/julia
3. Dietmar Saupe, Raouf Hamzaoui, Hannes Hartenstein. Fractal Image Compression An Introductory Overview. 1999.
4. Sanaz Shahraeini, Mahdi Yaghoobi, Mahdi Yaghoobi. A New Approach in Digital Image Watermarking Using Fractal Model in DWT Domain. 2011.