Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!rutgers!sri-spam!mordor!styx!ames!ucbcad!ucbvax!decvax!tektronix!sequent!mntgfx!gssc!jdm
From: jdm@gssc.UUCP
Newsgroups: comp.graphics
Subject: Re: Compressing Image Data
Message-ID: <252@gssc.UUCP>
Date: Fri, 30-Jan-87 13:39:34 EST
Article-I.D.: gssc.252
Posted: Fri Jan 30 13:39:34 1987
Date-Received: Sat, 31-Jan-87 20:26:21 EST
References: <505@hao.UCAR.EDU>
Reply-To: jdm@gssc.UUCP (John D. Miller)
Organization: Graphic Software Systems, Beaverton Or
Lines: 63
Keywords: Image processing

there are a *number* of ways to compress 1Kx1Kx16bit data.  the best one
requires you to think hard about the kind of data that you are likely to
have in these images.  certain algorithms work better if the data is fairly
homogoneous (i.e. large patches of the same color) and others work much
better if the data is in the other extreme.

if the data is homogoneous, simple run-length encoding may be enough.  using
this method, data is stored as a record of colors that appear on a scanline,
paired with their length.

for example, a scanline that looks like this:
	r r r r r r r r r w w r r r r r b b b b b b b b b b b b b b
where r=red, w=white, b=blue, etc.  could be run-length encoded like this:
	9r2w5r14b
indicating the number of pixels of a color index.

other, slightly newer and more sophisticated methods stem from digital
signal processing.  i am refering to the numerous pulse-code-modulation (PCM)
techniques, each of which have their own strengths and weaknesses in the DSP
field.  

for image processing, you might want to consider a form of PCM called PDM, or
pulse-delta-modulation, where the delta is the difference from one pixel value
to the next this makes sense when you are dealing with shades of related colors
AND these shades are close in proximity to each other in your color map.  some
trickyness is involved here: you can usually specify the delta from one pixel
to another in less than 16-bits (which saves you space over storing the pixel
values), but you must choose this quantity carefully.  if the spectral
frequency content of your image is very high, or can be very high, you may
easily saturate the delta quantity and the delta would have to be "overloaded",
that is, multiple deltas may sometimes equal the delta between two pixels, or
suffer a high-frequency loss in the picture, effectively lowering the contrast.
the problem with the overloading techinique is that image dumps may not all be
the same size, but that is easily fixed with appropriate info blocks, etc, that
allow you to find the start of each scanline.

in comparing the two techniques here:

	run-length: good for homogoneous data; prefers simple, steep-edged
	(high freq. content) images, as shading is non-homogoneous pixels.
	amount of compression can run from the best possible to the worst
	possible, depending on the number of colors on the scanline.

	PDM: very good for shaded images with relatively low spectral
	frequency.  amount of compression is tunable and should be set to
	make the best tradeoff of typical delta and overloading.  overloading
	reduces the compression slightly and requires a slightly smarted
	program, but leaves image data intact.

since you have 16 bits of resolution, my guess is that you have fairly
detailed images, and would benifit most from PDM.  do some investigation
into your spectral frequency content (how fast does, say, black turn into
white and how often) and try to group frequently used colors close together
in your color map.  if you use an 8-bit modulation index, you compress 50%,
optimially, and may never overload.  then try 4-bits and see how much more
you compress - you may overload a lot more until you reorganize your color
map, but you may find you really need 8 bits after all.  still, i'll take
a 500K file over a 1M file any time.

good luck, and if you need more info on PCM, try "The Sony Book of Audio
Technology."

-- jdm