Image compression.

You'd be forgiven for thinking that compressing an image is the same as compressing other pieces of data. After all, images are just data, right?

Well, yes and no. We can borrow some of the same techniques, but the rules of what constitutes valuable information are based on human visual perception, and so we can exploit some very specific characteristics of human vision to make images smaller.

╌╌╌╌

When compressing information like text, we are only really interested in using techniques that perfectly preserve the original information, known as lossless compression⁷. When it comes to stuff like images, video and audio, we can exploit the fact that our senses are imperfect and throw away parts of the information that we don't notice anyway, known as lossy compression⁸.

With images in particular, we can leverage the fact that we are much better at seeing detail in luminance⁹ than detail in chrominance. We can also take advantage of the fact that our brain automatically removes high frequency visual noise, known as spatial averaging.

JPEG

By far the most popular image format in use today is JPEG, short for Joint Photographic Experts Group after the group that created the standard in 1992. The reason for its popularity is that it's a lossy format that can achieve a 10:1 compression² ratio without too much noticeable degradation. It's also adjustable, allowing you to select the amount of compression, and therefore loss in fidelity.

You can imagine that in the early 90s that sort of compression was crucial to being able to transmit and store images in a bandwidth and memory constrained world. Like we discussed in the chapter on digital images^↗, an image file on your computer doesn't contain the image data in a way that you could recognize.

Rather it contains the compressed data encoded by the JPEG format and every time you view that image, your computer is decoding the data back into pixel data using the JPEG format. This means that your computer, or browser, needs to have the ability to decode JPEGs in order to properly read the file. Luckily, it has been the standard for decades and is baked into every operating system and browser.

More so than any other image format, JPEG takes advantage of the quirks of human perception to throw away information while largely preserving quality. Most of this saving comes from the fact that we are much less sensitive to changes in color than in luminance. The first step in JPEG compression is important for that reason, it converts the RGB¹¹ pixel data into the Y'CbCr¹² color space.

Y'CbCr is a color space with separate channels for Luma (Y'), blue-difference (Cb), and red-difference (Cr), effectively isolating the color information from the luminance information. The blue-difference and red-difference channels are a bit tough to get your head around, but basically it's the difference between the blue or red component and the Luma. We don't store the Green component directly but we can work it out from the other information.

The important thing is that we have separated out the color information so that we can compress it more than the luminance information. The next step, Chroma Subsampling¹ is all about doing just that, and it begins by dividing the image up into 8 pixel groups consisting of two rows of 4 pixels.

If we imagine this little block as two columns, each consisting of two rows we take the color value from the first pixel in each row and apply it to the next pixel, halving the amount of color information. If we want to be more aggressive, we can split the block into two columns and use the color value from the top-left pixel for all four pixels in the column.

Remember, this is happening in Y'CbCr, so we do this for the blue-difference and red-difference chroma channels separately. We can get away with this because there is likely not a great difference between pixels so close together here, unless we happen to be on some type of edge. This is why we don't resample a larger area as the likelihood that we'll flatten some details is higher.

The next stage is by far the most complex to understand but it's also the thing that makes JPEG so effective. We begin by dividing the image into 8x8 pixel blocks and map the pixel values so they range from -128 to 127, instead of 0-255. Remember, we are doing this on each channel separately and this time we are using the Luma channel.

Okay, before we can understand what's about to happen, we need to understand a bit about cosine waves. Let's imagine two 1D cosine waves that oscillate between 1 and -1, with the second wave having a higher frequency than the first. We can add those two waves together to create a new wave that is a weighted average of the two.

Now imagine we have some 1D signal on a graph that represents the pixel intensities of one row of eight pixels in one of these blocks, and our goal is to recreate that signal using only cosine waves of different frequencies. Because we have eight sample points we only need eight cosine waves of different frequencies to approximate the original signal.

