Subject: Re: compression of fits

From: warnock at nssdca.gsfc.nasa.gov (Archie Warnock)
Date: 24 Sep 91 20:26:00 GMT

I am willing to post the LaTeX source of the FITS Compression proposal 
here, although it's fairly long.  OTOH, I could E-mail it, if I don't 
get too many requests.  I'm delighted to see such an interest.

First of all, compression and FITS are separate issues.  The proposal is 
for a FITS syntax to _indicate_ a compressed data stream.  It does allow 
for keywords to indicate the compression method used on the data, but 
does not (yet) mandate any particular algorithms - though we do give an 
example.

In general, compression is tricky - binary files just don't compress 
very well.  Tables, on the other hand, compress wonderfully - helped no 
small amount by the padding FITS requires to "round out" the header and 
data lengths.

Further discussion _very_ welcome!

----------------------------------------------------------------------------
-- Archie Warnock                     Internet:  warnock at nssdc.gsfc.nasa.gov
-- ST Systems Corp.                   SPAN:      NSSDC::WARNOCK
-- NASA/GSFC                          "Unix - JCL for the 90s"

---

From: gsh7w at fermi.clas.Virginia.EDU (Greg Scott Hennessy)
Date: Tue, 24 Sep 91 22:36:35 GMT

Archie Warnock writes:
#I am willing to post the LaTeX source of the FITS Compression proposal 
#here, although it's fairly long. 

Please do post such.

#In general, compression is tricky - binary files just don't compress 
#very well. 

As with many things, the answer is "that depends". I have large
amounts of 2Kx2K images from the Astro-1 mission on my disk, and to
save disk space I use the unix "compress" facility. The images are all
16 bit signed integers, which are certainly "binary" images, but these
compress very well, not only because the large field of view (40
arcmin) means that there is lots of sky, but because in general images
tend to be rather smooth, and the compress utility works rather well
on these, compressing them to about 30 percent of the origional size.
As an experiment, I converted these images from 16 bit integer to 32
bit floating point, IEEE format, and I was suprized to find that the
compression ratio remained much the same. I would have ventured the
opinion that floating point numbers would not compress well, unless
fancy things were done line splitting the bytes to compress the
exponents and some of the most significant bits, however, this trial
worked fine. However, trying to compress a UV data set may not achieve
the same results. For a single data point though, I just ran the
compress utility on a UV data set that I have. The data set was 18
hours of VLA time, continuum mode, 2 IFs, full polarization, and 20
second integration time. The total dataset was 41.6 MBy, and the
compressed data set was 23.1 MBy, so the compressed data was 55% of
the origional, a nice healthy savings. This data is IEEE format, and
probably about one of the hardest data sets to work with. 

However, how will the FITS reader and writing programs deal with
compressed data? Currently the header (which I would argue should
NEVER be compressed) allows an exact determination of how much data is
in the file. If a new keyword is introduced (COMPRESSED = T?) is
introduced, then the header could be identical to current practice,
and just the bytes of the compressed data written, with the padding to
the 2880 octet buffer size (and whatever blocking factor) could be
written, but it is unknown how the uncompress algorithm would deal
with the padding values. It is unclear if compress should be used at
all. My understanding is that compress is what POSIX 1003.2 has
chosen, but with Unisys and IBM both claiming patents on compress, the
legality of using compress is not clear. My understanding is that
compress will never give out a larger output than the input, but I am
not certain of this. 

Sugguestions are most welcome.

--
-Greg Hennessy, University of Virginia
 USPS Mail:     Astronomy Department, Charlottesville, VA 22903-2475 USA
 Internet:      gsh7w at virginia.edu  
 UUCP:		...!uunet!virginia!gsh7w

---

From: markus at mso.anu.edu (Markus Buchhorn)
Date: 25 Sep 91 04:42:34 GMT

I apologise in advance for the length of this posting. I'm interested
in this topic, and want to stir up some conversation :-)

>#here, although it's fairly long. 

Agreed - or put it up for ftp on fits.cx.nrao.edu in the appropriate directory.
 
