Quantization

1Why an image is large

A digital photograph is a grid of pixels, and each pixel is three numbers giving the intensity of red, green and blue. At the common depth of eight bits per number, a single pixel costs twenty-four bits, and an image of twelve million pixels costs around thirty-six megabytes before anything is done to it. That figure is the problem this document addresses. It is too large to store in quantity and too large to send quickly, and it has been too large for as long as digital images have existed.

There are two ways to make the figure smaller, and the distinction between them organises the whole subject. Lossless compression records the same image in fewer bits by exploiting statistical regularity, so that the original can be reconstructed exactly. Lossy compression goes further and reconstructs only an approximation, having permanently discarded some of the original information. Lossless methods are essential where exactness is required, in medical imaging or in a archival master, and they achieve compression ratios for photographs of perhaps two to one. Lossy methods routinely achieve ten or twenty to one, and sometimes far more, which is why nearly every photograph encountered in ordinary use is stored in a lossy format.

The reason lossless compression is limited for photographs is worth stating precisely, because it motivates everything that follows. Claude Shannon's 1948 theory of communication [1] established that a source of data has an entropy, a quantity of genuine information measured in bits, and that no lossless code can represent the source in fewer bits than its entropy. A photograph of a natural scene, considered as a stream of pixel values, has a high entropy: adjacent pixels are correlated, which a good lossless coder exploits, but the fine variation of a real scene is close to random and cannot be coded away. To compress a photograph substantially, one must abandon exactness, and the question becomes which information to discard.

That question has a good answer only because the consumer of the image is a human eye, and the human eye is a specific and imperfect instrument. It does not record what a camera records. It is far more sensitive to changes in brightness than to changes in colour, and it is far more sensitive to coarse structure than to fine. An image carries information that the eye, presented with the result, simply cannot use. Lossy compression is the systematic identification and removal of that information, and the next section begins with the first and simplest instance of it.

2Colour, brightness and the eye

The red, green and blue values of a pixel are a convenient way for a display to emit light, but they are a poor way to think about what a viewer perceives, because perception does not treat the three channels equally. A more useful representation separates a pixel into one channel of brightness, called luma, and two channels of colour, called chroma. The conversion is a fixed linear transformation, and it is reversible, so nothing is lost in performing it. What it provides is a separation: it places the information the eye cares about most, the brightness, into a single channel by itself.

The value of the separation is that the two chroma channels can then be treated more harshly than the luma channel. The human visual system resolves fine detail in colour considerably less well than it resolves fine detail in brightness, a fact that can be confirmed by noticing how a coloured caption remains legible chiefly because of its brightness contrast with the page. Because of it, the chroma channels can be stored at reduced spatial resolution, typically at half resolution in each direction, while the luma channel is kept intact. This is chroma subsampling, and it discards half or more of the colour data before any transform coding has begun.

The figure compares an image at full colour resolution with the same image after subsampling. The effect on most scenes is difficult to see, which is the entire point: the data removed was data the eye was not going to use. The mode named 4:2:0, which halves the colour resolution both horizontally and vertically and so retains a quarter of the original colour data, is the default in JPEG and in most video, and its near-invisibility is the clearest possible demonstration of the principle that organises this document. The sections that follow apply the same principle, the removal of imperceptible information, but they apply it to the luma channel, where it requires considerably more machinery.

3A history of image compression: a literature review

The method described in the remainder of this document was assembled over four decades, and each of its parts was a response to a definite shortcoming of what came before. This section traces that sequence. As in any literature review the aim is causal: to record not merely what each contribution did, but which earlier limitation it was meant to remove.

The foundation is Shannon's 1948 result already cited [1], which fixed the entropy of a source as the hard limit of lossless coding. The practical instrument for approaching that limit arrived four years later in David Huffman's construction of a minimum-redundancy code [2]. Huffman's algorithm assigns short codes to frequent symbols and long codes to rare ones, in a way that is provably optimal among codes that assign a whole number of bits to each symbol. It remains in use, and it is the entropy-coding stage at the end of the JPEG pipeline. What it cannot do is compress a photograph by a large factor, because, as the previous section argued, the entropy of the raw pixels of a photograph is high.

