# zbMATH — the first resource for mathematics

Multiplierless lifting-based fast X transforms derived from fast Hartley transform factorization. (English) Zbl 1450.94023
Summary: This paper presents $$M$$-channel $$(M=2^N,\, N\in\mathbb{N},\, N\ge 1)$$ multiplierless lifting-based (ML-) fast X transforms (FXTs), where X = F (Fourier), C (cosine), S (sine), and H (Hartley), i.e., FFT, FCT, FST, and FHT, derived from FHT factorization as way of lowering the cost of signal (image) processing. The basic forms of ML-FXTs are described. Then, they are customized for efficient image processing. The customized ML-FFT has a real-valued calculation followed by a complex-valued one. The ML-FCT customization for a block size of 8, which is a typical size for image coding, further reduces computational costs. We produce two customized ML-FCTs for lossy and lossless image coding. Numerical simulations show that ML-FFT and ML-FCTs perform comparably to the conventional methods in spite of having fewer operations.
##### MSC:
 94A12 Signal theory (characterization, reconstruction, filtering, etc.) 65T50 Numerical methods for discrete and fast Fourier transforms
##### Software:
binDCT; SIPI Image Database
Full Text:
##### References:
 [1] Ahmed, N., & Rao, K. R. (1975). Orthogonal transforms for digital signal processing. Berlin: Springer. · Zbl 0335.94001 [2] Beauchamp, K. (1984). Applications of Walsh and related functions. Cambridge: Academic Press. · Zbl 0326.42007 [3] Bracewel, R. N. (1983). Discrete Hartley transform. Journal of the Optical Society of America, 73(12), 1832-1835. [4] Chen, Y. J., Oraintara, S., Tran, T. D., Amaratunga, K., & Nguyen, T. Q. (2002). Multiplierless approximation of transforms with adder constraint. IEEE Signal Processing Letters, 9(11), 344-347. [5] Chen, W. H., Smith, C. H., & Fralick, S. C. (1977). A fast computational algorithm for the discrete cosine transform. IEEE Transactions on Communications, 25(9), 1004-1009. · Zbl 0371.94016 [6] Cooley, J. W., & Tukey, J. W. (1965). An algorithm for the machine computation of complex Fourier series. Mathematics of Computation, 19(90), 297-301. · Zbl 0127.09002 [7] Daubechies, I., & Sweldens, W. (1998). Factoring wavelet transforms into lifting steps. Journal of Fourier Analysis and Applications, 4(3), 247-269. · Zbl 0913.42027 [8] Duhamel, P. (1986). Implementation of “split-radix” FFT algorithms for complex, real, and real-symmetric date. IEEE Transactions on Acoustics, Speech, and Signal Processing, 34(2), 285-295. [9] Duhamel, P., & Hollmann, H. (1984). ‘Split radix’ FFT algorithm. Electronics Letters, 20(1), 14-16. [10] Hewlitt, R. M., & Swartzlander, J. E. S. (2000). Canonical signed digit representation for FIR digital filters. In Proceedings of SiPS’00 (pp. 416-426). Lafayette, LA. [11] JPEG core experiment for the evaluation of JPEG XR image coding, EPFL, Multimedia Signal Processing Group. http://mmspg.epfl.ch/iqa. [12] Kumar, P., 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. [13] Lee, B. G. (1984). A new algorithm to compute the discrete cosine transform. IEEE Transactions on Acoustics, Speech, and Signal Processing, 32(6), 1243-1245. · Zbl 0576.65143 [14] Liang, J., & Tran, T. D. (2001). Fast multiplierless approximations of the DCT with the lifting scheme. IEEE Transactions on Signal Processing, 49(12), 3032-3044. [15] Liu, Z., & Karam, L. J. (2000). An efficient embedded zerotree wavelet image codec based on intraband partitioning. In Proceedings of ICIP’00. Vancouver, British Columbia, Canada. [16] Malvar, H. S. (1992). Signal processing with lapped transforms. Norwood, MA: Artech House. · Zbl 0948.94505 [17] Meckelburg, H. J., & Lipka, D. (1985). Fast Hartley transform algorithm. IET Electronics Letters, 21(8), 311-313. [18] Oraintara, S. (2002). The unified discrete Fourier-Hartley transforms: Theory and structure. In: Proceedings of ISCAS’02 (pp. III-433-436). Scottsdale, AZ. [19] Oraintara, S., Chen, Y. J., & Nguyen, T. Q. (2002). Integer fast Fourier transform. IEEE Transactions on Signal Processing, 50(3), 607-618. · Zbl 1369.65189 [20] Rao, K. R., & Yip, P. (1990). Discrete cosine transform algorithms. Cambridge: Academic Press. · Zbl 0726.65162 [21] Said, A., & Pearlman, W. A. (1996). A new, fast, and efficient image codec based on set partitioning in hierarchical trees. IEEE Transactions on Circuits and Systems for Video Technology, 6(3), 243-250. [22] Shapiro, J. M. (1993). Embedded image coding using zerotrees of wavelet coefficients. IEEE Transactions on Signal Processing, 41(12), 3445-3462. · Zbl 0841.94020 [23] Sorensen, H. V., Heideman, M. T., & Burrus, C. S. (1986). On computing the split-radix FFT. IEEE Transactions on Acoustics, Speech, and Signal Processing, 34(1), 152-156. [24] Strang, G., & Nguyen, T. (1996). Wavelets and filter banks. Wellesley, MA: Wellesley-Cambridge Press. · Zbl 1254.94002 [25] 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 and Systems for Video Technology, 22(12), 1649-1668. [26] Suzuki, T., Kyochi, S., Tanaka, Y., Ikehara, M., Aso, H. (2013). Multiplierless lifting based FFT via fast Hartley transform. In Proceedings of ICASSP’13 (pp. 5603-5607). Vancouver, Canada. [27] Suzuki, T., Tanaka, Y., Ikehara, M., Aso, H. (2012). Multiplierless fast algorithm for DCT via fast Hartley transform. In Proceedings of ICASSP’12 (pp. 3469-3472). Kyoto, Japan. [28] Suzuki, T., & Ikehara, M. (2010). Integer discrete cosine transform via lossless Walsh-Hadamard transform with structural regularity for low-bit-word-length. IEICE Transactions Fundamentals, 93(4), 734-741. [29] Suzuki, T., & Kudo, H. (2015). Extended block-lifting-based lapped transforms. IEEE Signal Processing Letter, 22(10), 1657-1660. [30] The USC-SIPI image database, University of Southern California, Signal and Image Processing Institute. http://sipi.usc.edu/database/. [31] Tran, T. D. (2000). The BinDCT: Fast multiplierless approximation of the DCT. IEEE Signal Processing Letters, 7(6), 141-144. [32] Tran, T. D., Liang, J., & Tu, C. (2003). Lapped transform via time-domain pre- and post-filtering. IEEE Transactions on Signal Processing, 6(6), 1557-1571. · Zbl 1369.94303 [33] Wallace, G. K. (1992). The JPEG still picture compression standard. IEEE Transactions on Consumer Electronics, 38(1), 18-34. [34] Wang, Z. (1984). Fast algorithms for the discrete W transform and for the discrete Fourier transform. IEEE Transactions on Acoustics, Speech, and Signal Processing, 32(4), 803-816. · Zbl 0577.65134 [35] Wang, Z. (1985). On computing the discrete Fourier and cosine transforms. IEEE Transactions on Acoustics, Speech, and Signal Processing, 33(4), 1341-1344. · Zbl 0621.65034 [36] Weinberger, M. J., Seroussi, G., & Sapir, G. (2000). The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS. IEEE Transactions on Image Processing, 9(8), 1309-1324. [37] Wiegand, T., Sullivan, G. J., Bjøntegaard, G., & Luthra, A. (2003). Overview of the H.264/AVC video coding standard. IEEE Transactions on Circuits and Systems for Video Technology, 13(7), 560-576. [38] Xu, J., Wu, F., Liang, J., & Zhang, W. (2010). Directional lapped transforms for image coding. IEEE Transactions on Image Processing, 19(1), 85-97. · Zbl 1371.94420 [39] Zhu, S., Yeung, S.-K. A., & Zeng, B. (2010). In search of “better-than-DCT” unitary transforms for encoding of residual signals. IEEE Signal Processing Letters, 17(11), 961-964.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.