Image compression

JPEG cuts an image into blocks of 8 by 8 pixels and describes each with as few numbers as it can. Watch two blocks below: the smooth one keeps 2 numbers out of 64, the one across an edge 27.

Smooth blocks need few numbers

A grey image of 128 by 128 pixels, one byte per pixel, takes 16 384 bytes. By this page’s estimate, JPEG’s standard setting needs about a tenth of that. Where do the savings come from?

The idea is one you met in The discrete cosine transform (13.6), in “Keep a few numbers, rebuild”. A smooth stretch of signal needs only a few DCT numbers. An image is mostly smooth stretches, with edges here and there. So JPEG spends its numbers where the edges are.

This page builds JPEG’s core in four steps: cut the image into blocks, take each block’s DCT, round the DCT numbers, and read them in a clever order. Real JPEG also handles colour; here every image is grey.

The test card on JPEG’s scale

I use the test card of Image filtering (28.2), from “What the weights add up to”. It is 128 by 128 pixels, with $x[n_1,n_2]$ the pixel in column $n_1$ and row $n_2$, as in Images as signals (28.1).

Its values run from 0 to 1. There is a gradient that brightens across, $0.25+0.35\,n_1/127$; a bright disc of 0.9; a dark square of 0.1; and a patch of diagonal stripes.

JPEG stores a grey pixel as a whole number from 0 to 255, so I multiply each value by 255 and round. On that scale the card runs from 26 to 230.

Then JPEG subtracts 128 from every pixel, so mid-grey becomes 0 and the values run from −102 to 102. This is the level shift.

Blocks of 8 by 8

JPEG does not transform the whole image at once. It cuts it into blocks of 8 by 8 pixels and treats each block on its own. The card has 16 blocks across and 16 down, 256 in all.

Why small blocks? A large transform would mix the sky at the top of a photo with the grass at the bottom. Inside a small block, the picture is usually either smooth or crossed by one or two edges.

Inside a block I count columns and rows from 0 to 7 again, and keep the names $n_1$ and $n_2$.

The DCT of a block

In “Rows first, then columns” of The 2-D DFT (28.3), a 2-D transform was a 1-D transform of every row, then of every column. JPEG does the same with 13.6’s orthonormal DCT: an 8-point DCT of each row of the block, then of each column of the result.

Written out, both passes together give

with 13.6’s weights for $N=8$: $w_0=\sqrt{1/8}$ and $w_k=\sqrt{2/8}=\tfrac12$ for $k\ge1$. Here $k_1$ counts cosine half-periods across the block and $k_2$ counts them down.

Each pair $(k_1,k_2)$ belongs to one little cosine pattern of 8 by 8 pixels. $X_\text{DCT}[0,0]$ is the flat pattern; its number is 8 times the block’s mean after the shift. Larger $k_1$ means finer stripes across, and larger $k_2$ finer stripes down.

13.6 showed that the orthonormal DCT keeps the energy. The same holds here, in both passes, so the 64 squared DCT numbers add up to the 64 squared pixels (after the shift).

Rounding with a table

Now the step that saves bits and loses detail. Each DCT number is divided by its own step $\Delta[k_1,k_2]$ and rounded, as in “Rounding to the nearest level” of Quantization & noise (11.1). The file keeps only the whole number

and the decoder later multiplies it back by $\Delta[k_1,k_2]$. As in 11.1, the rounding moves each DCT number by at most half its step.

The 64 steps form the quantisation table. The JPEG standard suggests this one for brightness, in its Annex K. Each row is one $k_2$, from 0 at the top, and each column one $k_1$, from 0 at the left:

The steps are small in the top left corner, from 10 to 16, and large towards the bottom right, up to 121. Fine patterns get coarse steps, because the eye notices errors in them less. Most fine-pattern numbers are small anyway, so a coarse step rounds them to 0.

The table is JPEG’s quality 50. The second instrument shows how other qualities scale it.

Reading in zig-zag order

The rounded block is 64 whole numbers, and most of the large ones sit near the top left. JPEG reads them in zig-zag order: start at the corner, step across, then sweep back and forth along the diagonals to the far corner.

The order runs from coarse patterns to fine ones. So a typical block’s sequence starts with a few nonzero numbers and ends in a long run of zeros. A coder does not write those zeros one by one. It writes “the rest are zero”, which costs almost nothing.

