Compressing a still picture
An uncompressed colour picture is a grid of samples, and the grid is large. Gregory K. Wallace, writing up the JPEG proposal, put a digitised colour frame at television resolution on the order of a million bytes, and a frame at 35mm resolution at about ten times that. Capture can be cheap. The file can still be too heavy to keep or to send. Those bytes are pixels. From a model to a pixel follows one of them from the model to the screen. Compression is the later cut, when the same samples are asked to occupy less of the disk and less of the wire.
Two families do that cut. A lossless method puts every sample back. A lossy method does not. Archives, medical pictures, technical drawings, clip art and comics usually stay lossless, because a changed sample is a changed fact. A photograph can spend a little fidelity and shrink hard. If the difference is too small to see, the result is called visually lossless. Push the rate down and the damage is a thing you can point at: blocks, halos along edges, colour that has gone flat.
Wallace put the state of the art, in 1991, at roughly a tenth to a fiftieth of the raw size for a typical picture, with no change a viewer would notice. The fraction is a setting, not a law. The encoder has to let the user pick the trade.
What the eye will spare
A change in brightness is easier to see than a change in colour. Chroma subsampling keeps the brightness grid and averages, or simply drops, some of the colour samples. A second saving throws most colours out and keeps a short list. GIF and PNG can carry a palette, often 256 entries, written in the header. A pixel then stores an index into that list, not a red, a green and a blue of its own. Dithering scatters the rounding error as speckle, so a smooth ramp does not fall into flat bands. Block palettes go further and give a 4 by 4 patch only two or four colours. BTC, S3TC and their cousins do this, which is why a compressed game texture can look posterised up close and fine at a distance.
Eight by eight
Gregory K. Wallace set the winning method out in The JPEG Still Picture Compression Standard, Communications of the ACM, April 1991. He was convenor of the Joint Photographic Experts Group, at Digital Equipment Corporation. JPEG was joint work of ISO and CCITT, for continuous-tone still pictures, grey and colour. In June 1987 the group looked at pictures from twelve proposals and kept three. In January 1988 a second, stricter viewing picked the adaptive discrete cosine transform on blocks of 8 by 8. The years 1988 to 1990 went into writing the details, so that one maker's file would open on another's machine. When Wallace published, Part 1 was in committee-draft ballot: ISO/IEC CD 10918-1, begun in February 1991. Recommendation T.81, the ITU-T text of the same work, is dated September 1992.
The cosine transform is older than the committee. Nasir Ahmed, T. Natarajan and K. R. Rao published it in 1974. On an 8 by 8 block it replaces 64 samples with 64 coefficients. A smooth patch puts almost all of its energy in the first few, the low frequencies. Quantization divides each coefficient by a step from a table and rounds. That rounding is the loss. High-frequency coefficients, the ones a viewer is least likely to miss, often round to zero. The survivors are read in a zig-zag, which gathers those zeros into one long tail, and a Huffman code writes the runs. David A. Huffman published that code in 1952, in the Proceedings of the IRE. Arithmetic coding is the other entropy coder the JPEG draft allowed. The baseline sequential codec uses Huffman.
| Step | What happens |
|---|---|
| Shift | Unsigned samples become signed, centred on zero |
| Forward DCT | 64 samples become 64 cosine coefficients |
| Quantize | Each coefficient is divided by a table step and rounded |
| Zig-zag | The coefficients are reordered so the zeros clump |
| Huffman | Runs of zeros, and the values that remain, are coded |
Baseline order is a single scan, left to right, top to bottom. Colour is not a second algorithm. Each component is compressed as its own grey picture. The encoder may finish one component and then the next, or it may interleave 8 by 8 blocks from each component in turn. Before the transform, samples in the range 0 to 2P−1 are shifted into signed values. P is the bits per sample.
The draft specified three further ways to run. Progressive coding holds the coefficients in a buffer and sends several scans, coarse and then clearer. That is the behaviour a slow line wants: a recognisable picture first, the rest while you wait. Lossless coding returns every sample and compresses less. Hierarchical coding stores more than one resolution, so a small picture can be fetched without unpacking the large one.
Methods that put the samples back
Run-length encoding counts a value that repeats and writes the count beside it. PCX uses that as its ordinary method. BMP, TGA and TIFF can use it too. LZW, from Abraham Lempel, Jacob Ziv and Terry Welch in 1984, grows a dictionary of strings it has already seen. GIF, introduced in 1987, compresses with that dictionary, and TIFF can as well. DEFLATE, Phil Katz's method, specified in RFC 1951 in May 1996, is the compressor inside PNG, and also inside MNG and TIFF. PNG first predicts a sample from its neighbours and stores the error. DEFLATE then compresses the errors, which are smaller and more repetitive than the samples were.
A fax page was the older proof that one shared compressor can make a machine ordinary. CCITT Recommendation T.4, from 1980, is the Group 3 fax method. It compresses bilevel marks, ink or no ink. It does not compress a photograph. Wallace set JPEG against that limit: the same hope of one method for many makers, this time for a picture that has grey in it.
After the blocks
JPEG 2000 was prepared from 1997 to 2000. It drops the 8 by 8 cosine blocks. The lossy path uses the CDF 9/7 wavelet of Albert Cohen, Ingrid Daubechies and Jean-Christophe Feauveau, from 1992. The lossless path uses the 5/3 wavelet of Didier Le Gall and Ali J. Tabatabai, from 1988. In 2004 that family, Motion JPEG 2000 included, was selected as the picture coding for digital cinema. A hard squeeze of the older JPEG shows a grid because the transform never looked past the edge of its block. A wavelet spreads the error differently. It still throws information away when the bit budget is small.
Peak signal-to-noise ratio scores the sample error with one number. The 1987 and 1988 JPEG choices were made by looking, with the method hidden from the viewers. A file can win the ratio and still look false. A path in Scalable Vector Graphics never entered an 8 by 8 transform. Flat pictures: pixels, sprites, and vectors is the split between that list of shapes and the grid these algorithms shrink.