Complexity-distortion tradeoffs in variable complexity 2-D DCT
Pages 460 - 465
Abstract
Variable complexity algorithms (VCAs) (i.e. algorithms which take a variable, input-dependent amount of time to complete a task) have been proposed to reduce the average computational complexity of compression algorithms for images and videos. In this paper we introduce a new 2-D variable-complexity DCT that can be used to replace the regular discrete cosine transform (DCT), if only a part of DCT coefficients need to be computed. Consequently, the computational complexity of the DCT can be reduced at the cost in degradation of the reconstructed image quality. We investigate fine-grained complexity-distortion tradeoffs for the proposed variable-complexity, separable DCT (VS-DCT). The evaluation includes a theoretical computational complexity analysis of the VS-DCT in terms of the number of additions and multiplications (note in this paper computational complexity does not refer to the polynomial order of operations) and empirical complexity-distortion curves of the VS-DCT running on two distinct platforms, including a desktop personal computer and an embedded system. The results of evaluation show that our VS-DCT can reduce the computational complexity of a regular DCT by up to 10% for every 3dB decrease in the PSNR (peak signal-to-noise ratio) of the reconstructed images.
References
[1]
W. Pan and A. Ortega. Complexity-scalable Transform Coding using Variable Complexity Algorithms. In Proc. of Data Compression Conference (DCC 2000), pp. 263--272, Mar. 2000, Snow Bird, Utah.
[2]
N. Ahmed, T. Natarajan, and K. R. Rao. On image processing and a discrete cosine transform. IEEE Trans. on Computers, vol. C-23, pp. 90--93, 1974.
[3]
E. Feig and S. Winograd. Fast Algorithms for the Discrete Cosine Transform. IEEE Trans. on Signal Processing, vol. 40, no. 9, pp. 2174--2193, 1992.
[4]
E. Feig and S. Winograd. On the multiplicative complexity of discrete cosine transforms. IEEE Trans. on Inform. Theory, vol. 38, pp. 1387--1391, 1992.
[5]
K. Lengwehasatit and A. Ortega. DCT computation based on variable complexity fast approximations. Proc. of Intl' Conf. of Image Proc. (ICIP'98), vol. 3, pp. 95--99, Oct. 1998.
[6]
I-Ming Pao and Ming-Ting Sun. Modeling DCT coefficients for fast video encoding. IEEE Trans. on Circuits and Systems for Video Technology, vol. 9, pp. 608--616, June 1999.
[7]
INTEL, Inc. Intel VTune Performance Analyzer tutorial {on-line document}, available at http://www.intel.com/software/products/college/gs_vtune/index.htm. 2003.
[8]
Todd Austin, Eric Larson, and Dan Ernst. SimpleScalar: An Infrastructure for Computer System Modeling. IEEE Computer, vol. 35, no. 2, pp. 59--67, February 2002.
[9]
W. Pan, A. Ortega, I. Hajj-Ahmad and R. Sannino. Proxy-Based Approaches for IDCT Acceleration. IS&T and SPIE Conf. on Visual Communications and Image Processing (VCIP 2001), Proc. of SPIE, Vol. 4310, pp. 625--636, January 2001.
[10]
De Queiroz, R. L. Variable Complexity DCT Approximations Driven by An HVQ-based Analyzer. IEEE Trans. on Circuits and Systems for Video Technology, Vol. 12, pp. 1021--1024, Nov. 2002.
Recommendations
On the odd-DFT and its applications to DCT/IDCT computation
In this correspondence, efficient algorithms are presented for simultaneous calculation of the odd discrete Fourier transform (odd-DFT) and the real DFT. These algorithms are used to derive a new algorithm to calculate the discrete cosine transform (DCT)...
Bidirectional conversion between DCT coefficients of blocks and their subblocks
Part IIn the context of the discrete Fourier transform (DFT) and the discrete cosine transform (DCT), we present efficient methods for bidirectional conversion between transform coefficients of a signal block (one- or two-dimensional) and transform ...
DCT-domain coder for digital video applications
In this paper, we present an effective DCT-domain video encoder architecture that decreases the computational complexity of conventional hybrid video encoders by reducing the number of transform operations between the pixel and the DCT domains. The ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2004
485 pages
Copyright © 2004 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 02 April 2004
Check for updates
Author Tags
Qualifiers
- Article
Conference
ACM SE04
Sponsor:
Acceptance Rates
Overall Acceptance Rate 502 of 1,023 submissions, 49%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 506Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 26 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in