Two blocks of the card

Let’s try it on two blocks of the card, both at quality 50. The first is smooth: columns 96 to 103 and rows 8 to 15, on the gradient. The second crosses the disc’s edge: columns 48 to 55 and rows 16 to 23.

Think of describing a blank wall: one sentence does it. Describing a doorway in that wall takes several. The picture at the top of the page shows both blocks; watch how many numbers each one keeps.

Notice the smooth block’s sequence: 3, −1, then 62 zeros. Two numbers describe 64 pixels, to within a level.

Why the smooth block packs

Look at the smooth block’s pixels. Every row is the same: 131, 132, 133, 133, 134, 135, 135, 136. The gradient changes only across, so down each column the value does not change at all.

The two passes can run in either order, so take the columns first. A column with one value is flat, so its DCT down the column keeps only $k_2=0$. Every DCT number with $k_2\ge1$ is 0, and only the top row of the DCT grid survives.

That top row is 13.6’s story again: the DCT of one smooth row. The flat number is 45.0, the first stripe across is −12.31, and the other six are 1.50 or less in size.

The flat number alone holds 92.7 % of the energy, and with the first stripe 99.7 %.

Rounding finishes the job. $45.0/16=2.8$ rounds to 3, and $-12.31/11=-1.12$ rounds to −1. The six small numbers, divided by steps from 10 to 61, all land within 0.15 of 0 and round to 0.

The decoder multiplies back: 3 × 16 = 48 and −1 × 11 = −11, then runs the inverse DCT. Rounded to whole levels, every rebuilt pixel is within 1 level of the original, with an RMS error of 0.61 levels.

The edge block is the opposite case. The disc’s edge cuts across it on a slant, a jump in both directions. As 13.6 showed for a cliff in one row, a jump needs many cosines, and here it needs them across and down.

The flat number now holds only 31.1 % of the energy, and 27 numbers survive the rounding. Rebuilt and rounded, its pixels are within 35 levels of the original, with an RMS error of 15.7 levels.

So the bits go where the detail is. A smooth block costs two numbers, and a block with an edge costs many.

Fewer numbers, more blocks

One table gives one trade between size and error. JPEG lets you choose the trade with a single number.

Quality scales the table

The quality $q$ is a whole number from 1 to 100. The widely used library of the Independent JPEG Group turns it into a scale $S$, in percent:

The brackets $\lfloor\ \rfloor$ mean “round down to a whole number”, as the library’s integer division does. At $q=3$, for example, $5000/3$ is 1666.7, and $S$ is 1666.

Each step is the Annex K entry in the same place, written “table” below, scaled by $S$ percent. It is rounded to a whole number and kept between 1 and 255:

Adding 50 before rounding down makes the division round to the nearest whole number. The limits come from the file format: a step of 0 would mean dividing by 0, and baseline JPEG stores each step in one byte.

At $q=50$, $S=100$ and the table is unchanged. At $q=90$, $S=20$: the first step is 3 and the last is 20. At $q=10$, $S=500$: the first step is 80, and the last would be 495 but is held at 255. At $q=100$, $S=0$ and every step is 1.

Lower quality, coarser steps. Coarser steps round more numbers to 0, and the ones that survive are rounded more roughly.

Measuring the error

To compare qualities I need one number for the error. The mean-square error, $\mathrm{MSE}$, is the average over all pixels of (decoded − original)², in levels squared.

In “Signal and noise, in decibels” of How big is a signal (1.3), a power ratio became decibels as $10\log_{10}$ of the ratio. Images use the largest possible pixel, 255, in place of the signal’s size. The result is the peak signal-to-noise ratio:

Higher is better. Each 10 dB is a tenfold smaller MSE.

Measuring the size

How many bits would a file need? Count how often each stored number appears. A number that makes up a share $p$ of all of them can be given a code of about $-\log_2p$ bits. Common numbers get short codes, and rare ones long codes.

Averaged over all the numbers, that is the entropy:

in bits per number, where $p_v$ is the share of the numbers equal to $v$. For the smooth block alone, with 62 zeros, one 3 and one −1, a zero costs 0.046 bits, each other value 6 bits, and $H$ is 0.23 bits per number.