>As with many things, the answer is "that depends". 
[...]
>worked fine. 
[...]
>with the padding values. 

Sorry about including all of that - but I think it's relevant.
The choice of compression algorithm and the storage of the compressed
data are the two main problems we would face here. I don't know what
Mr Warnock's work has done, so I can't comment on that. 

But a couple of ideas spring to mind: 

First off, for 2D image type of data (CCD images say),
even somewhat noisy ones, 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 d(pixel)/dx = 0 or const for many
pixels in a row. Any run-length encoding technique would be quite happy
with this. 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.

But what about a lossy compression technique ? Before anyone jumps on
that, look at the way HST will store their digitised sky survey.
They bin the data into 2x2 blocks, generate 4 coeffs, then treat the
coeffs as pixel values for another image (binned down by a factor of
2 effectively). Loop until you get down to a single pixel / group of.
By choosing which coeffs to keep and which to turf out,
they have achieved quite respectable compression (4:1), and, *they claim*
that photometry is not compromised by this. (Dunno about crowded fields
though ???)

The other thing is how do we store this compressed stream. I agree
with Greg that the header should not be compressed. If you want to use
'compress' to increase disk-space - fine. But you uncompress them yourself.
What we want is a technique that does this transparently to The User.
Perhaps what one would need to do is read in either the entire
image into RAM, compress all of it, then write out the compressed stream
in 2880 chunks, or else read in some fraction of that (N lines), compress
just that, and write out 2880 chunks. Padding is not a good idea as
(i) wastes space and (ii) decompression could have a problem with 
this. Also, the nice thing with raw FITS files is that one can
access them randomly/sequentially (see the FITSIO package). By
chunk-ifying the image, we can still achieve some of the advantages,
as reading any individual record won't need the previous one to
yield raw data. (Ok, possibly one would need to read a few adjacent
records, but not the whole thing..... )

Anyway - I can see problems(*) with the above already. I'm a busy student
so don't have much time to play with this sort of thing. But I am 
very interested in the problem, and look forward to seeing Mr Warnock's 
proposal.

Cheers,
	Markus

Markus Buchhorn
markus at mso.anu.edu.au 

(*) One problem with any(?) run-length compression scheme is that
a row or chunk of data may depend on the first pixel value
being known - what happens if there is a transmission error/tape-error/
generic-Murphy-Law error in that pixel? Then we need CRC/checksums ????

---

From: gsh7w at fermi.clas.Virginia.EDU (Greg Scott Hennessy)
Date: Wed, 25 Sep 91 15:12:41 GMT

Markus Buchhorn writes:
#Perhaps what one would need to do is read in either the entire
#image into RAM, compress all of it, then write out the compressed stream
#in 2880 chunks, or else read in some fraction of that (N lines), compress
#just that, and write out 2880 chunks. Padding is not a good idea as
#(i) wastes space and (ii) decompression could have a problem with 
#this. 

It is very common already to have FITS data sets that will not fit
into RAM, and I think that it would be a mistake to rely on a
compression scheme that required reading the whole data set into ram. 

Another aspect is what will the existing FITS readers do with a
compressed image. The original FITS papers considered this point, and
conceded that not all reader programs can read every FITS file, but
the programs should at least exit gracefully. I have encounted data
sets that were called FITS files, that did not have the last record
padded out to 2880 octects, and some FITS readers die horribly at
this. Blocking out the last record to 2880 octects is not very
wastefull of space, at least for modern data sets (trying to transport
icons for your workstation with FITS isn't very efficient spacewise to
begin with). The more important issue is how do the decryption program
deal with this padding. 

It is also very import to remember during all these discussions on
what the non-unix users will do. While POSIX 1003.2 may specifiy
compress, there are going to be interesting computers that will not
have this algorithm, and it seems a disservice to leave these systems
high and dry.

---

From: tody at noao.edu (Doug Tody NOAO/IRAF CCS)
Date: 26 Sep 91 06:29:17 GMT

>From article <1991Sep25.151241.1531 at murdoch.acc.Virginia.EDU>, by gsh7w at fermi.clas.Virginia.EDU (Greg Scott Hennessy):
> Markus Buchhorn writes:

Unless there are good reasons to do otherwise it would be wise to use a
compression techinique which is local in nature (assuming the pixel data is
to be compressed instead of the entire FITS file).  This is particularly
important if the data is to be randomly accessed at runtime, for example,
when reading a FITS image from a CD-ROM, or from disk.  It would also aid in
recovery from data losses.  A simple technique would be to compress each
image line independently, using an index to record the offset of each
compressed line.  An existing example of this is the pixel mask image format
in IRAF, which preserves all the semantics of the random access image while
storing the image in a compressed form.

A line-oriented, random access approach would be one way of justifying a
FITS specific compression technique, rather than simply compressing the
entire FITS file with a standard adaptive compression program like
COMPRESS.  I don't think it is worthwhile to try to compress headers; if you
want to compress the entire file, just use a non-FITS file oriented
compression program.  This would not necessarily have to be COMPRESS; we
could write our own adaptive compression program if we wished, more oriented
towards noisy image data, without having to tie it to FITS or any other
specific image format.

> It is also very import to remember during all these discussions on what the
> non-unix users will do. While POSIX 1003.2 may specifiy compress, there are
> going to be interesting computers that will not have this algorithm, and it
> seems a disservice to leave these systems high and dry.

Source for the compress/uncompress programs is available on the net.  A
while back we hacked a version of this here for VMS.  Source for both the
UNIX and VMS versions, plus VMS binaries, are in the util subdirectory on
iraf.noao.edu (I believe gatekeeper.dec.com has an older copy as well).  The
VMS version isn't as easy to use as the UNIX one due to the record
structures of VMS files, but it works.  As many will be aware there are
efforts to patent the LZ algorithm used in compress, but the authors of the
original algorithm oppose this, and since the source has been publically
available for years it may be difficult for the lawyers to win this one.

I think more research, and trial implementations, are needed before we want
to settle on a FITS standard for image compression.  Getting experimental
support for compression into our online image formats, which can be more
easily changed than the FITS standard, would be a good start.  Some basic
algorithms research is badly needed as well.  A general purpose program like
COMPRESS, with an adaptive algorithm which could do well on noisy pixel data
as well as text, could prove immediately useful and would provide an
opportunity for algorithms development.
-- 
Doug Tody, National Optical Astronomy Observatories, Tucson AZ, 602-325-9217
UUCP: {arizona,decvax,ncar}!noao!tody  or  uunet!noao.edu!tody 
Internet: tody at noao.edu             SPAN/HEPNET: NOAO::TODY (NOAO=5355)

---

From: warnock at nssdca.gsfc.nasa.gov (Archie Warnock)
Date: Thu, 26 Sep 1991 14:29:00 GMT

In article <1991Sep26.062917.1517 at noao.edu>, tody at noao.edu (Doug Tody NOAO/IRAF CCS) writes...
>compressed line.  An existing example of this is the pixel mask image format

