14 ms·

The "actual compression magic" has been used before DCT in other codecs, but applied directly to pixels gave lousy results. You can also look at 90's software

by pornel 2y ago

The "actual compression magic" has been used before DCT in other codecs, but applied directly to pixels gave lousy results. You can also look at 90's software video codecs developed when DCT was still too expensive for video. They had all kinds of approaches to quantization and entropy coding, and they all were a pixelated mess. DCT is the key ingredient that enabled compression of photographic content.

HarHarVeryFunny 2y ago
What's so special about DCT for image compression? The main idea of lossy image compression is throwing away file detail, which means converting to frequency domain and throwing away high frequency coefficients. Conceptually FFT would work fine for this, so use of DCT instead seems more like an optimization rather than a key component.
- pizza 2y ago
  In practice there is a difference because FFT would have more edge artifacts at block boundaries - lowering visual quality - and DCT has better energy compaction into lower frequencies meaning longer runs of zeros of higher frequency coefficients after quantization so better compression. Another plus is the DCT only needs real numbers.
  - disqard 2y ago
    There's at least one specific optimization in H.264 (aka "MPEG-4 Part 10") to smooth out these artifacts at block boundaries, called "deblocking". https://en.wikipedia.org/wiki/Deblocking_filter https://en.wikipedia.org/wiki/Deblocking_filter
    - iggldiggl 2y ago
      And then there's the current maintainer of libjpeg, who switched the down- and up-scaling algorithms for chroma subsampling to use DCT scaling because that's mathematically more beautiful, which does introduce some additional artifacts at the block boundaries of each upsampled chroma block.
- Sesse__ 2y ago
  The DCT, just like the DFT, is a discrete version of the (analog) Fourier transform. (FFT is just a clever, fast implementation of the DFT, just like when people say “DCT” they usually mean a similarly fast implementation of the DCT. Call it FCT if you wish.) Where they differ is the assumed boundary conditions; DFT works like Fourier-transforming a signal that is repeated and then loops forever, while DCT is like Fourier-transforming a signal that is _reflected_ and then loops forever. (There is also a related transform called DST, where it assumes the signal is _inverted_ and reflected. It's occasionally useful in solving certain kinds of differential equations; only rarely so in compression.) This matches much better with what happens when you cut out small pieces of a signal, so it gives less noise and thus better energy isolation. Say your little pixel block (let's make it 8x1 for simplicity) is a simple gradient, so it goes 1, 2, 3, 4, 5, 6, 7, 8. What do you think has the least amount of high-frequency content you'd need to deal with; 123456788765432112345678… or 123456781234567812345678…? (There's also a DCT version that goes more like 1234567876543212345678 etc., but that's a different story)
  - derf_ 2y ago
    A DST is optimal when the variance of the signal you are compressing grows linearly (as opposed to the DCT, which is optimal for uniform variance). That happens, for example, when you have a prediction on one side (e.g., intra prediction in image compression) and you are coding the prediction residual. The farther you get from the source of your prediction, the less accurate it is likely to be. Block-based motion compensation prediction residuals in video coding are also not uniform: the prediction error is higher at block edges than the block center, so a DST sometimes works better (e.g., when using a transform size smaller than the motion compensation block size). So still useful for compression, just in more specialized circumstances.
    - Sesse__ 2y ago
      Yes, I think “only rarely useful” covers it :-) I know there are some codecs that support it, e.g. VP9?
      - 2y ago

by pornel 2y ago

HarHarVeryFunny 2y ago

What's so special about DCT for image compression? The main idea of lossy image compression is throwing away file detail, which means converting to frequency domain and throwing away high frequency coefficients. Conceptually FFT would work fine for this, so use of DCT instead seems more like an optimization rather than a key component.

pizza 2y ago
In practice there is a difference because FFT would have more edge artifacts at block boundaries - lowering visual quality - and DCT has better energy compaction into lower frequencies meaning longer runs of zeros of higher frequency coefficients after quantization so better compression. Another plus is the DCT only needs real numbers.
- disqard 2y ago
  There's at least one specific optimization in H.264 (aka "MPEG-4 Part 10") to smooth out these artifacts at block boundaries, called "deblocking". https://en.wikipedia.org/wiki/Deblocking_filter https://en.wikipedia.org/wiki/Deblocking_filter
  - iggldiggl 2y ago
    And then there's the current maintainer of libjpeg, who switched the down- and up-scaling algorithms for chroma subsampling to use DCT scaling because that's mathematically more beautiful, which does introduce some additional artifacts at the block boundaries of each upsampled chroma block.
Sesse__ 2y ago
The DCT, just like the DFT, is a discrete version of the (analog) Fourier transform. (FFT is just a clever, fast implementation of the DFT, just like when people say “DCT” they usually mean a similarly fast implementation of the DCT. Call it FCT if you wish.) Where they differ is the assumed boundary conditions; DFT works like Fourier-transforming a signal that is repeated and then loops forever, while DCT is like Fourier-transforming a signal that is _reflected_ and then loops forever. (There is also a related transform called DST, where it assumes the signal is _inverted_ and reflected. It's occasionally useful in solving certain kinds of differential equations; only rarely so in compression.) This matches much better with what happens when you cut out small pieces of a signal, so it gives less noise and thus better energy isolation. Say your little pixel block (let's make it 8x1 for simplicity) is a simple gradient, so it goes 1, 2, 3, 4, 5, 6, 7, 8. What do you think has the least amount of high-frequency content you'd need to deal with; 123456788765432112345678… or 123456781234567812345678…? (There's also a DCT version that goes more like 1234567876543212345678 etc., but that's a different story)
- derf_ 2y ago
  A DST is optimal when the variance of the signal you are compressing grows linearly (as opposed to the DCT, which is optimal for uniform variance). That happens, for example, when you have a prediction on one side (e.g., intra prediction in image compression) and you are coding the prediction residual. The farther you get from the source of your prediction, the less accurate it is likely to be. Block-based motion compensation prediction residuals in video coding are also not uniform: the prediction error is higher at block edges than the block center, so a DST sometimes works better (e.g., when using a transform size smaller than the motion compensation block size). So still useful for compression, just in more specialized circumstances.
  - Sesse__ 2y ago
    Yes, I think “only rarely useful” covers it :-) I know there are some codecs that support it, e.g. VP9?
    - 2y ago