5 ms·

JPEG: Image Compression Algorithm (2017)

126 points by max_ 5y ago

theandrewbailey 5y ago
I would love to see breakdowns like this for newer image formats, like AVIF, JPEG XL, and WebP.
- yboris 5y ago
  For JPEG XL there are some nice articles: https://cloudinary.com/blog/how_jpeg_xl_compares_to_other_image_codecs https://cloudinary.com/blog/how_jpeg_xl_compares_to_other_im... https://cloudinary.com/blog/time_for_next_gen_codecs_to_dethrone_jpeg https://cloudinary.com/blog/time_for_next_gen_codecs_to_deth...
shp0ngle 5y ago
When you see ~ in the URL, you know it's the good stuff.
LeoPanthera 5y ago
30 years old in September.
- system2 5y ago
  I know JPEG is old but why does the article say March 2017?
  - can16358p 5y ago
    The particular article is probably written in 2017.
Jasper_ 5y ago
If you ever wanted to write your own JPEG decoder for fun, I recommend Cristi Cuturicu's notes. I wrote my decoder using nothing more than this, and it was a ton of fun. http://www.opennet.ru/docs/formats/jpeg.txt http://www.opennet.ru/docs/formats/jpeg.txt
- tyingq 5y ago
  I found this pure python implementation very easy to follow: https://github.com/ghallak/jpeg-python/blob/master/decoder.py https://github.com/ghallak/jpeg-python/blob/master/decoder.p... Some of the helper functions in this separate file: https://github.com/ghallak/jpeg-python/blob/master/utils.py https://github.com/ghallak/jpeg-python/blob/master/utils.py
- userbinator 5y ago
  I wrote one using the official spec --- it has some very useful flowcharts --- but I do recommend writing a JPEG decoder as a short but possibly open-ended exercise, because the results are very perceptible and fun. GIF isn't hard either, and once you've done those, you can move on to video codecs.
jonatron 5y ago
The Computerphile "How JPEG works" playlist is pretty good: https://www.youtube.com/playlist?list=PLzH6n4zXuckoAod3z31QEST1ZaizBuNHh https://www.youtube.com/playlist?list=PLzH6n4zXuckoAod3z31QE... Specifically I found the DCT explanation useful
yboris 5y ago
Obligatory comment about the upcoming replacement of JPEG: JPEG XL (.jxl) -- better in every way! https://jpegxl.info/ https://jpegxl.info/
- mistercow 5y ago
  Well, better in every way except for implementation complexity. It would be an interesting project to try to make a codec that can be implemented in, say, a few hundred lines of code, and can beat JPEG on quality/size while being somewhere in the ballpark on performance (or swap those last two constraints).
SavantIdiot 5y ago
This glosses over the best part: the quantized DCT is where the magic happens. Basically the 8x8 block is converted in to one of a handful (64) different possible choices, they look kinda like electron orbitals, modulated by coefficients. I didn't understand JPEG until I saw this matrix of choices and then a light went on and I understand why the DCT was necessary. Basically the entire image is reduced down to a finite collection of pre-computed shapes. https://image.slidesharecdn.com/jpeg-dct-131006054709-phpapp01/95/jpeg-dct-12-638.jpg?cb=1381039084 https://image.slidesharecdn.com/jpeg-dct-131006054709-phpapp...
- jarenmf 5y ago
  That's interesting, I'm a bit confused, in this case high frequencies are not removed they are just quantized like all other frequencies. How is this reconciled with the assumption that high frequencies carry little information?
  - tinus_hn 5y ago
    Where is the contradiction? As far as the theory goes, the transform using the DCT is lossless apart from rounding errors. The quantization step just rounds more roughly. Which is where the lossy compression happens. Basically you’re not removing the high frequencies because they carry little information, you remove the information they carry. If you just remove the high frequency you end up with a blurred, smooth picture that doesn’t look like the original. But if you quantize the strength you get a pretty similar looking picture, apart from the degenerate case of sharp edges in a drawing.
    - magicalhippo 5y ago
      > If you just remove the high frequency you end up with a blurred, smooth picture that doesn’t look like the original. Well it looks like a blurred, smoothed picture. This can be exploited during decoding if you want a smaller size than the original. For example if you only decode the 2x2 lower-frequency components of a 2000x1000 image, you get a nice downsampled 500x250 image "for free". For example when making thumbnails this can be very useful, as for larger images you can often use just 2x2 or 1x1, dramatically cutting down the work needed for the final resample.
