Extensions on Low-Complexity DCT Approximations for Larger Blocklengths Based on Minimal Angle Similarity
Authors: 
Anabeth P. Radünz, Luan Portella, R. S. Oliveira, Fábio M. Bayer, Renato J. CintraAuthors Info & Claims
Pages 495 - 516
Abstract
The discrete cosine transform (DCT) is a central tool for image and video coding because it can be related to the Karhunen-Loéve transform (KLT), which is the optimal transform in terms of retained transform coefficients and data decorrelation. In this paper, we introduce 16-, 32-, and 64-point low-complexity DCT approximations by minimizing individually the angle between the rows of the exact DCT matrix and the matrix induced by the approximate transforms. According to some classical figures of merit, the proposed transforms outperformed the approximations for the DCT already known in the literature. Fast algorithms were also developed for the low-complexity transforms, asserting a good balance between the performance and its computational cost. Practical applications in image encoding showed the relevance of the transforms in this context. In fact, the experiments showed that the proposed transforms had better results than the known approximations in the literature for the cases of 16, 32, and 64 blocklength.
References
[1]
Van der Perre L, Liu L, and Larsson EG Efficient DSP and circuit architectures for massive MIMO: State of the art and future directions IEEE Transactions on Signal Processing 2018 66 18 4717-4736
[2]
Domouchtsidis S, Tsinos CG, Chatzinotas S, and Ottersten B Symbol-level precoding for low complexity transmitter architectures in large-scale antenna array systems IEEE Transactions on Wireless Communications 2019 18 2 852-863
[3]
Ibhaze AE, Orukpe PE, and Edeko FO High capacity data rate system: Review of visible light communications technology Journal of Electronic Science and Technology 2020 18 3
[4]
Zhang L, Li W, Wu Y, Lafleche S, Hong Z, Park S-I, Lee J-Y, Kim H-M, Hur N, Iradier E, Angueira P, and Montalban J Using layered division multiplexing for wireless in-band distribution links in next generation broadcast systems IEEE Transactions on Broadcasting 2021 67 1 68-82
[5]
Gonzalez RC and Woods RE Digital image processing, Upper Saddle River 2012 NJ Prentice Hall
[6]
Britanak, V., Yip, P., & Rao, K. R. (2007). Discrete cosine and sine transforms. Academic Press.
[7]
Ochoa-Dominguez, H., & Rao, K. R. (2019). Discrete cosine transform. CRC Press.
[8]
Poularikas, A. D. (2010). Transforms and applications handbook. CRC Press.
[9]
Salomon, D., Motta, G., & Bryant, D. (2007). Data compression: The complete reference. Springer.
[10]
Jain AK Image data compression: A review Proceedings of the IEEE 1981 69 3 349-389
[11]
Welch TA A technique for high-performance data compression Computer 1984 17 6 8-19
[12]
Pennebaker WB and Mitchell JL JPEG Still Image Data Compression Standard 1992 New York, NY Van Nostrand Reinhold
[13]
Jolliffe, I. (2002). Principal component analysis. Wiley Online Library.
[14]
Blahut, R. E. (2010). Fast algorithms for signal processing (2nd ed.). Cambridge University Press.
[15]
Wallace GK The JPEG still picture compression standard IEEE Transactions on Consumer Electronics 1992 38 1 18-34
[16]
Puri, A., Chen, X., & Luthra, A. (2004). Video coding using the H. 264/MPEG-4 AVC compression standard. Signal Processing: Image Communication, 19(9), 793–849.
[17]
Pourazad, M. T., Doutre, C., Azimi, M., & Nasiopoulos, P. (2012). HEVC: The new gold standard for video compression: How does HEVC compare with H.264/AVC? IEEE Consumer Electronics Magazine, 1(3), 36–46.
[18]
Ahmed, N., Natarajan, T., & Rao, K. R. (1974). Discrete cosine transform. IEEE Transactions on Computers, C-23(1), 90–93.
[19]
Clarke RJ Relation between the Karhunen-Loève and cosine transforms IEEE Proceedings F Communications, Radar and Signal Processing 1981 128 6 359-360
[20]
Clarke R Application of sine transform in image processing Electronics Letters 1983 19 13 490-491
[21]
Rao KR and Yip P Discrete cosine transform: Algorithms 1990 Advantages Applications, Academic Press, San Diego, CA
[22]
Sayood, K. (2017). Introduction to data compression. Morgan Kaufmann.
[23]
Rao, K. R., & Yip, P. (2001). The transform and data compression handbook. CRC Press.
[24]
Cintra RJ, Bayer FM, and Tablada C Low-complexity 8-point DCT approximations based on integer functions Signal Processing 2014 99 201-214
[25]
Sheltami T, Musaddiq M, and Shakshuki E Data compression techniques in wireless sensor networks Future Generation Computer Systems 2016 64 151-162
[26]
Haweel TI A new square wave transform based on the DCT Signal Processing 2001 82 2309-2319
[27]
Liang J and Tran TD Fast multiplierless approximation of the DCT with the lifting scheme IEEE Transactions on Signal Processing 2001 49 3032-3044
[28]
Cintra RJ and Bayer FM A DCT approximation for image compression IEEE Signal Processing Letters 2011 18 10 579-582
[29]
Bouguezel S, Ahmad MO, and Swamy MNS Low-complexity 8 × 8 transform for image compression Electronics Letters 2008 44 21 1249-1250
[30]
Bouguezel, S., Ahmad, M. O., & Swamy, M. N. S. (2010). A novel transform for image compression. In 2010 53rd IEEE International Midwest Symposium on Circuits and Systems (pp. 509–12).
[31]
Tablada CJ, Bayer FM, and Cintra RJ A class of DCT approximations based on the Feig-Winograd algorithm Signal Processing 2015 113 38-51
[32]
Bayer FM and Cintra RJ DCT-like transform for image compression requires 14 additions only Electronics Letters 2012 48 15 919-921
[33]
Coutinho, V. A., Cintra, R. J., Bayer, F. M., Kulasekera, S., & Madanayake, A. (2015) A multiplier less pruned DCT-like transformation for image and video compression that requires ten additions only. Journal of Real-Time Image Processing, 1–9.
[34]
Oliveira RS, Cintra RJ, Bayer FM, da Silveira TL, Madanayake A, and Leite A Low-complexity 8-point DCT approximation based on angle similarity for image and video coding Multidimensional Systems and Signal Processing 2019 30 3 1363-1394
[35]
Shi, Y. Q., & Sun, H. (1999). Image and video compression for multimedia engineering: Fundamentals, algorithms, and standards. CRC Press.
[36]
Zhao X, Kim S-H, Zhao Y, Egilmez HE, Koo M, Liu S, Lainema J, and Karczewicz M Transform coding in the VVC standard IEEE Transactions on Circuits and Systems for Video Technology 2021 31 10 3878-3890
[37]
Bayer, F. M., Cintra, R. J., Edirisuriya, A., Madanayake, A. (2012, November). A digital hardware fast algorithm and FPGA-based prototype for a novel 16-point approximate DCT for image compression applications. Measurement Science and Technology,23(8).
[38]
da Silveira TL, Oliveira RS, Bayer FM, Cintra RJ, and Madanayake A Multiplierless 16-point DCT approximation for low-complexity image and video coding Signal, Image and Video Processing 2017 11 2 227-233
[39]
Coelho, D. F., Cintra, R. J., Madanayake, A., & Perera, S. M. (2021). Low-complexity scaling methods for DCT-II approximations. IEEE Transactions on Signal Processing, 1–1.
[40]
Canterle DR, da Silveira TL, Bayer FM, and Cintra RJ A multiparametric class of low-complexity transforms for image and video coding Signal Processing 2020 176
[41]
Coelho DF, Cintra RJ, and Dimitrov VS Efficient computation of the 8-point DCT via summation by parts Journal of Signal Processing Systems 2018 90 4 505-514
[42]
Sun H, Cheng Z, Gharehbaghi AM, Kimura S, and Fujita M Approximate DCT design for video encoding based on novel truncation scheme IEEE Transactions on Circuits and Systems I: Regular Papers 2019 66 4 1517-1530
[43]
Zeng, Y., Sun, H., Katto, J., & Fan, Y. (2021). Approximated reconfigurable transform architecture for VVC. In 2021 IEEE International Symposium on Circuits and Systems (ISCAS) (pp. 1–5).
[44]
Liang, W.-D., & Liu, X.-D. (2021). Comparison of approximate DCT and approximate DTT for image compression. In 2021 IEEE 2nd International Conference on Big Data, Artificial Intelligence and Internet of Things Engineering (pp. 337–41).
[45]
Paim, G., Fonseca, M., Costa, E., & Almeida, S. (2015). Power efficient 2-D rounded cosine transform with adder compressors for image compression. In 2015 IEEE International Conference on Electronics, Circuits, and Systems (ICECS) (pp. 348–51).
[46]
Almurib HA, Kumar TN, and Lombardi F Approximate DCT image compression using inexact computing IEEE Transactions on Computers 2018 67 2 149-159
[47]
Puchala D Approximate calculation of 8-point DCT for various scenarios of practical applications EURASIP Journal on Image and Video Processing 2021 2021 1 1-34
[48]
Belyaev, E., Bie, L., & Korhonen, J. (2020). Motion JPEG decoding via iterative thresholding and motion-compensated deflickering. In 2020 IEEE 22nd International Workshop on Multimedia Signal Processing (MMSP) (pp. 1–6).
[49]
Busson, A. J., Mendes, P. R., de Moraes, D. S., da Veiga, Á. M., Guedes, Á. L. V., & Colcher, S. (2020). Video quality enhancement using deep learning-based prediction models for quantized DCT coefficients in MPEG I-frames. In 2020 IEEE International Symposium on Multimedia (ISM) (pp. 29–32).
[50]
Singhadia A, Mamillapalli M, and Chakrabarti I Hardware-efficient 2D-DCT/IDCT architecture for portable HEVC-compliant devices IEEE Transactions on Consumer Electronics 2020 66 3 203-212
[51]
Masera M, Masera G, and Martina M An area-efficient variable-size fixed-point DCT architecture for HEVC encoding IEEE Transactions on Circuits and Systems for Video Technology 2020 30 1 232-242
[52]
Maher J and Meher PK Scalable approximate DCT architectures for efficient HEVC-compliant video coding IEEE Transactions on Circuits and Systems for Video Technology 2017 27 8 1815-1825
[53]
Suresh, H., Hegde, S., & Sartori, J. (2017). Approximate compression: Enhancing compressibility through data approximation. In Proceedings of the 15th IEEE/ACM Symposium on Embedded Systems for Real-Time Multimedia (pp. 41–50).
[54]
Sidaty, N., Hamidouche, W., Déforges, O., Philippe, P., & Fournier, J. (2019). Compression performance of the versatile video coding: HD and UHD visual quality monitoring. In 2019 Picture Coding Symposium (PCS) (pp. 1–5).
[55]
Dong J, Ngan KN, Fong C-K, and Cham W-K 2-D order-16 integer transforms for HD video coding IEEE Transactions on Circuits and Systems for Video Technology 2009 19 10 1462-1474
[56]
Thiripurasundari C, Sumathy V, and Thiruvengadam C An FPGA implementation of novel smart antenna algorithm in tracking systems for smart cities Computers & Electrical Engineering 2018 65 59-66
[57]
Madanayake A, Cintra RJ, Dimitrov V, Bayer F, Wahid KA, Kulasekera S, Edirisuriya A, Potluri U, Madishetty S, and Rajapaksha N Low-power VLSI architectures for DCT/DWT: Precision vs approximation for HD video, biomedical, and smart antenna applications IEEE Circuits and Systems Magazine 2015 15 1 25-47
[58]
Rajapaksha N, Edirisuriya A, Madanayake A, Cintra RJ, Onen D, Amer I, and Dimitrov VS Asynchronous realization of algebraic integer-based 2D DCT using Achronix Speedster SPD60 FPGA Journal of Electrical and Computer Engineering 2013 2013 1-9
[59]
Madishetty SK, Madanayake A, Cintra RJ, Dimitrov VS, and Mugler DH VLSI architectures for the 4-tap and 6-tap 2-D daubechies wavelet filters using algebraic integers IEEE Transactions on Circuits and Systems I: Regular Papers 2012 60 6 1455-1468
[60]
Haghighat MBA, Aghagolzadeh A, and Seyedarabi H Multi-focus image fusion for visual sensor networks in DCT domain Computers & Electrical Engineering 2011 37 5 789-797
[61]
Liang Y, Liu G, Zhou N, and Wu J Image encryption combining multiple generating sequences controlled fractional DCT with dependent scrambling and diffusion Journal of Modern Optics 2015 62 4 251-264
[62]
Wahid, K., Ko, S.-B., & Teng, D. (2008). Efficient hardware implementation of an image compressor for wireless capsule endoscopy applications. In 2008 IEEE International Joint Conference on Neural Networks (pp. 2761–2765). IEEE.
[63]
Wahid, K. A., Islam, M. A., & Ko, S.-B. (2011). Lossless implementation of Daubechies 8-tap wavelet transform. In 2011 IEEE International Symposium of Circuits and Systems (pp. 2157–2160). IEEE.
[64]
Chiper, D. F., & Cotorobai, L. T. (2020). A novel VLSI algorithm for a low complexity VLSI implementation of DCT based on pseudo circular correlation structures. In 2020 International Symposium on Electronics and Telecommunications (pp. 1–4).
[65]
Chung R-L, Chen C-W, Chen C-A, Abu PAR, and Chen S-L VLSI implementation of a cost-efficient Loeffler DCT algorithm with recursive CORDIC for DCT-based encoder Electronics 2021 10 7 862
[66]
Hsiao S-F, Hu YH, Juang T-B, and Lee C-H Efficient VLSI implementations of fast multiplierless approximated DCT using parameterized hardware modules for silicon intellectual property design IEEE Transactions on Circuits and Systems I: Regular Papers 2005 52 8 1568-1579
[67]
SenthilPari, C., Nirmal Raj, M. I. T., Kumar, P. V., & Francisca, J. S. (2018). Design a low voltage amp; low power multiplier-free pipelined DCT architecture using hybrid full adder. In 2018 IEEE 5th International Conference on Engineering Technologies and Applied Sciences (ICETAS) (pp. 1–6).
[68]
Saponara S Real-time and low-power processing of 3D direct/inverse discrete cosine transform for low-complexity video codec Journal of Real-Time Image Processing 2012 7 1 43-53
[69]
Bahar, A. N., & Wahid, K. A. (2020). Design and implementation of approximate DCT architecture in quantum-dot cellular automata. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 28(12), 2530–2539.
[70]
Lee D-U, Kim H, Rahimi M, Estrin D, and Villasenor JD Energy-efficient image compression for resource-constrained platforms IEEE Transactions on Image Processing 2009 18 9 2100-2113
[71]
Mechouek K, Kouadria N, Doghmane N, and Kaddeche N Low complexity DCT approximation for image compression in wireless image sensor networks Journal of Circuits Systems and Computers 2016 25 08 1650088
[72]
Zidani, N., Kouadria, N., Doghmane, N. & Harize, S. (2019). Low complexity pruned DCT approximation for image compression in wireless multimedia sensor networks. In 2019 5th International Conference on Frontiers of Signal Processing (ICFSP) (pp. 26–30).
[73]
Ma, S., & Ampadu, P. (2019). Approximate memory with approximate DCT. In Proceedings of the 2019 on Great Lakes Symposium on VLSI (pp. 355–358).
[74]
Campobello, G., Segreto, A., Zanafi, S., & Serrano, S. (2017) RAKE: a simple and efficient lossless compression algorithm for the internet of things. In 2017 25th European Signal Processing Conference (EUSIPCO) (pp. 2581–5).
[75]
Hamza, R., Hassan, A., & Patil, A. S. (2019). A lightweight secure IoT surveillance framework based on DCT-DFRT algorithms. In International Conference on Machine Learning for Cyber Security (pp. 271–8). Springer.
[76]
Ma, Z., Hu, T., Shen, L., Kong, W., & Zhao, B. (2015). A detection and relative direction estimation method for UAV in sense-and-avoid. In 2015 IEEE International Conference on Information and Automation (pp. 2677–2682).
[77]
Margelis G, Fafoutis X, Oikonomou G, Piechocki R, Tryfonas T, and Thomas P Efficient DCT-based secret key generation for the internet of things Ad Hoc Networks 2019 92
[78]
Kansal L, Gaba GS, Chilamkurti N, and Kim B-G Efficient and robust image communication techniques for 5G applications in smart cities Energies 2021 14 13 3986
[79]
Potluri U, Madanayake A, Cintra R, Bayer F, and Rajapaksha N Multiplier-free DCT approximations for RF multi-beam digital aperture-array space imaging and directional sensing Measurement Science and Technology 2012 23 11
[80]
Kulasekera, S., Madanayake, A., Suarez, D., Cintra, R. J., & Bayer, F. M. (2015). Multi-beam receiver apertures using multiplierless 8-point approximate DFT. In 2015 IEEE Radar Conference (RadarCon) (pp. 1244–9). IEEE.
[81]
Zhang J, Shi W, Zhou L, Gong R, Wang L, and Zhou H A low-power and high-PSNR unified DCT/IDCT architecture based on EARC and enhanced scale factor approximation IEEE Access 2019 7 165684-165691
[82]
Madanayake A, Cintra RJ, Akram N, Ariyarathna V, Mandal S, Coutinho VA, Bayer FM, Coelho D, and Rappaport TS Fast radix-32 approximate DFTs for 1024-beam digital RF beamforming IEEE Access 2020 8 96613-96627
[83]
Jain, R., & Jain, P. (2021). FPGA implementation of recursive algorithm of DCT. In Proceedings of International Conference on Artificial Intelligence and Applications (pp. 203–12). Springer.
[84]
Escobar, R. V., Patiño, A. M., Moreno, I. M., Ramírez, M. G., Archundia, E. R., & Gnecchi, J. A. G. (2020). Evaluation and comparison of DCT approximations on FPGA for hardware reduction. In 2020 IEEE International Autumn Meeting on Power, Electronics and Computing (Vol. 4, pp. 1–5).
[85]
Tsounis I, Papadimitriou A, and Psarakis M Analyzing the impact of approximate adders on the reliability of FPGA accelerators, in IEEE European Test Symposium 2021 2021 1-2
[86]
Higham, N. J. (2008). Functions of matrices: Theory and computation. SIAM.
[87]
Flury B and Gautschi W An algorithm for simultaneous orthogonal transformation of several positive definite symmetric matrices to nearly diagonal form SIAM Journal on Scientific and Statistical Computing 1986 7 1 169-184
[88]
Bouguezel S, Ahmad MO, and Swamy M A low-complexity parametric transform for image compression, in IEEE International Symposium of Circuits and Systems 2011 2011 2145-2148
[89]
Lengwehasatit K and Ortega A Scalable variable complexity approximate forward DCT IEEE Transactions on Circuits and Systems for Video Technology 2004 14 11 1236-1248
[90]
Feig E and Winograd S Fast algorithms for the discrete cosine transform IEEE Transactions on Signal Processing 1992 40 9 2174-2193
[91]
Bouguezel, S., Ahmad, M. O., & Swamy, M. (2008). A multiplication-free transform for image compression. In 2008 2nd International Conference on Signals, Circuits and Systems (pp. 1–4).
[92]
Bouguezel, S., Ahmad, M. O., & Swamy, M. N. S. (2009). A fast 8 8 transform for image compression. In International Conference on Microelectronics (pp. 74–7).
[93]
Haweel RT, El-Kilani WS, and Ramadan HH Fast approximate DCT with GPU implementation for image compression Journal of Visual Communication and Image Representation 2016 40 357-365
[94]
Senapati, R. K., Pati, U. C., & Mahapatra, K. K. (2010). A low complexity orthogonal transform matrix for fast image compression. Proceeding of the Annual IEEE India Conference (INDICON), Kolkata, India (pp. 1–4).
[95]
Potluri US, Madanayake A, Cintra RJ, Bayer FM, Kulasekera S, and Edirisuriya A Improved 8-point approximate DCT for image and video compression requiring only 14 additions IEEE Transactions on Circuits and Systems I: Regular Papers 2014 61 6 1727-1740
[96]
Mardia, K., & Jupp, P. (2009). Directional Statistics. Wiley Series in Probability and Statistics, Wiley.
[97]
Jammalamadaka, S., & Sengupta, A. (2001). Topics in Circular Statistics (Vol. 5). Series on Multivariate Analysis. World Scientific.
[98]
Strang, G. (1988). Linear algebra and its applications. Brooks Cole.
[99]
Seber, G. A. (2008). A matrix handbook for statisticians (Vol. 15). John Wiley & Sons.
[100]
Maher J, Alfalou A, and Meher PK A generalized algorithm and reconfigurable architecture for efficient and scalable orthogonal approximation of DCT IEEE Transactions on Circuits and Systems I: Regular Papers 2014 62 2 449-457
[101]
Bartle RG and Sherbert DR Introduction to real analysis 2000 New York Wiley
[102]
Katto J and Yasuda Y Performance evaluation of subband coding and optimization of its filter coefficients Journal of Visual Communication and Image Representation 1991 2 4 303-313
[103]
Hou HS A fast recursive algorithm for computing the discrete cosine transform IEEE Transactions on Acoustic, Signal, and Speech Processing 1987 6 10 1455-1461
[104]
Yip P and Rao K The decimation-in-frequency algorithms for a family of discrete sine and cosine transforms Circuits, Systems and Signal Processing 1988 7 1 3-19
[105]
Oppenheim, A. V. (1999). Discrete-time signal processing (3rd ed.). Pearson Education India.
[106]
Levitin, A. (2008). Introduction to design and analysis of algorithms, 2/E. Pearson Education India.
[107]
USC-SIPI. (2017). The USC-SIPI image database. Retrieved May 12, 2020, from http://sipi.usc.edu/database/
[108]
Suzuki T and Ikehara M Integer DCT based on direct-lifting of DCT-IDCT for lossless-to-lossy image coding IEEE Transactions on Image Processing 2010 19 11 2958-2965
[109]
Wang Z, Bovik AC, Sheikh HR, and Simoncelli EP Image quality assessment: From error visibility to structural similarity IEEE Transactions on Image Processing 2004 13 4 600-612
[110]
Wang Z and Bovik AC Mean squared error: Love it or leave it? A new look at signal fidelity measures IEEE Signal Processing Magazine 2009 26 1 98-117
[111]
Dummit, D. S., & Foote, R. M. (2004). Abstract algebra (Vol. 3). Wiley Hoboken.
[112]
Zassenhaus H. J. (2013). The theory of groups. Courier Corporation.
[113]
Rotman J. J. (2012). An introduction to the theory of groups (Vol. 148). Springer Science & Business Media.
Recommendations
Fast approximate DCT with GPU implementation for image compression
A multiplierless efficient and low complexity 8-point approximate DCT is proposed.A flow diagram is provided for the fast computation.The proposed transform is suitable for fast high performance compression.A GPU implementation is provided for further ...
Type-IV DCT, DST, and MDCT algorithms with reduced numbers of arithmetic operations
We present algorithms for the type-IV discrete cosine transform (DCT-IV) and discrete sine transform (DST-IV), as well as for the modified discrete cosine transform (MDCT) and its inverse, that achieve a lower count of real multiplications and additions ...
DCT-Based Real-Valued Discrete Gabor Transform and Its Fast Algorithms
CCCM '08: Proceedings of the 2008 ISECS International Colloquium on Computing, Communication, Control, and Management - Volume 02The traditional DCT-based real-valued discrete Gabor transform (RGDT) was limited to the critical sampling case. The biorthogonality relationship between the analysis window and synthesis window for the transform was not unveiled. To overcome those ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2023. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 01 March 2023
Accepted: 20 January 2023
Revision received: 19 December 2022
Received: 23 March 2022
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 09 Jan 2025