5 ms·

How are images compressed? An explanation of JPEG [video]

103 points by davidbarker 4y ago

diogenes_of_ak 4y ago
Oh! Hey! I just did something like this! I was messing around and used SVD to write a compressor. Do I dare share my feeble GitHub here lol
- texaslonghorn5 4y ago
  Please do!
  - diogenes_of_ak 4y ago
    Debating it - my GitHub account is basically my name… so yah… debating the subsequent loss of anonymity
    - unnouinceput 4y ago
      Then create another one, and share that one. It's not like there is a limit of how many GitHub accounts you can have.
- gabsens 4y ago
  Sounds similar to performing PCA and keeping only the top eigenvectors
  - IIAOPSW 4y ago
    Any sufficiently good compression algorithm is inherently also a dimensionality reduction algorithm, reducing the representation down to as few dimensions as needed. This simple fact is suggestive of an origin to a number of cognitive abilities. Out of a system which evolves only for condensed representation, the ability to discern patterns in the represented things emerges for free.
Guzba 4y ago
I recently helped work on a new open source JPEG decoder in Nim. (Over here on GitHub: https://github.com/treeform/pixie/blob/master/src/pixie/fileformats/jpeg.nim https://github.com/treeform/pixie/blob/master/src/pixie/file...) This video was extremely helpful to understand the "why" of all the things the spec was trying to explain. It made a huge difference in us being able to get things working. We talk a bit about JPEG and actually writing our decoder in Nim here: https://www.youtube.com/watch?v=vYwD7OynFcg https://www.youtube.com/watch?v=vYwD7OynFcg Overall, our concluding opinion is that JPEG has some extremely cool and really smart ideas for how to compress images but the binary file format itself has some very painful things in it (progressive and restart markers as a couple examples).
- Sesse__ 4y ago
  The amazing thing is how well JPEG performs for something that is pretty simple and worked (although very slowly) on 1992 hardware. (I don't mind restart markers, BTW, but stuffing definitely was a mistake.) Look at the state of the art in video codecs in 1992 versus today, then consider that we still make new image formats that can beat JPEG only on PSNR (not perceived quality), or in very narrow niches like super-low bit rates. As the quote goes, “it's like alien technology from the future”. JPEG XL appears to finally be getting there, with a meaningful improvement. But still nothing like 3x. Also perhaps AVIF, but current encoders have problems with rough texture on high bitrates.
  - TacticalCoder 4y ago
    It's the same with the, even older, CD audio format. Sure, it's lossless and uncompressed but stereo 16-bit 44.1 kHz was a stroke of genius. In 1980. Some may argue about lossy audio format (as it the nineties called and wanted their 20 GB HDD back) while others may argue about SACD, 24 bit 96 kHz and whatnots but the fact stays: there are engineers out there who came up with the CD audio format in 1980, which is still in use to this day. I legally and bit-perfectly rip my CDs to FLAC files and it still boggles my mind that it's basically the format from 1980 (FLAC files are lossless and you can re-burn the exact same identical CD, which you can then, if you fancy so, re-rip to the exact same, bit perfect, WAV or FLAC files, rinse & repeat as many times as you want). Speakers definitely got better. DACs are ubiquitous now. Amps probably got better too. But 16-bit 44.1 kHz stereo lives on since 42 years (40 years commercially). Soon half a century. "It's like alien technology from the future" indeed.
Traubenfuchs 4y ago
I was disheartened right at the beginning at the color space conversion: Why is there no green chrominance? Is the chrimonance quantization done for both red and blue chrominance?
- astrange 4y ago
  You don’t need it. Y has all the info you need.
- vanderZwan 4y ago
  The calculated red and blue chrominance values can be both positive and negative. The latter may sound a bit ridiculous in isolation, but if you combine it with luminance it works out: you can subtract blue and red from white to reconstruct green.
GeertJohan 4y ago
The QOI format is relatively easy to understand, explained in a single page pdf file. I found it very interesting, knowing nothing of image encoding/compression. https://qoiformat.org/ https://qoiformat.org/
- vanderZwan 4y ago
  It's great but it's an entirely different beast, being both lossless and designed to be fast and minimal above everything else. It works by minimizing the overhead of encoding deltas and run-lengths.
vanderZwan 4y ago
Out of curiosity: why did they decide to go with a zig-zag pattern instead of grouping same frequencies of each block together? That way you'd end up with even longer runs of zeros. edit: is that perhaps how progressive jpegs work and is that why they typically compress better?

103 points by davidbarker 4y ago

Oh! Hey! I just did something like this! I was messing around and used SVD to write a compressor. Do I dare share my feeble GitHub here lol

texaslonghorn5 4y ago
Please do!
- diogenes_of_ak 4y ago
  Debating it - my GitHub account is basically my name… so yah… debating the subsequent loss of anonymity
  - unnouinceput 4y ago
    Then create another one, and share that one. It's not like there is a limit of how many GitHub accounts you can have.
gabsens 4y ago
Sounds similar to performing PCA and keeping only the top eigenvectors
- IIAOPSW 4y ago
  Any sufficiently good compression algorithm is inherently also a dimensionality reduction algorithm, reducing the representation down to as few dimensions as needed. This simple fact is suggestive of an origin to a number of cognitive abilities. Out of a system which evolves only for condensed representation, the ability to discern patterns in the represented things emerges for free.

Guzba 4y ago

I recently helped work on a new open source JPEG decoder in Nim. (Over here on GitHub: https://github.com/treeform/pixie/blob/master/src/pixie/fileformats/jpeg.nim https://github.com/treeform/pixie/blob/master/src/pixie/file...) This video was extremely helpful to understand the "why" of all the things the spec was trying to explain. It made a huge difference in us being able to get things working. We talk a bit about JPEG and actually writing our decoder in Nim here: https://www.youtube.com/watch?v=vYwD7OynFcg https://www.youtube.com/watch?v=vYwD7OynFcg Overall, our concluding opinion is that JPEG has some extremely cool and really smart ideas for how to compress images but the binary file format itself has some very painful things in it (progressive and restart markers as a couple examples).

Sesse__ 4y ago
The amazing thing is how well JPEG performs for something that is pretty simple and worked (although very slowly) on 1992 hardware. (I don't mind restart markers, BTW, but stuffing definitely was a mistake.) Look at the state of the art in video codecs in 1992 versus today, then consider that we still make new image formats that can beat JPEG only on PSNR (not perceived quality), or in very narrow niches like super-low bit rates. As the quote goes, “it's like alien technology from the future”. JPEG XL appears to finally be getting there, with a meaningful improvement. But still nothing like 3x. Also perhaps AVIF, but current encoders have problems with rough texture on high bitrates.
- TacticalCoder 4y ago
  It's the same with the, even older, CD audio format. Sure, it's lossless and uncompressed but stereo 16-bit 44.1 kHz was a stroke of genius. In 1980. Some may argue about lossy audio format (as it the nineties called and wanted their 20 GB HDD back) while others may argue about SACD, 24 bit 96 kHz and whatnots but the fact stays: there are engineers out there who came up with the CD audio format in 1980, which is still in use to this day. I legally and bit-perfectly rip my CDs to FLAC files and it still boggles my mind that it's basically the format from 1980 (FLAC files are lossless and you can re-burn the exact same identical CD, which you can then, if you fancy so, re-rip to the exact same, bit perfect, WAV or FLAC files, rinse & repeat as many times as you want). Speakers definitely got better. DACs are ubiquitous now. Amps probably got better too. But 16-bit 44.1 kHz stereo lives on since 42 years (40 years commercially). Soon half a century. "It's like alien technology from the future" indeed.

Traubenfuchs 4y ago

I was disheartened right at the beginning at the color space conversion: Why is there no green chrominance? Is the chrimonance quantization done for both red and blue chrominance?

astrange 4y ago
You don’t need it. Y has all the info you need.
vanderZwan 4y ago
The calculated red and blue chrominance values can be both positive and negative. The latter may sound a bit ridiculous in isolation, but if you combine it with luminance it works out: you can subtract blue and red from white to reconstruct green.

GeertJohan 4y ago

The QOI format is relatively easy to understand, explained in a single page pdf file. I found it very interesting, knowing nothing of image encoding/compression. https://qoiformat.org/ https://qoiformat.org/

vanderZwan 4y ago
It's great but it's an entirely different beast, being both lossless and designed to be fast and minimal above everything else. It works by minimizing the overhead of encoding deltas and run-lengths.

vanderZwan 4y ago

Out of curiosity: why did they decide to go with a zig-zag pattern instead of grouping same frequencies of each block together? That way you'd end up with even longer runs of zeros. edit: is that perhaps how progressive jpegs work and is that why they typically compress better?