Path: utzoo!attcan!uunet!snorkelwacker!apple!vsi1!zorch!xanthian
From: xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan)
Newsgroups: comp.graphics
Subject: Re: Compression of multi-bit images
Keywords: compression, raster
Message-ID: <1990Jun11.101113.17714@zorch.SF-Bay.ORG>
Date: 11 Jun 90 10:11:13 GMT
References: <8099@b11.ingr.com>
Organization: SF Bay Public-Access Unix
Lines: 35

In article <8099@b11.ingr.com> dan@b11.ingr.com (Dan Webb) writes:
>I'm looking for a space-efficient (not necessarily speed-efficient)
>algorithm for data compression of multi-bit (color) images.
>I would prefer that the technique be fully reversible, but I will
>consider anything.
>
>Thanks in advance.
>
>Dan Webb
>Intergraph Corp.

As later articles mentioned, arithmetic coding is one possibility.
Recent experiments I've performed show compressions as high a 50 to 1
for sparse, "line drawing" type images.  This technique is useful in
general for any dataset which is large, and makes sparse use of the
total range of possible symbols or bit patterns.  Since it accomplishes
its compression at the pixel/symbol level, rather than by run lengths,
or repeated sequences, it is somewhat less sensitive to "speckly" input
images than are other methods.

An article in Communications of the ACM a couple of years back gives
working C code for such a compression algorithm.  The code is written
to be tutorial rather than efficient, so it runs rather slowly (about
30 times slower than LZ compression, for example), but can be very space
efficient given the right sort of data.  Cleaned up (the code does
subroutine calls at the per bit level of the compressed file), the
code could probably run a lot faster, and there are better and fuller
implementations of arithmetic compression around, as another article
notes.

Kent, the man from xanth.
<xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>

-- 
in the distance a roasted cave newt screamed in agony -- Andrew Palfreyman