Comment by pornel | Hacker News Reader

Comment by pornel | Hacker News Reader

Parent Full thread

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.

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.

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.

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

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.

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)

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.

Yes, I think “only rarely useful” covers it :-) I know there are some codecs that support it, e.g. VP9?

Probably every video coding standard published after c. 2012 has some version of it in its toolbox (including VP9).

Thanks!

Reply on news.ycombinator.com