Transcription
What you see here is one part of a really elaborate process that defines the universally used JPEG image compression format. JPEG is rather complex, and in this video, the majority of the focus will be on understanding how computer scientists came up with an algorithmic and mathematical framework for solving the complex problems that image compression presents.
But to understand the motivation behind the ideas in JPEG, we'll have to dive into the inner workings of the many components involved. The perspectives we'll take will be a little bit unorthodox, but my hope is that you come away with a better understanding of the big themes in image compression, which apply to other compression-related problems. It's not an exaggeration to say that these concepts are used every time you open an image, play a video, or listen to some music. As we go through JPEG, we'll interact with the wide variety of beautiful ideas in the world of data compression and signal processing that make the technology around us possible.
Before we dive into JPEG, let's talk about how computers represent images. The standard color space that computers use is the RGB model. Every pixel of an image stores three values from 0 to 255, with higher values representing a larger weighting of the respective color. So, assuming each color component is expressed in 8 bits, or a single byte of memory, an image has 3 bytes per pixel. Here's an image with a little more than 5 million pixels. Based on our assumptions, the total size of this image should be about 15 megabytes. But with JPEG compression, the actual file is only 0.8 megabytes. Same number of pixels, but 5% of the expected size, and the image looks absolutely beautiful. This is the real magic of JPEG compression. JPEG aggressively takes advantage of several clever ideas to achieve seemingly ridiculous amounts of compression with minimal effects on the quality of the original image.
One of the primary reasons JPEG works so well is it uses lossy compression. To understand what that means, let's think about compression from a big picture perspective. We start with an RGB representation of an image, and then we encode it using a compression algorithm. This is what we store in memory, and it's more compact, but quite different than our original RGB representation. So, part of a compression scheme requires also defining a decoding component that converts the stored representation of our data into the RGB format that a computer can render as an image. Part of the JPEG standard is defining how both the encoding and decoding work. A key point in JPEG is that the final decoded image is not going to be the same as the original uncompressed image. That's why we call it lossy compression. In the compression part of the pipeline, we are going to deliberately lose information to get compression. On the levels of 5%, there's really no other option other than to actually discard some information from our original image.
Now, the fun question to ask is, what sort of information from an image can we get rid of, and how do we get rid of it? Answering this question is going to be the primary focus of our journey into understanding JPEG.
Here's an interesting image for you. If I were to ask you what colors the squares of A and B were, I imagine most of you would quickly say that A is a darker shade of gray than B. But what if I told you that A and B were actually the same color? It's okay if you don't see that. This picture is designed to trick our visual system. But once we have a connector of the common color between the two squares, it's much easier for us to see that they are in fact the same color.
So, what's going on here? Over the years, scientists have developed a human visual system model through the study of our eyes. And one incredibly interesting finding through experimentation is that our eyes are much more sensitive to brightness than they are to colors. And part of the JPEG compression scheme can take advantage of this. But to understand how, we have to dive into the world of color spaces.
As we've discussed, the RGB color space is a combination of red, green, and blue color components. If we put each value on a separate axis in a three-dimensional space, we can see how all the possible colors are just a point on this cube. One aspect of RGB color space is, as you progress on the diagonal from the origin to the color 255, 255, 255, you get gradually brighter colors. And in fact, the exact line between these points defines all possible grayscale colors, which are a direct measure for brightness.
This idea of separating brightness is core to another color space called YCbCr. YCbCr stands for Y (luma), Chroma Blue, and Chroma Red. Our Y component is going to measure the luma, or brightness, of an image, and our Cb and Cr components are going to encode the colors. If we look at the color space, the Y can be thought of as a single vertical axis, with larger values encoding more brightness. Every cross-section of the space defines a range of colors at that particular brightness. For our purposes with JPEG, using the color space gives us direct access to the part of color that our eyes perceive best. As a result of being more sensitive to brightness than colors, one idea to compress our original image involves sampling less of the CbCr components and keeping all of the luma components. The technique is referred to as chroma downsampling, or more commonly, chroma subsampling.
Suppose I have this 8x8 image, which has the following Y, Cb, and Cr components. The key idea of chroma downsampling, or subsampling, is to take fewer samples from Cb and Cr components since our eyes are less sensitive to them. Here's one approach that defines a 4:2:0 chroma downsampling scheme. We go through our original 8x8 image in 2x2 blocks and simply average the group of pixels to get a shared value of the four pixels in the original image. Averaging the pixels, by the way, is all downsampling really means. Chroma subsampling is the same exact idea, but instead of averaging, we just choose one of the samples, usually the top-left pixel, to be the color of the entire 2x2 block.
Once we have these fewer samples from the color components, we can merge them with the luma component, which will retain the original 16 pixels, and this gives us our subsampled image. In this case, you can see quite a difference since our 8x8 pixel image is significantly scaled up. But in real-world images, it's often hard to see any changes after subsampling. By merging 2x2 blocks on the Cb and Cr channels into one color, we are left with a quarter of the original data in each color channel, shrinking the total file size by 50%. We're still quite far from the 5% levels that we saw in JPEG, so we're going to have to exploit more than just human perception of brightness for the following components of JPEG.
Let's focus on the Y channel, which essentially defines grayscale images. The principles we'll discuss from here on out will also apply to the color components of an image. The next clever idea in JPEG requires looking at images in a completely different perspective, one that can be a little bit counter-intuitive.
One way to think about images is treating them as signals. If I slice a particular row of an image, I essentially have a row of pixels, each with some value between 0 and 255. If we plot these values, we can get an approximation of a signal. Visualizing an image as a signal allows us to talk about frequency components within an image. Higher frequency components correspond to rapid changes between pixels, while lower frequency components are related to smoother changes between pixels.
There are two key aspects of frequencies within images that are incredibly important to JPEG compression. The first is that a lot of real-world images shot from cameras are mostly composed of lower frequency components. In other words, if I take a random portion of a realistic image, it's pretty likely that the pixels in that area do not change that rapidly. And the second key fact is that from a variety of experiments, the human visual system is generally less sensitive to higher frequency detail in images. JPEG takes advantage of these ideas by strategically removing less important and less common higher frequency components from an image to achieve even more compression.
But there's one big problem: how do we get frequency components from an image? This is where some particularly clever and beautiful math comes into play. The answer to this question lies in a special operation called the Discrete Cosine Transform, or the DCT.
The DCT works for any size input, but to simplify things, let's focus on an input of 8 pixels, just as we did earlier. Let's suppose these 8 pixels form some sort of signal. We'll never be sure what exactly the signal looks like since we only have 8 points. But the clever and definitely not obvious idea of the DCT is to represent these eight points as sums of sample points from cosine waves. And I really want to emphasize the fact that we only care about the discrete samples. Visually, I think it's nice to see the continuous signals and cosine waves, but throughout our discussion, the only values that really matter are the sampled points from these functions.
The DCT takes an input of sampled points from our original signal and gives us an output of the same size. We'll refer to the outputs of the DCT as coefficients. These coefficients represent the weights of cosine waves of different frequencies that contribute to the original signal. A nice analogy is to think of this as unraveling a complex signal into a weighted sum of simpler cosine waves. If you've never interacted with this type of idea before, it's natural to be confused. What cosine waves do we even use? How do cosine waves relate to pixels on an image? None of it makes any sense. Don't worry, these are important questions that we will answer.
Let's start simple and talk about cosine waves. Here's a graph of cosine from 0 to pi. I've given you this general notion that the DCT is supposed to tell us how much of a specific cosine wave is contained in a signal. So let's test this out. What happens if I provide an actual cosine wave as the input signal to the DCT? What do we expect to happen? Okay, we can try this, but there's a problem. To follow our existing example, we need eight sampled points from the cosine wave to make this work. How exactly should we sample the cosine wave? Well, there are a few options, but let me present to you the most common one. What we can do is split our cosine wave's domain into 8 even slices and then we take the midpoint of each of these slices. This gives us the following input points, which we can generalize for any number of points, but for our purposes, we'll stick with the smaller n=8 example.
So, going back to our question, what should we expect the output to be when we pass in sample points from a standard cosine function? This is an interesting experiment. When we pass these points from a cosine wave into a DCT transform, we get the following output. Only one coefficient has a non-zero value, meaning there's only one cosine wave that contributes to our input, and that seems to make some sense since the input is literally from a cosine wave. In this case, the first index is the only coefficient with a non-zero value. When trying to understand complex ideas, it really helps to play around with these simple examples.
A cool follow-up to our experiment is to see what happens when we change the amplitude of this cosine wave. The first index DCT coefficient increases. If we flip the cosine wave by multiplying by -1, the DCT coefficient changes sign. It's exactly acting like a weight for a cosine wave. When the amplitude of the input cosine wave changes, the weight correspondingly reflects that change.
So, taking a step back, how does this relate to images? Well, just as we took images and represented them as signals, the reverse also works. Standard grayscale images have pixels ranging from 0 to 255. The intuition with cosine waves to images makes more sense when we shift the range of pixel values by 128. With pixel values from -128 to 127, we can see a better mapping between this cosine wave to an actual set of 8 pixels. This particular wave is a nice way to represent a row of gradually decreasing pixel values, and the magnitude of that change, as well as the direction of the change, is reflected in the amplitude of the original cosine wave and, consequently, the DCT coefficient.
So, let's continue this experiment to see what else we can uncover about the DCT. We've messed with the amplitude of a cosine wave. What other parameters could we change? A simple one is to just shift the cosine wave up or down. Let's see what happens when we try that. It looks like shifting up or down the signal only affects the zeroth index coefficient. That's an interesting data point that we'll come back to.
Another parameter of cosine waves is the frequency. What we're going to do now is show the DCT coefficients as we wind up the frequency of this cosine wave. I'll keep the sampling strategy we discussed earlier consistent among all frequencies. Let's see what happens as we increase the frequencies. We get a few different DCT coefficients for the respective cosine wave. That is, until we get to this cosine wave. For this particular cosine wave, only the second index has a non-zero coefficient. This cosine wave is actually just double the frequency of the previous cosine wave. This is super interesting. The first index of the output seems to nicely correspond with the cosine wave of frequency 1, while the second index correlates with a cosine wave of frequency 2.
Let's continue this experiment of increasing frequencies, but before I continue, see if you can take a guess at what frequencies the other coefficients will correspond to. Here we go. We slowly increase the frequency, and boom! The index 3 coefficient corresponds to a cosine wave of frequency 3. Then frequency 4 comes next, and this pattern continues until we get to a cosine wave of frequency 7. Pretty insane, right? So, for the coefficients indexed 1 to 7, it looks like they represent the weight on a cosine wave with the frequency that matches the index.
So, what about the remaining index zero? We saw shifting cosine waves up and down led to a change in the zeroth index. What cosine wave does that represent? Some of you have probably figured it out, but if you think about what a zero-frequency cosine wave is, it's just a constant signal. What that means in terms of images is it gives us a measure of the overall brightness of a set of pixels. Brighter images will have a larger zero-to coefficient than darker images. This is why shifting up a cosine wave only impacts the zeroth coefficient.
Putting this all together, each of these frequencies correspond to a different pattern of images, and what the core DCT does is break down how each of these fundamental patterns contribute to the original image. And it turns out that all possible combinations of 8 pixel values can be represented as a sum of these eight cosine waves. Why that's true is not at all obvious, but we can begin to understand it once we translate this intuition to the actual math behind the DCT.
If you look at the mathematical definition of the DCT, we usually have a vector definition of the original signal and the output coefficients. We want to define the kth index of the coefficient vector mathematically. What you often see is something that looks like the following. And with the intuition that we just built up, we'll see that this equation is doing exactly what we want. Let's start with the cosine term. This function should be familiar. It's the exact representation of a sampled point from a cosine wave using our earlier sampling scheme, and it incorporates the frequency of the cosine wave as well.
Now, what's interesting is, in order to get the kth index, we are actually summing over a product of each sampled point with samples from the cosine wave. Why does that make sense? This type of expression might look vaguely familiar to a lot of you. Let me rewrite this another way. We know that the original signal points can be represented as a vector, but what if we rewrote the sampled points from the cosine wave as a vector as well? What does this expression mean in the context of these two vectors? It's a dot product. And what we know about dot products is they're a nice way to measure similarity between two vectors. That's why when we pass in sample points from a cosine wave of frequency k as the input to the DCT, we got large values at the kth index coefficient. These two vectors were just scaled versions of each other, so the dot product was maximized.
And this perspective reveals what I think is truly the most surprising and elegant part of the DCT. By picking the points through the sampling method, we can think of the entire DCT as a matrix-vector product. All we're doing here is a linear transformation. The rows of the matrix are the sampled points from the cosine waves of the respective frequencies, and what's truly astounding is that all row vectors in this matrix are orthogonal to each other. What I mean by that is, if you take the dot product of any two row vectors representing cosine waves, you will get zero if they are different rows of the matrix. Intuitively, this is why in our earlier experiments, when we pass in a cosine wave of a particular frequency as an input into the DCT, we didn't get a contribution from any of the other coefficients which represented different frequency cosine waves. The orthogonality of the sampled points from different cosine waves generates this behavior. It's really quite beautiful.
Another great property of the DCT that follows from these facts is invertibility. I've talked about the DCT as a way of decomposing a signal into a coefficient representation of weights associated with cosine waves. We can also reverse this process. If I take my coefficient representation of the signal, I can apply what's called the inverse DCT to get back the original signal, and it is the exact same signal. No information is lost in this step. How we do that is by multiplying our coefficient representation with the inverse of the matrix. What's cool about this is that because of the orthogonality of the vectors, the inverse is just the transpose of our original matrix with some additional normalization constants.
Now, there's a super nice interpretation of the inverse DCT. The sample cosine wave points are now column vectors. So, what the inverse DCT is doing is essentially summing over a weighted combination of cosine waves directly to get the original signal. And because these columns are orthogonal to each other, that's what allows us to represent any set of eight points with these eight cosine waves. Absolutely incredible. I know we spent some time and went through some fairly complex math to get here, but it's precisely these details that are the most fundamental part of not only the DCT but many other similar transforms in the world of signal processing.
Now that we have a good intuition on the one-dimensional DCT, let's talk about how JPEG specifically uses it. JPEG takes an image and splits it into 8x8 blocks, and then centers their values around 0 by subtracting 128. Then we take the block and apply the DCT to each row of the block, giving us eight sets of DCT coefficients. We then apply the DCT to each column of the block. This process is what defines the two-dimensional DCT. So, in the end, we have 64 coefficients, each of which are a weight on a specific 8x8 pattern. Notice the first row and column correspond to the earlier one-dimensional patterns, and the other elements are compositions of these patterns. And just like in the one-dimensional case, the big idea here is that we can build up any 8x8 image using these 64 fundamental patterns.
The same signal perspective we talked about earlier also applies here, except now with 2D waveforms. What's going on here is we are plotting the pixel value on the Z-axis, with brighter pixels having larger values. What's fun to play around with is seeing how the waveform and image come together as we slowly put together the 64 coefficients in increasing frequencies. Seeing this in action makes you realize that one interesting property is that by the time we incorporate a small portion of the coefficients, our signal and image already look pretty close to the original versions.
There's an even more direct experiment we can run to quantify this notion. This particular 8x8 block was randomly picked out of the original image. If we map out the magnitude of the DCT coefficients on this block, we see that most of the largest values are in the upper-left section, which corresponds to lower frequency components. And what's even more interesting, if I take any 8x8 block on this image, almost all of them have the same property. This property of the DCT is what's commonly referred to as energy compaction. After applying the DCT, most of the largest values are concentrated in a few low-frequency coefficients, and this holds true in a lot of real-world images. The concept of energy compaction is incredibly important in image compression, as we will see. It's exactly the property that will allow us to aggressively compress images while still retaining high visual quality.
Fun fact: The original discovery of the DCT centered around approximating other transforms that had better energy compaction properties but were too expensive to carry out. The DCT is just one example of a transform that has this property for real-world images, and we use it because it's quite easy to compute. There's a lot of complexity involved here, but one of my goals in this discussion of the DCT and JPEG was directly interacting with these deep and important ideas through questions and visual experiments. Interactivity is a core part of learning, and a website that does a fantastic job of interactive explanations is Brilliant.
The sponsor for this video, from the basics of mathematics and algorithmic thinking to more complex ideas and deep learning and probability, Brilliant offers a variety of courses and learning paths for those interested in getting hands-on practice. Our discussions of JPEG interacted with some linear algebra in the application of image compression, and Brilliant has an entire linear algebra module that goes through the fundamentals and even shows applications of these ideas in image compression, cryptography, error-correcting codes, and much more. When I was a student, I really enjoyed their Computer Science Fundamentals course, which has engaging visualizations of concepts and great practice problems that helped me solidify my foundations. You can get started for free by going to brilliant.org/reducible, which is linked in the description below. Brilliant is providing a special offer through this channel where the first 200 members to sign up get 20% off the annual subscription. It's a great way to learn more about the topics in these videos and also a good way to support this channel. Big thanks to Brilliant for sponsoring this video.
Let's put everything we've discussed with the DCT together in one more experiment. We'll split our image into 8x8 blocks and then basically rebuild the image with each block having only a certain number of DCT coefficients. We're going to start off with zero coefficients and slowly build up the image. After one coefficient, we end up with basically a blur of the original image. And as we add DCT coefficients slowly, notice how quickly the image starts looking like the original. By the time we get to less than 25% of the DCT coefficients, you almost can't even tell the difference between the two images. This confirms the key aspects of why JPEG works. For this particular image, almost all the blocks are composed of the lowest frequency components, and we are generally less sensitive to changes in high-frequency details.
So, at this point, we know we can eliminate higher frequency components from the DCT, but the next natural question is, how do we actually do this? The process for eliminating higher frequency components in JPEG is called quantization. Quantization is a simple idea. Given an 8x8 matrix of frequency coefficients from the DCT, what we're going to do is basically divide each element by a scalar value and round it to an integer. These values are defined in terms of a quantization table. Notice larger values in the bottom right of the table, leading to zero values in the higher frequency components. In the decoding stage of JPEG, we'll actually be multiplying this result by the same quantization matrix element by element, and as you can see, the final coefficient matrix will be quite different from the original one. So, what that means is we're purposely losing information in this step. But the key idea here is most of the lower frequency components will be retained. This is why the energy compaction property of the DCT is so useful. When the largest values lie in the lowest frequencies, we will end up with a lot of zeros in the less important high-frequency components. These quantization tables are provided by the JPEG standard from visual experiments and are the main way for JPEG to define quality of compression. High-quality compression parameters can be translated to lower quantization table values. In practice, JPEG also defines a separate quantization table for both the luma and color channels. Notice that in the color channels, quantization can be even more aggressive.
After performing quantization, we have a matrix of quantized DCT coefficients, where we can now exploit redundancy to get even more compression. The last part of JPEG encoding involves a combination of run-length encoding and Huffman encoding. One clever trick is that a JPEG encoder will order the coefficients in a zigzag manner to maximize the chance of a large sequence of zeros. In order, classic run-length encoding can compress this fairly easily. All that's going on here is we are compressing every sequence of zeros into a count of the occurrences in a continuous sequence. JPEG actually performs something a little bit more sophisticated by keeping track of a triplet for every coefficient. This triplet encodes the number of preceding zeros, the number of bits required to encode the coefficient, and finally, the actual coefficient value. We also have an "end of block" value to signal that everything from here on out will be zeros.
This particular scheme works well with Huffman coding to further exploit redundancy. The big idea of Huffman codes is that more frequently used data can be encoded with fewer bits, and it turns out, especially with the nature of quantization, these triplets can be further compressed since some of these values will be more frequent than others. However, I'm purposefully not going to go into the details of how JPEG uses Huffman codes to compress the data because it really does get quite tricky. To give you some sense of the problems we have to deal with: encoding signs of coefficients, as well as triplets for all 8x8 blocks, most encoders also encode the top-left coefficient separate from all the other coefficients. And when you handle that, you have to deal with this on both luma and color channels. And when you eventually get that working, a good chunk of your logic will break when you have to deal with the different types of chroma subsampling. Implementing an optimized, fully functional JPEG encoder and decoder is no joke. I wouldn't give that task to even my worst enemies. But in terms of the big picture, all that's going on in this component is taking advantage of the redundancy that quantization creates.
A JPEG decoder will be able to use the Huffman code data in the files to get back all quantized DCT coefficients that were encoded. This part of the JPEG algorithm does not lose any information.
JPEG, as a whole, brings about an interesting discussion on the philosophy of data compression. The classic and most straightforward way to compress data is by taking advantage of redundancy. This is the basis of lossless image compression algorithms, such as those found in PNG file formats. In fact, for images where it's really important not to lose any information, PNG format is recommended over JPEG. But on most real-world images, being aware of the medium of presentation introduces another really powerful perspective. A lot of innovation in JPEG compression comes from experiments and understanding of human visual systems. It's from these experiments that we realized human eyes are less sensitive to color and also less sensitive to higher frequencies, so we can remove that information without a significant visual impact. This is why JPEG is so much more effective at compressing images than lossless formats.
You'll find these same types of techniques used in audio and video compression, where algorithms use our perceptions of sound and motion, respectively, to remove less relevant data. In fact, variations of the Discrete Cosine Transform and quantization show up in both audio and video compression. It really is incredible to me how people in these fields came up with the mathematical and algorithmic framework to utilize the way we actually perceive the digital technology around us. There's so much depth to these topics that I could never hope to cover in just one video, but I do hope this gives you a sense and appreciation for the complexity of the technology around us that we use on a daily basis. Thanks for watching, and I'll see you all in the next one.