Subject: image compression

From: rlw at stsci.edu (Rick L. White)
Date: 28 Oct 91 18:16:22 GMT

I got into this discussion late (thanks to Bob Hanisch for directing me to
this group and to Don Wells for maintaining the archive); I apologize that
this posting is so long.  As an introduction, I am the person who developed
the image compression technique we will be using to distribute the digitized
sky survey plates that were used in the construction of the Guide Star
Catalog.  There are about 1500 images, each of with 14000x14000 I*2 pixels,
so the total data volume is 600 GBytes.  For distribution we will compress
the images by about a factor of 10, i.e.  the compressed data will require
about 1.5 bits/pixel.  This is, of course, lossy compression -- but the only
loss (according both to my analysis and to tests we have done) is that we
have thrown away most of the noise in the image.  In fact, at 1.5 bits/pixel
we are still keeping 1 bit of noise everywhere -- we can compress down to
about 0.7 bits/pixel before we start to throw away real information.  We
will soon be distributing a CD-ROM sampler with 8 different plates (north &
south, galactic plane & pole, etc.) compressed at 3 different levels (about
1.5, 0.7, and 0.3 bits/pixel).

Archie Warnock (warnock at nssdca.gsfc.nasa.gov) writes: 
% In general, compression is tricky - binary files just don't compress
% very well.

Greg Scott Hennessy (gsh7w at fermi.clas.Virginia.EDU) writes:
% As with many things, the answer is "that depends". 

Don Wells (dwells at fits.cx.nrao.edu) writes: 
% I agree with both statements. The real issue is what fraction of the
% bits of the file are "random"...

Don has it exactly right.  It is easy to put a lower bound on the data
volume required to store an image (thus an upper bound on the
compression) if it is to be compressed with no loss:  just count the
total number of bits of noise in the image.  For the GS digitized
plates, the noise is typically sigma = 200 DN in each pixel, so
lossless compression will always require at least 8.5 bits/pixel (+/- 1
sigma requires 8.5 bits).

Not only is this a lower bound to the data volume, but it is actually a
pretty good estimate of what can be achieved.  The real structure in
most astronomical images can be stored with very little information,
typically less than 1--2 bits/pixel (even for crowded fields in the
galactic plane).  If your lossless method requires much more than N+2
bits/pixel, where N is the number of noise bits, then you probably need
a better method.

An upper bound to the data volume can be calculated from the entropy of
the image, S = Sum[f*log2(f)], where the sum is over all different
pixel values and f is the fraction of pixels having the given value.
This is an upper bound because if there are any correlations between
pixels (as there always are in real images), then less than S bits/pixel
are required.

Note that one can generate a highly incompressible image simply by
adding a whole bunch of noise bits to each pixel.  One way to do this,
for example, is to convert the image to float and divide by a flat
field.  A flat-fielded R*4 image is very difficult to compress -- if you
insist on lossless compression!  Of course the key is to allow some loss
in the compression.  Lossless compression may make sense for low-noise CCD
images, but no sensible person cares whether a compressed R*4 image agrees
with the original in the last bit.

Markus Buchhorn (markus at mso.anu.edu) writes:
% ... one way of helping the compression algorithm might be to store the data
% as differences from one pixel to the next. If the Universe was well behaved
% and skies were truely smooth, the gain would be astounding ...  As the noise
% increases, the efficiency would decrease.  Another advantage (possibly the
% main one) is that all the dp/dx values would be closer in number-space,
% which means that a trick like compressing high and low bytes separately
% would work much better.

Archie Warnock (warnock at nssdca.gsfc.nasa.gov) writes: 
% ... this is virtually the algorithm IHW used for compressing the 
% digitized large-scale images.  We observed that, for most of our 1600 
% images, although the data itself required 2 bytes for storage, the 
% pixel-to-pixel differences fit in 1 byte.

This method is often suggested for compression, but it does not work very
well for noisy images.  Suppose we have a completely empty image with each
pixel = SKY+NOISE.  If we take the difference of adjacent pixels, then each
pixel has SQRT(2)*NOISE (assuming that the noise is independent and equal in
each pixel).  Taking differences of consecutive pixels _increases_ the
noise, which actually makes the image _harder_ to compress (by about 0.5
bit/pixel).

Even when there is real structure in the image, taking differences often
does not help.  Astronomical images are filled with point sources, so when a
signal appears it tends to change very rapidly from one pixel to the next.
If you take the derivative of an image you spread the structure over more
pixels and make it more complicated, which does not help compression.
Smooth objects are pretty rare in astronomical images.

I think Markus is right that the main reason this method has been found to
be useful is that it shifts the values of pixels so that they are centered
around zero.  One would do better, though, just to subtract the SKY value
directly so that the noise does not get combined.  Of course, if SKY varies
(i.e. there is structure in the image), this doesn't work and one needs a
fancier method.  Nonetheless, just taking differences of adjacent pixels is
not a very good first step in compressing images.

Markus Buchhorn (markus at mso.anu.edu) writes:
% But what about a lossy compression technique ? Before anyone jumps on
% that, look at the way HST will store their digitised sky survey...
% they have achieved quite respectable compression (4:1), and, *they claim*
% that photometry is not compromised by this. (Dunno about crowded fields
% though ???)

Archie Warnock (warnock at nssdca.gsfc.nasa.gov) writes: 
% Excellent idea - especially if we can arrange the compression so what's 
% lost is the noise, not the signal.  Still, astronomers are conservative 
% folks and want to preserve every last bit of noise.

Don Wells (dwells at fits.cx.nrao.edu) writes: 
% The general strategy which I speculate will generally make the maximum
% gain is to split the datastream into streams which have homogeneous
% statistics, and compress each stream separately...  It may be advantageous
% to compress even and odd bytes separately for 16-bit data, or use four
% streams for 32-bit.

Jean-Pierre Veran (veran at cfht.hawaii.edu) writes: 
% The images are generally very noisy and I have found that I can improve
% considerably the compression if I get rid of a certain number of the least
% significant bits, then use COMPACT 1.0 to compress the remaining most
% significant bits and finally just append the least significant bits to
% the file, without trying any compression on them.

Yes, the trick is to separate the noise and the signal.  The signal is
highly compressible, while you are wasting your time if you try to compress
the noise.  I've tried a number of techniques similar to those mentioned
above.  The difficulty with just stripping off the bottom N bits is that
there is still some signal buried in those bits.  If you throw the bits away
(lossy compression) you have lost some potentially valuable information; if
you write them out directly, you have saved a lot of noise to get a little
more information.  If you leave more of the noise bits in the signal
when you do your split, the signal becomes much harder to compress (e.g.
run-length coding fails completely in the presence of even a little
noise.)

The trick in the method I use -- based on the H-transform, see Fritze et
al.  Astron.Nachr (1978) 298, 189 and Capaccioli et al. (1988) Astron.Nachr.
309, 69 -- is that it preserves the mean of the image on all scales.
Effectively it blocks the image in groups of 1x1, 2x2, 4x4, ... pixels and
preserves the average of each such block if it differs signficantly from the
average of neighboring blocks.  That means that low-surface brightness
objects, which are not detected in single pixels but _are_ detected if one
averages over blocks, can be preserved even if you throw away the noise.
This method manages to keep as much as possible of the information which is
buried in the pixel noise without keeping too much of the noise itself.
Of course, you can still keep the noise if you want it -- but with this
method it is much clearer where to draw the line and stop trying to
compress the data.

Rick White,   rlw at stsci.edu
Space Telescope Science Institute