jaclaz 5y ago
Still, as a non-programmer, if everything is so "easy" isn't it surprising that there are very few actually working (free/low cost) JPEG recovery/repair programs? A very minor corruption in the file and poof you can retrieve nothing. Many years ago there was a single program[1] that could, in a very small subset of cases, "fix" corrupted JPEG files (manually/inteactively), now (AFAIK) there is almost only [2] and [3] and this (service) [4] that actually produce (in some cases) good results. In my (admitted) ignorance on the matter, I would have expected that with progresses like increased computer power, AI, deep fakes or whatever the problem by now was - if not solved - at least solved in a number of subset of cases. [1] https://directory.s2services.com/jpg-bmp.htm https://directory.s2services.com/jpg-bmp.htm [2] https://www.jpegmedic.com/tools/jpegmedic/ https://www.jpegmedic.com/tools/jpegmedic/ https://www.jpegmedic.com/tools/ https://www.jpegmedic.com/tools/ [3] https://www.hketech.com/ https://www.hketech.com/ [4] https://www.disktuna.com/ https://www.disktuna.com/
- kevmo314 5y ago
  I've never run across only a corrupted jpeg file, only something like entire fs corruption. So as someone who works in this space it's not so surprising because while I could probably write one it's not a problem I've ever thought of solving.
  - jaclaz 5y ago
    Well, you are lucky. It is actually quite common to find partial/corrupted images. Typically an image will have a grey band/area or it will be "shifted" in some parts, some examples are here: https://www.jpegmedic.com/tools/jpegmedic/ https://www.jpegmedic.com/tools/jpegmedic/ Even checking if a file or an extent on disk is actually an image is not as easy as it seems (JFYI): https://www.forensicfocus.com/forums/mobile-forensics/jpeg-carving-identifying-recovering/ https://www.forensicfocus.com/forums/mobile-forensics/jpeg-c...
- mistercow 5y ago
  This is just inherent to compression. The whole idea is to represent many bytes of data with fewer bytes. That means that the bytes you have each tend to count for a lot. So a small corruption has a huge effect. To solve this, the format itself needs to incorporate error correction. There are various ways to do that with different trade-offs, but all of them will hurt your compression ratio, because the only way to correct errors is to have some kind of redundancy, and removing redundancy is precisely what compression is about.
bob1029 5y ago
Check out libjpegturbo if you are looking for one of the faster ways to do this. I've used it for experimental UI projects and had no problem chewing through 1080p bitmap encodes with latency for each somewhere around 5 milliseconds.

126 points by max_ 5y ago

theandrewbailey 5y ago

I would love to see breakdowns like this for newer image formats, like AVIF, JPEG XL, and WebP.

yboris 5y ago
For JPEG XL there are some nice articles: https://cloudinary.com/blog/how_jpeg_xl_compares_to_other_image_codecs https://cloudinary.com/blog/how_jpeg_xl_compares_to_other_im... https://cloudinary.com/blog/time_for_next_gen_codecs_to_dethrone_jpeg https://cloudinary.com/blog/time_for_next_gen_codecs_to_deth...

shp0ngle 5y ago

When you see ~ in the URL, you know it's the good stuff.

LeoPanthera 5y ago

30 years old in September.

system2 5y ago
I know JPEG is old but why does the article say March 2017?
- can16358p 5y ago
  The particular article is probably written in 2017.

Jasper_ 5y ago

If you ever wanted to write your own JPEG decoder for fun, I recommend Cristi Cuturicu's notes. I wrote my decoder using nothing more than this, and it was a ton of fun. http://www.opennet.ru/docs/formats/jpeg.txt http://www.opennet.ru/docs/formats/jpeg.txt

tyingq 5y ago
I found this pure python implementation very easy to follow: https://github.com/ghallak/jpeg-python/blob/master/decoder.py https://github.com/ghallak/jpeg-python/blob/master/decoder.p... Some of the helper functions in this separate file: https://github.com/ghallak/jpeg-python/blob/master/utils.py https://github.com/ghallak/jpeg-python/blob/master/utils.py
userbinator 5y ago
I wrote one using the official spec --- it has some very useful flowcharts --- but I do recommend writing a JPEG decoder as a short but possibly open-ended exercise, because the results are very perceptible and fun. GIF isn't hard either, and once you've done those, you can move on to video codecs.

jonatron 5y ago

The Computerphile "How JPEG works" playlist is pretty good: https://www.youtube.com/playlist?list=PLzH6n4zXuckoAod3z31QEST1ZaizBuNHh https://www.youtube.com/playlist?list=PLzH6n4zXuckoAod3z31QE... Specifically I found the DCT explanation useful

yboris 5y ago

Obligatory comment about the upcoming replacement of JPEG: JPEG XL (.jxl) -- better in every way! https://jpegxl.info/ https://jpegxl.info/

