home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / compress / research / 97 < prev    next >
Encoding:
Text File  |  1992-07-28  |  3.6 KB  |  78 lines
  1. Newsgroups: comp.compression.research
  2. Path: sparky!uunet!paladin.american.edu!darwin.sura.net!mips!sdd.hp.com!usc!rpi!batcomputer!cornell!rochester!cantaloupe.srv.cs.cmu.edu!tgl
  3. From: tgl+@cs.cmu.edu (Tom Lane)
  4. Subject: Re: Fast DCT algorithm
  5. Message-ID: <1992Jul28.161123.274442@cs.cmu.edu>
  6. Date: Tue, 28 Jul 92 16:11:23 GMT
  7. Organization: School of Computer Science, Carnegie Mellon
  8. Nntp-Posting-Host: g.gp.cs.cmu.edu
  9. Summary: some references
  10. References: <1992Jul25.083953.28947@iti.gov.sg> <Bs3KuC.EnM@watserv1.uwaterloo.ca> <1992Jul28.011648.9934@rp.CSIRO.AU>
  11. Keywords: DCT
  12. Lines: 64
  13.  
  14. Here are some recent references on fast DCT algorithms.  (The 1977 reference
  15. given by a previous poster is Stone Age DCT technology.)
  16.  
  17. Incidentally, the current public release (v3) of the free JPEG code
  18. mentioned by Eric Praetzel uses an old, not very good DCT algorithm (Iron
  19. Age maybe :-)).  The Loeffler et al. paper cited below describes the algorithm
  20. that will be used in the next release, unless we discover something else is
  21. better.
  22.  
  23.                 tom lane
  24.                 organizer, Independent JPEG Group
  25.  
  26. -------------------------
  27. To: IJG mailing list
  28. Subject: DCT references
  29. Date: Tue, 14 Jul 92 11:13:45 -0400
  30. From: Tom_Lane@G.GP.CS.CMU.EDU
  31.  
  32. > BTW, I'm looking for papers describing fast DCT routines. Has somebody
  33. > out here some reference to give me ? Thanks.
  34.  
  35. I did a literature search before settling on the LL&M algorithm used in the
  36. new (v3a) code.  The best places to look are recent conference proceedings:
  37. ICASSP (IEEE Intl. Conf. on Acoustics, Speech, and Signal Processing),
  38. ICCAS (IEEE Intl. Conf. on Circuits and Systems), DCC (Data Compression
  39. Conference).  Also look at the IEEE Transactions for ASSP (recently renamed
  40. just Tr. Signal Processing) and IEEE Tr. for Circuits and Systems.
  41.  
  42. In particular, I have copies of these articles on my desk:
  43.  
  44. Polynomial Transform Computation of the 2-D DCT, Duhamel & Guillemot,
  45.   ICASSP '90 p. 1515.
  46. A Forward-Mapping Realization of the Inverse DCT, McMillan & Westover,
  47.   DCC '92 p. 219.
  48. A Fast Algorithm for 2-D DCT, Cho, Yun & Lee, ICASSP '91 p. 2197.
  49. Fast Algorithm and Implementation of 2-D DCT, Cho & Lee, Tr. CAS v38 p. 297.
  50. A DCT Chip based on a new Structured and Computationally Efficient DCT
  51.   Algorithm, Duhamel, Guillemot & Carlach, ICCAS '90 p. 77.
  52. Trade-offs in the Computation of Mono- and Multi-dimensional DCTs,
  53.   Vetterli, Duhamel & Guillemot, ICASSP '89 p. 999.
  54. Practical Fast 1-D DCT Algorithms with 11 Multiplications,
  55.   Loeffler, Ligtenberg & Moschytz, ICASSP '89 p. 988.
  56. New Scaled DCT Algorithms for Fused Multiply/Add Architectures,
  57.   Linzer & Feig, ICASSP '91 p. 2201.
  58. Fast Algorithms for the 2-D Discrete Cosine Transform, Kamangar & Rao,
  59.   IEEE Tr. Computers, v C-31 p. 899.
  60. Fast 2-D Discrete Cosine Transform, Vetterli, ICASSP '85 p. 1538.
  61. A Two-Dimensional Fast Cosine Transform, Haque, Tr. ASSP v ASSP-33 p. 1532.
  62. Real-Time Parallel and Fully Pipelined 2-D DCT Lattice Structures with
  63.   Application to HDTV Systems, Chiu & Liu, Tr. CAS for Video Tech, v 2 p. 25.
  64.  
  65. The Rao & Yip book cited in the v3 DCT code is a good overall introduction,
  66. with an extensive (though now dated) bibliography.
  67.  
  68. Although the 2-D methods look good from the point of view of minimal number
  69. of multiplications, they aren't necessarily a win in practice, especially
  70. since many of them calculate the denormalized DCT which means you need extra
  71. multiplications to get the correct DC terms.  Also, some of the methods
  72. described above may be subject to patents.  (LL&M is public domain.)
  73.  
  74. I'm a bit burnt out on the DCT problem, so if other people want to
  75. investigate further algorithm improvements, it's fine with me.
  76.  
  77.                 regards, tom lane
  78.