Subject: Thoughts from WGAS -- compression and nesting extensions

From: warnock at Hypatia.gsfc.nasa.gov (Archie Warnock)
Date: Fri, 19 Jun 1992 19:21:34 GMT

I've been thinking about our data compression proposal since the WGAS
meeting last week, and talking to some people about possible
modifications.  Here are some semi-random thoughts for discussion...

1.  Chris Biemesderfer recommends changing the optional "logical"
keywords (LAXIS, LBITPIX, etc), so that the first character is a "U"
(for uncompressed), and so that the "U" character is just prepended to
each of the keywords which go in the header for the uncompressed data.
This has the advantage of being extensible (i.e., there could
conceivably be other characters used for other extensions and/or coding
schemes) and mnemonic.  I like it.

2.  As I mentioned at the WGAS, Bill Thompson has pointed out that the
proposal will no work for lossy compression schemes (which Immanual
Freedman calls "approximate" compression schemes - I like that
terminology), since the current proposal calls for compressing the
entire original data stream, header and all.  I'm not sure what to do
about this.  There's a certain beauty in uncompressing the bitstream and
getting a fully-qualified FITS data stream out of it (hey - it's
recursion... I always {\em knew} there had to be a use for it besides
calculating factorials :-).  The difficulty lies in figuring out a way
to save the header(s) which go along with the resulting uncompressed
data, but not necessarily required by the compressed stuff.

The current proposal calls for compressing the headers with the data
because that ensures that they're retrieved when the data is
uncompressed, and that they're unambiguously associated with the
uncompressed data.  I claim it doesn't matter if the compression
algorithm doesn't work well for the headers - if the data volume is such
that the header is roughly the same size as the data, it's probably not
a good candidate for compression anyway.

Now... here's an idea which addresses some of these issues, but I warn
you that I don't know how to cast it into FITS yet.  What is probably
sufficient, if not necessary, to allow a solution to the problem is to
develop a scheme to allow extensions to be nested.  Here's why - if we
can do that, we can make the first extension indicate compressed data,
and within that, nest the headers necessary for documenting the
compressed data, tables, etc.  The question is, how would such a syntax
be built?  Suppose the next data record after an extension header were
another extension header (with due care taken in specifying the values
of keywords related to the length of the data)?  Tractable?  

----------------------------------------------------------------------------
-- Archie Warnock                   Internet:  warnock at hypatia.gsfc.nasa.gov
-- Hughes STX                       "Unix --- JCL For The 90s"
-- NASA/GSFC                        

-- 
----------------------------------------------------------------------------
-- Archie Warnock                   Internet:  warnock at hypatia.gsfc.nasa.gov
-- Hughes STX                       "Unix --- JCL For The 90s"
-- NASA/GSFC

---

From: thompson at stars.gsfc.nasa.gov (William Thompson, code 682.1, x2040)
Date: Fri, 19 Jun 1992 22:25:00 GMT

In article <1992Jun19.192134.8051 at nsisrv.gsfc.nasa.gov>,
warnock at Hypatia.gsfc.nasa.gov (Archie Warnock) writes...

>  ... (deleted stuff) ...
> ... (more deleted stuff) ...
>

As far as I'm concerned, anything is allowed to be stored in the data records
of a FITS extension, so long as the total number of records used can be
calculated from the BITPIX, NAXIS*, PCOUNT and GCOUNT keywords.  Software that
doesn't know how to read that kind of extension should be able to simply skip
over it.

One simple way of doing this that I thought of, after reading this, would be to
store the header after the compressed data array.  The PCOUNT keyword could be
used to give the number of bytes in the stored header.  I haven't thought
everything out yet, but there would have to be keywords signalling that there
was or was not a stored header to go with the compressed data, and maybe a
keyword signalling where the header started in the parameter area, similar to
THEAP for binary tables.  One might want to start the stored header on a
2880-byte record boundary.

When I talked to Archie, I understood that he was thinking about using nested
headers for other things besides the data compression.  I don't want to get
into what those could be, but at first blush it seems to me that one could
store anything in the parameter field, including another complete FITS file if
one wanted to.  The FITS readers could get pretty hairy, but there's no reason
in principal why it couldn't be done.

Bill Thompson

---

From: warnock at Hypatia.gsfc.nasa.gov (Archie Warnock)
Date: Mon, 22 Jun 1992 14:07:32 GMT

In article <19JUN199218254599 at stars.gsfc.nasa.gov>, thompson at stars.gsfc.nasa.gov (William Thompson, code 682.1, x2040) writes:
|> One simple way of doing this that I thought of, after reading this, would be to
|> store the header after the compressed data array.  The PCOUNT keyword could be
|> used to give the number of bytes in the stored header.  I haven't thought
|> everything out yet, but there would have to be keywords signalling that there
|> was or was not a stored header to go with the compressed data, and maybe a
|> keyword signalling where the header started in the parameter area, similar to
|> THEAP for binary tables.  One might want to start the stored header on a
|> 2880-byte record boundary.
|> 

I sorta like this idea.  Let's think on it a bit and see if anyone else
leaps into the fray, too.  It's been kinda quiet around here anyway...

|> When I talked to Archie, I understood that he was thinking about using nested
|> headers for other things besides the data compression.  I don't want to get

Well... it really wasn't that specific, but I felt that a general
technique for nesting extensions would _allow_ using it for other things
- in the best FITS tradition of extensibility.

The first name in FITS is "flexible", after all...

---

From: forveill at gag.observ-gr.fr (Thierry Forveille)
Date: Mon, 22 Jun 1992 19:45:05 GMT

>Archie Warnock writes

I certainly support the idea of only compressing the data, but I don't
like the idea of dumping the header after the data. After all a header
is supposed to be at the head... More seriously, a usefull feature of
FITS is that one can type the file on just about any terminal, look at
the header, and ctrl C before binary stuff starts appearing. This
become impossible if one has to skip a few megabytes of binary data.
Of course I can write a program to skip the data, but then why keep
the header as formatted card images?
I would thus rather advocate storing the header before the data (of course
starting on a record boundary), and using a keyword to signal where the 
compressed data start.

>The first name in FITS is "flexible", after all...

but the third one is "transport"... Flexibility should not be such that nobody
(may be including the originator!) can read back the data.
It should thus be a basic rule that extensions are only added if they are
needed, and when they are needed. Compression doesn't seem to need nested
extensions, so let's wait till something needs it.

One point in the compression proposal which is unclear (at least to me) is
what is supposed to be compressed: a FITS file or an extension? It looks
to me as if the extension is the natural unit for compression, if only
because different algorithms will probably be needed for different extensions
(one wouldn't want to use previous pixel compression on a ASCII table, which
could well be as large as the data).

Another point which I would like to see discussed is semi random access to the
compressed data. One application I have in mind would involve compressing
binary tables which have about 200 rows, each of which has a size of roughly
1 (uncompressed) megabyte. Even though this is obviously a good candidate for 
compression (there would be a few thousand of them...), I would rather not
have to decompress 100 megabytes each time I access one row. One possibility
that I have considered is adding an index to the compressed stream before
the data, probably as a separate binary table in the same fits file, but
I would be interested in a standardized solution if that exists, and would
otherwise like to learn about existing solutions to this problem (maybe at
STScI for the digitized POSS??)

	Thierry Forveille
	Observatoire de Grenoble
	forveill at gag.observ-gr.fr