Fast DCT Conversion

Question

The standard equation for generating DCT coefficients during JPEG compression is a DCT formula expressed by:

I have red that this implementation is expensive (slow), and there is a much faster way. Is there an explicit formula for this faster way to generate DCT coefficients?

Answer 1

Yes, this general version is slow, very slow. There is a much faster approach.

Fast DCT conversion software can be found in the BinDCT family.

They only need basic additions and shifts, and therefore they are very fast, due to some accuracy.

Excellent presentation: On the process of implementing the best BinDCT configuration for image compression (especially slide 12)

Answer 2

Modern video codecs, such as MPEG4-AVC, use Hadamard Transform instead of DCT as a spatial transform.

The Hadamard transform is an exact transform with low complexity and gives results similar to DCT (it can be considered an approximate DCT), but does not require multiplication. As a result, HT implementations are very fast.