From: rthomson@dsd.es.com (Rich Thomson)
Newsgroups: comp.compression
Subject: Fractal compression
Date: 13 Aug 92 14:16:06 GMT
Reply-To: rthomson@dsd.es.com (Rich Thomson)
Organization: Design Systems Division, Evans & Sutherland, SLC, UT

[Rich Thomson <rthomson@dsd.es.com> sent me the following message
in answer to item 17 of the FAQ "What is the state of fractal compression?".
I thought it was interesting and Rich asked me to post it.
Jean-loup Gailly <jloup@chorus.fr> ]


At SIGGRAPH 1992, Barnsley was at a press conference held by the
publisher Jones & Bartlett.  They are publishing two new books by
Barnsley that give more concrete details of the method:

    The Fractal Transform,
    Michael F. Barnsley and Louisa F. Anson
    ISBN 0-86720-218-1, ca. 250 pp, $49.95

and
    Fractal Image Compression
    Michael F. Barnsley and Lyman P. Hurd
    ISBN 0-86720-457-5, ca. 250 pp., $49.95

the publisher can be reached at:

    Jones & Bartlett Publishers, Inc.
    One Exeter Plaza
    Boston, MA 02116
    (617) 859-3900
    FAX: (617) 859-7675
    kpeters@math.harvard.edu

Also, at this press conference Barnsley claimed to have patents filed
"worldwide" for their technology.

>from Tal Kubo <kubo@zariski.harvard.edu>:
>
>According to Barnsley's book 'Fractals Everywhere', this method is
>based on a measure of deviation between a given image and its
>approximation by an IFS code.  The Collage Theorem states that there is
>a convergent process to minimize this deviation.  Unfortunately,
>according to an article Barnsley wrote for BYTE a few years ago, this
>convergence was rather slow, about 100 hours on a Cray, unless assisted by
>a person.

Their performance has improved dramatically beyond what they were
talking about in BYTE a few years ago.  Human assistance to the
compression is no longer needed and the compression time is
reasonable, although the more time and compute power you throw at the
compression, the smaller the resulting file for the same level of
quality.

>Barnsley et al are not divulging any technical information beyond the
>meager bit in 'Fractals Everywhere'.

See above; now that they have obtained their patents they are talking
more about the method (since their 'competitive edge' is protected).

>There is reason to believe that Barnsley's company has
>*no algorithm* which takes a given reasonable image and achieves
>the compression ratios initially claimed for their fractal methods.

Barnsley may have pissed alot of people off because of the way he
presents (or doesn't) his work, but that doesn't mean that his method
is bogus.  It is quite reasonable and it works.

>Steve Tate <srt@duke.cs.duke.edu> confirms:
>
>Compression ratios (unzoomed) seem to range from 20:1 to 60:1...  The
>quality is considerably worse than wavelets or JPEG on most of the
>non-contrived images I have seen.

You need to supply a date for this observation because Iterated
Systems Inc. has 10 full-time mathematicians who do nothing but work
on making the fractal compression algorithms more efficient as well as
produce higher-quality images for a given file size.  I suspect that this
observation "quality is considerably worse" is quite dated by now.

>  A. Jacquin, 'Fractal image coding based on a theory of iterated
>    contractive image transformations', Visual Comm. and Image
>    Processing, vol SPIE-1360, 1990.

For people who are starving to find out what the method really is,
this is the best paper that explains the concept in a simple way.

The algorithm searches for 'affine redundancy' by searching for
transformations that map regions of pixels to a smaller region of
pixels in the source image.  The space of all possible transformations
is quite large for any given image, so that is why the process needed
human aid at first and also explains why smaller file sizes can be
found for a given quality level if more compute power/time is applied
to the search process.

Also, at the press conference Barnsley stated that Microsoft has
licensed the technology and will be supplying a CDROM with 16,000
compressed images on it.  He didn't mention what the original
resolution of the images was, but I suspect something common for PC
images like 640x480.

						-- Rich
-- 
	Repeal the personal income tax; vote Libertarian in 1992.
Disclaimer: I speak for myself, except as noted; Copyright 1992 Rich Thomson
UUCP: ...!uunet!dsd.es.com!rthomson			Rich Thomson
Internet: rthomson@dsd.es.com	IRC: _Rich_		PEXt Programmer
Newsgroups: comp.compression