Path: utzoo!mnetor!uunet!portal!cup.portal.com!doug-merritt
From: doug-merritt@cup.portal.com
Newsgroups: comp.graphics
Subject: Re: Fractals!
Message-ID: <4901@cup.portal.com>
Date: 28 Apr 88 19:26:16 GMT
References: <811@unioncs.UUCP> <1776@uhccux.UUCP> <5595@pyr.gatech.EDU> <931@stracs.cs.strath.ac.uk>
Organization: The Portal System (TM)
Lines: 83
XPortal-User-Id: 1.1001.4407


To answer a recent question about IFS encoding achieving a 1:10000
compression ratio of images. Yes, it's true. Although it has its
problems.

The basic idea is this: fractals have been used to generate realistic
looking images of certain (many) kinds of things. It turns out that
practically any image of any of those types of objects can be IFS
encoded, loosely speaking. The BYTE article showed a very nice b/w
fern, for example. One of the areas that IFS is particularly *bad*
at is human faces (perspective 3d views of same), because it's not
clear yet how to decompose any face into a fractally self similar
representation (this point appeared in the Scientific American
"Science and the Citizen" news column; I'm not 100% clear on why
this is true, given the Collage theorem discussed below).

In more detail: say you have an image of a black square. It is self
similar: you can create the whole image from four smaller squares,
each of which can be created from ...(etc)

The IFS *decompression* method uses affine transformations in the
plane (affine == polynomial of degree 1 or a 2x2 matrix). For the
example of a square, its encoding consists of a set of affine
transformations that can be used to map any point in the set to any
other point in the set.

Any corner point of the square can be mapped via one or more rotations
to any of the other corner points. It can also be rotated and
"shrunk" to map to a corner point of one of the 4 sub-squares. Similar
mappings apply to the interior of the square.

So you figure out one of the complete self-mapping sets of affine
transformations (it's non-unique), and starting from the origin, apply
all possible transformations to end up with new points inside the
set. Then apply all transformations to each of those new points...
continue infinitely, and you'll have generated all of the points in
the set.

In practice this is too time consuming, and so at each step, just
one of the possible transformations is chosen at random, so that you
keep mapping a single old point to a single new point. I should have
been more careful before, because I missed something important:
you want all of the transformations to contract the figure (I forget
the proper word for this). That way, after a certain number of
iterations, the sub-figures you're generating will be smaller than
a pixel. At which point you repeat, to follow a new probablistic
trajectory through the possible points. After not too many passes,
you'll have generated enough random points within the figure that
it becomes discernable. Eventually you'll have done enough points that
you've drawn essentially 100% of those that are displayable with
any given resolution.

So it looks like the figure is being drawn via a "dissolve", with
random points gradually filling in.

It's a little nonintuitive at first but some thought experiments
help.

The hard part is the *compression* phase where you figure out the
appropriate affine transformations to start with. The author of
the BYTE article has an enormous library of appropriate IFS codes
for various types of objects/features done as part of a sizeable
research project.

The original image is analyzed 7 ways from Sunday (edge detection,
2D FFT, etc, etc), and the subfeatures that are found this way are
looked up in the IFS code library. So for *him* I guess it's relatively
easy, but very time consuming due to the amount of analysis.

The crux of the method is based on something called the Collage Theorem,
which basically means that it's been proved that the method will be
guaranteed to work if you approach it the right way. Even though the
reconstruction process is statistical, the Collage Theorem says that
you can recreate the original to within any desired degree of accuracy
(in terms of pixel resolution and color reproduction, say). THe name
comes from the idea of taking an image and breaking it apart into
affinely distorted subimages. It turns out that it's *always* theoretically
possible to do this.

See the Byte article itself if you want more details.

      Doug Merritt        ucbvax!sun.com!cup.portal.com!doug-merritt
                      or  ucbvax!eris!doug (doug@eris.berkeley.edu)
                      or  ucbvax!unisoft!certes!doug