| |
ISSN 1320-0682 | |||
| Volume 02 | April 1995 | |||
John E. Hutchinson
Department of Mathematics
School of Mathematical Sciences
Australian National University
Email: John.Hutchinson@anu.edu.au
Some of the underlying mathematics is explained in more detail, but still at an informal level, in [8]. Other general references at an elementary level are [4] and [12].
Examples of sets with scaling properties, and whose dimension is not an integer, have been known to mathematicians for a long time. However, it was Mandelbrot who introduced the term fractal and who developed the connections between these ideas and a range of phenomena in the physical, biological and engineering sciences (see [10]).
One point that sometimes causes confusion is the following. A "mathematical" fractal in a certain precise sense looks the same at all scales; when examined under a microscope at no matter what the magnification it will appear similar to the original object. On the other hand, a "physical" fractal will only display this "self-similarity" for a range of magnifications or scales. The mathematical object will be an accurate model only within this particular range.
To fix our ideas, let us begin with the following Brain fractal, Figure 1, which we call B.
The set B is self-similar in that it is
the union of two sets
and
, the left and right brains,
each of which is a scaled version of B (actually,
if we draw a vertical line
through the centre of B, a little of
is to the right of this line, and a
little of is to the left of this line). Thus, we can write
and
The scaling maps
and
can be thought of as maps which apply to the
entire plane, not just to the set B. Explicitly,
consists of an
anticlockwise rotation through
(that is,
radians)
about the point (-1,0), followed by a contraction centred at (-1,0)
with contraction ratio
(as a little calculation shows).
Similarly, consists of a
clockwise rotation through
about the point (1,0), followed by a contraction centred at (1,0)
with contraction ratio
. We see after a simple calculation that
We can regard
as a Scaling Law and we interpret (1)
as stating that the Brain B satisfies the scaling law
.
We can now give some important definitions, which can be best understood by referring to the examples which follow.
We remark that what we call here a Scaling Operator, is often called an Iterated Function System, c.f. [4].
Figure 2: Approximating the Koch curve
In this section, it is convenient to consider the following type of sets.
The "Brain" is compact, being both closed and bounded!
The following result from [7], which characterises certain types of "fractal sets", has turned out to be quite useful in image compression work.
Technical Remark The first two parts of the theorem can be proved either by explicit construction using an N-branching tree to code up the members of the resulting fractal, or by using the Contraction Mapping Principle for the Hausdorff metric on compact sets.
Examples
1. Thus, the Brain and the Koch Curve are the unique compact sets invariant under the respective Scaling Operators.
2. The convergence result of the above theorem is indicated in Figure 2.
3. The Open Set Condition corresponds to a sort of "minimal overlap condition" of the parts of
the associated fractal. This holds for the Koch curve, but not for the Brain. In each case, the
contraction ratios are 
, and in the case of the Koch
curve, this gives
where D is the dimension. Taking logs of both sides gives
It seems likely, that in the case of the Brain, the dimension has the same value.
From the point of view of image compression, the significance of Scaling Operators is that the information describing a complicated fractal set K can be "coded up", at least approximately, by a set of maps which can often be described by a finite set of parameters. An important problem is the Inverse Problem of finding a Scaling Operator which will, to some prescribed degree of accuracy, approximate a given image, or part thereof. A simple consequence of the Contraction Mapping proof of Theorem 1 is that if a compact set C can be approximated by scaled images of itself - that is, if
- then also
where K is the fractal generated by
and " 
" means "approximately equals". The degree of approximation can be
made precise and is usually measured in the Hausdorff metric. Barnsley calls this the
Collage Theorem, c.f. [3, 4, 8].
For purposes of image compression, and for a natural mathematical treatment, it is convenient to work with fractal measures rather than fractal sets. Whereas a set can be considered as either black ("in the set") or white ("not in the set"), a measure corresponds to an image with a grey scale. A set is a particular type of measure, where there are only two scales of grey, rather than a continuum of scales.
Another way to think of a measure is as a distribution of matter. Thus, one can imagine matter "uniformly" distributed along the Brain or the Koch Curve. More generally, one can imagine a highly non-uniform distribution of matter along the same underlying sets. The density of matter at a point corresponds to the scale of grey at the point. The total amount of matter is called the mass of the measure.
Corresponding to each measure, there is an underlying set called the support of the measure. The support can be thought of (loosely speaking) as the grey part of the plane (or space) given by the measure; that is, the set of points with at least some colouring. The support of the measures noted in the previous paragraph are just the Brain and the Koch Curve respectively.
It is convenient to restrict considerations to the following type of measures.
The requirement that the total mass be one is a normalisation requirement and amounts to a choice of units for mass. The second requirement is, in particular, satisfied if the support of the measure is bounded.
We have seen that a fractal set is self-similar in a manner which
is described by a set of contraction maps. A
fractal measure is self-similar in a manner which
is described by a set of dilation maps
together with a set of weights
satisfying certain extra conditions.
The following make this precise.
Analogous to the case of fractals sets, one has the following result [7], which can perhaps be best understood by considering the examples which follow.
Examples
1. In Figure 2 let v be a unit mass measure concentrated on the point +. Let
be unchanged, and choose
. Since
, it is easy to see that (5) and (6) are true. Then,
is a unit mass measure with 1/4 unit mass concentrated on each of the
four points 
. Similar remarks apply to
and
. The sequence
converges to a unit mass distributed "uniformly" along the Koch curve.
If in the previous example, the weights 
and
are taken to be unequal, then is still a unit mass measure, but the
masses of each will no longer be equal, and will in fact, be
(which is of course the same as
) and
. Similar remarks apply to other members of the sequence (7).
3. If the 
are all contraction maps, so each
‹ 1, then condition (6) follows from condition (5). However, in fact, it is only necessary
that one of the be a contraction map, in the sense that it is
then always possible to choose weights such that (5) and (6) are true.
For example, in Figure 3, we show a fractal measure generated by two dilation maps
where one of the dilation ratios is a little larger than one and the two weights
satisfy . the mass distribution is indicated by the density of the
points. What is shown is (as always) only an approximation and the actual fractal is unbounded,
although most of the mass does lie in the region shown.
* Remarks One of the problems with working with sets and the Hausdorff metric is the so-called problem of "outliers". Two sets may be close, or even coincide, except for a few points which are far apart. We think of such sets as being close, yet as measured by the Hausdorff metric, they are far apart. However, if we consider the sets as measures in an appropriate sense, then they will only differ on a samll amount of mass, and they will indeed be close in the Monge-Kantorovitch sense. Thus, using measures and the Monge-Kantorovitch metric, is often more natural, even when we are not interested in grey scales.
A related point is as follows. In Figure 3, the support of the fractal measure is an
unbounded but closed set satisfying the scaling law
. By working
with measures, we can thus analyse unbounded fractal sets in a natural setting.
There are also generalisations of the Monge-Kantorovitch metric that may prove useful in applications, see [13] and [9].
There are at least two other methods of obtaining fractal-like (deterministic) objects along the lines of Theorems 1 and 2, and which may have further applications. One can work with parameterised curves or surfaces in the uniform, and other, metrics, c.f. [7]. One can also use the notion of "flat distance" between curves or surfaces as in [7].
Figure 3: An unbounded fractal
Many objects occurring in nature can more realistically be described using the notion of a random, or non-deterministic, fractal. Such a fractal is a set or measure generated or selected according to a probability distribution. The self-similarity, strictly speaking, applies to the underlying probability distribution, rather than to a particular realisation of the random fractal.
Consider a Brownian particle, a microscopic particle in a fluid. The particle is buffeted by the molecules with which it comes in contact and it traces out an irregular path, called a Brownian path. The paths traced out between times t=0 and t=1, and between times t=1 and t=2 are, after rescaling, "statistically" similar to the path traced out between times t=0 and t=2. In a sense which can be made precise, a Brownian path is a realisaton of a random fractal set.
In Figure 4, we show three different realisations of a kind of random Koch curve. For each realisation K, we have
where 
and
are the "left" and "right" halves of K.
The sets and
look "statistically" like rescaled
versions of K. It is important to realise that, as in Figure 1,
the diagram is only an approximation. More precisely, each small straight line
segment should be replaced by a (different) scaled realisation of the random Koch curve,
and this process should be repeated at smaller and smaller scales.
Figure 4: Realisations of a random Koch curve
It again turns out to be more natural to work with (standard) random measures, rather than random sets. If, for example, we imagine a unit mass distributed uniformly along each of the three realisations shown, then we have three different realisations of a certain underlying probability distribution on measures. More generally, it is possible to have the masses themselves distributed in a random (but self-similar) manner along the shown curves.
We make this precise as follows. We consider random (standard) measures
which are
generated by a probability distribution
.
While all this may seem rather abstract, it gives in many instances a more natural model of physical reality than the notion of a deterministic fractal.
Once again, one has the following analogue of Theorems 1 and 2.
The above theorem, under the assumption that all the
are
contraction maps, was proved in [1], [5], [6] and [11],
under the extra condition that the
be all contraction maps,
but with the weaker assumption that
rather than 
. In [9] we give a very simple proof
of the first three parts using the contraction mapping principle.
* Remarks Figure 4 took 1.2 megabytes to store as a postscript file. But the probability
distribution 
required to generate the appropriate similitudes takes only a few
lines of code.
Consider now, the Inverse Problem of finding
, given one or more
realisations of the corresponding random fractal set. For a probability distribution on random
numbers (say), it is in fact impossible to gain much information about the underlying distribution
from one, or a small number, of realisations of the distribution. However, in the case of a random
self-similar set, the situation is much better. By taking small parts of a single realisation and
rescaling, we can obtain a large number of realisations. From these, it is, at least in principle,
possible to obtain a good approximation to the underlying distribution of the generating maps
.
Once one knows the underlying probability distribution, it is possible to generate realisations of the self-similar process. If one wants to store a good approximation to a particular realisation, it would be necessary to condition the process by various constraints.
It would not be simple to implement such a procedure (to solve the Inverse Problem) in an efficient manner, but it may be well worth exploring the possibility.
Fractals: A Mathematical Framework
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html jeh2frac.
The translation was initiated by Pam Milliken on Fri Dec 6 15:21:31 EST 1996Fri Dec 6 15:21:31 EST 1996