A second family of lossless methods, the dictionary coders of Ziv and Lempel [3] and the variant of Welch [4] that became the basis of the GIF format, compress by replacing repeated sequences with references to earlier occurrences. They are effective on text and on images with large areas of identical colour, and they are ineffective on photographs, for the same reason: a photograph contains few exactly repeated sequences. By the early 1970s it was clear that substantial compression of photographs required lossy methods, and that a lossy method needed a representation in which the perceptually important and the perceptually negligible parts of an image were separated, so that the negligible parts could be identified and removed.

Transform coding is that representation. The idea is to apply a mathematical transform that re-expresses a block of pixels as a sum of standard patterns, because in the transformed form the slow, broad variation that the eye depends upon is separated from the fast, fine variation to which the eye is largely blind. The optimal such transform for a given source, the Karhunen-Loève transform, is statistically ideal but has a disqualifying practical cost: it depends on the statistics of the particular image and must be recomputed for each. The contribution of Ahmed, Natarajan and Rao in 1974 [5] was to show that the discrete cosine transform, a fixed transform that does not depend on the image and that admits a fast algorithm, approximates the Karhunen-Loève transform closely for the kind of correlated data that natural images provide. The discrete cosine transform made transform coding affordable, and it is the subject of section four.

The discrete cosine transform was carried into universal use by the Joint Photographic Experts Group, whose standard was issued in 1992 and is described in the survey by Wallace [6]. JPEG fixed a complete pipeline: convert to luma and chroma, subsample the chroma, divide each channel into eight-by-eight blocks, apply the discrete cosine transform to each block, quantize the coefficients against a standard table, scan them into a sequence and code that sequence with run-length and Huffman coding. Every component had been known; the standard's achievement was to assemble them, fix the details, and so make a JPEG file readable everywhere. The format's ubiquity is the reason it is the worked example of this document.

JPEG also has a well-understood weakness, and it follows directly from one of its design choices. Because the image is divided into independent eight-by-eight blocks, and each block is quantized on its own, the reconstructed blocks do not in general agree at their shared edges, and at low quality the eight-by-eight grid becomes visible as a pattern of blocking artifacts. The wavelet transform, developed in a form suited to images by Mallat [7], offered a way past this: a wavelet analysis is inherently multi-resolution and is applied to the image as a whole rather than to isolated blocks, so it has no block grid to expose. The JPEG 2000 standard [8] was built on it and produced visibly better images at low bit rates, free of blocking. It nonetheless saw little adoption, for reasons that were practical rather than technical: it was computationally heavier, it arrived after JPEG was entrenched in every camera and browser, and the improvement, though real, was not large enough to overcome that inertia.

The more recent formats took a different route to improvement. WebP, and later the AVIF format [9], are derived from video codecs, and they import from video coding a technique that JPEG lacks: intra-frame prediction, in which a block is first predicted from the already-decoded pixels along its top and left edges, and only the prediction error is transformed and quantized. This attacks precisely the redundancy that JPEG's independent blocks ignore, the strong correlation between a block and its neighbours. A further line of work, the learned image compression of Ballé and colleagues [10], replaces the fixed transform and the fixed quantization with a transform learned by a neural network and optimised, end to end, for the trade-off between file size and perceived quality. The pattern is by now familiar from any survey of a maturing field: a hand-designed component, once its limitations are understood, is replaced by one that is learned.

4The discrete cosine transform

JPEG divides each channel of an image into blocks of eight pixels by eight, and it processes each block independently. The first operation applied to a block is the discrete cosine transform, and its purpose is to change the description of the block without changing the block itself. Before the transform, a block is described by sixty-four pixel values, one brightness at each position. After it, the block is described by sixty-four coefficients, and each coefficient is the amount of one fixed pattern that must be added to reconstruct the block. The transform is exactly reversible. No information has yet been lost; the block has only been re-expressed.