So instead of storing the original signal, we could store which cosine waves we used to recreate it and their weights, because we might need some waves to have more influence than others. This isn't helpful for this toy example but if we had a much longer signal, we could split it up into chunks of 8 samples and represent each sample as a sum of these same eight cosine waves.

This is called a Discrete Cosine Transform (DCT)³ and it's exactly what we are going to do to those 64 pixel blocks, except we are doing it in 2D. We only need 64 cosine waves to approximate these blocks, which we can visualize as images with shades of gray, where white is 1 and black is -1. This is why we remapped the values in the blocks to be centered around 0, because a cosine wave is centered around 0.

So we go through each block and work out how to recreate it based on a weighted sum of patterns from this DCT table, known as the DCT II table. What we are left with is 64 coefficients, which tells us how much each one of these patterns influences the 64 pixel block.

Because of the way images tend to work, the low frequency patterns tend to have larger coefficients and the high frequency patterns have smaller coefficients. That's because images tend to have less high-frequency information in them, or less sharp changes in intensity especially in such small blocks.

We can leverage this to reduce the amount of data needed to recreate the block. The idea is that because the patterns with the smaller coefficients aren't contributing much to the block, we can effectively flatten them and not lose too much quality. This process of removing small coefficients is called quantization¹⁰.

The way we do this in JPEG is with a quantization table, which is a block of 64 values that we use to divide the coefficients for our patterns. A larger value in this table means that the corresponding pattern will have less of an effect on the block, and for patterns with small coefficients they will go to 0. The quantization table is arranged in such a way that the high frequency patterns will be diluted more than the low frequency patterns.

If we compare our coefficient tables before and after quantization, you can see that a lot of the coefficients are now 0 and the idea is that with just the remaining patterns we can get pretty close to our original pixel values.

When we change the quality of a JPEG we are changing the values in the quantization table to make them larger, for more quantization and less quality, or smaller for less quantization and higher quality. It's really in this step that we permanently lose information because there's no way for us to figure out the original values after they've been quantized.

The last step is to write this data to the file by running it through a Huffman⁵ encoder, like we spoke about in the chapter on compression^↗. We serialize the values in a zig-zag pattern, starting from the top-left and ending in the bottom right, so that we end up with a long string of 0s in a row which will compress nicely.

Remember we've been operating on each channel separately, so we might quantize the color channels more than the luminance channel. When we write the image data for each block, we first interleave the different channels into one long byte stream that is fed to the encoder. So the first 64 values will be the luminance, the next 64 values will be the blue-difference, the next will be the red-difference and after that are 64 luminance values for the next block and so on.

Okay so we've encoded our JPEG, but how do we decode it? Well it's the same process in reverse. We decode our Huffman string to get the channel values for each block and then we multiply them by the same quantization table we used to encode them. This is important because any difference on the table will corrupt our image.

So after that, we have a table of coefficients except this time we use a slightly different DCT table, called DCT III which is an inverse of the DCT we used in the encoding process. This will give us back a block of pixel values that are mapped between -128 and 127, known as a shifted block, which we can then remap to 0-255 and recreate our image.

If we look at the block of pixels we fed into the encoder and the block we got out of the decoder, you can see that almost none of the values are the same but they are all fairly close to the original. We've definitely lost data but because the differences are small, we largely don't notice.

There's some stuff I didn't go into here, like the JFIF or EXIF file containers we store the image data in, or the fact that we store the DC and AC DCT patterns separately but they are not very important nor very interesting.

GIF

The Graphics Interchange Format, introduced by CompuServe in 1987, is actually one of the first attempts to create an image container that could be used across different types of computers. It has two primary components: an indexed color system and the Lempel-Ziv-Welch (LZW) compression algorithm.

The primary way GIF compresses an image by limiting the number of colors in a given frame to 256. These 24-bit colors are stored in an indexed color⁶ lookup table and the actual pixel data contain an 8-bit index for this table, which is already a 3:1 compression ratio. The process of reducing the colors in the image is called quantization, similar to the quantization we spoke about with JPEG in that it reduces high frequency information.

