JPEG DCT, Discrete Cosine Transform (JPEG Pt2)- Computerphile

Key Takeaways

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 coine transform which is really how the lossy compression happens within a JPEG uh compressed file so um we start with our RGB image we convert that into the ycbcr color space which separates the luminance and the chrominance and then we can downsample the chrominance if we want and we can kind of get away with quite a bit of down sampling there but people won't be able to see the next step is the discrete cosine transform before we start talking about how images are compressed using a discrete transform it's much better just to start with a simple example of what a discrete cosine transform is and how it works a cosine function for anyone that isn't familiar with it is a function that goes between one a minus one what we tend to do on this on this x- axis is go from n to Pi to 2 pi this is in radians those of you familiar with degrees this is 180° at pi and 360° at 2 pi and the cosine wave looks like this so it's one at zero and then at Pi it goes down to minus one and then it goes back up to one at 2 pi and it just goes on and on like this up and down as you increase the wer to discrete cosine transform works is we take some data in this case our image data and we try and represent it as the sum of lots of these waves which doesn't make a lot of sense until you start drawing them out 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 much higher frequency so that will be come down a bit faster go up a bit faster come down a bit faster and go up a bit faster like this okay 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 so if we draw in here in this dash line we can see halfway between these two waves is like this and then kind of like this and you can see that we've created another more complex shaped Wave by adding these two together now as we increase the number of cosiness we can increase the number of possible shapes of wav 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 so what in fact we do is we wait both of these and so we take an average so both of these are weighted in this case as a half and so this is essentially the average of both of them we could also change the weighting of these so we could have it was mostly this high frequency one but only a little bit of this low frequency one and we'd have a different shaped way coming out the end so each wave represents a small constituent of the of the output and the higher the frequency of the wave the higher the frequency part of the signal we're dealing with so if we look at my my jumper here there's a low frequency change from this black table to a brightness right over my jumper to dark table again and there's much higher frequency changes on my jumper where we go up and down within sort of the Woolen knit 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 so this is just a one-dimensional discrete coine transform with only two components the way that the the mathematics works is if we have a signal that's eight long then we find that we can represent it using eight cosine waves of different frequencies and the same is true of an image what we do in jpeg is we split each image into 8 by8 pixel groups and each of those pixel groups is separately encoded with its own discrete coine transform each of those 8 by8 pixel groups can be ex exctly replicated by 64 so 8 by8 cosine waves this actually shows the 64 base cosine waves that produce any image we might like to do in 8 by8 pixels this particular component here is essentially flat okay so if you had only this component and that was all that contributed to your final output your image would look like that okay if you had only this one your image would go white and then it would dip down and go black and you can see that the frequency is increasing as we go here this is in the X Direction and then in the y direction the frequency is increasing down here so this is a cosine wave and this is a high frequency cosine wave down here as we increase the frequency in both directions we get a kind of checkerboard pattern and this is a high frequency information that we're encoding in these regions so these are the 64 cosine functions that can be combined to make any 8 by8 image this is only in one channel so let's say just luminance or just CR for example if we had half of this wave and half of this wave then what you would get is a square of of image that was generally brighter on the left with a little bit of bright on the right hand side because you've sum the two together to create any kind of 8 by8 image what we need to do is have a combination of all of these at the same time each of these is weighted based on something called a coefficient which represents is a number representing the contribution of each of these individual blocks to the hole so for example if the contribution of this one is z then there is no part of this cosine wave in the in the 8 by8 image that we're looking at if it's an 0.1 and this one's 10 then this has obviously got 100 fold less impact on your output image than this one and what we do with a discrete coine transform is basically calculate the coefficients for these waves putting this discrete coine transform aside for a minute if we just look at an example image so this is a small crop section of our flower image uh this is the Y component so it's just every value from not to 255 how intense is the pixel so you can see this is not a hugely interesting piece of image it's kind of gray with a little bit of brighter region down here what we want to try and do is calculate the contribution of each of our cosine waves to this image which bits of cosine do we need that add together to create an image that looks exactly like this so to start with what we need to do is Center all of these values which are currently centered around 128 because they're from not to 255 we Center these values around zero because remember a cosine wave go goes from one to minus one not from one to n so we take away 128 off every value and we get our shifted block like this so this is the exact same image but this time now centered around zero and now we can use this in the discrete coine transform to calculate our coefficients we apply the it's actually discrete cosine transform number two uh which is the one that's always used in JPEG and what that does is calculate the the contribution of each of our cosine waves that when added together will create image exactly right which of these blocks when multiplied by their coefficients to tell us how much of each one we use will add together to create this exact image so it might be a bit of that a bit of this a bit of that a lot of that yeah and none of this one exactly and so you'll find that all of these will have some impact on the image it's almost certain unless the image is completely flat one of the nice things about jpeg is these low frequency ones will have a much bigger effect than the high frequency data and we also see them better so that's how we we compress jpeg so we calculate our DC T2 coefficients and that gives us some slightly arbitrary values between -124 and plus 1,24 but that's not too much a big problem and what we have each of these represents the weight or the amount of each of our cosine waves so if we 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 multiply by 29.7 and so on and we do it for all of them the added sum will be our original image back again usually this top left coefficient is much bigger than the others because this because it's a flat and it's actually flat and not a cosine wave represents the general intensity of that particular image block so this is called our direct current coefficient our DC coefficient all of the others are alternating current AC coefficients in practice usually the DC coefficients are stored separately but we you know we won't we won't dwell on that too much the really important aspect of JPEG that you need you want to understand is that these coefficients are often very very small and these ones are very very big and what that tells us is that the high frequency cosine wave don't really contribute very much to the image for example this one is zero which means that this cosine wave here is having no effect on the image at all the image is essentially not a checkerboard in any way these ones compared to these big coefficients here are incredibly small as well and have very subtle effects on the actual output pixel data I mean these weights are so small but if you took these away the image would be almost identical and yet we could just take them away and save all that space so that's how we do it the next step after calculating our discrete coine transform coefficients is basically try and remove the ones we don't want we call the process of removing the high frequency data quantization hopefully it'll be easier if I show you a quantization table this is the standard jpeg quantization table that represents a quality of 50% so in the jpeg standard different compressors like the one used in Photoshop will use different quantization tables depending on how they feel 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 okay and you can see already that these ones are much bigger than these ones 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 so for example 370 ID 16 is roughly 23 or minus 23 and the actual quantized output is this and you can see that almost all of it now zero so this coefficient now no longer has an effect is this one or this one the only ones that have any effect on our image are these nine here and essentially the argument that we're making is that with just these nine we can get pretty much the exact same image back it won't be exactly the same the couple of pixels will be maybe an intensity level up or down but when viewed at a normal image range you know let's say a photograph or on a monitor it'll look exactly the same to us so what we then finally do when we want to Output this information into our file is we essentially list all these in a along line we then use a Huffman encoding which Professor bford has covered in a video to further compress this data the way that we serialize this into our file is in a zigzag fashion so we start with - 23 then we go Min -2 - 21 so we're going up and down and up and down 6 4 0 0 2 1 and so on and the important thing about this is by doing this we're going to get a huge list of norts all in a row and that is very easily compressed by halfman encoding so we take this table we do this for every 8 by8 Block in our image we then serialize them out into a long line and we use halfman encoding to shrink them right down and that's what goes into our JPEG and then all other aspects of jpeg are really sort of minor format considerations that's the the core of how the compression Works to decompress the image let's imagine that we've we've sent our JP to someone and their decoder is trying to read it what we have to do is the exact opposite of this approach so we begin by multiplying each of these values by our quantization table so this is the same quantization table it's stored inside the jpeg so we know which one they used cuz if you use a different one on the way out you're going to ruin your image 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 not most of them on the other side are also not so none of these are going to contribute to our image anymore then in Reverse we use discrete cosine transform number three which is usually just called the um the inverse discrete cosine transform because it's generally used to inverse what we did for discrete coine transform 2 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 so that's the complete jpeg compression using discrete cosine transform if we look at our input block and our output block next to each other so there we go we can see that there are some changes in these values but it's actually pretty close these have sort of changed this has gone up a few intensity levels this is the same this has gone down four but these are from not to 255 no one's 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 so in the jpeg standard this is the quantization table that they give you 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 Gray it's even less important given that we don't color that well one thing you can do to immediately increase the quality of our overall jpeg compression that is preserve as much image as possible is to have all of these values in a quantization table if we divide all of these values by two then essentially everything's being scaled by less 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 on the other hand if we increase the values in these quantization tables we're essentially operating a lower jpeg uh quality setting this is the approach that the jpeg standard uses in other software they may have their own um quantization tables in fact as far as I know Photoshop I think they have 12 quality settings and they have different quantization tables for most of both settings and different sampling frequencies so lots of different things that they've decided make for pretty good scale bar that a user can use and all of those settings are all then stored in the header of the files yeah between each part you'll get a small block that says these are the quantization tables and the Huffman coding 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 what what might it be just different colors it could be a completely different image you've divided by certain numbers you need to multiply Again by those numbers to reverse the process otherwise you might get nonsense back out 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 then our DCT essentially removes the high frequency information in our image so if we've got an image where lots of high frequency information uh high frequency pixel changes are happening that might get significantly compressed but it might also look worse okay but if but in most photographs certainly over an 8 by8 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 we calculate our DCT coefficients we quantize them to remove the high frequency ones and then we use Huffman encoding to compress that into a manageable small stream that we put into our JPEG file and then the reverse of that Pro is exactly that we decode the Huffman tables the Huffman encoding we un quantize 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 by8 image in our in our picture if our image isn't a multiple of eight then we have to add some padding bites at the end to make it work usually we could duplicate the ones near the edge so that it kind of is coherent um or you might do something a little bit smarter text violates our assumptions that high frequency information doesn't contribute a lot to the image so this is a small 8 by8 image this is in a sense text this is the computer file C with its little triangular brackets