Fast DCT transformation

Question

Standard equation for generating DCT coefficients in JPEG compression process is DCT formula given by:

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

Answer 1

Yes, this general version is slow, very slow indeed. There are much faster approximation out there.

Fastest software DCT transformation can be found within the BinDCT family.

They only need some basic additions and shifts, and are therefore very fast, at the expense of some precision.

An excellent presentation of it : On the Process of Realizing the Best BinDCT Configuration for Image Compression (especially slide 12)

Answer 2

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

The Hadamard Transform is an exact low complexity transform and gives results similar to the DCT (it can be considered an approximate of the DCT) but requires no multiplication. As a result, implementations of the HT are very fast.