But how do we reduce the number of colors in the image down to just 256 while still preserving the most important colors? Well there are a few algorithms to do this but the most interesting is called the Median Cut algorithm, which is a way of recursively sorting data.

Imagine all the colors in our uncompressed images plotted on an RGB cube. The first step is to draw a hypothetical box that fits all the colors and work out which axis is the longest, or which component has the widest range of values.

If, in our case, the widest range is the red axis we arrange all of our color values in a list with the red values in order, from 0 - 255. We then split the list at the median red value, creating two boxes.

We then recursively do the same thing for each of these two new boxes: determining the widest axis, re-arranging the values by this component value, splitting them at the median and creating two new boxes.

In our visualization we stop at 8 boxes but in reality we only stop when we have 256 boxes and then we turn each box into a color by averaging all the original pixel values that fall inside that box.

Median cut does a pretty good job at reducing the colors of an image in a way that matches the original data because it allocates more colors to the parts of the image that take up the most space. But any aggressive quantization like this will create harsh steps between colors, so we apply some dithering⁴ to diffuse the blocks of color. Dithering helps improve the visual quality but it also makes the compression step less efficient.

Anyway, so now we have a list of at most 256 24-bit colors that we store in our table and we replace the pixel data with an 8-bit pointer, or index, to a specific color in that table. We scan through the original pixel data looking up which box from our Median cut algorithm the color value falls in and replace it with a pointer to the average color we calculated for that box.

We've already compressed the image a fair bit just by quantizing it but we're not done. What we're left with now is a long sequence of values between 0-255 which we are going to feed through one of the family of Lempel-Ziv algorithms, the Lempel-Ziv-Welch (LZW) algorithm.

We covered the LZ-77 and LZ-78 algorithms in the chapter on compression, so I won't go into as much detail here, but the LZW algorithm builds on LZ-78. It's also a dynamic dictionary encoding method, so it's looking for long strings of characters that repeat and replacing them with pointers to the original string.

It starts with a dictionary of 8-bit characters, so values between 0-255, which is perfect for us because we have exactly 256 color values. It then creates another empty dictionary for repeating character strings that starts at 9-bits long, so from values between 258-512 (256 and 257 are reserved codes).

Imagine we had a pixel stream that looked like this: [28, 28, 24, 28, 28, ...]. When the algorithm initializes, it set the Current string to empty and begins scanning the next pixel, K. Every time it reads a new pixel value it asks the same question - does Current string + K exist in the dictionary?

Because Current string is empty and we know that K will be a value between 0-255 we know we have dictionary entry for it, 28. In this case, we can just leave 28 there but we update the Current string to include K making it 28.

We then read the next pixel and ask the same question which will now be "do we have a dictionary entry for the string 28-28"? The answer is no, so we create a new entry at 258 : 28-28 and reset the Current string to just be K.

The next time there is a sequence of 28-28, we'll have that in the dictionary already and use the code 258. But the algorithm keeps going, trying to match the longest possible sequence of strings, so the next dictionary entry will be 259 : 28-24 and then 260 : 24-28.

After this, we finally arrive at a sequence we've seen before and so we can replace it with a code from our dictionary: [28, 28, 24, 258, ...].

This works well for areas with large blocks of the same color, which thanks to quantization is likely to happen in a GIF. It's possible to replace a run of 100 red pixels with just a single 12-bit code, which is why GIF works particularly well for logos and illustrations.

If you're smarter than me, you might have noticed something problematic with our new sequence [28, 28, 24, 258, ...]. The issue is we are expecting each pixel value to be 1-byte, or 8-bits, long but 258 is 9-bits long. The compressor and decompressor know, based on the dictionary size, how wide the largest code will be and so it uses that information to pack the bits into 8-bit chunks.

If we have two 9-bit codes, A and B, and we need to pack them into 8-bit bytes we begin by putting code A into the first byte, using the least significant bits, or the ones on the right, first. This means that Byte 0 will look like this: A7 A6 A5 A4 A3 A2 A1 A0.

