🚀 go-pugleaf

Here are some recent references on fast DCT algorithms.  (The 1977 reference
given by a previous poster is Stone Age DCT technology.)

Incidentally, the current public release (v3) of the free JPEG code
mentioned by Eric Praetzel uses an old, not very good DCT algorithm (Iron
Age maybe :-)).  The Loeffler et al. paper cited below describes the algorithm
that will be used in the next release, unless we discover something else is
better.

				tom lane
				organizer, Independent JPEG Group

-------------------------
To: IJG mailing list
Subject: DCT references
Date: Tue, 14 Jul 92 11:13:45 -0400
From: Tom_Lane@G.GP.CS.CMU.EDU

> BTW, I'm looking for papers describing fast DCT routines. Has somebody
> out here some reference to give me ? Thanks.

I did a literature search before settling on the LL&M algorithm used in the
new (v3a) code.  The best places to look are recent conference proceedings:
ICASSP (IEEE Intl. Conf. on Acoustics, Speech, and Signal Processing),
ICCAS (IEEE Intl. Conf. on Circuits and Systems), DCC (Data Compression
Conference).  Also look at the IEEE Transactions for ASSP (recently renamed
just Tr. Signal Processing) and IEEE Tr. for Circuits and Systems.

In particular, I have copies of these articles on my desk:

Polynomial Transform Computation of the 2-D DCT, Duhamel & Guillemot,
  ICASSP '90 p. 1515.
A Forward-Mapping Realization of the Inverse DCT, McMillan & Westover,
  DCC '92 p. 219.
A Fast Algorithm for 2-D DCT, Cho, Yun & Lee, ICASSP '91 p. 2197.
Fast Algorithm and Implementation of 2-D DCT, Cho & Lee, Tr. CAS v38 p. 297.
A DCT Chip based on a new Structured and Computationally Efficient DCT
  Algorithm, Duhamel, Guillemot & Carlach, ICCAS '90 p. 77.
Trade-offs in the Computation of Mono- and Multi-dimensional DCTs,
  Vetterli, Duhamel & Guillemot, ICASSP '89 p. 999.
Practical Fast 1-D DCT Algorithms with 11 Multiplications,
  Loeffler, Ligtenberg & Moschytz, ICASSP '89 p. 988.
New Scaled DCT Algorithms for Fused Multiply/Add Architectures,
  Linzer & Feig, ICASSP '91 p. 2201.
Fast Algorithms for the 2-D Discrete Cosine Transform, Kamangar & Rao,
  IEEE Tr. Computers, v C-31 p. 899.
Fast 2-D Discrete Cosine Transform, Vetterli, ICASSP '85 p. 1538.
A Two-Dimensional Fast Cosine Transform, Haque, Tr. ASSP v ASSP-33 p. 1532.
Real-Time Parallel and Fully Pipelined 2-D DCT Lattice Structures with
  Application to HDTV Systems, Chiu & Liu, Tr. CAS for Video Tech, v 2 p. 25.

The Rao & Yip book cited in the v3 DCT code is a good overall introduction,
with an extensive (though now dated) bibliography.

Although the 2-D methods look good from the point of view of minimal number
of multiplications, they aren't necessarily a win in practice, especially
since many of them calculate the denormalized DCT which means you need extra
multiplications to get the correct DC terms.  Also, some of the methods
described above may be subject to patents.  (LL&M is public domain.)

I'm a bit burnt out on the DCT problem, so if other people want to
investigate further algorithm improvements, it's fine with me.

				regards, tom lane