Xref: utzoo alt.fractals:195 comp.graphics:10866
Path: utzoo!attcan!uunet!brunix!cslab9a!cs001005
From: cs001005@cslab9a.cs.brown.edu (Thomas Colthurst)
Newsgroups: alt.fractals,comp.graphics
Subject: Re: How well does Barnsley's system perform?
Message-ID: <35038@brunix.UUCP>
Date: 4 Apr 90 15:16:49 GMT
References: <3166@usceast.UUCP> <11700@ttidca.TTI.COM>
Sender: news@brunix.UUCP
Reply-To: cs001005@cslab9a.cs.brown.edu (Thomas Colthurst)
Organization: Brown Computer Science Dept.
Lines: 45


     In the January 1988 issue of BYTE, Barnsley and Sloan ("A Better
Way to Compress Images", p. 215-223) claim 10,000 to 1 image compression
ratios.  Specifically, they claim that high-detail gray-scale aerial
photographs taking 130 megabytes can be compressed downto 13,000 bytes. 
They also show pictures of the Black Forest, a Bolivian girl, and the
Monterey coast that are encoded to 2000, 2000, and 100 bytes,
respectively, and were "based on photographs in recent issues of
National Geographic."  At SIGGRAPH '87, they showed a full sequence
video animation, A Cloud Study, which was "encoded at a ratio exceeding
1,000,000 to 1." A Cloud Study actually wasn't a pure IFS; it used IFS's
with time-varying parameters as detailed in "Blowing in the Wind:  The
Continuous Dependence of Fractals on Parameters" (Fractals Everywhere,
3.11, p. 111-117 ).
     The times required for these compressions is estimated as 100 hours
for complex color images on a Masscomp 5600 workstation (dual
68020-based systems).  Decoding takes 30 minutes.  Barnsley describes in
BYTE a custom hardware device prototype, called IFSIS, but gives no
performance characteristics.  The algorithm they use first breaks up the
image into segments using edge detection, spectrum analysis, color
separation, etc.  They then try to match these segments with a library
of fractals.  I have yet to find a detail description of how this is
done, but Discover March 1989 ("Fractals in Your Future", pg. 26-27)
shows computer screen photos of the process.  A non-automatic (requires
user to do the collage) program called Collage is described in Fractals
Everywhere (9.8, pg. 377-380).  If anyone can find a more exact
description of the automatic compression algorithm, I would love to hear
about it, as I am currently working on an evolutionary algorithm for IFS
image compression.
     A few details on the properties of IFS and IFS compressed images: 
The size of the IFS increases at most linearly with increasing detail. 
This is on of the main results of the Collage Theorem (see "Solution of
an inverse problem for fractals and other sets" by Barnsley, et al., in
Proc. Natl. Acad. Sci. USA, Vol. 83, pp. 1975-77, Apr. 1986 ).  One of
the nice things about IFSs is that they aren't just for fractals:  IFS
codes for polygons, for instance, are also very easy to construct.  As
for real world images, the examples above sound very impressive, but the
algorithm used for compression has a large influence on the ratio
acheived (i.e., I'm not completely sure that the above images weren't
hand compressed, which would give them an advantage over machine
compressed ratios).  Again, if anyone has details about the performance
of an automatic IFS compression algorithm, I would appreciate hearing
about them.

-Thomas C