This would, indeed, be very handy.  One of the drawbacks of the 
bit-oriented compression schemes is that random access into the image is 
tricky, at best.  On the other hand, I also want to address the 
_interchange_ of data, in which case the maximum compression ratio is 
desirable.  I still think of FITS as an interchange format (which it is 
good at), rather than a working format (which it isn't so good at).

>compression program.  This would not necessarily have to be COMPRESS; we

Except that this decidedly non-FITS like.  It relies on external means 
to document the algorithm, rather than packaging the data in 
self-documenting form, and doesn't necessarily select the compression 
algorithm from what I hope will be a widely available set.  The point of 
the proposal we made is to implement the strategy _within the FITS 
framework_.

>available for years it may be difficult for the lawyers to win this one.

Two strong arguments for implementing compression as part of the FITS 
syntax, rather than relying exclusively on "external" techniques.

>algorithms research is badly needed as well.  A general purpose program like

I can't agree more strongly.

---

From: warnock at nssdca.gsfc.nasa.gov (Archie Warnock)
Date: 25 Sep 91 18:34:00 GMT

In article <1991Sep25.044234.18639 at newshost.anu.edu.au>, markus at mso.anu.edu (Markus Buchhorn) writes...
>the next. If the Universe was well behaved and skies were truely smooth,

<ding, ding, ding>  Ladies and gentlemen, we have a winner in the "IHW 
Compression Contest".

Seriously, 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.  Presto - instant 50% 
compression (almost instant - it requires only a single addition per 
pixel to decompress the image).  Best bang for the buck, in our 
estimation.  Not the best possible, but the best for the lowest 
(computational) cost.

>that, look at the way HST will store their digitised sky survey.

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.

>generic-Murphy-Law error in that pixel? Then we need CRC/checksums ????

A checksum keyword would be an excellent idea.  Currently, none of the 
FITS data structures inherently incorporate such a thing - it's not 
unique to compressed data.

The successive-differences scheme used by IHW has to "re-calibrate" the 
8-bit differences whenever the pixel-to-pixel difference is too big.  
This means that such transmission errors wouldn't propagate too far down 
the image.

---

From: warnock at nssdca.gsfc.nasa.gov (Archie Warnock)
Date: 25 Sep 91 18:26:00 GMT

In article <1991Sep24.223635.14295 at murdoch.acc.Virginia.EDU>, gsh7w at fermi.clas.Virginia.EDU (Greg Scott Hennessy) writes...
>tend to be rather smooth, and the compress utility works rather well

If you got those from where I think you did (digitized by my collegues
at Goddard), I'm intimitely familiar with the microdensitometer which
generated those digital images (we digitized 1600 plates of Halley's
Comet with the same PDS).  It uses a 10-bit A/D converter, so the data
is only 10 bits deep (although it still requires 16 bits to store it). 
And you're right - at 10 bits, the data is quite smooth and easily
compressed (see examples in the Compression proposal from the
International Halley Watch). 

In any event, far be it from me to deny that certain compression schemes 
work well on certain data.  Clearly, that's so.  There are two things 
necessary for interchanging compressed data under the FITS syntax.  The 
first is that the astronomical community has to agree on what that
syntax shall be - that's the primary subject of the proposal.  The
second thing is to have software which is "smart" enough to select an
_appropriate_ compression scheme for the data in question.  Just
applying Unix compress won't cut it - there are too many counter
examples. 

My claim is that there's no single best scheme for all astronomical 
data.  New algorithms need to be developed, existing algorithms need to 
be modified and ultimately (I predict) we'll find that the approach of 
the PC-based compressors will be best - to compress the data in question 
with a variety of techniques and keep the one which works best (ala 
PKZIP).

The "trick" of the compression proposal is that it allows the header to 
specify the type of compression used, so we only need to agree on names 
for the particular scheme to use it within the FITS framework.

>compressed data? Currently the header (which I would argue should

As a FITS extension:

XTENSION= 'COMPRESS'
[...]
COMPRES1= 'HUFFMAN'
COMPRES2= 'PREVPIXEL'
[etc]

Additional informational keywords can be added to the extension header, 
if desired.  The second "trick" is that, when you compress the data, you 
compress everything, including a FITS header.  The reason for this is 
that it allows you to compress _any_ FITS data stream, and the result of 
the decompression will always be a fully-qualified FITS data stream, 
which you can feed directly back into your FITS reader.

---

From: gsh7w at fermi.clas.Virginia.EDU (Greg Scott Hennessy)
Date: Wed, 25 Sep 91 19:16:36 GMT

Archie Warnock writes:
#In any event, far be it from me to deny that certain compression schemes 
#work well on certain data.  . . . The
#second thing is to have software which is "smart" enough to select an
#_appropriate_ compression scheme for the data in question.  Just
#applying Unix compress won't cut it - there are too many counter
#examples. My claim is that there's no single best scheme for all astronomical 
#data.  New algorithms need to be developed, existing algorithms need to 
#be modified and ultimately (I predict) we'll find that the approach of 
#the PC-based compressors will be best - to compress the data in question 
#with a variety of techniques and keep the one which works best (ala 
#PKZIP).

While no single compression scheme is best for the many types of data
that are available, I would argue that the number of different schemes
should be kept small. It is a large burden to expect that every
observatory and every department support a large number of different
algorithms. Even saying "Oh, as long as
[IRAF,AIPS,MIDAS,STSDAS,whatever] supports the decompression I am ok"
is simply dumping the problems onto Doug Tody, Bill Cotton, Preben
Grosbol, Bob Hanisch, or whomever supports the software. I.E. people
already under heavy burdens. Also, I doubt the utility of running (as
in the Warnock et. al. draft) five different compression schemes to
obtain a further 5 percent reduction in space. Table 1 in the Warnock
et. al. draft clearly shows what we all know now. Some data sets
compress well (using a generic compress, not referring to any
particular algorithm) and some data sets do not. My conclusion from
Table 1 is that the space savings from different algorithms is a small
fraction of the range of savings possible, hence picking a good but
admittedly not best for all cases algorithm to standarize on is a win
in keeping down software complexity over supporting multiple
compression algorithms to gain 5-10 percent savings. 

Does anyone make a different conclusion?

Cheers,

---

From: warnock at nssdca.gsfc.nasa.gov (Archie Warnock)
Date: 25 Sep 91 21:42:00 GMT

In article <1991Sep25.191636.4068 at murdoch.acc.Virginia.EDU>, gsh7w at fermi.clas.Virginia.EDU (Greg Scott Hennessy) writes...
>should be kept small. It is a large burden to expect that every

No argument there.  It's time-consuming to repeatedly compress data to 
see what works best.  On the other hand (as an earlier posting showed - 
Nelson?) there are pathological cases which can get bigger, not smaller. 
Either we require the user to somehow characterize their data, or 
educate the user as to which schemes compress which data the best, or we 
let the software do that - or we use some generic scheme which doesn't 
to too bad on anything, but doesn't do too well, either.

In any event, the proposal allows for all those eventualities.  I don't 
believe _anyone_ has done the type of comprehensive testing necessary to 
draw conclusions about _which_ compression algorithms ought to be 
adopted.  Whatever the result of such studies in the future, the main 
point of our proposal is to make the data compressed by _any_ of those 
schemes transportable.  The framework is what's proposed - how to fill 
in the details remains to be resolved/investigated.

>compression algorithms to gain 5-10 percent savings. 

Bang for the buck - a good concept.  Computing time goes up 
substantially with increasing compression ratio.  I hope no one claims 
to be able to decide for everyone else what investment level is 
sufficient.

---

From: dwells at fits.cx.nrao.edu (Don Wells)
Date: Wed, 25 Sep 1991 20:44:29 GMT

In article <1991Sep24.223635.14295 at murdoch.acc.Virginia.EDU>

 > As with many things, the answer is "that depends". 

I agree with both statements. The real issue is what fraction of the
bits of the file are "random", or alternatively what types of patterns
can the compressor detect in binary data.

 > ... 2Kx2K images from... Astro-1 ... I use... "compress" ... 16 bit
 > signed integers ... compress utility ... to about 30 percent of...
 > origional ... experiment... converted... to 32 bit... IEEE...
 > suprized... that... compression ratio remained much the same. 

Most of the image probably has sky background with DN values of order
25-35, i.e., 5 bits per pixel typically, or else it is smooth with 5
bits of noise; this enables about 10 bits to be eliminated in every
pixel. When such data are converted to IEEE they still only have a
modest number of significant bits. In particular, the lower 16 bits of
the mantissa are probably zero; this is worth 50%. In addition, there
will be only a few possible exponents in the IEEE values, and so most
of the exponent information will compress. Compression of the most
significant byte is similar to the original problem. If the four bytes
were separately compressed you might get down to about 15% of
original, i.e., about same number of bits as for the 16bit version,
but with the bytes interleaved compress will not be able to take full
advantage of the fact that the four bytes have very different
statistical distributions.

 > ... ran... compress on a UV data set ... 18 hours of VLA time,
 > continuum mode, 2 IFs, full polarization... 41.6 MBy...
 > compressed... was 23.1 MBy... 55% of... origional... 

I am surpised that the gain was this much.  My guess is that much of
the gain came from the random parameters, with things like baseline
number and maybe weights having few values.  I suspect that if it had
not been full polarization the relative gain would have been greater
(visibility data is probably fairly random noise to compress).

			=-=-=-=

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. For a table, compress
each column as a stream. For random groups, compress each random
parameter separately.  For binary data I advocate using first
differences (integer subtraction) in the streams to eliminate even
more of the variation (this should be tested). It may be advantageous
to compress even and odd bytes separately for 16-bit data, or use four
streams for 32-bit.

			=-=-=-=

I have done only one small experiment. Last November two astronomers
in Germany asked me to help them get copies of several HST images
which were in anonymousFTP on fits.cx.nrao.edu. They were having
trouble with slow, congested, unreliable circuits in Germany at that
time, and could not reliably FTP a 5 MB file. I wrote a script and
trivial c routine to split the file into an even-byte file and an
odd-byte file and compress each separately. The even-byte (high order
byte) file compressed by 80%, but the noisy odd-byte file would not
compress, so the net reduction was by 40%. Fortunately, it turned out
that it was possible to FTP a 3 MB file. Sometimes compression can
make the difference between success and failure! If this interests
you, do anonFTP to fits.cx.nrao.edu [192.33.115.8] and fetch the smallest
of the following three files (the tar file) in directory FITS/HST:

-rw-r--r--  1 dwells   vlb       5158080 Oct 19  1990 w0bs0102t_cvt.c0h
-rw-r--r--  1 dwells   vlb       4380234 Nov 15  1990 w0bs0102t_cvt.c0h.Z
-rw-r--r--  1 dwells   vlb       3088384 Nov 16  1990 w0bs0102t_cvt.c0h.tar

The tar file will unpack to two files and a C program and a Makefile,
and it will compile the program and execute it to uncompress and zipper
the two files back together to recover the 5.1_MB original. As you can
see, compress on the un-split file only got 20%, as compared to 40% on
the split file.

			=-=-=-=

I recommend that anyone who is serious about compression should
consider applying a low-pass filter to the sampled data (e.g.,
convolve with Gaussian with, say, 2 pixel halfwidth). The purpose of
the filtering is to increase the correlation of adjacent pixels (i.e.,
reduce high frequency noise) so that the subtraction will eliminate
more bits. Even a modest reduction in resolution can make a gain in
smoothness, with a resulting saving in bits.  It will also be *very*
important to consider how many of the least significant bits you
really need after the filtering.  Every least significant bit that you
mask is a bit that won't go into your compressed dataset!

Donald C. Wells             Associate Scientist        dwells at nrao.edu
National Radio Astronomy Observatory                   +1-804-296-0277
Edgemont Road                                     Fax= +1-804-296-0278
Charlottesville, Virginia 22903-2475 USA            78:31.1W, 38:02.2N 
--

Donald C. Wells             Associate Scientist        dwells at nrao.edu
National Radio Astronomy Observatory                   +1-804-296-0277
Edgemont Road                                     Fax= +1-804-296-0278
Charlottesville, Virginia 22903-2475 USA            78:31.1W, 38:02.2N

---

From: warnock at nssdca.gsfc.nasa.gov (Archie Warnock)
Date: Thu, 26 Sep 1991 14:19:00 GMT

In article <DWELLS.91Sep25154429 at fits.cx.nrao.edu>, dwells at fits.cx.nrao.edu (Don Wells) writes...
>statistics, and compress each stream separately. For a table, compress

Another reason this might help matters, at least for compression schemes 
like that used in Unix compress, is that the symbol table for such 
schemes usually assumes 8-bit data (Huffman, LZ, etc. are usually 
designed for text, not numeric, data).  I'm not aware of any 
investigation into 16-bit tables.

>convolve with Gaussian with, say, 2 pixel halfwidth). The purpose of

Yes, yes, yes - the more often we say it, the better our chances of 
actually getting the astronomical community to believe it - you don't 
necessarily need (or even _want_) all those bits, particularly if you're 
limited in storage space and/or bandwidth.

---

From: pwb at newt.phys.unsw.oz.au (Paul W. Brooks)
Date: 25 Sep 91 02:48:05 GMT

I have experimated extensively with compressing FITS images on our
MS-DOS system (to try to squeeze more images on each tape).
I tried all sorts of archiver algorithms, and found that uniform flat
frames (such as bias or dark frames) could be compressed to about 45% of
the original length, but any structure (such as large galaxies) reduced
the effectiveness, until our flat fields (which are quite non-flat :-( )
could only be compressed by 20% - i.e. to 80% of the original length.
This is because the compression algorithms all go looking for repeated
sequences of bytes - the larger the dynamic range covered by an image,
the less compression is possible, as there are fewer repeated sequences.
In practice, at the byte level images are effectively random (assuming
you are sampling the sky noise or the CCD readout noise) sequences,
which don't vary much. What is required is a compression algorithm that:
	a) works on a pixels (1,2,4,8 bytes depending on BITPIX) rather
		than single bytes
	b) encodes the difference between a pixel and its neighbour
		(which is small, and might normally be stored in a
		single byte)

