Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!cmcl2!nrl-cmf!ames!elroy!mahendo!jplgodo!wlbr!etn-rad!jru
From: jru@etn-rad.UUCP (John Unekis)
Newsgroups: comp.graphics
Subject: Re: Chaotic Compression
Message-ID: <305@etn-rad.UUCP>
Date: Sat, 14-Nov-87 20:48:14 EST
Article-I.D.: etn-rad.305
Posted: Sat Nov 14 20:48:14 1987
Date-Received: Sun, 15-Nov-87 22:29:38 EST
References: <619@applix.UUCP>
Reply-To: jru@etn-rad.UUCP (John Unekis)
Organization: Eaton Inc. IMSD, Westlake Village, CA
Lines: 48

In article <619@applix.UUCP> scott@applix.UUCP (Scott Evernden) writes:
>This months issue of "Computer Graphics World", in the
>"Graphics Technology" section, describes an image compression
>technique called "Chaotic Compression" which is supposed to
>yield exact image compression ratios as high as 1,000,000 to 1.
>
>The article attempts to hint at the algorithm, but winds up
>not making any sense.  Does anyone have any information?
>
>Along the same lines, HyperCard utilizes some new image compaction
>algorithms yielding (I think) 200-1 compression.  Does anyone know what
>Atkinson's trick is?
...
The Computer Graphics World article is rather slim on details, but 
from what I gather , the million-to-one algorithm only works on graphics
images. If you have an object which has well defined borders and is 
filled with relatively random data inside the borders then you simply
encode the borders as vectors , and the expansion algorithm will draw 
the borders then walk around inside of them filling the image with
random data. Big Deal. Useless for practical applications.

As for the 200-to-1 compression, this is an old trick. If this is what
I think it is, then they cant really perform compression like this on
any given arbitrary image. Usually these algorithms work on a sequence
of VIDEO images. The trick is that after transmitting frame N , you 
subtract frame N from frame N+1, leaving only the differences between
the two frames. Run-length encoding of the difference image should produce 
very good compression, and all the receiving side has to do is expand
the difference image and add it to what is currently on the screen. The
triple digit compression ratios are achieved by aiming the video camera
at an inanimate object like a flower pot. The differences between images
are then almost all zero, except for noise in the video camera, and will
run length encode extremely well. If anything in the image should have the 
audacity to actually move the compression drops to single digit figures
instantly. If you are using a scheme like this to send video over a 
fixed bandwidth comm line, every time something moves you get blurring
and ghosting which takes many frames to settle down.

In general There Aint No Such Thing AS A Free Lunch. Information preserving
compression schemes that work on single arbitrary gray-scale images almost
never produce over 3 to 1 compression without using a weeks time on a CRAY.
Non information preserving algorithms wont go much over 10 to 1 on a real
(not rigged for the algorithm) image without turning it to MUD. The best 
compression algorithm for general purpose images that I have seen yet is
the National Imagery Transmission Format from the DIA. It will let you
convert an 8 bit per pixel image into 4.5b/p, 2.3b/p, 1.4b/p, 0.75b/p,
or 0.5b/p depending on how much degradation you can stand. If anyone
has seen a REAL algorithm that works better than this, please let me know.