We take the leftover bits from code A and pack them into Byte 1 with bits from code B: B6 B5 B4 B3 B2 B1 B0 A8.

We keep overflowing like this so Byte 2 looks like this: ?? ?? ?? ?? ?? ?? B8 B7.

The encoder splits the file up into blocks of 255 bytes prefixed by a length byte so the decoder can parse the stream without needing to know the file size in advance.

So that's how a GIF is compressed. You might be thinking that we store those expanded dictionaries in the file to decompress it, but we don't. Instead we allow the decompressor to work out what the original code must have been using the same logic.

The decompressor reads the string [28, 28, 24, 258, ...] and when it encounters 258, a value not in the core dictionary, it knows it must be the first set of repeating characters 28-28 and reconstructs the string to be [28, 28, 24, 28, 28 ...]. Smart huh?

Of course GIFs can be animated and so the compression and decompression happens for each frame in the sequence. The same for the quantization step, which can create local color tables for each frame.

PNG

The company that owned the LZW algorithm, Sperry Corporation (later Unisys), patented it in 1981 and forced any software that could compress or decompress GIFs to pay for a license to do so in the early 90s once they realized GIF used the algorithm. In fact, IBM was also granted a patent in 1983 because the US Patent and Trademark Office didn't realize it was the same algorithm which is funny.

Anyway, that patent enforcement pissed off a lot of people who had been using the format for free and so they started developing alternatives. This is how the Portable Network Graphics (PNG) format was born - out of spite, which is my favorite way to develop things.

The developers of PNG wanted to create a new format that would surpass the compression of GIF while being lossless and allowing for true colors. It's made up of a two step pipeline: Prediction (or Filtering) and DEFLATE compression.

The prediction step exploits the fact that in most natural images, like photographs, the values of adjacent pixels tend to be quite similar. So instead of transmitting the raw pixel values, it transmits the difference between the current pixel and a predicted value derived from neighboring pixels.

This means that the sequence of values sent to the compressor isn't distributed randomly between 0-255, but rather has distribution that is clustered tightly around 0 in a Laplacian distribution that looks like this. This lowers the entropy of the pixel stream making it easier to compress.

PNG has 5 filtering methods that it can switch between on the fly based on the pixels in the current scanline:

0. None – no modification.
1. Sub – the horizontal difference.
2. Up – the vertical difference.
3. Average – the average between two neighbors.
4. Paeth - a local gradient predictor.

For simplicity, let's just work with a single channel - the filters technically work on each channel but we'll come back to that later - using the same sequence of values from the GIF example: [28, 28, 24, 28, 28, ...]. The Sub filter is pretty simple, it transmits the difference between the current pixel and the pixel to the left of it. If there's no pixel to the left, we assume a value of 0 for that pixel. This means our sequence becomes [28, 0, -4, 4, 0, ...].

The Up filter does the same, but uses the pixel value directly above the current pixel. If we imagine the row above our sequence looks like this [28, 28, 25, 26, 28, ...], our sequence would become [0, 0, -1, 2, 0, ...]. You wouldn't want to use the Up filter on the first scanline so the ability to change filters per scanline is quite important.

The Average filter combines the Up and Sub filters by subtracting the current pixel value from the average of the pixel values to the left and above. For our example this would produce the sequence: [14, 0, -2, 3, 0]. Note, we have to use a floor() function to round the value to the nearest integer.

The Paeth filter is more complicated and works out a value based on the gradient between the values of the pixels to the left, above and top-left. This interpolates a value based on those three values and we then subtract that from our current value.

Earlier I mentioned that the filter operates per channel, but it actually just operates per byte, and our image data contains a byte per channel: R G B A R G B A .... When we are applying a filter to a byte, we need to know where to jump in the stream to find the vertical or horizontal neighbors of that byte.