Probably some other smarts are required as well, but compression
algorithms designed for text probably will never work effectively on
binary data. At least with the above system, the larger your pixel size,
the better compression you get! (BITPIX=16 images could only achieve
under 50% compression, BITPIX=32 might approach 75% compression)

P.S. my images tested above were 600x400x16bits - close enough to 0.5
MB in size.

Paul Brooks        |Internet: pwb at newt.phys.unsw.edu.au
Uni. of N.S.W.     |If you have trouble sleeping, try lying on the end of
Kensington NSW 2033|   your bed. With a little luck you'll drop off. 
AUSTRALIA          |                              - Mark Twain.

---

From: warnock at nssdca.gsfc.nasa.gov (Archie Warnock)
Date: 25 Sep 91 18:36:00 GMT

In article <2589 at usage.csd.unsw.oz.au>, pwb at newt.phys.unsw.oz.au (Paul W. Brooks) writes...
>which don't vary much. What is required is a compression algorithm that:

I claim that what is required is a set of algorithms to choose from.  
The variety of data representations is too varied to find a single 
algorithm which works in all cases.  Think bigger <ahem - so to speak>

---

From: warnock at nssdca.gsfc.nasa.gov (Archie Warnock)
Date: 26 Sep 91 14:09:00 GMT

In article <1991Sep25.234751.26451 at newshost.anu.edu.au>, markus at mso.anu.edu (Markus Buchhorn) writes...
>Uhmmm - 'scuse me - if you compress the header using <chosen-algorithm>
>then how can the decompression program know which algorithm you chose ?
>(You've compressed the keyword which actually tells you....)

Not quite.  Take your original FITS file, header and all, and compress 
it however you like.  Take the resulting byte stream and glue it onto a 
header.  The latter header is the one which gives the compression 
algorithm, along with the other information necessary to read the file.

>Some sort of magic-cookie at the head of the file ? or am I misinterpreting

Yep - another FITS header...  (sorry - I just had to...)

>I think that the FITSIO library written by .... [dang....sorry, forgotten]

Bill Pence.

>is going to become quite widespread. News I heard was that the FITSIO
>stuff was *very* popular. Thus the need for support is dropped onto
>only one person - and if people are prepared to help him, there shouldn't

Well, it seems that's the way lots of stuff is done these days - by 
contributed labor.  My hope/intention is that the "accepted" compression 
algorithms will be published so that anyone can code them up.  That is 
the purpose of the appendix in the compression proposal itself - to 
illustrate the process by publishing the first algorithm (PREVPIXEL).

>[BTW - have you put your comp. proposal docs up for ftp somewhere ? If you
>did (and announced it) then we're not getting all the messages down (up :-) ) 
>here in Australia :-( ]

Yep - Don Wells has posted it on fits.cx.nrao.edu.

---

From: tody at noao.edu (Doug Tody NOAO/IRAF CCS)
Date: 26 Sep 91 06:29:17 GMT