×

An orthogonal 16-point approximate DCT for image and video compression. (English) Zbl 1380.94043

Summary: A low-complexity orthogonal multiplierless approximation for the 16-point discrete cosine transform (DCT) was introduced. The proposed method was designed to possess a very low computational cost. A fast algorithm based on matrix factorization was proposed requiring only 60 additions. The proposed architecture outperforms classical and state-of-the-art algorithms when assessed as a tool for image and video compression. Digital VLSI hardware implementations were also proposed being physically realized in field programmable gate array technology and implemented in 45 nm up to synthesis and place-route levels. Additionally, the proposed method was embedded into a high efficiency video coding (HEVC) reference software for actual proof-of-concept. Obtained results show negligible video degradation when compared to Chen DCT algorithm in HEVC.

MSC:

94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Arai, Y., Agui, T., & Nakajima, M. (1988). A fast DCT-SQ scheme for images. Transactions of the IEICE, E-71(11), 1095-1097.
[2] Bayer, F. M., & Cintra, R. J. (2012). DCT-like transform for image compression requires 14 additions only. Electronics Letters, 48(15), 919-921. doi:10.1049/el.2012.1148. · doi:10.1049/el.2012.1148
[3] Bayer, F. M., Cintra, R. J., Edirisuriya, A., & Madanayake, A. (2012). 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), 114010-114019. · doi:10.1088/0957-0233/23/11/114010
[4] Blahut, R. E. (2010). Fast algorithms for signal processing. Cambridge: Cambridge University Press. · Zbl 1253.94001 · doi:10.1017/CBO9780511760921
[5] Bouguezel, S., Ahmad, M. O., & Swamy, M. N. S. (2008). Low-complexity \[8\times \]×8 transform for image compression. Electronics Letters, 44(21), 1249-1250. doi: 10.1049/el:20082239. · doi:10.1049/el:20082239
[6] Bouguezel, S., Ahmad, M. O., Swamy, M. (2009). A fast \[8\times \]×8 transform for image compression. In: 2009 International conference on microelectronics (ICM), pp. 74-77. doi:10.1109/ICM.2009.5418584.
[7] Bouguezel, S., Ahmad, M. O., Swamy, M. N. S. (2010). A novel transform for image compression. In: 53rd IEEE international midwest symposium on circuits and systems (MWSCAS), pp. 509-512. doi:10.1109/MWSCAS.2010.5548745. · Zbl 0576.65143
[8] Bouguezel, S., Ahmad, M. O., Swamy, M. N. S. (2011). A low-complexity parametric transform for image compression. In: Proceedings of the 2011 IEEE international symposium on circuits and systems.
[9] Bouguezel, S., Ahmad, M. O., & Swamy, M. N. S. (2013). Binary discrete cosine and Hartley transforms. IEEE Transactions on Circuits and Systems I: Regular Papers, 60(4), 989-1002. doi:10.1109/TCSI.2012.2224751. · Zbl 1468.94030 · doi:10.1109/TCSI.2012.2224751
[10] Britanak, V., Yip, P., & Rao, K. R. (2007). Discrete cosine and sine transforms. New York: Academic Press.
[11] Capelo, M. (2011). Advances on transforms for high efficiency video coding. Master’s thesis, Instituto Superior Técnico, Lisboa.
[12] Cham, W. K. (1989). Development of integer cosine transforms by the principle of dyadic symmetry. IEE Proceedings I Communications, Speech and Vision, 136, 276-282. · doi:10.1049/ip-i-2.1989.0039
[13] Cham, W. K., & Chan, Y. T. (1991). An order-16 integer cosine transform. IEEE Transactions on Signal Processing, 39(5), 1205-1208. doi:10.1109/78.80974. · doi:10.1109/78.80974
[14] Chang, T. S., Kung, C. S., & Jen, C. W. (2000). A simple processor core design for DCT/IDCT. IEEE Transactions on Circuits and Systems for Video Technology, 10(3), 439-447. doi:10.1109/76.836290. · doi:10.1109/76.836290
[15] Chen, W. H., Smith, C., & Fralick, S. (1977). A fast computational algorithm for the discrete cosine transform. IEEE Transactions on Communications, 25(9), 1004-1009. doi:10.1109/TCOM.1977.1093941. · Zbl 0371.94016 · doi:10.1109/TCOM.1977.1093941
[16] Cintra, R. J. (2011). An integer approximation method for discrete sinusoidal transforms. Circuits, Systems, and Signal Processing, 30(6), 1481-1501. doi:10.1007/s00034-011-9318-5. · Zbl 1238.65121 · doi:10.1007/s00034-011-9318-5
[17] Cintra, R. J., & Bayer, F. M. (2011). A DCT approximation for image compression. IEEE Signal Processing Letters, 18(10), 579-582. doi:10.1109/LSP.2011.2163394. · doi:10.1109/LSP.2011.2163394
[18] Cintra, R. J., Bayer, F. M., & Tablada, C. J. (2014). Low-complexity 8-point DCT approximations based on integer functions. Signal Processing, 99, 201-214. doi:10.1016/j.sigpro.2013.12.027. · doi:10.1016/j.sigpro.2013.12.027
[19] Dong, J., Ngan, K. N., Fong, C. K., & Cham, W. K. (2009). 2-D order-16 integer transforms for HD video coding. IEEE Transactions on Circuits and Systems for Video Technology, 19(10), 1462-1474. doi:10.1109/TCSVT.2009.2026792. · doi:10.1109/TCSVT.2009.2026792
[20] Edirisuriya, A., Madanayake, A., Dimitrov, V., Cintra, R. J., & Adikari, J. (2012). VLSI architecture for 8-point AI-based Arai DCT having low area-time complexity and power at improved accuracy. Journal of Low Power Electronics and Applications, 2(2), 127-142. doi:10.3390/jlpea2020127. · doi:10.3390/jlpea2020127
[21] Feig, E., & Winograd, S. (1992). Fast algorithms for the discrete cosine transform. IEEE Transactions on Signal Processing, 40(9), 2174-2193. · Zbl 0762.65103 · doi:10.1109/78.157218
[22] Fong, C. K., & Cham, W. K. (2012). LLM integer cosine transform and its fast algorithm. IEEE Transactions on Circuits and Systems for Video Technology, 22(6), 844-854. · doi:10.1109/TCSVT.2011.2177938
[23] Haweel, T. I. (2001). A new square wave transform based on the DCT. Signal Processing, 82, 2309-2319. · Zbl 0986.94004 · doi:10.1016/S0165-1684(01)00106-2
[24] Heideman, M. T., & Burrus, C. S. (1988). Multiplicative complexity, convolution, and the DFT. Signal processing and digital filtering. Berlin: Springer. · doi:10.1007/978-1-4612-3912-3
[25] Herstein, I. N. (1975). Topics in algebra (2nd ed.). London: Wiley. · Zbl 1230.00004
[26] Hou, H. S. (1987). A fast recursive algorithm for computing the discrete cosine transform. IEEE Transactions on Acoustic, Signal, and Speech Processing, 6(10), 1455-1461.
[27] International Organisation for Standardisation. (1994). Generic coding of moving pictures and associated audio information—Part 2: Video. ISO/IEC JTC1/SC29/WG11—Coding of moving pictures and audio, ISO.
[28] International Telecommunication Union. (1990). ITU-T recommendation H.261 version 1: Video codec for audiovisual services at \[p \times 64\] p×64kbits. Tech. rep., ITU-T.
[29] International Telecommunication Union. (1995). ITU-T recommendation H.263 version 1: Video coding for low bit rate communication. Tech. rep., ITU-T.
[30] International Telecommunication Union. (2013). Infrastructure of audiovisual services: Coding of moving video—High efficiency video coding. Telecommunication Standarization Sector of ITU.
[31] Joint Collaborative Team on Video Coding (JCT-VC). (2013). HEVC references software documentation. Fraunhofer Heinrich Hertz Institute. https://hevc.hhi.fraunhofer.de/.
[32] Joint Video Team. (2003). Recommendation H.264 and ISO/IEC 14 496-10 AVC: Draft ITU-T recommendation and final draft international standard of joint video specification. Tech. rep., ITU-T. · Zbl 0371.94016
[33] Lee, B. G. (1984). A new algorithm for computing the discrete cosine transform. IEEE Transactions on Acoustics, Speech and Signal Processing, ASSP-32, 1243-1245. · Zbl 0576.65143
[34] Lengwehasatit, K., & Ortega, A. (2004). Scalable variable complexity approximate forward DCT. IEEE Transactions on Circuits and Systems for Video Technology, 14(11), 1236-1248. doi:10.1109/TCSVT.2004.835151. · doi:10.1109/TCSVT.2004.835151
[35] Liang, J., & Tran, T. D. (2001). Fast multiplierless approximation of the DCT with the lifting scheme. IEEE Transactions on Signal Processing, 49, 3032-3044. · doi:10.1109/78.969511
[36] Lin, M. C., Dung, L. R., & Weng, P. K. (2006). An ultra-low-power image compressor for capsule endoscope. BioMedical Engineering Online, 5(1), 1-8. doi:10.1186/1475-925X-5-14. · doi:10.1186/1475-925X-5-14
[37] Loeffler, C., Ligtenberg, A., Moschytz, G. (1989), Practical fast 1D DCT algorithms with 11 multiplications. In: Proceedings of the international conference on acoustics, speech, and signal processing, pp. 988-991.
[38] Malvar, H. S. (1992). Signal processing with lapped transforms. London: Artech House. · Zbl 0948.94505
[39] Oppenheim, A. V. (2006). Discrete-time signal processing. Upper Saddle River: Pearson Education.
[40] Ortega, A., & Ramchandran, K. (1998). Rate-distortion methods for image and video compression. IEEE Signal Processing Magazine, 15(6), 23-50. doi:10.1109/79.733495. · doi:10.1109/79.733495
[41] Pao, I. M., & Sun, M. T. (1998). Approximation of calculations for forward discrete cosine transform. IEEE Transactions on Circuits and Systems for Video Technology, 8(3), 264-268. doi:10.1109/76.678620. · doi:10.1109/76.678620
[42] Pennebaker, W. B., & Mitchell, J. L. (1992). JPEG still image data compression standard. New York, NY: Van Nostrand Reinhold.
[43] Potluri, U. S., Madanayake, A., Cintra, R. J., Bayer, F. M., & Rajapaksha, N. (2012). Multiplier-free DCT approximations for RF multi-beam digital aperture-array space imaging and directional sensing. Measurement Science and Technology, 23(11), 114003. doi:10.1088/0957-0233/23/11/114003. · doi:10.1088/0957-0233/23/11/114003
[44] Potluri, U. S., Madanayake, A., Cintra, R. J., Bayer, F. M., Kulasekera, S., & Edirisuriya, A. (2014). Improved 8-point approximate DCT for image and video compression requiring only 14 additions. IEEE Transactions on Circuits and Systems I, 61(6), 1727-1740. doi:10.1109/TCSI.2013.2295022. · doi:10.1109/TCSI.2013.2295022
[45] 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. doi:10.1109/MCE.2012.2192754. · doi:10.1109/MCE.2012.2192754
[46] Proakis, J. G., & Manolakis, D. K. (2006). Digital signal processing (4th ed.). Englewood Cliffs: Prentice Hall.
[47] Rao, K. R., & Yip, P. (1990). Discrete cosine transform: Algorithms, advantages, applications. San Diego, CA: Academic Press. · Zbl 0726.65162 · doi:10.1016/B978-0-08-092534-9.50007-2
[48] Roma, N., & Sousa, L. (2007). Efficient hybrid DCT-domain algorithm for video spatial downscaling. EURASIP Journal on Advances in Signal Processing, 2007(2), 30. doi:10.1155/2007/57291. · Zbl 1168.68597 · doi:10.1155/2007/57291
[49] Seber, G. A. F. (2007). A matrix handbook for statisticians. New York: Wiley-Interscience. · doi:10.1002/9780470226797
[50] Smith, S. W. (1997). The scientist and engineer’s guide to digital signal processing. San Diego, CA: California Technical Publishing.
[51] Tran, T. D. (2000). The binDCT: Fast multiplierless approximation of the DCT. IEEE Signal Processing Letters, 6(7), 141-144. · doi:10.1109/97.844633
[52] USC-SIPI. (2011). The USC-SIPI image database. University of Southern California, Signal and Image Processing Institute. http://sipi.usc.edu/database/.
[53] Valova, I., & Kosugi, Y. (2000). Hadamard-based image decomposition and compression. IEEE Transactions on Information Technology in Biomedicine, 4(4), 306-319. · doi:10.1109/4233.897063
[54] Vetterli, M., & Nussbaumer, H. (1984). Simple FFT and DCT algorithms with reduced number of operations. Signal Processing, 6, 267-278. · Zbl 1218.65158 · doi:10.1016/0165-1684(84)90059-8
[55] Wang, Z. (1984). Fast algorithms for the discrete W transform and for the discrete Fourier transform. IEEE Transactions on Acoustics, Speech and Signal Processing, ASSP-32, 803-816. · Zbl 0577.65134 · doi:10.1109/TASSP.1984.1164399
[56] Wang, Z., & Bovik, A. (2002). A universal image quality index. IEEE Signal Processing Letters, 9(3), 81-84. · doi:10.1109/97.995823
[57] Wang, Z., Bovik, A. C., Sheikh, H. R., & Simoncelli, E. P. (2004). Image quality assessment: From error visibility to structural similarity. IEEE Transactions Image Processing, 13(4), 600-612. doi:10.1109/TIP.2003.819861. · doi:10.1109/TIP.2003.819861
[58] Watkins, D. S. (2004). Fundamentals of matrix computations. Pure and applied mathematics: A Wiley series of texts, monographs and tracts. London: Wiley.
[59] Wien, M., Sun, S. (2001). ICT comparison for adaptive block transforms. Tech. rep.
[60] Yarlagadda, R. K., Hershey, J. E. (1997). Hadamard matrix analysis and synthesis with applications to communications and signal/image processing. Kluwer Academic Publishers.
[61] Yip, P., Rao, K. R. (1988). The decimation-in-frequency algorithms for a family of discrete sine and cosine transforms. Circuits, Systems, and Signal Processing, 7(1), 3-19. doi:10.1007/BF01600005. · Zbl 0648.65094
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.