After we filter the image, we are left with a string of values that has a lower entropy than our original pixel data and so we can feed this into the compression algorithm. PNG uses the DEFLATE algorithm which is a composite of the LZ77 algorithm and Huffman Coding. We covered both in the compression chapter but I'll rehash some of that here.

The first stage is LZ77 which, like the LZW algorithm, tries to replace repeating sequences of characters with pointers to the original strings. It works slightly differently, instead of creating a dictionary entry it replaces repeating strings with two numbers: the distance to the original string and the length of the string.

The way it does this is using a sliding window to look at the last 32KB of data and compare it to the current symbol, asking "have I seen this before?". If it hasn't, it just uses the literal value but if it has it inserts a pointer instead. The result is our stream is a mix of literal values between 0-255 and pointers (length, distance).

We then feed this stream into two separate Huffman encoders to generate two trees, one for the literal and length values and one for the distance values. I go into Huffman Coding in more detail in the compression chapter, but to summarize it creates a binary tree based on the probabilities of a symbol, or how often they appear in the stream, and uses that tree to assign variable length codes to those symbols.

The result is that we get very short codes for the symbols that repeat a lot and long codes for the rare symbols. The idea behind generating separate trees for the literal/lengths and the distance is that they can be optimized independently. If you have a file with many short matches nearby, the distance tree will be highly optimized for small numbers.

The decompression step runs everything in reverse. First we decode our Huffman trees back into literals and pointers, then the LZ77 decompressor reassembles our repeating symbols and lastly we invert the filters. Every step is lossless so we end up with the exact same image we fed into the compressor.

There are some drawbacks to PNG though. A high resolution photograph tends to contain a lot of noise, small high frequency variations in pixel intensities due to sensor noise, and LZ77 has a tough time compressing this because it can't find any patterns to match. This is an inherent downside of lossless compression of random high frequency data.

The filtering process is also fairly slow, because the encoder needs to figure out which of the filters to use for each scanline to produce the best result. Some encoders will encode the entire image five different times, once with each filter, and then determine which filter produces the best result for each scanline. Obviously, this is computationally expensive for large images.

WebP

Historically, if you wanted to transmit an image on the internet you had to make a choice between lossy JPEG and lossless PNG but in 2010 google developed a hybrid format called WebP, presumably named after the WebM video codec it is based on. The original version actually only contained a lossy algorithm but they added a lossless variant a year later. We'll talk about the lossy version first.

WebP is great because it steals techniques from a bunch of other formats. Like I mentioned it is based on the WebM, or VP8, video codec and specifically the way VP8 performs intra-frame compression, or the compression inside a single frame. The first stage is called MacroBlocking and looks remarkably similar to the first stages of JPEG.

First, we convert the image into the YCbCr, which is similar to the Y'CbCr color space we used in JPEG except that the Y component isn't clipped. Next we split each component up into 16x16 macro blocks, but for the two chroma components we downsample them into 8x8 blocks, effectively throwing away 75% of the color information. This is exactly the same idea as the chroma subsampling we saw in JPEG.

The next phase is where things get clever by performing a similar prediction filter to PNG, except we predict these blocks instead of rows. It takes the blocks for each component and looks at the row of pixels directly above that block and the column directly to the left - these values are coming from other blocks.

Whereas PNG does this prediction filter per pixel, WebP predicts that value of the whole block. There are four basic prediction modes which are very similar to the PNG filters:

1. Horizontal – copies the left column values.
2. Vertical – copies the top row values.
3. DC - fills with an average of the top row and left column
4. True Motion - creates a gradient between the top row and left column.

In practice, it tries each prediction mode, compares the result to the original and chooses the one with the lowest error. For the luminance component, it then subdivides the blocks into 4x4 squares and tries 10 different prediction modes for each of the four squares which will give a higher quality approximation of the original image.

Now the encoder tries to work out whether to keep the predictions of the 4x4 blocks or use the prediction of the larger 16x16 block. It does this by calculating the cost, which is function of the error, or distortion, and the amount of bits required. The 4x4 predictions might give a lower error but require too many bits to make the tradeoff worth it. Again, this subdivision only happens in the luminance channel.

