|
|
|
|
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=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 |
|
|
|
|
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 |
|
po = pi*c + k |
|
po is output pixel |
|
pi 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? |
|