Part of How The Heck?, a series of interactive explanations of everyday technology designed primarily for curious, non-technical readers.
If you like these, you can follow the author, buy him a coffee, or suggest what comes next.
✨150,000+ views📊50+ bespoke visualizations📝40+ TL;DRs🤎25+ coffee donations
This is my cat, Dorito.
You may recognize her from a previous entry in this series about QR codes.
When my phone took this picture, it contained exactly 12,533,760 pixels. Each pixel is captured as three bytes: one each for red, green, and blue. That adds up to 37,601,280 bytes, or 37.6 megabytes.
Taking advantage of some math and how our eyes work, we can reduce this to about 1.5 megabytes with no perceptible loss of quality. The resulting file is a JPEG (which, as a good trivia question, stands for Joint Photographic Experts Group, the standards committee that created the format in 1992).
This piece will explore how we can lose so much data and still have a picture that looks just as good to us.
Information isn't the same as data
TL;DR
Data is about the raw representation of something, while information is about what's actually interesting in that data.
Colloquially, we use the words information and data interchangeably. But in information theory, they mean different things.
Data is the raw representation of something, like the 37.6 megabytes of pixels in our image. It doesn't matter if every pixel is the same color; when it's stored in my phone's memory, it's still 37.6 megabytes.
Information is about surprise. Consider an image of a crossword puzzle. Almost every pixel is going to be the same color as its neighboring pixels, all in their black and white squares. The actual information only happens at the thin lines where one square ends and the next begins. Most of the image, pixel after pixel, is just confirming what you already knew.
The goal of compression is to bridge that gap. If we can transmit data (the raw bits) with the same efficiency as the information it represents, we've compressed it.
Lossless and lossy compression
TL;DR
Lossless compression doesn't lose any information, while lossy compression does. Lossy compression gives us much bigger savings. JPEG is lossy, but uses both lossy and lossless techniques.
There are two main ways to bridge that gap: lossless and lossy.
Lossless compression is the process of reducing the size of data without losing any of the information it contains. If your friend sends you a picture, and your phone is able to perfectly reconstruct the original image, down to the last bit, then the compression used was lossless.
Lossy compression lets us cheat a bit. Instead of transmitting the exact data, we can transmit a simplified version that still looks like the original to our eyes. The tradeoff for this information loss is a much bigger file size reduction.
JPEG compression is a lossy algorithm, but it uses a combination of lossless and lossy techniques.
The simplest lossless trick: run-length encoding
TL;DR
The simplest trick there is: instead of storing a run of identical values one by one, store the value once and count how many times it repeats.
Imagine you're texting your friend a cheat code for a video game. The cheat code is AAAAAAAAAAAABBBBBBXXXXYYAAAA. Instead of writing out each letter, you notice five runs, so you text them 12A6B4X2Y4A (ideally in real life, they'd add spaces between the runs, but that's neither here nor there). Your text has gone from 28 characters to 11 without losing any information.
That's the idea behind run-length encoding (RLE). It works really well for patterns where there are long runs of the same value, but less well for patterns where the values change frequently. You can try it out below with different kinds of text. The catch becomes obvious pretty quickly.
Why do we need to store the 1 at all?
A real-world RLE format usually wouldn't store that 1 at all. It might reserve a special marker byte to mean "a run follows" and otherwise just write single values plainly, so the decoder only expects a count when it sees that marker.
Demo examples usually write the count, even for single-value runs, so you can see the overhead clearly.
A better lossless trick: Huffman coding
TL;DR
Give the most common symbols the shortest codes and the rarest ones the longest. Nothing is lost, and the total shrinks. This is the engine inside ZIP and PNG.
Before we can do better than RLE, we need to understand how computers store characters. There are different systems; in the common Extended ASCII system, a character like A is stored as a single byte made up of 8 bits (each a 0 or 1): 01000001.
Our video game code, AAAAAAAAAAAABBBBBBXXXXYYAAAA, is stored as 28 bytes in memory, or 224 bits. Huffman coding asks the question: why should every character, even the most common ones, be 8 bits?
By calculating the frequency of each character in our data and constructing a code that gives the shortest codes to the most common symbols, we can see massive savings without losing any information. Here's what the code tree looks like for our video game code:
| Symbol | Count | ASCII | Huffman |
|---|---|---|---|
| A | 16 | 01000001 | 1 |
| B | 6 | 01000010 | 00 |
| X | 4 | 01011000 | 011 |
| Y | 2 | 01011001 | 010 |
ASCII: 224 bitsHuffman: 46 bits
The code needs to be constructed in a specific way: no code can be a prefix of another code. Imagine a code where A is 0, B is 1, and C is 01. If you see 01, it's unclear if the the sequence is AB or C.
It's also worth noting that for this to work, the decoder also needs access to the same tree, so the compressed file must either include enough information to rebuild it or use a tree that both sides already know.
The interactive below shows the steps of constructing the Huffman tree for our video game code, or any other example you might want to try.
Huffman coding is key to the ZIP and PNG formats. And it's not the last time we'll see it in this piece!
Is Huffman coding mathematically optimal?
Huffman coding is the best possible prefix code, but not quite the theoretical best possible compression.
Huffman requires whole-bit codes, but the ideal code length for a symbol is rarely a whole number. A symbol appearing 90% of the time has an ideal length of about 0.15 bits, but Huffman cannot go below 1. That rounding wastes a little space.
Newer techniques like arithmetic coding close this gap by encoding an entire message as one number instead of symbol by symbol. Some modern formats use these instead of Huffman for exactly that reason.
You can read more here.
Introducing the YCbCr color space
TL;DR
Human vision is bad at fine detail and much worse at color than at brightness. Lossy compression exploits every one of those blind spots - starting by quietly discarding half the color.
There are multiple ways to represent pixels in an image, and JPEG takes advantage of that.
As the opening of this piece mentioned, JPEG usually starts by storing each pixel as 3 bytes using the RGB color space: one each for red, green, and blue. We can also represent pixels as 3 bytes using the YCbCr color space: one each for brightness, and two for color.
One orange pixel
#E69F00
RGB
red · green · blue
⇄
YCbCr
brightness · blue difference · red difference
Conceptually, you can think of this as each pixel separately storing information about its brightness and color, instead of the RGB values which mix together the concepts of brightness and color.
This turns out to be an extremely useful representation of color. The human eye is much better at detecting changes in brightness than it is at detecting changes in color, so we can throw away a lot of the color information without losing much in perception.
The reason we're so good at detecting changes in brightness is because our eyes have roughly 120 million rods per eye and only 6 million cones, which respectively give us our sense of brightness and color. We've evolved to be much better at detecting changes in brightness, likely because that was the most important trait for surviving at night.
Our first lossy trick: chroma subsampling
TL;DR
Neighboring pixels almost always share similar colors, so instead of storing color for every pixel, we can store one color sample for a small group and share it. This alone can cut color data by 75% with almost no visible difference.
With the YCbCr color space, we can start to apply techniques like chroma subsampling.
The idea is relatively simple: instead of each pixel storing its own color, we can group neighboring pixels and store an average color for that group. A color sample here means one Cb value and one Cr value.
- 4:4:4: Every pixel keeps its own color.
- 4:2:2: Every two horizontal pixels share one color sample.
- 4:2:0: Every 2×2 block of pixels shares one color sample.
- 4:1:1: Every four horizontal pixels share one color sample.
- 4:4:0: Every two vertically stacked pixels share one color sample.
- 4:1:0: Every 4×2 block of pixels shares one color sample.
- 4:0:0: No color samples are stored at all, leaving a grayscale image made only from brightness.
The three most common arrangements are 4:4:4, 4:2:2, and 4:2:0.
Here's an example showing what the chroma subsampling looks like in practice, using a 64x64 grid of pixels, where each pixel is enlarged to show the effect more clearly.
For a real photo, the effect will be much less noticeable than the exaggerated demo above. Here's chroma subsampling applied to our venerable calico. You'll notice that even with 4:2:0 subsampling, where we're reducing the color information by 75%, the overall image quality looks the same to the human eye. I couldn't tell the difference, even with magnification, until isolating the color channel separately and scanning around her eyes.
The DCT
TL;DR
Any signal can be rebuilt by stacking simple waves. The DCT rewrites a block of pixels as a recipe of those waves, which conveniently sorts the detail your eye cares about away from the detail it doesn't.
If you've read the previous piece on synths, this next part will sound familiar.
A signal, whether it's a sound or an image, can be rebuilt by stacking simple waves. The Discrete Cosine Transform (DCT) rewrites a block of pixels as a recipe of those waves, which conveniently sorts the detail your eye cares about.
Starting with one dimension
The easiest way to understand how JPEG uses the DCT in two dimensions is to start with one dimension. JPEG uses the DCT across all three channels (Y, Cb, and Cr), but we'll just focus on the brightness channel for the sake of example.
Imagine you have a row of 8 pixels, each with a brightness value between 0 and 255. The DCT mathematically comes up with 8 different patterns which can be combined in different ways to reconstruct any original sequence of 8 brightness values.
The patterns are fixed. Only the amount of each pattern changes.
Pattern 0flat
Pattern 1broadest wave
Pattern 2broad wave
Pattern 3medium wave
Pattern 4medium wave
Pattern 5fine wave
Pattern 6fine wave
Pattern 7finest wave
Intuitively, we can think of the eight patterns as transparent stencils. The stencils never change. The same eight are available for every row of eight pixels, but each has a "volume knob" that controls how strongly it contributes. Stack them at the right volumes, and they can recreate any original sequence of eight brightness values exactly. Mathematically, these volume levels are called "coefficients".
The example below shows a few possible stacks of the eight patterns, and the resulting brightness values.
How do we compute the patterns?
The fact that we need eight patterns for eight pixels is not a coincidence. With fewer than eight, there would be some rows we could never rebuild, while more than eight would be redundant.
Each pattern is generated by sampling a cosine wave at the centers of the eight pixels. For pattern k and pixel position n, the formula is:
JPEG uses cosines instead of sines because cosine patterns do not have to fall to zero at the edges, so they usually fit image blocks without introducing an artificial jump at the boundary.
You don't need to run this formula yourself to understand the concept. When k = 0, it produces a totally flat wave. There are no ripples at all, just a constant value, which is why the first pattern is flat. As k increases, the wave ripples faster, producing patterns with finer and finer detail, until k = 7 gives you the tightest possible ripple, alternating at every single pixel.
The key thing to notice is that this formula is fixed. It doesn't look at your image at all. It always produces the same eight stencils, every time, for every row of eight pixels, in any JPEG, of any photo, ever. Only the coefficients, meaning how much of each stencil to use, change from row to row. The stencils themselves never do.
In the "flat" example, why is the first coefficient 124 instead of 172?
Before running the DCT, JPEG shifts every brightness value down by 128, centering the range around zero. A flat row of 172s therefore enters the transform as eight 44s. Since the coefficient measures the amount of a normalized pattern rather than a pixel brightness, the first coefficient is 44√8, or about 124, rather than 172.
Then two dimensions
It's a bit trickier to visualize the DCT in two dimensions, but the idea is the same. We can pair each of the eight horizontal patterns from above with eight vertical patterns, resulting in 64 patterns in total, which can be combined in different ways to reconstruct any set of 64 brightness values.
Quantization
TL;DR
Once the DCT has sorted the important detail from the ignorable, quantization helps us round away the noise.
You might be wondering what the point of all of this is. Why is DCT useful if it just rearranges 64 brightness values arranged by pixel position into 64 other brightness values arranged by pattern coefficients?
The key is that we can use quantization to round away the noise, and then compress the result significantly using Huffman coding.
Quantization works by dividing each of the 64 pattern coefficients by a fixed amount, and then rounding to the nearest whole number. Coefficients for the later, finer patterns are divided by much larger numbers, meaning they get rounded to zero much more often, unless the 8x8 block truly is very noisy.
You can use the interactive below to click on the original photo to generate an 8x8 brightness value block, and then use the slider to adjust the quantization level. Notice that the more quantization you apply, the more the image looks blocky and pixelated, and that more and more of the patterns are rounded to zero and will be easily discarded with compression. This is the tradeoff.
How does the rounding work?
Say the DCT produces these eight numbers for one row, ordered from broad pattern to fine detail:
52, 8, -3, 1, 0.4, -0.1, 0.05, 0.01
Quantization divides each one by a number from a lookup table. That table uses bigger divisors for the finer patterns:
1, 2, 4, 8, 16, 32, 64, 128
Dividing and rounding to the nearest whole number gives us:
| Coefficient | ÷ Divisor | = Result | Rounded |
|---|---|---|---|
| 52 | 1 | 52 | 52 |
| 8 | 2 | 4 | 4 |
| -3 | 4 | -0.75 | -1 |
| 1 | 8 | 0.125 | 0 |
| 0.4 | 16 | 0.025 | 0 |
| -0.1 | 32 | ≈ -0.003 | 0 |
| 0.05 | 64 | ≈ 0.0008 | 0 |
| 0.01 | 128 | ≈ 0.00008 | 0 |
The result:
52, 4, -1, 0, 0, 0, 0, 0
Notice what happened. The three broadest coefficients survived as nonzero values, while every smaller coefficient rounded to exactly zero. This will compress very well, but we have lost information.
Different JPEG encoders will use different quantization tables, even when they claim to use the same quality setting. All of these tables, however, are based on the same idea of using larger divisors for the finer patterns. Or, in other words, stripping away the patterns we can't notice to save space.
Zigzag ordering
TL;DR
Instead of reading the 64 coefficients one row at a time, JPEG reads them in a zigzag pattern.
There's one last trick to help us compress the result even further. The 64 quantized coefficients from the previous step sit in an 8x8 grid, with the broad patterns in the top-left and the fine patterns in the bottom-right.
To try to get the most out of our compression, we want the zeros to be together, so the JPEG algorithm reads the coefficients in a diagonal zigzag pattern. The goal is to put the meaningful numbers together in the beginning, and the zeros at the end.
Consider this example of an 8x8 grid of coefficients, and a row-by-row sweep of it compared to a zigzag sweep.
Row by row
528-210000-32-1000004300000011000000-10000000000000000000000000000000
52,
8,
-2,
1,
0,
0,
0,
0,
-3,
2,
-1,
0,
0,
0,
0,
0,
4,
3,
0,
0,
0,
0,
0,
0,
1,
1,
0,
0,
0,
0,
0,
0,
-1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0
5 separate zero runs
Zigzag
528-210000-32-1000004300000011000000-10000000000000000000000000000000
52,
8,
-3,
4,
2,
-2,
1,
-1,
3,
1,
-1,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0
1 zero run
The zigzag pattern compresses all of the zeros together at the end into one long run. This is exactly the type of pattern that RLE works best with.
Combining everything
This was a lot of steps! Here's how the JPEG algorithm puts it all together:
- Convert the image from RGB to YCbCr.
- Apply chroma subsampling to the color channels, such as 4:2:0.
- Split each channel (Y, Cb, and Cr) into 8×8 blocks.
- For each block, apply the DCT to get the 64 pattern coefficients.
- Apply quantization to round away the noise.
- Read the coefficients in a zigzag pattern.
- Apply run-length encoding to compress the zeros.
- Apply Huffman coding to compress the remaining values.
In addition to all of the compressed bits, the JPEG file also needs to store the Huffman codes and the compressed coefficients. The file itself is organized into sections called markers, with each one holding a piece of the puzzle. One marker holds the Huffman codes, another holds the compressed data, etc.
One marker even holds EXIF data, like the camera settings and timestamp. Platforms like Instagram strip this away when you post there.
There are newer image formats that are more efficient at compressing photos, such as WebP and AVIF. There are lossless formats like PNG, which also supports transparency with an alpha channel. There are animated formats like GIF, which support multiple frames.
But JPEG has been the standard for decades, with billions of photos taken and saved with it every day. At that scale, saving orders of magnitude more space is what keeps our internet affordable. And now you know how it works!