For areas with lots of high frequency detail, it might stick with the smaller blocks whereas areas of low frequency detail it'll stick with the larger blocks. So after this we have a collection of blocks containing the differences between the predicted value and the original value and the next step is to feed those blocks into DCT.

Notice the difference between WebP and JPEG here - in JPEG we feed the shifted pixel values into the DCT but in WebP we are feeding it the difference values. Because the predictions are pretty good, our values are often going to be smaller than the original values.

The DCT stage is a bit more complicated here. WebP uses a 4x4 DCT because although we have 16x16 blocks we apply the DCT to 16 smaller sections which contains the artifacts to a smaller area (we occasionally have to run some special transforms if we have a large luminance blocks). This DCT also only uses integers to avoid some floating point issues we get when using the traditional one.

Similar to JPEG, we quantize the DCT matrix to reduce the coefficient sizes and the results are sent to a boolean arithmetic compressor in the same zig-zag pattern.

We discussed arithmetic compressors in the chapter on compression, so I won't go into too much detail about that here, but it represents each block as a range of numbers between 0 and 1. The smart thing about the VP8 Boolean Arithmetic Coder WebP uses is that it is context adaptive and so can update its probabilities based on the blocks it has just seen. If the 4x4 block to the left was full of complex detail, the probability of this block being complex is high, and if it was empty the probability of this block being empty is also high.

Okay, so that's the lossy WebP algorithm which is like a neat hybrid between PNG and JPEG, but how does the lossless version work? Well the answer is that it basically doesn't use anything from the lossy version, instead it's like an improved version of PNG where there are two steps: transforms and compression

The one part it does keep from the lossy version is the prediction transforms, where the image is split up into 16x16 blocks and the same prediction modes are applied to create the difference between the prediction and original values. After that it applies some color transforms to try reduce the entropy in the color information.

This leverages the idea that in most images the red, green, and blue channels for a given pixel are highly correlated. Basically, if the green channel is bright, it's highly likely that either the red or blue channels is also bright. So to take advantage of this, it preserves the green channel but transforms the red channel to be Red - Green and the blue channel to Blue - Green. The result is that the red and blue channels will be full of smaller numbers which compress well, but we can easily decompress the original values.

After the transforms we send the grid of difference values through an LZ77 algorithm to compress redundant patterns and then a Huffman encoder to further compress the LZ77 symbols. So far this is just like PNG, but things get a little weird here. Instead of one giant Huffman tree for the whole image, we split the image up into 16x16 blocks and generate Huffman trees based on these blocks.

We don't create Huffman trees for each one, rather we analyze the contents of each block and group together ones with similar values. So all the blocks that contain the sky might use the one Huffman tree and all the grass ones might use a different one, typically ending up with 10-30 Huffman trees per image.

Part of this process is creating something called an entropy map - we calculate the entropy of each block to group together similar blocks and this entropy map tells the decoder which huffman tree to use. In practice, this looks like a low resolution version of our image, where each pixel is a block.

So why do all this? Well it means we can optimize the size of the Huffman trees. A large one for the whole image would end up with a ton of long code values while generating one for each block would take up a lot of space. This is like a perfect middle ground.

To decompress this, the decoder looks at the entropy map and selects the correct Huffman tree. We then decompress the LZ77 strings and undo all the transforms by adding the red and blue channels back and adding the differences from the prediction modes back to get our original image.

Now that WebP is widely supported by browsers and operating systems, there's really no downside to using it. It's much more flexible than JPEG or PNG and offers better compression than both of them.

╌╌╌╌

Phew, okay so that's image compression. It was a long one, so if you made it down here well done. I say this about a lot of stuff, but image compression is one of my favorite things to learn about. I think it's a bit easier to understand than text compression because it is a little less statistics based and sometimes quite vibes based.

╌╌ END ╌╌