Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!uunet!ns-mx!pyrite.cs.uiowa.edu
From: jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879)
Newsgroups: comp.compression
Subject: Re: looking for info on image compression
Message-ID: <5043@ns-mx.uiowa.edu>
Date: 25 Mar 91 19:48:07 GMT
References: <5040@ns-mx.uiowa.edu>
Sender: news@ns-mx.uiowa.edu
Lines: 38

From article <5040@ns-mx.uiowa.edu>,
by drenze@umaxc.weeg.uiowa.edu (Douglas Renze):

> ... a set of algorithms for GIF image compression.  I haven't looked at
> them, but I would assume that they're fairly complete & that they could
> (maybe) be adapted to other image types ...
> 

GIF images use Ziv-Lempel compression, which is not a particularly good
way to compress images.  The problem is, it operates on strings of
successive letters, and it works best if short strings of letters have
some significance and are likely to be repeated.  In images, repetitions
of any string, when they occur, are usually accidental, and strings of
pixels, reading left to right, are lousy predictors of the next pixel
compared to 2-dimensional neighborhoods.

I did an experiment using my splay-tree based compression algorithm with
just one state in its source model, and it equalled the performance of
Ziv-Lempel compression on digitized portraits.  Multi-state compression
models for images can do much better (and my splay-tree based algorithm
is not intended to be a space-optimal compression algorithm).

These results were published in my CACM paper of Aug, 1988.  Further
results of mine concerning use of splay-tree based compression on images
will appear in the 1991 Data Compression Conference two weeks from now.

(PS:  Does the use of Ziv-Lempel compression for GIF images mean that
the question of patent rights for the Ziv-Lempel algorithm applies to
GIF images?  My source code for one GIF viewer had a note saying that
the uncompression code was borrowed from the UNIX compress command, and
I understand that there are patent infringement questions currently being
asked about UNIX compress.)

(PPS:  I give away copies of my splay-tree compression code to anyone
who asks for it.)

					Doug Jones
					jones@cs.uiowa.edu