mistercow 5y ago
Well, better in every way except for implementation complexity. It would be an interesting project to try to make a codec that can be implemented in, say, a few hundred lines of code, and can beat JPEG on quality/size while being somewhere in the ballpark on performance (or swap those last two constraints).

SavantIdiot 5y ago

This glosses over the best part: the quantized DCT is where the magic happens. Basically the 8x8 block is converted in to one of a handful (64) different possible choices, they look kinda like electron orbitals, modulated by coefficients. I didn't understand JPEG until I saw this matrix of choices and then a light went on and I understand why the DCT was necessary. Basically the entire image is reduced down to a finite collection of pre-computed shapes. https://image.slidesharecdn.com/jpeg-dct-131006054709-phpapp01/95/jpeg-dct-12-638.jpg?cb=1381039084 https://image.slidesharecdn.com/jpeg-dct-131006054709-phpapp...

jarenmf 5y ago
That's interesting, I'm a bit confused, in this case high frequencies are not removed they are just quantized like all other frequencies. How is this reconciled with the assumption that high frequencies carry little information?
- tinus_hn 5y ago
  Where is the contradiction? As far as the theory goes, the transform using the DCT is lossless apart from rounding errors. The quantization step just rounds more roughly. Which is where the lossy compression happens. Basically you’re not removing the high frequencies because they carry little information, you remove the information they carry. If you just remove the high frequency you end up with a blurred, smooth picture that doesn’t look like the original. But if you quantize the strength you get a pretty similar looking picture, apart from the degenerate case of sharp edges in a drawing.
  - magicalhippo 5y ago
    > If you just remove the high frequency you end up with a blurred, smooth picture that doesn’t look like the original. Well it looks like a blurred, smoothed picture. This can be exploited during decoding if you want a smaller size than the original. For example if you only decode the 2x2 lower-frequency components of a 2000x1000 image, you get a nice downsampled 500x250 image "for free". For example when making thumbnails this can be very useful, as for larger images you can often use just 2x2 or 1x1, dramatically cutting down the work needed for the final resample.

jaclaz 5y ago

Still, as a non-programmer, if everything is so "easy" isn't it surprising that there are very few actually working (free/low cost) JPEG recovery/repair programs? A very minor corruption in the file and poof you can retrieve nothing. Many years ago there was a single program[1] that could, in a very small subset of cases, "fix" corrupted JPEG files (manually/inteactively), now (AFAIK) there is almost only [2] and [3] and this (service) [4] that actually produce (in some cases) good results. In my (admitted) ignorance on the matter, I would have expected that with progresses like increased computer power, AI, deep fakes or whatever the problem by now was - if not solved - at least solved in a number of subset of cases. [1] https://directory.s2services.com/jpg-bmp.htm https://directory.s2services.com/jpg-bmp.htm [2] https://www.jpegmedic.com/tools/jpegmedic/ https://www.jpegmedic.com/tools/jpegmedic/ https://www.jpegmedic.com/tools/ https://www.jpegmedic.com/tools/ [3] https://www.hketech.com/ https://www.hketech.com/ [4] https://www.disktuna.com/ https://www.disktuna.com/

kevmo314 5y ago
I've never run across only a corrupted jpeg file, only something like entire fs corruption. So as someone who works in this space it's not so surprising because while I could probably write one it's not a problem I've ever thought of solving.
- jaclaz 5y ago
  Well, you are lucky. It is actually quite common to find partial/corrupted images. Typically an image will have a grey band/area or it will be "shifted" in some parts, some examples are here: https://www.jpegmedic.com/tools/jpegmedic/ https://www.jpegmedic.com/tools/jpegmedic/ Even checking if a file or an extent on disk is actually an image is not as easy as it seems (JFYI): https://www.forensicfocus.com/forums/mobile-forensics/jpeg-carving-identifying-recovering/ https://www.forensicfocus.com/forums/mobile-forensics/jpeg-c...
mistercow 5y ago
This is just inherent to compression. The whole idea is to represent many bytes of data with fewer bytes. That means that the bytes you have each tend to count for a lot. So a small corruption has a huge effect. To solve this, the format itself needs to incorporate error correction. There are various ways to do that with different trade-offs, but all of them will hurt your compression ratio, because the only way to correct errors is to have some kind of redundancy, and removing redundancy is precisely what compression is about.

bob1029 5y ago

Check out libjpegturbo if you are looking for one of the faster ways to do this. I've used it for experimental UI projects and had no problem chewing through 1080p bitmap encodes with latency for each somewhere around 5 milliseconds.