JPEG DCT, Discrete Cosine Transform (JPEG Pt2)- Computerphile
Вставка
- Опубліковано 13 жов 2024
- DCT is the secret to JPEG's compression. Image Analyst Mike Pound explains how the compression works.
Colourspaces: • Colourspaces (JPEG Pt0...
JPEG 'files' & Colour: • JPEG 'files' & Colour ...
Computer That Changed Everything (Altair 8800): • Computer That Changed ...
Problems with JPEG: COMING SOON
Upside Down Trees (Huffman Encoding): • How Huffman Trees Work...
Colourspaces: • Colourspaces (JPEG Pt0...
JPEG isn't a file format - JPEG pt1: • JPEG 'files' & Colour ...
Upside Down Trees (Huffman Encoding): • How Huffman Trees Work...
Problems with JPEG: COMING SOON!
Computer That Changed Everything (Altair 8800): • Computer That Changed ...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscom...
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
1:24 that is the best freehand sine wave I've ever seen.
Cosine*
It's exactly the same curve, just shifted to the left by π/2 .....
Look again, he bottomed out the curve well past pi radians. That is a blatant error.
@@davidjames1684 lol you would hate to see what I can achieve freehand
David James Oh dear, that will not do. Fire up the guillotine and prep my guillotine dress.
I love it when I procrastinate and notice "hey, I need the stuff this guy's explaining in my exam!"
double win
Was exactly my thoughts just before i saw this comment :D
18 years after university, I finally understand what my prof tried to explain....
But it's the best way to get in touch with professionals a and get job offers in the field as a junior
With luck and understanding other parts well enough.
doubt you need that to graduate (at least as bachelor) ... . took disney years to figure out how to handle fur of pets :P
Il vaut mieux tard que jamais
Better late than never
@@カラスKarasu It is? How so?
There's a few steps that he skipped.
as many of you might realize, images aren't all going to make those nice blocks of 8, so you need to pad the edges with a few pixels most of the time.
second, he never actually talked about how the DCT is mathematically performed. Basically it's matrix multiplication between your shifted values and a DCT matrix that's generated as basically a sum of a bunch of cosine saves.
third, i'm not sure if this is included with their huffman video or not, but the values are actually stored in 1's complement, which is interesting because they completely ignore 0's. In coding, there's basically a skip code which could mean either skip every remaining coefficient or skip a chain of several.
fourth, the DC value (top left) isn't just stored separately, but it also needs to be encoded in a separate way. Because the values are typically so much larger than the others, you don't actually store the DC value itself, but the comparison to the previous value. For instance, if the first value is 84 and the second is 85, you store 84 for the first block, then 1 for the second.
This is by far the best video I've ever seen for explaining jpeg, and all of the above isn't really necessary for anyone just curious about how jpeg works, but it's still cool stuff to know imo.
the first is at 14:45
hey man, can you answer me, I need your help
Explains why JPEG lossless cropping never quite matches the original boundaries unless they hit edges of the frame.
I'm trying to work out step two you listed, applying the DCT but I'm not getting the correct values. Would you be able to help me out? I'm using google sheets to get the sumproduct of T M T'. For the DC I get -332.7 instead of -370. The AC values are just completely out of whack
@@steelmagnum use matlab image processing toolbox
For anyone interested: this is roughly how the fourier transform on images works. The main 3 differences is that you don't do it on 8x8 blocks but on the image as a whole, you consider 'waves' with lots of different angles and not just vertically and horizontally and you also add in sine waves and not just cosine waves.
These series are fantastic for three reasons: 1) high quality information 2)organized, sequential presentation with examples 3) no youtube fluff
6:11 nice how he did the trick with the pen without even stopping to talk
doe maeries well spotted!
doe maeries This guy has skills. His freehand sinusoids are also pretty impressive.
doe maeries Typical computer scientist. :P Almost half of my fellow students can do this aswell. And the drawing of the function? Well... If you are forced to draw them so often in your courses, you just get used to it, I guess. (He is competent and good though, nonetheless, it's just not THAT special in our field of nerds. :p)
I rewatched that part 4-5 times, so awesome that was.
Oh SOB, I didn't even notice it and I've seen this video a few times, only because of this comment, wow, awesome trick, smart guy, a little nervous had a energy release with that, it usually happens
This young gentleman uses paper and pen to explain something so well, much better than many others using fancy cartoons and movies. Thanks!
I'd love to experiment with changing the quantization numbers and see what weird images that would produce. Like glitch art maybe. :)
I had the same thought after watching this
I bet you could do some really interesting stenography with this
now those arts are being sold as NFT
now those NFTs are worthless
I love the by-the-way-I-do-penspinning on 6:13 xD
Omg I paused the video, played it in slow motion a few times, practised the rotation by holding the pen with my other hand and after 10 minutes I did my first successful pen spin. I did not expect to learn that watching this video.
Okay so during my university course we learned this in 90 minutes. And there are still some bits in this video that we never learned. This is so much better explained than anything we learned or that I could find on the topic online. Very awesome video!
I am so glad that I clicked on this video out of the search results to learn something about DCT. I have to say that the quality of teaching in this video is simply top-notch. Many other videos out there simply explains how to calculate DCT, without ever relating to any practical usage at all. Some of them dwell only in the dark regions of the textbook filled with a lot of formulas.
Tried to understand this around a year ago, but Mike really put it in words better than any book I read. Thanks!
this is just awesome. Thank you for explaining JPEG in a compressed form
Jpeg is like a fastfood worker who drops the bun on the floor and picks it back up "they won't notice"
And you won’t.
@@cancername true
It blows my mind how some people can just rattle this stuff off like it's nothing, meanwhile if you asked me what I ate for dinner last night I'd probably have to think for two solid minutes.
Tons of great information! RGB hurts my brain much less than YCbCr..
Dude may be the guys teaching in the video doesn't now what he eat yesterday but its the passion that helps people store this much info in brain.
its just practise and interest. its like learning a language. after some time (and work, most want to skip *g* ) you get there usually.
Obamna
this is sickly true.
That was such a discreet pen flip
looks more like a twirl to me, not a flip. Also, closer to 6:14, not 6:10.
Bloke talks a bit loud and fast, though. Snowden semi-doppelganger with brow jewel to boot. Sorry, back to the graph now.....
@@a.wosaibi
discrete* :)
After an online university lecture about JPEG compression, that video sets all the stuff in my head to the right places! Thanks for such a great example of tables with their input/output performed
Thanks so much for the clear explanations! I was reading through different papers trying to understand the concept of DCT but always felt a gap here and there. This video gave a super lucid and straightforward understanding in a layman-friendly way.
Very well done! I've been meaning to learn more about JPEG, and here you come along and explain it very coherently. Thanks for that!
Extremely well presented. There was a bit about what exactly the AC values represented that I didn't already know and this video didn't skip a beat.
This man explained this so easily which I was not able to understand through any article/book. Great job!!
This is by far the best video I have seen on JPEG compression. He explained the process thoroughly.
This is so cool! It's like Fourier Transform but only the cosine coefficient. In university class, analysis, the Prof always said it's being used all over the computer image and video compression, but never really gave an example, so now that I have one its really cool to see this at work
I think no one has ever explained frequency transformation as good as this video. Thank you man!
This guys is so eloquent. make the jpeg so much easier to understand
For those wondering what is a *macroblock*, it is a superset of *blocks*.
For instance, in *4:2:0 YCbCr* (subsampling by two both horizontally and vertically), a macroblock is 16x16 pixel², thus containing four 8x8 pixel² Y blocks + one 8x8 Cb block + one 8x8 Cr block.
Branch Education just did a fantastic video on jpeg compression but this one is even more fantastic!
Very well done. Very clear explanation that included all necessary information to get an understanding of the entire process! I wished my prof would take that as an example of an efficient way of explaining a theory. He could save 50% of his time.
How I missed this great lecture about JPEG all these years. Well youtube won't recommend these videos and I searched for JPED compression and landed up here part 1 and part 2. Amazing :D ....
What I love about this channel is that it keeps me interessted in maths lessons.
Brilliant - I've wondered this for 25 years (since meeting the .jpg format in 1996). Another well prepared lecture by Dr Pound
Wow. Just wow. Hands down, the best video for understanding JPEG on the internet! Thank you Sir :)
Worth waiting for! Thank you for this very enlightening explanation. I realise there's more to it than you showed, but I now have a very good idea of what's going on. It may sound odd to say this, but I think this is an important day in my life. I've been using JPEG since at least 1995, and twenty years later I've finally discovered some of its secrets. It's like having a deep talk with an old friend...
This is the best basic explanation of JPEG compression that I've seen.
and once again this channel comes to the rescue, doing a superb job in explaining a complex concept in an easy manner
OMG! Mike just drew the most perfect sine curve I've ever seen drawn by hand! Impressive. Most impressive.
This is the best explanation for the DCT process I've ever searched.
the greatest video ever created tbh
This is so fascinating!!! This video is gotten me more interested in compression than i already am. I love seeing math at work.
This guy is really good at explaining really complicated concepts.
College senior here, and I was fascinated by the gist of it. I always wondered how the hell are jpegs so small.
Will there be any talk about PNG files? I guess they have a different encoding dimension for the opacity/alpha levels.
Man, this is brilliant. I'm going to put the video to my college students and sit with them to watch it instead of giving the lecture myself.
Your knowledge with your great voice makes this subject more interesting
What a nice repetition of forgotten lectures back from college :) Thanks a lot!
You addressed the meaning of frequency in images, which others completely miss out . Thanks.
Wonderfully done, but it would have been nice if you explained how the coefficient for each 8x8 DCT was calculated. I assume its just a straight accumulation of each pixel difference on the 8x8 block, hoping for a total of zero, but I'm left wondering.
At 6:58 “we calculate the DCT coefficients” which are the weights of each cosine wave, or the amount that each cosine wave contributes to the original image. But the actual calculation is not shown, suddenly a piece of paper with DCT II coefficients just appears with all the numbers.
How are these coefficients calculated??
you can see it at 6:26. Basically, each 8x8 block from the image has a contribution from all blocks "the ones that have blue borders". How do you find the contribution of each blue block to our 8x8 image block ?
Well, you correlate the 8x8 image block with a blue block and the result will be a number (coefficient). This coefficient is the "weight" of the blue block to our 8x8 image.
Correlation here means multiply each element in the 8x8 block with its corresponding element in the blue block and sum the result into one number.
Hope this helps
Very nice explanation. I've had some ideas of how the encoding works, but seeing the cosine chart really clarified it.
The jpeg videos are probably some of my favorite computerphile videos! Well done! 😊
Incredible, clear and concise explanation. Greetings from Argentina
Great explanation of some fairly difficult subject matter. Looking forward to the next part.
Love the casual pen spin 6:14 .
So the spectral method with truncation is the common practice in compressing images. Now I understand why we see the dirty patches from highly compressed jpeg images of texts or line works, which in fact have different weights (smaller in low freq. and greater in high freq.) from the pictures.
greetings from Turkey. we will do a jpeg algorithm this year at school. While researching I found this video. You explained it very well. I hope we can succeed too.
14 day for finish...
Thank you for saving my course project, Sir.
You explained this 100x better than my prof did in 1/100th of the time... Thank-you for this!
You guys make the most interesting video on youtube, all channels considered. High level synthesis. Please keep doing what you do!
9:53 so satisfying when he reveals all the 0s that can be huffman-encoded!
very nice series of videos. used them for preparing exams on multimedia systems.
There is one step missing between zigzag-reorder and Huffman: the zeros are actually not compressed by Huffman at all, but the block is zero-length encoded first: instead of storing all the 0s, you just store the number of zero elements.
I used a hex editor to mess with the quantization table of an image, fun times! The picture comes out all weird looking, but once you know how it works you can achieve some interesting effects.
Very Impressive Dr. Mike Pound..
I have a question. What if the input image dimensions are not divisible by 8? If you have an image like 700x500 px you can't divide it into 8x8 segments without some residuals right and bottom borders. Great content by the way. This video especially is packed with very useful information.
this is brilliant. so well explained!
just got one question: how is the quantisation table created? are the values adjusted "manually" or is there some math to decide which cosine is more important?
MichaelKingsfordGray thank you for the answer! creating such tables must be a very interesting process, considering that they can be different for each channel. now i'm really curious to see what happens when decoding with a different quantisation.
MichaelKingsfordGray ah, the internet!
Well, that was much easier than reading 5 pages of the book. Thanks.
Sir, you have way too much of knowledge. Thanks a lot for such super high-quality knowledge resources that you are providing for free.
It is the first time in my life I actually understand what happens with DCT in JFIF compression. So I am grateful for this video. But WHY has everything to be shown so fast. Papers, figures, graphics, diagrams are all shown like flash-flash-flash as if this were an action movie. As far as I understand video time on UA-cam does not cost anything, and neither does it require reels of celluloid or film processing. Like I said, I understand how DCT is used, but I had to replay the video several times and pause it often.
Modified DCT is used to compress MP3, AAC etc. audio formats.. Didn't know that, read it in wikipedia but since it is essentially a frequency filter, i thought it could be used for audio too. Audio, of course is 1 dimensional and images are 2D so the exact same can't be applied, thus "modified" DCT or MDCT..
Quote " In MP3, the MDCT is not applied to the audio signal directly, but rather to the output of a 32-band polyphase quadrature filter (PQF) bank."
SquidCaps Yepp, thats was why the Pentium MMX was made
matsv201
Ah, thanks for that tidbit. It was if i remember right it was marketed as MultiMedia Extension or something like that and it really was considerably faster than non-MMX machines.. Made my first album on 188MHz MMX :)
SquidCaps Actually sound compression using DCT operate reversed to image compression. JPEG transform real color values into frequency domain as explained in the video but sound is already in frequency so the DCT transform them into real value domain before compression.
Stig Helmer
Again, makes sense, audio is serial data to begin with.
Stig Helmer That's not correct. Uncompressed PCM audio data as well as raw data fed to the audio card is in the time domain, not the frequency domain. That's why filtering of audio data is done with FIR and and IIR filters in the time domain with convolution. If audio generally was represented in the frequency domain, you would just do filtering with multiplication and an appropriate window.
I always thought it was more complex than this, with JPEG using more systems/divisions or shapes/patterns for the image compression. I never realised the 8x8 sections were using just cosine waves. Wow.
This is by far the best JPEG explanation I found. Thank you!
DCT is very similar to FFT as it converts samples from a time domain to a frequency domain. MP3 also uses DCT but with windowing.
Mr Spectacals Correct. MP3 uses a variant of the DCT-IV with overlapped window, called the MDCT. that's applied to the granules of each subband
Okay okay, guys.. I don't understand mathses that well so help me out... "Windowing" is defining a finite domain of the series of functions, right?
And what is the difference between FFT and DCT exactly? They are both series of sine or cosine waves at different frequencies used to make an approximation of a signal or other function or such.
tried the wikipedia page, but that is not much helpful with those big words :/
This is one of my favourite videos on UA-cam.
this application is cool. now I have a better and concrete appreciation for the cosine wave
This was very straightforward to understand although I am a Mechanical Engineer !
This was a very good and thorough explanation of the encoding. I am currently studying transform theory and signal processing and this was a great complement for further understanding!
insane hand-drawn waves, wow.
Great explanation! All the 8x8 printouts worked well on my brain.
Thanks for taking the time to post this excellent video. I have seen the terms for DCT and Huffman related to image compression for years and never really understood how it worked. Does mpg and mp3 work in a similar fashion?
Yes! Just like JPEG takes advantage of "spacial coherence" (pixels are often similar to their neighboring pixels), MPEG takes advantage of this too and takes advantage of "temporal coherence" (pixels are often similar to what they were in the recent past). I do not know about mp3.
So... what did you just say?
Great video. Can you also talk about JPEG2000 compression algorithm? I heard that it uses discrete wavelet transform to achieve even higher compression than DCT.
Ingenious method to remove quick changes in a channel!
One of the best videos on computerphile. Thanks for this.
A lot of info compressed into 15 minutes, well done.
If PNG is equally fun to explain then to that next! It would be good to see something lossless in comparison.
Thanks.
George Edwards PNG is unfortunately not as interesting as JPEG.
Wow! I really very badly needed this explanation. Thanks a ton!
He is the coder that rips people off.
Very good explanation. The sheets with tables helped a lot!
terrific video...cleared all the doubts in a flash...thank you sir
Correction: the AC coefficients are compressed by run-length encoding (which will save a lot of space representing the long run of zeros)... we apply DPCM to the DC coefficients... and at the end, everything is compressed by Huffman encoding or Arithmetic encoding.
FANTASTIC explanation.
This is a fantastic video and makes what could be a very tricky topic very understandable. The overview of the Lytro from Peta Pixel started me down this rabbit hole. I think something that would be helpful would be 'playlists'. I see "Triangles and Pixels" has a channel, but a suggested flow for this would be great (should I read Huffman before jpeg 0-2). Maybe I am just too lazy :)
If you are still taking topics I would love a bit of information on lens elements, I see on specs that I have 19 elements in 14 groups and some are spherical vs a spherical. I am sure this is a huge topic (without adding coatings) but it would be great if you guys could offer some insight (or maybe someone else in the comments can suggest a great source I have missed).
So this means that if because of a disk writing error one value in the quantization table (or a few) gets messed up, your image is gone for good, right?
Anyway, I found this video really compelling. I don't know how I didn't watch this video earlier (considering that I am subbed) but I have to say that after several attempts of understanding what quantization was I finally understand the basis of it and I am really thankful for it. I now feel confident (and knowledgeable) enough to tackle the challenge of writing a compressing/decompressing algorithm of JPEG.
Best explanation so far! Thank you
Damn, Mike Pound can really draw some freehand cosines
Why isn't the quantisation table symmetric across the diagonal? are we better at seeing horizontal lines than vertical ones?
Kasper Guldmann That's right, it has to do with how your 2 eyes are positioned.
Kasper Guldmann I came here with the exact same question. I guess it means that pictures taken in the wrong orientation (and flipped later) will be of worse quality! Now I'm really curious as to how the values in the quantisation table were decided.
Michael Ferguson Interesting question. You can 'profile' a set of natural pictures (Faces, landscapes, nature, etc) and test how much the image perceptually degrades for each possible value for every coefficient, with that you can make an ideal DCT coef table for any given 'quality level'. This would be a little computationally expensive which probably explains why a lot of JPEGs use standard DCT coef tables.
+Edwin Spellcaster I think you may have missed the point. The question wasn't "What is the quantisation table and how is it applied" (an interesting question whose answer is explained in the video) but rather "Why does the quantisation table have the values it does, when intuition suggests they should be different".
+SerBallister It would be interesting to see that done, though I guess something like that is how the standard values were chosen in the first place.
Michael Ferguson I believe so, I remember reading years back about how VideoCD used natural images to create their DCT and huffman tables.
I'd love to see a video like this explaining music compression (particularly MP3).
This guy is pretty good at drawing those waves.
He did a stellar good job, I feel like I understood everything. I see the asymmetrical quantization table has already been addressed in the comments; I was about to ask.
Another question regarding 6:27 though: can the coefficients for each cosine be computed separately (i.e. in sequence) or does the algorithm need to take all of them into account (as intermediate values) to determine the final values for each?
Adrian I'm not sure why you said "separately" followed by "i.e. in sequence"; if they were able to be computed separately then you wouldn't want to do it in sequence. You'd want to do them in parallel. But to answer the question, yes, they can be computed separately and do not rely on the other ones around them. The definition of the Fourier coefficients is just an integral.
Alexander Reynolds
Yes, you're right. What I meant to express was: separately, without worrying about the others. Thanks for the answer!
Probably one of the best explanation I have ever seen!
Thanks a bunch! Helped with my exam tomorrow
Dr. Mike I love the way you explain things