7

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?

Nayuki
  • 17,911
  • 6
  • 53
  • 80
MrD
  • 2,423
  • 3
  • 33
  • 57

2 Answers2

7

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)

Cyan
  • 13,248
  • 8
  • 43
  • 78
7

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.

endolith
  • 25,479
  • 34
  • 128
  • 192
flanglet
  • 564
  • 4
  • 11
  • Warning! The simplicity and speed up of the Hadamard transform comes at the expense of invertibility of sub-selections of frequencies and samples. Image compression is done by choosing a sub-selection of frequencies which in combination with corresponding samling selection leads to noninvertibility. To prevent this the algorithm may use a larger frequency distribution, which counteracts the purpose of image compression. See the similar case for DFT: https://math.stackexchange.com/questions/4498591/is-the-amount-of-zero-valued-minors-of-a-size-n-discrete-fourier-transform-matri – David Jonsson Aug 29 '23 at 20:08