JPEG Discrete Cosine Transform Explained | Image Compression

[00:00:00]In the last video, we talked about the beginnings of JPEG, so what do we do at the beginning of the process to start preparing for the discrete cosine transform, which is really how the lossy compression happens within a JPEG.

[00:00:14]We start with our RGB image, we convert that into YCbCr color space, which separates illuminance and chrominance.

[00:00:20]And then we can down sample the chrominance if we want, and we can kind of get away with quite a bit of down sampling there that people won't be able to see.

[00:00:27]The next step is the discrete cosine transform.

[00:00:32]Before we start talking about how images are compressed using the discrete cosine transform, it's much better just to start with a simple example of what a discrete cosine transform is and how it works.

[00:00:41]A cosine function, for anyone who isn't familiar with it, is a function that goes between 1 and -1.

[00:00:47]What we tend to do on this x-axis is go from 0, to pi, to 2*pi.

[00:00:52]This is in radians, those of you familiar with degrees, this is 180° at pi, and 360° at 2*pi.

[00:00:59]And the cosine wave looks like this. So it's 1 at 0, and then at pi, it goes down to -1, And then it goes back up to one at 2*pi.

[00:01:09]And it just goes on and on like this up and down as you increase.

[00:01:12]The way that the discrete cosine transform works, is we take some data, in this case our image data, and we try to represent it as the sum of lots of these waves.

[00:01:20]Which doesn't make a lot of sense until you start drawing them out.

[00:01:22]So let's imagine that we've got this cosine wave here, which is our standard frequency cosine wave, and then we've got another cosine wave, which is a much higher frequency.

[00:01:31]So that would be, come down a bit faster, go up a bit faster, come down a bit faster, and go up a bit faster like this.

[00:01:38]So now we have two waves. If we add them together, what we get is a sort of another wave which is a combination of the two.

[00:01:45]So if we draw it in here in this dashed line, we can see halfway between these two waves is like this, and then kind of like this.

[00:01:53]And you can see that we've created a more complex shaped wave by adding these two together.

[00:01:59]Now, as we increase the number of cosines, we can increase the number of possible shapes of waves that we can produce In practice, if we added these two waves together, we'd have a wave that was much taller than the input So here, it would be two, not one.

[00:02:11]So what in fact we do is we weight both of these, and so we take an average So both of these are weighted, in this case it's a half, and so this is essentially the average of both of them.

[00:02:21]We can also change the weighting of these.

[00:02:23]So we can have it with mostly this higher frequency one, but only a little bit of this low frequency one.

[00:02:28]And we'd have a different shaped wave coming out at the end.

[00:02:31]So each wave represents a small constituent of the output.

[00:02:35]And the higher the frequency of the wave, the higher the frequency part of the signal we're dealing with.

[00:02:39]So if we look at my jumper here, there's a low frequency change from this black table to a brightness, bright of my jumper, to dark table again.

[00:02:47]And there's much higher frequency changes on my jumper, where we go up and down within the woolen knit.

[00:02:52]And it's the same kind of principle. We're arguing in JPEG that we can get rid of some of the higher frequency signals and the general gist of the image will still be there.

[00:03:01]So this is just a one-dimensional discrete cosine transform with only two components.

[00:03:06]The way that the mathematics works, is if we have a signal that 8 long, Then we find that we can represent it using 8 cosine waves of different frequencies.

[00:03:16]And the same is true of an image. What we do in JPEG is we split each image into 8 by 8 pixel groups.

[00:03:22]And each of those pixel groups is separately encoded with its own discrete cosine transform.

[00:03:27]Each of those 8 by 8 pixel groups can be exactly replicated by 64, so 8 by 8 cosine waves.

[00:03:34]This actually shows the 64 base cosine waves that produce any image we might like to do in 8 by 8 pixels.

[00:03:42]This particular component here, is essentially flat.

[00:03:45]So if you had only this component, and that was all the contributed to your final output, your image would look like that.

[00:03:52]If you had only this one, your image would go white, and then it would dip down and go black.

[00:03:57]And you can see that the frequency is increasing as we go along here.

[00:04:00]This is in the x direction, and in the y direction, the frequency is increasing down here.

[00:04:05]So this is a cosine wave, and this is a higher frequency cosine wave down here.

[00:04:10]As we increase the frequency in both directions, we get a kind of checkerboard pattern.

[00:04:13]And this is a high frequency information that we're encoding in these regions.

[00:04:18]So these are the 64 cosines functions that can be combined to make any 8 by 8 image.

[00:04:26]This is only in one channel, so let's say just illuminance or just Cr.

[00:04:30]For example, if we had half of this wave and half of this wave, then what you get is a square image that is generally brighter on the left with a little bit of bright on the right hand side, because you've summed the two together.

[00:04:42]To create any kind of 8 by 8 image, what we need to do is have a combination of all of these at the same time.

[00:04:47]Each of these is weighted based on something called a coefficient Which is a number representing the contribution of each of these individual blocks to the whole.