The fixed patterns are the basis functions, and the figure below displays all sixty-four of them. They are products of cosine waves of increasing frequency. The pattern at the top-left corner is a constant, a uniform grey, and its coefficient records the average brightness of the block; it is called the DC coefficient, after the constant component of an electrical signal. Moving to the right, the patterns oscillate more rapidly from left to right, describing finer horizontal detail. Moving downward, they oscillate more rapidly from top to bottom. The pattern at the bottom-right corner is the finest available checker.

The reason this particular re-expression is useful is that the coefficients of a natural image are not equally important to a viewer. The patterns near the top-left, the low frequencies, carry the broad tonal shape of the block, the part of it the eye attends to most. The patterns near the bottom-right, the high frequencies, carry the finest texture, the part to which the eye is least sensitive. Moreover, for an ordinary photographic block, the low-frequency coefficients are typically large and the high-frequency coefficients typically small, because natural images vary smoothly far more often than they vary sharply. The transform has therefore concentrated most of the block's energy into a few coefficients, and it has done so in a way that aligns with what the eye values. That alignment is what the next two sections exploit.

5One block through the pipeline

It is worth following a single block through the whole sequence of operations before examining any one of them in detail, because the sequence is short and its shape is easier to hold in mind than its parts. The figure below carries one eight-by-eight block from its pixels, through its transform, to its reconstruction.

The first panel is the block as pixels. The second is the block after the discrete cosine transform and after quantization, the step described in the next section; each cell is one coefficient, and a cell drawn empty is a coefficient that quantization has set to zero. The third panel is the block reconstructed from those quantized coefficients by the inverse transform. The two numbers reported beneath the figure are the count of coefficients that survived as non-zero, and the root-mean-square difference between the reconstruction and the original.

The figure repays a particular experiment. Select the gradient block and lower the quality: the count of surviving coefficients falls quickly to a mere handful, and the reconstruction error stays small, because a smooth gradient genuinely is the sum of a few low-frequency patterns and the discarded coefficients held almost nothing. Now select the texture block and repeat: the surviving count falls more slowly and the error grows faster, because the texture's energy was spread across the high frequencies that quantization attacks first. The method is not equally kind to all content. It compresses smooth regions almost for free and charges a real price for fine detail, which is the behaviour section eight will show at the scale of a whole image.

6Quantization: the step that loses information

The discrete cosine transform of the previous sections lost nothing; it was exactly reversible. Quantization is the step that does the discarding, and it is the only lossy step in the JPEG pipeline. It is also, for that reason, the operation the format quietly named, and the one this document is named for.

To quantize a coefficient is to divide it by a chosen integer and round the result to the nearest whole number. The rounding is the loss: once a coefficient has been divided by, say, forty and rounded, the original value cannot be recovered, only a multiple of forty near it. Coefficients that were smaller than half the divisor round to zero and are gone entirely. The divisors are not uniform across the block. They are read from a quantization table of sixty-four entries, and the table is deliberately gentle on the low-frequency coefficients, with small divisors that preserve them well, and harsh on the high-frequency coefficients, with large divisors that round many of them away. The table is, in effect, a numerical statement of the eye's diminishing sensitivity to fine detail.

The quality setting that every JPEG encoder exposes is a single number that scales the whole table. At a high quality setting the divisors are small, few coefficients are lost, the reconstruction is faithful and the file is large. At a low setting the divisors are multiplied up, most of the high-frequency coefficients and some of the low-frequency ones round to zero, the reconstruction is visibly degraded and the file is small. The quality slider in the figure of section five, and in the figure of section eight, is exactly this scaling. There is no separate mechanism for trading quality against size in JPEG. There is only the coarseness of this rounding.

Why zeros are the goal

Quantization is valuable not only because a rounded coefficient carries fewer distinct values, but because it produces runs of exact zeros. A run of zeros costs almost nothing to record, as the next section shows. The art of the quantization table is to drive as many coefficients as possible to zero while disturbing the ones the eye depends on as little as possible.

7The zig-zag scan and entropy coding

After quantization a block is sixty-four integers, most of them zero, and the zeros are not scattered at random. Because the quantization table rounds away the high frequencies, the surviving non-zero coefficients are concentrated at the low-frequency corner of the block, near the top-left, and the bottom-right region is typically all zero. The final stage of the pipeline is the lossless coding of these integers into a compact stream, and it is designed around that concentration.

