



Fractal geometry is a relatively new field that
appears effective a describing the properties of many natural scenes. 

It has also been shown to have applications to
the compression of computer images. 




What are fractals 

Fractal landscape generation 

Iteratated functional systems 

Collages 

Indexing fractal mappings 




Pythagoreans believed that the universe was
number. General Platonist belief in the existence of ‘forms’ or ‘Ideas’,
perfect geometric entities that exist independently of material
embodiments. 

Suitable for describing planets, or crystals,
but classical geometry unable to deal with mountains or plants. 

Fractals can describe the shape of many
naturally occuring objects. 




Fractals supply the underlying geometry of much
of nature 

Fractals are self similar 

Selfsimilarity implies repeated patterns 

These can be used for compression 




Fractal  an object which is self similar at a
number of scales 

Contractive transform  a mapping such that
distances under some metric are shrunk 

Iterated functional system  a set of
contractive transforms applied to an image 




An example is a coast line 

A section of coast in a 20 miles view looks much
like a section in a 10 mile view. 

Its length depends upon the scale at which we
examine it. The small the scale we look at the more little wiggles there
are. It is not of dimension 1 like a line, but neither does it completely
fill an area. 

It has fractional dimension between 1 and 2. 




Given points a,b find midpoint m 

chose a point n at distance e from m 

call fline(a,n), fline(n,b) 

where e = d(a,b) k r 

and d measures distance, k a constant 

r a random number between 0..1 





Mandelbrot set image obtained by plotting the
escape time of the function 

z=z^{2} + y 

Escape defined by iterations till z >1 

Set defined on the complex plane, with x real
and y imaginary 

Generates infinite recursion of detail 




Large areas can be mapped to a similar smaller
area 

This may involve some rotation as well as
scaling 

A approximately mapped onto b by shrinking 




There exists a set of contractive mappings such
that each point in the image falls within the target area of at least one
such mapping. 




A collage can be constructed by making a
rectangular subdivision of the image and for each small rectangle finding a
big rectangle that approximates it. 

Thus small block B is approximated by big block A 






Convert image into description of a set of
contractive mappings. 

For each small square specify 

the coordinates of the doublesized square that
maps onto it 

any rotation required 

brightness and contrast adjustment 




Block A derived from B at 17,78 with mirror
imaging 

A can thus be encoded as 17,78M 




Patch a is derived from b, but b has more
contrast and is darker 

We can perform a contractive mapping in the
brightness space as follows 

p_{o} = p_{i}*c + k 

p_{o} is output pixel 

p_{i }input pixel 

c contrast adjustment <1 

k brightness shift 






For each square we send 

(x,y,m,r,c,k) 

x,y coords of big block, m for mirroring, r in
range 0..3 for rotation, c contrast,k brightness 

34 bits, for an 8x8 block containing 512 bits
originally 






Initially all blocks are uniform grey. 

Replace all blocks with their sources under
contractive mappings 

This gives a blocky image with blocks set to
brightnesses k. 

Iterate 

Each iteration fills in more detail 




As all mappings, both spatial and brightness are
contractive, each iteration produces a smaller change in the picture than
the last. 

After about 8 iterations the picture no longer
changes. 

This is the fixed point of the iterated function
series, and the final image. 




Fractals encode self similarity 

Collage theorem 

Contractive mappings 

Iteration to a fixed point 




“Fractals Everywhere”, by M. Barnsley 






What do you find difficult about this? 

Could you write a fractal
compressor/decompressor? 
