What image compression algorithm did the Voyagers use?

Question

Recently, Reed-Solomon error correction codes were discussed: How is stacking oranges in 24 dimensions related to receiving and decoding signals from the Voyagers?

Whilst the craft were between Saturn and Uranus the onboard software was upgraded to do a degree of image compression and to use a more efficient Reed-Solomon error-correcting encoding.

But being passionate about image compression, the second part of this upgrade interested me.

The above is supported by a reference to Voyager Telecommunications

Uncompressed Voyager images contain 800 lines, 800 dots (pixels) per line, and 8 bits per pixel (to express one of 256gray levels). However, much of the data content in a typical planetary or satellite image is dark space or low-contrast cloud features. By counting only the differences between adjacent pixel gray levels, rather than the full 8-bit values, image data compression reduced the number of bits for the typical image by 60% without unduly compromising the information. This reduced the time needed to transmit each complete image from Uranus and Neptune to Earth.

So it's a form of predictive coding.

However, this description is incomplete, because predictive coding does by itself not reduce bitrates. The residuals from a predictor extends the range to 9 bits per sample, though only the 8 least significant bits are necessary to recover the sample.

A wide range of residual coding options would have been available in the the early 1980s:

• Arithmetic coding (doubtful)
• Fixed tables of precalculated prefix codes (quite reasonable since residuals are known to be approximately Laplace distributed)
• Huffman coding
• Run length codes for near-zero residuals.
• Clamping residuals to a smaller range (crude lossy compression).

And even if not mentioned, chronologically this is also recent enough that some Lempel–Ziv variant could have been involved. Those are normally not all that great for photographic images, but if most of the image is dark space and no other entropy coding is used, it would have been a reasonable choice.

Even the choice of spatial predictor is left out, it just says "adjacent pixel gray levels".

Conceptually, I doubt anything more advanced than a LEFT predictor was used, but it could easily have been a NONE/TOP/LEFT mix. I don't think any gradient predictor were used, as this predates both the paper by Alan Paeth, and the general knowledge of the excellent ClampedGrad (LOCO) predictor.

Q: How did Voyager image compression work, in addition to being some form of predictive coding?

Answer 1

It would be nice to look at Voyager image data compression and block encoding by Urban, but it's paywalled.

It's described in Space Data Compression Standards though, which says

Robert Rice of the Jet Propulsion Laboratory devised an adaptive code for the Voyager mission,^6-10 which was extremely efficient in terms of detecting changes in data entropy and switching codes without requiring the compressor to maintain and update statistical information. The Rice algorithm is described in the boxed insert, The Rice Encoder Lossless Compression Algorithm.

The long and to me unintelligible explanation of the Rice encoder starts

The Rice encoder architecture (Fig. A) consists of a preprocessor stage that performs a predictive operation on the original data. The predictor will result in symbols that are centered about zero.

Please see the reference for the details.

Also described in Lossless Data Compression

(Note: I am not 100% sure this method was used for the images, it may have been just for scientific data. Please advise if this is not so, and I'll delete it)

Answer 2

I tried to look for a publicly accessible link to the Urban (1987) paper that was referenced in @Organic Marble's answer. Fortunately, it is publicly accessible through the University of Arizona: Voyager Image Data Compression and Block Encoding

From pages 5 and 6, we see that:

• the Image Data Compressor (IDC) is a universal noiseless coding compressor
• the algorithm, named FAST, is an adaptive split pixel compressor

Answer 3

Since Urban (1987) is available, I could look for the Details of IDC and FAST implementation missing:

1. What spatial predictor was used?

Simple scanline order pixel differences, or in other words a LEFT predictor.

2. What does "adaptive split pixel compressor" mean?

"Adaptive" here means they spilt the image into blocks and use different parameters for each block. "Split pixel" means they encode the least significant and most significant bits separately (where the split occurs is the configurable parameter). Why do such a thing? Well, that's because of the next item:

3. What form of Rice codes were used?

It turns out, the actual scheme implemented is a rather simple one: pick the split between LSBs and MSBs such that all set bits are on the LSB side. Then, use an appropriate code length, 1-6 or 8.

I would hesitate to call this "Rice coding", except that the ideas here are certainly due to Robert F. Rice.