The first step is to read the two-dimensional block into a one-dimensional sequence, and the order in which it is read matters. A simple row-by-row scan would repeatedly cross from the low-frequency region into the zero region and back. The zig-zag scan, shown in the figure, instead traverses the block in diagonal sweeps, moving systematically from the low-frequency corner toward the high-frequency corner. It therefore tends to read all of the non-zero coefficients first and then a single long, unbroken run of zeros.

That unbroken run is what the coding exploits. Two lossless techniques are applied to the scanned sequence. Run-length coding replaces a run of identical values with a single value and a count, so that the long tail of zeros becomes a single end-of-block marker rather than dozens of separate symbols. Huffman coding, the minimum-redundancy code of section three, then assigns short bit patterns to the common symbols and longer ones to the rare. Neither step loses any information; they are the lossless final compression of a result that quantization has already made highly compressible. The zig-zag scan is the small, elegant hinge between the lossy part of the pipeline and the lossless part: it costs nothing, and it arranges the quantized block into precisely the shape that run-length coding rewards.

8A whole image, and its artifacts

An image is compressed by applying the pipeline of the previous sections to every eight-by-eight block in turn. The figure below does this to a complete test image and shows the original beside the reconstruction, under a quality slider that scales the quantization table. The error view amplifies the difference between the two so that the loss, which at moderate quality is hard to see directly, can be inspected.

At high quality the reconstruction is faithful and the difference is confined to the finest texture. As the quality is lowered, two characteristic kinds of damage appear, and both have their explanation in the sections above. The first is blocking. Because each eight-by-eight block is transformed and quantized independently, the reconstructed blocks no longer meet smoothly at their shared edges, and the eight-by-eight grid emerges as a visible mosaic, most plainly in regions that should be smooth. This is the weakness that the literature review identified as JPEG's structural cost, and the reason the wavelet-based formats were developed.

The second kind of damage is ringing. Near a sharp edge, a strong light-to-dark transition, the reconstruction shows faint ripples running parallel to the edge. The cause lies in section four. A sharp edge is built from many high-frequency coefficients acting together, and when quantization removes or coarsens some of them, the remaining coefficients reconstruct the edge imperfectly, overshooting and undershooting around it. The error view makes both artifacts explicit: the error concentrates on the block boundaries and along the edges of shapes, and it is small in the smooth interiors, which is the same unevenness of treatment that the single-block figure of section five showed in miniature.

The compression ratio reported beneath the figure is an estimate, drawn from the count of coefficients that survived quantization rather than from a full entropy coder, and it should be read as indicative rather than exact. Its trend, however, is the real lesson: as quality falls, more coefficients are driven to zero, the estimated file shrinks, and the error grows. That trade-off, between the size of the file and the fidelity of the image, is the whole of lossy compression, and the quality slider is the reader's hand on it.

9Conclusion

Lossy image compression begins from a fact about its audience. The eye is sensitive to brightness more than to colour, and to coarse structure more than to fine, and an image therefore carries information that its viewer cannot perceive. The method this document has followed is the disciplined removal of that information. Colour is separated from brightness and stored at lower resolution. Each block of the image is re-expressed by the discrete cosine transform as a sum of patterns ordered from coarse to fine. Quantization then rounds the coefficients, gently where they describe the structure the eye depends on and harshly where they describe detail it does not, driving most of them to zero. The zig-zag scan and the entropy coders turn the result, losslessly, into a compact stream.

The literature review placed this method in a sequence. It was made possible by Shannon's account of the entropy bound and by Huffman's optimal code, it was made affordable by the discrete cosine transform, and it was made universal by the JPEG standard. Its one structural weakness, the visible grid of its independent blocks, prompted the wavelet-based formats, and its lack of prediction between blocks prompted the codecs derived from video. The most recent work replaces the transform itself with a learned one. A reader who has followed the argument here holds the fixed point of that history: every later format is a different answer to the same question this document has posed, which is how to find the information in an image that no one will miss, and how to spend the fewest bits on the rest.