I’m studying for a Digital Video Coding and Compression exam, and just wanted to share the coolness that is fractal coding.
Fractals are geometric objects which are said to have infinite complexity, and are often self-similar (that is, a small portion of the fractal is the same as the whole fractal). Iterated Function Systems (IFS) are one kind of fractal. An example is the Sierpinski gasket. Zoom into any of the sub-triangles, and they look just like the original.
It’s formed by making three ‘copies’ of an original image (it doesn’t matter what the image is), and placing them in the shape of a triangle; one above, one bottom-left, one bottom-right. Repeat an infinite number of times:
The same process, with an altered replication pattern, can be applied to form other shapes, such as a fern leaf (which uses 4 copies of the previous iteration’s image: One thin one for the stem, two rotated shrunk ones for the fronds coming off the sides, and one for the rest of the fern). Such patterns are often observed in nature, which makes fractals particularly interesting.
Fractal image coding applies a similar concept. Parts of the image are used to build up other parts (imagine an image of a tree; A bit of a branch is copied and shrunk, to form the image of a smaller branch coming off the first one). This process of searching for similar parts within the image, and using them to form the current part, is repeated over the whole image.
To reconstruct the image, the same process as generating the Sierpinski gasket is used: Bits of the starting pattern (which, amazingly, can be anything) are copied, scaled, coloured and rotated, as instructed by the encoding process. The whole process is repeated until the image is built:
Oh, it’s such black magic.
Unfortunately, the whole process is incredibly slow, because so much searching is required during the encoding process (Looking for that branch part that looks like the current part of the image being encoded). It also doesn’t quite give enough performance to make the extra work worthwhile. Still, it definitely performs well in some circumstances; maybe it will make a comeback when we have faster computers.
NB. Most of the images are nicked shamelessly from Dr. Tim Ferguson’s lecture notes on fractal coding, from CSE5302. Also, for further reading, Mirsad suggested this paper: A Review of the Fractal Image Coding Literature, by Brendt Wohlberg and Gehard de Jager.
Actually, I think the more interesting application of fractal compression is audio, which is inherently more repetitive than imagery.
Interesting concept.. I didn’t look for long, but I found one paper that explored the idea:
“Fractal Wavelet Compression of Audio Signals”, Wannamaker, R. and Vrscay, E., ftp://links.uwaterloo.ca/pub/Fractals/Papers/Waterloo/wavr97.ps.gz
Apparently, fractal methods alone do not give adequate performance, but when combined with wavelet techniques, they got 6:1 compression with good signal reconstruction, without exploiting psychoacoustic redundancy – Apparently quite competitive, compared with current methods, and with room for improvement.
Ewww, postscript. Why can’t unix users get with the 1990s and jump to PDF?
Eh, yeah I know. There’s probably a PDF there somewhere, I just clicked on the first version I could find.
Yes but how did the exam go??
WOW eye’V always hada fascination for fractals & light & dark & & & … but eye’m still not sure what it all means :p
… you apparently do, gee that’s prolly a very good thing
and good luck with all your thes’Is werkings !!!
eye so relate to what your mum is saying lol
cheers
ash :)