Path: utzoo!attcan!uunet!kddlab!ccut!tansei!b39756
From: b39756@tansei.cc.u-tokyo.JUNET (Martin J. Duerst)
Newsgroups: comp.graphics
Subject: Re: Fractal Compression
Keywords: Economic aspects, trade offs
Message-ID: <1947@tansei.cc.u-tokyo.JUNET>
Date: 19 May 88 03:37:14 GMT
References: <686@thalia.rice.edu> <5546@cup.portal.com>
Reply-To: b39756@tansei.cc.u-tokyo.JUNET (Martin J. Duerst)
Organization: Dept. of Inf. Sc., Faculty of Sc., University of Tokyo, Japan.
Lines: 55

In article <5546@cup.portal.com> doug-merritt@cup.portal.com writes:
>Eric Salituro writes (wrt IFS image compression):
>>I fail to see what the hoopla over fractal-based image compression is all
>>about. In the last two weeks, I've read a couple of breathless articles
>>proclaiming 1000 to 1 reduction but all I've seen as evidence are a couple
>>of low-res pictures.  [...]
>
>Compression ratios of *10,000* to 1 aren't all that unusual. The "close
>approximation" can be made as close as is desired (e.g. exactly the same
>as the original image, within the parameters of your display device). This
>latter fact has in fact been proven mathematically (see "the Collage
>Theorem"), which is why people are somewhat excited about it. If some
>imprecision is tolerable then you can speed up the decoding somewhat.
    There are two aspects of exactness involved here. The first is how
exactly the decoded image conforms to the abstract picture described by
the IFS coefficients. This depends on the time you use for decoding
(number of random iterations). The second (and bigger) problem is how
exactly the IFS coefficients describe the original picture. As a hard fact,
with e.g. 2000 bytes you can't encode more than 2**16'000 pictures, which
is a lot, but may be not enough. If you want exact encoding, you can't have
short codes for all pictures, but only a few of them.
>I'm not clear on the question of the tradeoff between compression ratio
>and error epsilon, but it certainly isn't as large a factor as one would
>initially think.
    Seems to depend on the original picture. For idealized farns and forests
without the natural irregularities, it applies.
>I don't think I called it revolutionary before, but that's not a bad
>word for it. Although it's pretty slow any way you look at it. But
>more cpu horsepower is right around the corner. And direct IFS hardware
>support is being implemented. We're going to be hearing more and more
>about this technique in the coming years. Put money on it.
    What matters here isn't the (granted) improvement of a single
technology (here: CPU speed), but the relations. The main focus of
IFS is animation and transmition over networks. For animation playback,
the volume and cost of mass storage will improve greatly, too (optical R/W
disks), so it may be much cheaper to use that storage than special IFS hardware.
The same applies for transmition over networks, where capacity and price are
improving, too. For one-to-many links (TV, etc.), full bandwith transmition
is used already, and for one-to-one links (picture telephone, etc.),
the ratio of encoding and decoding time (and the large libraries needed
for encoding) are a big problem.
    Another tradeoff aspect is the comparision with other encoding algorithms.
Many methods are available that provide reasonalble compression ratios,
are much faster, esp. for encoding, and at least as easily implementable
in hardware. They probably fit the CPU/storage cost relations much better.
    Fractal encoding is an interesting research subject, but economic
and engineering tradeoffs don't help it. Better put your money on 
something else. It could die silently.

Martin J. Duerst
Dept. of Information Science,
Faculty of Science
University of Tokyo
7-3-1 Hongo, Bunkyo-ku
113 Tokyo, Japan