Fractal Compression

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

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,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