The instrument counts all 16 384 stored numbers of the card in one histogram. Each block has 64 numbers for 64 pixels, so bits per number are bits per pixel. The card’s pixels need 8 bits each, so the compression ratio is 8 divided by the bits per pixel.

This is an estimate. A real JPEG file adds headers and uses Huffman codes, so its size differs; I come back to this after the instrument.

What to look for

When the steps get coarse, a block may keep little more than its flat number. It then turns into a flat square, and its neighbour into a slightly different flat square. Steps then appear at the block borders, where the original image had none. These are blocking artefacts.

JPEG codes brightness, called luminance, separately from colour, and this card has only brightness.

Watch the zoom as the quality falls from 90 to 10: it stays sharp at first, and at 10 the 8 × 8 grid shows through as blocks.

Notice the top strip of the zoom at quality 10, the gradient above the disc. It has turned into flat squares, and its grey changes only on grid lines.

Reading the numbers

Here is the whole range. I computed these seven settings of the slider:

Down the table, as the quality falls, every column moves one way: fewer numbers, fewer bits, a lower PSNR. At quality 50 the card would take about 1655 bytes instead of 16 384.

Even quality 100 is not perfect. Its steps are all 1, but the DCT numbers are still rounded to whole numbers, so a little error remains: a PSNR of 66.2 dB, not an infinite one.

Now the blocks at quality 10. On the gradient, rows 0 to 7, the original climbs 0.70 levels per pixel. After coding, neighbouring pixels inside a block differ by 0.00 levels on average, and at the block borders by 5.33.

Where does that come from? At quality 10 the flat number’s step is 80. The flat number is 8 times the block’s mean, so a step of 80 moves the whole block by 10 levels. The finer numbers of these blocks all round to 0.

So each block on that strip is flat, and each border either jumps by 10 levels or not at all. Here 8 of the 15 borders jump, which averages 5.33. The gradient has become a staircase with treads one or two blocks wide.

The estimate looks at each stored number on its own. A real coder also uses structure: it writes runs of zeros as one symbol, and stores each block’s flat number as the change from the block before. So real JPEG files of this card would have different sizes. The trend with quality is the same.

Worked example

1. The smooth block’s flat number. The block’s mean is 133.625, so 5.625 after the shift. The flat number is 8 times that, 45.0. The step at quality 50 is 16, and $45.0/16=2.8$, which rounds to 3.

2. One stripe across. The smooth block’s $X_\text{DCT}[1,0]$ is −12.31. Its step is 11, and $-12.31/11=-1.12$ rounds to −1. The decoder gets back $-1\times11=-11$, off by 1.31, less than half the step.

3. A step at quality 10. $S=\lfloor5000/10\rfloor=500$. The first table entry gives $\lfloor(500\times16+50)/100\rfloor=80$, five times the step at quality 50.

4. PSNR at quality 50. The MSE over the card is 22.82 levels squared. Then $255^2/22.82=2849$, and $10\log_{10}2849=34.5$ dB.

5. Bits to ratio. At quality 50 the entropy is 0.81 bits per pixel. Against 8 bits per pixel, the ratio is $8/0.81=9.9$.

Where you’ll meet this

JPEG photos, from cameras and on the web, are coded in 8 × 8 blocks as on this page. In colour, JPEG first turns red, green and blue into a brightness and two colour-difference images. It often stores the colour ones at half the resolution across and down, since the eye sees colour detail less sharply.

Video codecs code some frames as still images, the intra frames, in the same way. H.264’s basic transform is a 4 × 4 integer version of the DCT, so it can be computed exactly with whole numbers.

MP3 and AAC use a 1-D cousin, the MDCT, on overlapping blocks of sound. Perceptual audio coding (29.3) takes that up.

JPEG 2000 uses the wavelets of Wavelets (23.2), with “Keep the big coefficients, drop the rest” as its core idea. It transforms the whole image, so it has no blocks and no blocking artefacts. Its artefacts at low rates are blur and ringing near edges instead.

I left out colour, the Huffman codes, and progressive JPEG, which sends a rough image first and refines it. For more, see G. K. Wallace, “The JPEG still picture compression standard” (Communications of the ACM, 1991), the standard itself, ITU-T T.81, and Gonzalez and Woods, Digital Image Processing, chapter 8.

Reference card