Complexity-distortion tradeoffs in variable complexity 2-D DCT

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: Wendi Pan , Antonio Ortega, Complexity-Scalable Transform Coding Using Variable Complexity Algorithms, Proceedings of the Conference on Data Compression, p.263, March 28-30, 2000
• 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 , Dan Ernst, SimpleScalar: An Infrastructure for Computer System Modeling, Computer, v.35 n.2, p.59-67, February 2002 [doi>10.1109/2.982917]
• 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.

INDEX TERMS

Keywords:
Complexity-Distortion tradeoffs, Discrete Cosine Transform (DCT), Variable Complexity Algorithm (VCA)