The H-transform

The image compression technique we are using is based on the H-transform (Fritze et al. 1977; see also Richter 1978 and Capaccioli et al. 1988). The H-transform is a two-dimensional generalization of the Haar transform (Haar1910). The H-transform is calculated for an image of size 2^N x 2^N as follows:

This calculation can be inverted easily to recover the original image from its transform. The transform is exactly reversible using integer arithmetic if one does not divide by 2 for the first set of coefficients. The extension of the definition of the transform so that it can be computed for non-square images that do not have sides which are powers of 2 is straightforward. The H-transform can be performed in place in memory and is very fast to compute,requiring only about 4 M^2 (integer) additions for a M x M image.

If the image is nearly noiseless, the H-transform is somewhat easier to compress than the original image because the differences of adjacent pixels (as computed in the H-transform) tend to be smaller than the original pixel values for smooth images. Consequently, fewer bits are required to store the values of the H-transform coefficients than are required for the original image. For very smooth images the pixel values may be constant over large regions, leading to transform coefficients which are zero over large areas.

Noisy images still do not compress well when transformed, though. Suppose there is noise sigma in each pixel of the original image. Then from simple propagation of errors, the noise in each of the H-transform coefficients is also sigma. To compress noisy images, divide each coefficient by S sigma, where S ~1 is chosen according to how much loss is acceptable. This reduces the noise inthe transform to 0.5 / S, so that large portions of the transform are zero (ornearly zero) and the transform is highlycompressible.

Why is this better than simply thresholding the original image? If we simply divide the image by sigma then we lose all information on objects that are within 1 sigma of sky in a single pixel, but that are detectable by averaging a block of pixels. On the other hand, in dividing the H-transform by sigma, we preserve the information on any object that is detectable by summing a block of pixels! The quantized H-transform preserves the mean of the image forevery block of pixels having a mean significantly different than that of neighboring blocks of pixels.

Coding the H-transform

The quantized H-transform has a rather peculiar structure. Not only are large areas of the transform image zero, but the non-zero values are concentrated strongly in the lower-order coefficients. The best approach we have found to code the coefficient values efficiently is quadtree coding of each bitplane of the transform array. Quadtree coding has been used for many purposes (see Samet 1984 for a review); the particular form we are using was suggested by Huang and Bijaoui (1991) for image compression.

This coding (which Huang and Bijaoui call ``hierarchic 4-bit one'' coding) is obviously very well suited to the H-transform image because successively lower orders of the H-transform coefficients are located in successively dividedquadrants of the image.

We follow the quadtree coding with a fixed Huffman coding that uses 3 bits for quadtree values which are common (eg. 0001, 0010, 0100, and 1000) and uses 4 or 5 bits for less common values. This reduces the final compressed file size by about 10% at little computational cost. Slightly better compression can beachieved by following quadtree coding with arithmetic coding (Witten, Neal, andCleary 1987), but the CPU costs of arithmetic coding are not, in our view,justified for 3-4% better compression.

For completely random bitplanes, quadtree coding can actually use more storage than simply writing the bitplane directly; in that case we just dump the bitplane with no coding.

Astrometric and Photometric Properties of Compressed Image

We have conducted experiments to study the degradation of astrometry and photometry on the compressed images compared to the original images (White,Postman, and Lattanzi 1992). Even the most highly compressed images have very good photometric properties for both point sources and extended sources; indeed,photometry of extended objects can be improved by the adaptive filtering of the H-transform (Cappacioli et al. 1988). Astrometry is hardly affected by the compression for modest compression factors (up to about a factor of 20 for our digitized Schmidt plates), but does begin to degrade for images with higher compression factors.