×

Low-complexity 8-point DCT approximation based on angle similarity for image and video coding. (English) Zbl 1429.94019

Summary: The principal component analysis (PCA) is widely used for data decorrelation and dimensionality reduction. However, the use of PCA may be impractical in real-time applications, or in situations were energy and computing constraints are severe. In this context, the discrete cosine transform (DCT) becomes a low-cost alternative to data decorrelation. This paper presents a method to derive computationally efficient approximations to the DCT. The proposed method aims at the minimization of the angle between the rows of the exact DCT matrix and the rows of the approximated transformation matrix. The resulting transformations matrices are orthogonal and have extremely low arithmetic complexity. Considering popular performance measures, one of the proposed transformation matrices outperforms the best competitors in both matrix error and coding capabilities. Practical applications in image and video coding demonstrate the relevance of the proposed transformation.
In fact, we show that the proposed approximate DCT can outperform the exact DCT for image encoding under certain compression ratios.
The proposed transform and its direct competitors are also physically realized as digital prototype circuits using FPGA technology.

MSC:

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

References:

[1] Ahmed, N., Natarajan, T., & Rao, K. R. (1974). Discrete cosine transform. IEEE Transactions on Computers, C-23(1), 90-93. · Zbl 0273.65097
[2] Álvarez-Cortés, S., Amrani, N., Hernández-Cabronero, M., & Serra-Sagristà, J. (2017). Progressive lossy-to-lossless coding of hyperspectral images through regression wavelet analysis. International Journal of Remote Sensing, 39, 1-21.
[3] Arai, Y., Agui, T., & Nakajima, M. (1988). A fast DCT-SQ scheme for images. Transactions of the IEICE, E-71(11), 1095-1097.
[4] Bae, J., & Yoo, H. (2017). Analysis of color transforms for lossless frame memory compression. International Journal of Applied Engineering Research, 12(24), 15664-15667.
[5] Bayer, F. M., & Cintra, R. J. (2010). Image compression via a fast DCT approximation. IEEE Latin America Transactions, 8(6), 708-713. · doi:10.1109/TLA.2010.5688099
[6] 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
[7] 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. · doi:10.1088/0957-0233/23/11/114010
[8] Bjøntegaard, G. (2001). Calculation of average PSNR differences between RD-curves. In 13th VCEG Meeting, Austin, TX, USA, Apr 2001, document VCEG-M33.
[9] Blahut, R. E. (2010). Fast algorithms for signal processing. Cambridge: Cambridge University Press. · Zbl 1253.94001 · doi:10.1017/CBO9780511760921
[10] Bossen, F. (2013). Common test conditions and software reference configurations, San Jose, CA, USA, Feb 2013, document JCT-VC L1100.
[11] Bouguezel, S., Ahmad, M. O., & Swamy, M. N. S. (2008). Low-complexity \[8\times 88\]×8 transform for image compression. Electronics Letters, 44(21), 1249-1250.
[12] Bouguezel, S., Ahmad, M. O., & Swamy, M. N. S. (2009). A fast \[8\times 88\]×8 transform for image compression. In 2009 international conference on microelectronics (ICM) (pp. 74-77), Dec 2009.
[13] 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, May 2011.
[14] 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. · Zbl 1468.94030 · doi:10.1109/TCSI.2012.2224751
[15] Britanak, V., Yip, P., & Rao, K. R. (2007). Discrete cosine and sine transforms. New York: Academic Press.
[16] Cham, W. K. (1989). Development of integer cosine transforms by the principle of dyadic symmetry. IEE Proceedings I Communications, Speech and Vision, 136(4), 276-282. · doi:10.1049/ip-i-2.1989.0039
[17] Chan, R. K. W., & Lee, M.-C. (2006). Multiplierless fast DCT algorithms with minimal approximation errors. In International conference on pattern recognition (Vol. 3, pp. 921-925). Los Alamitos, CA, USA: IEEE Computer Society.
[18] 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. · Zbl 0371.94016 · doi:10.1109/TCOM.1977.1093941
[19] Chen, H., & Zeng, B. (2012). New transforms tightly bounded by DCT and KLT. IEEE Signal Processing Letters, 19(6), 344-347. · doi:10.1109/LSP.2012.2195172
[20] Choi, K., Lee, S., & Jang, E. S. (2010). Zero coefficient-aware IDCT algorithm for fast video decoding. IEEE Transactions on Consumer Electronics, 56(3), 1822-1829. · doi:10.1109/TCE.2010.5606332
[21] Cintra, R. J. (2011). An integer approximation method for discrete sinusoidal transforms. Journal of Circuits, Systems, and Signal Processing, 30(6), 1481-1501. · Zbl 1238.65121 · doi:10.1007/s00034-011-9318-5
[22] 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
[23] 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
[24] Clarke, R. J. (1981). Relation between the Karhunen-Loève and cosine transforms. IEEE Proceedings F Communications, Radar and Signal Processing, 128(6), 359-360. · doi:10.1049/ip-f-1.1981.0061
[25] Cormen, T., Leiserson, C., Rivest, R., & Stein, C. (2001). Introduction to algorithms, chapter 16. Cambridge: MIT Press. · Zbl 1047.68161
[26] Coutinho, V. A., Cintra, R. J., Bayer, F. M., Kulasekera, S., & Madanayake, A. (2015). A multiplierless pruned DCT-like transformation for image and video compression that requires ten additions only. Journal of Real-Time Image Processing, 12, 1-9.
[27] Dimitrov, V., Jullien, G., & Miller, W. (1998). A new DCT algorithm based on encoding algebraic integers. In Proceedings of the 1998 IEEE international conference on acoustics, speech and signal processing, 1998 (Vol. 3, pp. 1377-1380 ), May 1998.
[28] Dunteman, G. H. (1989). Principal components analysis (Vol. 69). Beverly Hills: Sage. · doi:10.4135/9781412985475
[29] 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
[30] 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
[31] Gonzalez, R. C., & Woods, R. E. (2006). Digital image processing (3rd ed.). Upper Saddle River, NJ: Prentice-Hall Inc.
[32] Gorban, A. N., Kgl, B., Wunsch, D. C., & Zinovyev, A. (2007). Principal manifolds for data visualization and dimension reduction (1st ed.). Springer Publishing Company, Incorporated.
[33] Goyal, V. K. (2001). Theoretical foundations of transform coding. IEEE Signal Processing Magazine, 18(5), 9-21. · doi:10.1109/79.952802
[34] Han, J., Xu, Y., & Mukherjee, D. (2013). A butterfly structured design of the hybrid transform coding scheme. In Picture coding symposium (PCS), 2013 (pp. 17-20). IEEE.
[35] Hanhart, P., & Ebrahimi, T. (2014). Calculation of average coding efficiency based on subjective quality scores. Journal of Visual Communication and Image Representation, 25(3), 555-564. qoE in 2D/3D Video Systems. · doi:10.1016/j.jvcir.2013.11.008
[36] 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
[37] Heideman, M. T., & Burrus, C. S. (1988). Multiplicative complexity, convolution, and the DFT, ser. Signal processing and digital filtering. Berlin: Springer.
[38] Higham, N. J. (1986). Computing the polar decomposition—With applications. SIAM Journal on Scientific and Statistical Computing, 7(4), 1160-1174. · Zbl 0607.65014 · doi:10.1137/0907079
[39] Higham, N. J. (1987). Computing real square roots of a real matrix. Linear Algebra and Its Applications, 88-89, 405-430. · Zbl 0625.65032 · doi:10.1016/0024-3795(87)90118-2
[40] Higham, N. J. (2008). Functions of matrices: Theory and computation, ser. SIAM e-books. Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104).
[41] Higham, N. J., & Schreiber, R. S. (1988). Fast polar decomposition of an arbitrary matrix, Ithaca, NY, USA, Tech. Rep., October 1988. · Zbl 0711.65024
[42] 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.
[43] International Telecommunication Union. (1990). ITU-T recommendation H.261 version 1: Video codec for audiovisual services at \[p \times 64\] p×64 kbits, ITU-T, Tech. Rep.
[44] International Telecommunication Union. (1995). ITU-T recommendation H.263 version 1: Video coding for low bit rate communication, ITU-T, Tech. Rep.
[45] Jammalamadaka, S., & Sengupta, A. (2001). Topics in circular statistics, ser. Series on multivariate analysis. Singapore: World Scientific.
[46] Joint Collaborative Team on Video Coding (JCT-VC), “HEVC reference software documentation”. (2013). Fraunhofer Heinrich Hertz Institute. [Online]. Available: https://hevc.hhi.fraunhofer.de/. Accessed 19 Sept 2016.
[47] Jolliffe, I. (2002). Principal component analysis. New York: Wiley Online Library. · Zbl 1011.62064
[48] Jridi, M., Alfalou, A., & Meher, P. K. (2015). A generalized algorithm and reconfigurable architecture for efficient and scalable orthogonal approximation of DCT. IEEE Transactions on Circuits and Systems I: Regular Papers, 62(2), 449-457. · doi:10.1109/TCSI.2014.2360763
[49] Katto, J., & Yasuda, Y. (1991). Performance evaluation of subband coding and optimization of its filter coefficients. Journal of Visual Communication and Image Representation, 2(4), 303-313. · doi:10.1016/1047-3203(91)90011-4
[50] Le Gall, D. J. (1992). The MPEG video compression algorithm. Signal Processing: Image Communication, 4(2), 129-140.
[51] 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
[52] 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
[53] 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
[54] 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), May 1989.
[55] Luthra, A., Sullivan, G. J., & Wiegand, T. (2003). Introduction to the special issue on the H.264/AVC video coding standard. IEEE Transactions on Circuits and Systems for Video Technology, 13(7), 557-559. · doi:10.1109/TCSVT.2003.815169
[56] Mahan, R. P. (1991) Circular statistical methods: Applications in spatial and temporal performance analysis, ser. Special report. U.S. Army Research Institute for the Behavioral and Social Sciences.
[57] Mardia, K., & Jupp, P. (2009). Directional statistics, ser. Wiley series in probability and statistics. New York: Wiley.
[58] Masera, M., Martina, M., & Masera, G. (2017a). Odd type DCT/DST for video coding: Relationships and low-complexity implementations. In 2017 IEEE International Workshop on Signal Processing Systems (SiPS), pp. 1-6. IEEE.
[59] Masera, M., Martina, M., & Masera, G. (2017b). Adaptive approximated dct architectures for HEVC. IEEE Transactions on Circuits and Systems for Video Technology, 27(12), 2714-2725.
[60] Meher, P. K., Park, S. Y., Mohanty, B. K., Lim, K. S., & Yeo, C. (2014). Efficient integer DCT architectures for HEVC. IEEE Transactions on Circuits and Systems for Video Technology, 24(1), 168-178. · doi:10.1109/TCSVT.2013.2276862
[61] Ohm, J.-R., Sullivan, G. J., Schwarz, H., Tan, T. K., & Wiegand, T. (2012). Comparison of the coding efficiency of video coding standards—Including high efficiency video coding (HEVC). IEEE Transactions on Circuits and Systems for Video Technology, 22(12), 1669-1684. · doi:10.1109/TCSVT.2012.2221192
[62] 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
[63] Park, J.-S., Nam, W.-J., Han, S.-M., & Lee, S.-S. (2012). 2-D large inverse transform \[(16\times 1616\]×\[16, 32\times 3232\]×32) for HEVC (high efficiency video coding). JSTS: Journal of Semiconductor Technology and Science, 12(2), 203-211. · doi:10.5573/JSTS.2012.12.2.203
[64] 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: Regular Papers, 61(6), 1727-1740. · doi:10.1109/TCSI.2013.2295022
[65] 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
[66] Puri, A. (2004). Video coding using the H.264/MPEG-4 AVC compression standard. Signal Processing: Image Communication, 19, 793-849.
[67] 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
[68] Salomon, D., Motta, G., & Bryant, D. (2007). Data compression: The complete reference, ser. Molecular biology intelligence unit. Berlin: Springer.
[69] Seber, G. A. F. (2008). A matrix handbook for statisticians, ser. Wiley series in probability and mathematical statistics. New York: Wiley.
[70] Senapati, R. K., Pati, U. C., & Mahapatra, K. K. (2010). A low complexity orthogonal \[8\times 88\]×8 transform matrix for fast image compression. In Proceeding of the annual IEEE India conference (INDICON), Kolkata, India (pp. 1-4).
[71] Snigdha, F. S., Sengupta, D., Hu, J., & Sapatnekar, S. S. (2016). Optimal design of JPEG hardware under the approximate computing paradigm. In Proceedings of the 53rd annual design automation conference (p. 106). ACM.
[72] Strang, G. (1988). Linear algebra and its applications. Belmont: Brooks Cole. · Zbl 1329.15004
[73] Sullivan, G. J., Ohm, J.-R., Han, W.-J., & Wiegand, T. (2012). Overview of the high efficiency video coding (HEVC) standard. IEEE Transactions on Circuits Systems for Video Technology, 22(12), 1649-1668. · doi:10.1109/TCSVT.2012.2221191
[74] Suzuki, T., & Ikehara, M. (2010). Integer DCT based on direct-lifting of DCT-IDCT for lossless-to-lossy image coding. IEEE Transactions on Image Processing, 19(11), 2958-2965. · Zbl 1371.94359 · doi:10.1109/TIP.2010.2051867
[75] Tablada, C. J., Bayer, F. M., & Cintra, R. J. (2015). A class of DCT approximations based on the Feig-Winograd algorithm. Signal Processing, 113, 38-51. · doi:10.1016/j.sigpro.2015.01.011
[76] Thomakos, D. (2016). Smoothing non-stationary time series using the discrete cosine transform. Journal of Systems Science and Complexity, 29(2), 382-404. · Zbl 1376.37124 · doi:10.1007/s11424-015-4071-7
[77] USC-SIPI Image Database. (2017). University of Southern California. [Online]. Available: http://sipi.usc.edu/database/. Accessed 15 Sept 2016.
[78] Wallace, G. K. (1992). The JPEG still picture compression standard. IEEE Transactions on Consumer Electronics, 38(1), xviii – xxxiv.
[79] Wang, Z. (2011). Combined DCT and companding for PAPR reduction in OFDM signals. Journal of Signal and Information Processing, 2(2), 100-104. · doi:10.4236/jsip.2011.22013
[80] Wang, Z., & Bovik, A. C. (2009). Mean squared error: Love it or leave it? A new look at signal fidelity measures. IEEE Signal Processing Magazine, 26(1), 98-117. · doi:10.1109/MSP.2008.930649
[81] Wang, Z., Bovik, A. C., Sheikh, H. R., & Simoncelli, E. P. (2004). Image quality assessment: From error visibility to structural similarity. IEEE Transactions on Image Processing, 13(4), 600-612. · doi:10.1109/TIP.2003.819861
[82] Watkins, D. S. (2004). Fundamentals of matrix computations, ser. Pure and applied mathematics: A Wiley series of texts, monographs and tracts. New York: Wiley.
[83] Xu, X., Li, J., Huang, X., Dalla Mura, M., & Plaza, A. (2016). Multiple morphological component analysis based decomposition for remote sensing image classification. IEEE Transactions on Geoscience and Remote Sensing, 54(5), 3083-3102. · doi:10.1109/TGRS.2015.2511197
[84] Yip, P., & Rao, K. (1988). The decimation-in-frequency algorithms for a family of discrete sine and cosine transforms. Circuits, Systems and Signal Processing, 7(1), 3-19. · Zbl 0648.65094 · doi:10.1007/BF01600005
[85] Yuan, W., Hao, P., & Xu, C. (2006). Matrix factorization for fast DCT algorithms. In IEEE international conference on acoustic, speech, signal processing (ICASSP) (Vol. 3, pp. 948-951), May 2006.
[86] Zeng, J., Cheung, G., Chao, Y.-H., Blanes, I., Serra-Sagristá, J., & Ortega, A. (2017). Hyperspectral image coding using graph wavelets. In Proceedings of the IEEE international conference on image processing (ICIP).
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.