[00:04:57]So for example, if the contribution of this one is zero, Then there's no part of this cosine in the 8 by 8 image that we're looking at.

[00:05:04]If it's 0.1, and this one's 10, then this has a hundred-fold less impact on your output image than this one.

[00:05:12]And what we do with the discrete cosine transform, is basically calculate the coefficients for these waves.

[00:05:17]Putting this discrete cosine transform aside for a minute, If we just look at an example image. So this is a small crop section of our flower image.

[00:05:24]This is the y-component, so it's just every value from 0-255, how intense is the pixel.

[00:05:31]So, you can see this is not a hugely interesting piece of image, it's kind of grey with a little bit of brighter region down here.

[00:05:37]What we want to try and do is calculate the contributions of each of our cosine waves to this image.

[00:05:43]Which bits of cosine do we need to add together to create an image that looks exactly like this.

[00:05:48]So to start with, what we need to do is center all of these values, which are currently centered at 128, because they're from 0-255, We center with values around zero, because remember cosine wave goes from 1 to -1, not 1 to 0.

[00:06:02]So we take away 128 off every value, and we get our shifted block like this.

[00:06:08]So this is the exact same image, but this time now centered around zero.

[00:06:11]And how we can use this in the discrete cosine transform to calculate our coefficients.

[00:06:16]We apply the -- it's actually discrete cosine transform #2, which is the one that's always used in JPEG.

[00:06:22]And what that does, is calculate the contribution of each of our cosines waves that when added together, will create this image exactly.

[00:06:30]Which of these blocks, when multiplied by that coefficient, to tell us how much of each one we use, will add together to create this exact image.

[00:06:38]So it might be a bit of that, a bit of this, and bit a that, a lot of that, and none of this one. Exactly.

[00:06:43]And so you'll find that all of these will have some impact on the image.

[00:06:47]It's almost certain, unless the image is completely flat.

[00:06:48]One of the nice things about JPEG is these low frequency ones will have a much bigger effect than high frequency data.

[00:06:54]And we also see them better.

[00:06:55]So that's how we compress JPEG.

[00:06:57]So, we calculate our DCT2 coefficients, and that gives us some slightly arbitrary values between -1024 and 1024.

[00:07:06]But that's not too much of a big problem.

[00:07:08]And what we have, each of these represents the weight, or the amount, of each of our cosine waves.

[00:07:13]So if you put this next to here, we can say that if we take this cosine, and multiply it by -370, and add it to this one multiplied by 29.7, and so on, And we do it for all of them, the added sum will be the original image back again.

[00:07:27]Usually, this top left coefficient is much bigger than the others.

[00:07:31]Because it's flat and not a cosine wave it represents the general intensity of that particular image block.

[00:07:37]So that is called our direct current coefficient, or DC coefficient, All of the others, are alternating current, AC coefficients.

[00:07:43]In practice, usually the DC coefficients are stored separately, but we won't dwell on that too much.

[00:07:49]The really important aspect of JPEG that you want to understand is that these coefficients are often very very small.

[00:07:54]And these ones are very very big. And what that tells is that for the high frequency cosine waves, don't really contribute much to the image.

[00:08:01]For example, this one is zero, which means that this cosine wave here is having no effect on the image at all.

[00:08:06]The image is essentially not a checkerboard in any way.

[00:08:09]These ones, compared to these big coefficients here, are incredibly small as well, and have very subtle effects on the actual output pixel data.

[00:08:17]I mean, these weights are so small that if you took these away, the image would be almost identical.

[00:08:22]And yet, you could just take them away and save all that space.

[00:08:25]So that's how we do it. The next step, after calculating our discrete cosine transform coefficients is, basically, try to remove the ones you don't want.

[00:08:33]We call the process of removing the high frequency data quantization.

[00:08:37]Hopefully, it would be easier if I show you a quantization table.

[00:08:40]This is the standard JPEG quantization table that represents a quality of 50%.

[00:08:45]So in a JPEG standard, different compressors, like the ones used in photoshop, will use different quantization tables depending on how they feel.

[00:08:52]And also, what level of quality you set it at. And what we do, is we divide every one of our coefficients by the corresponding quantization value and then round to the nearest integer.

[00:09:04]And you can see already that these ones are much bigger than these ones.

[00:09:07]So what essentially happens is these get scaled by a huge amount, usually to close to zero, And then get removed by being set to zero when we round to the nearest integer.

[00:09:15]So for example, 370 divided by 16 is roughly 23. Or minus 23. And the actual quantized output is this.

[00:09:24]And you can see that almost all of it is now zero. So, this coefficient now no longer has any effect, nor does this one or this one.

[00:09:30]The only ones that have any effect on our image are these nine here.

[00:09:35]And, essentially, the argument that we're making is that with just these nine, we can get pretty much the same image back.

[00:09:43]It won't be exactly the same, a couple of pixels will maybe be an intensity level up or down, but when viewed at normal image range, you know, let's say a photograph or on a monitor, it will look exactly the same to us.

[00:09:53]So what we then finally do when we want to output this information into our file Is we essentially list all these in a long line.We then use a huffman encoding, which Professor Brelfooters (?) covered in a video to further compress this data.

