Fractal Compression

Paul Cockshott

faraday

Introduction

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

Collages

Indexing fractal mappings

Overview

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.

Connections

Fractals supply the underlying geometry of much of nature

Fractals are self similar

Selfsimilarity implies repeated patterns

These can be used for compression

Vocabulary

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

Diagram

a

Mandelbrot set

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

z=z² + 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

p_o = p_i*c + k

p_o is output pixel

p_iinput pixel

c contrast adjustment <1

k brightness shift

Final encoding

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

Decoding

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

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.

Summary

Fractals encode self similarity

Collage theorem

Contractive mappings

Iteration to a fixed point

Where to get more information

“Fractals Everywhere”, by M. Barnsley

Feedback

What do you find difficult about this?

Could you write a fractal compressor/decompressor?


	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² + 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 double-sized 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_iinput 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


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