Blog

Fractal image coding

I’m studying for a Digital Video Coding and Compression exam, and just wanted to share the coolness that is fractal coding.

Sierpinski GasketFractals 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.

. Bookmark the permalink. Both comments and trackbacks are currently closed.

6 Comments

  1. Posted October 20, 2005 at 3:55 am | Permalink

    Actually, I think the more interesting application of fractal compression is audio, which is inherently more repetitive than imagery.

  2. Posted October 20, 2005 at 4:29 am | Permalink

    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.

  3. Posted October 20, 2005 at 7:15 am | Permalink

    Ewww, postscript. Why can’t unix users get with the 1990s and jump to PDF?

  4. Posted October 20, 2005 at 7:53 am | Permalink

    Eh, yeah I know. There’s probably a PDF there somewhere, I just clicked on the first version I could find.

  5. Mike's Mum
    Posted October 22, 2005 at 1:19 am | Permalink

    Yes but how did the exam go??

  6. Posted November 1, 2005 at 7:58 pm | Permalink

    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 :)