Fractal Compression
Paul Cockshott

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.

Summary of Lecture
What are fractals
Fractal landscape generation
Iteratated functional systems
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

Fractals of dimension 1 to 2
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.

Creating a fractal line- fline(a,b)
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
Mandelbrot set image obtained by plotting the escape time of the function
z=z2 + 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

Contractive mappings
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

Collage Theorem
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.

Constructing collage
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

The fractal transform
Convert image into description of a set of contractive mappings.
For each small square specify
the coordinates of the double-sized square that maps onto it
any rotation required
brightness and contrast adjustment

Coordinates of source
Block A derived from B at 17,78 with mirror imaging
A can thus be encoded as 17,78M

Brightness and contrast
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
po = pi*c + k
po is output pixel
pi input pixel
c contrast adjustment <1
k brightness shift

Final encoding
For each square we send
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.
Each iteration fills in more detail

Fixed point
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

Where to get more information
“Fractals Everywhere”, by M. Barnsley

What do you find difficult about this?
Could you write a fractal compressor/decompressor?