[00:10:06]The way that we serialize this into our file is in a zig-zag fashion.

[00:10:10]So we start with -23, then we go -2, -21, so we're going up and down and up and down -- 6, 4, 0, 0, 2, 1, and so on.

[00:10:21]And the important thing about this is that by doing this, we're going to get a huge list of naughts in a row.

[00:10:26]At that is very easily compressed by huffman encoding.

[00:10:30]So we take this table, and we do this for every 8 by 8 block in our image.

[00:10:33]We then serialize them out into a long line, and we use huffman encoding to shrink them right down, and that's what goes into our JPEG.

[00:10:40]And in all other aspects of JPEG, are really sort of minor format considerations. That's the core of how the compression works.

[00:10:46]To decompress the image, let's imagine that we've sent our JPEG to someone, and their decoder is trying to read it.

[00:10:52]What we have to do is the exact opposite of this approach.

[00:10:54]So we begin by multiplying each of the values by our quantization table.

[00:11:00]So this is the same quantization table. It's stored inside the JPEG so we know which one the used.

[00:11:04]Because if use a different one on the way out, you're going to ruin your image.

[00:11:07]So we multiply each of these values by the specific value in the quantization table And we get the coefficients. And you can see that because most of them are naught, most of them on the other side are also naught.

[00:11:17]So, none of these are going to contribute to our image anymore.

[00:11:21]Then, in reverse, we use discrete cosine transform #3, which is usually just called the inverse discrete cosine transform because it's generally used to reverse what we did for discrete cosine transform two, and that gives us our shifted block back again, which of course we then add 128 to every value And we have our output block. And there it is.

[00:11:40]So that's the complete JPEG compression using discrete cosine transforms.

[00:11:44]If we look at our imput block and our output block, next to each other, we can see that there are some changes in values, but it's actually pretty close. These are sort of changed -- like this has gone up a few intensity levels, this is the same, this has gone down four, But these are from 0 to 255. No one is going to see that kind of difference. And this is at 50%. So you can do a lot less than this If you have your JPEG quality set higher, and smaller values in your quantization table.

[00:12:10]So in the JPEG standard, this is the quantization table they give you.

[00:12:14]This is actually the quantization table for luminosity, not for chrominance. They have a different one for chrominance which is much -- has much higher penalties on the high frequency because if high frequency data is not very important in grey, it's even less important given that we don't see color that well.

[00:12:30]One thing you can do to immediately increase the quality of our overall JPEG compression if I just preserve as much image as possible, is to halve all of these values in the quantization table. If we divide all of these values by two, then essentially everything is being scaled by less.

[00:12:44]All of these high frequency coefficients won't necessarily be rounded to zero, they might be rounded to one or two, and they'll still have a little bit of an effect.

[00:12:50]On the other hand, if we increase the values in these quantization tables, we're essentially operating a lower JPEG quality setting.

[00:12:58]This is the approach that the JPEG standard uses. In other software, they may have their own quantization tables in fact, as far as I know, photoshop I think they have 12, 14 settings, and they have different quantization tables for most of those settings.

[00:13:11]And different sampling frequencies. So lots of different things that they've decided make for a pretty good scale bar that a user can use.

[00:13:18]And all of those settings, are all then stored in the header of the file -- Yeah. Between each part of the image, you'll get a small block that says these are the quantization tables and the huffman encoding tables that we used so that everyone can reverse that process. If you don't know what the quantization table was, you might be multiplying your encoded coefficients by different values and get something completely different out at the end.

[00:13:37]What would it be? Just different colors?

[00:13:39]It could just be a completely different image. You've divided by certain numbers, you need to multiply by those numbers to reverse the process Otherwise you might get nonsense back out.

[00:13:46]So going back to the original diagram that I drew, this is sort of the overview of JPEG. We start with our image, we've transformed our color, and in then DCT, essentially removes the high frequency information in our image.

[00:13:59]So if we've got an image where lots of high frequency information pixel changes are happening, that might get significantly compressed, but it also might look worse. In most photographs, certainly over an 8 by 8 image block, you won't be finding that much high frequency information and so we can quite safely get rid of a lot of it.

[00:14:17]We calculate our DCT coefficients, we quantize them to remove the high frequency ones, and then we huffman encoding to compress that into a manageable small stream that we put into our JPEG file.

[00:14:27]And then the reverse of that process is exactly that. We decode the huffman tables, the huffman encoding, we unquantize by multiplying by all our values in the quantization table, and then we apply the inverse DCT, to obtain our block back. And we do this for every little 8 by 8 image in our picture.

[00:14:44]If our image isn't a multiple of 8, then we have to add some padding bytes at the end to make it work, usually we could duplicate the ones near the edge, so that it kind of is coherent, or do something a little smarter.

[00:15:00]Text violates our assumtions that high frequency information doesn't contribute a lot to the image.

[00:15:05]So this is a small 8 by 8 image. This is, in a sense text. This is the computerphile 'C' with little triangular brackets