×

Tensor transform-based quaternion Fourier transform algorithm. (English) Zbl 1391.94078

Summary: The traditional Fourier transform is a fundamental tool in signal and image processing, which in color imaging transforms images either in monochrome or as separate color channels, thereby ignoring interactions between the color channels. The quaternion discrete Fourier transform (QDFT), a generalization of the Fourier transform, represents the three color channels of an image in the RGB color space as a vector field in the quaternion arithmetic allowing for simultaneous analysis of all color data. It is expected that this new color imaging model which captures the interactions between the different color channels will improve upon existing image processing and recognition systems. Efficient QDFT algorithms are derived by combining classical DFT transforms, enabling standard fast Fourier transform (FFT) software to provide a fast QDFT numerical implementation. We developed an open-source quaternion Fourier transform tool that calculates the 2-D QDFT by the column-row method which is performed by calculating multiple 1-D QDFTs where each 1-D transform is calculated by two complex 1-D DFTs. The matrices involved in these calculations necessitate the inclusion of a discussion on symplectic decomposition. Our main contribution is the presentation a new algorithm for the tensor representation of the QDFT that is structurally simpler and uses less multiplications than its predecessors. For instance, for the images of size \(N \times N\), where \(N = 2^r, r > 2\), the tensor 2-D QDFT saves about \(2 N^2 r\) real multiplications.

MSC:

94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
65T50 Numerical methods for discrete and fast Fourier transforms

Software:

Quaternion; AAFFT
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Afshari, E.; Bhat, H. S.; Hajimiri, A., Ultrafast analog Fourier transform using 2-D LC lattice, IEEE Trans. Circ. Syst. I, Reg. Papers, 55, 8, 2332-2343 (2008)
[3] Agaian, S.; Gevorkian, D., Synthesis of a class of orthogonal transforms. Parallel SIMD-algorithms and specialized processors, Pattern Recogn. Image Anal., 2, 394-408 (1992)
[5] Agaian, S. S.; Panetta, K.; Grigoryan, A. M., Transform-based image enhancement algorithms, IEEE Trans. Image Process., 10, 3, 367-382 (2001) · Zbl 1036.68605
[6] Grigoryan, A. M.; Agaian, S. S., Transform-based image enhancement algorithms with performance measure, (Advances in Imaging and Electron Physics, vol. 130 (2004), Academic Press), 165-242
[7] Agaian, S. S.; Sarukhanyan, H. G.; Egiazarian, K. O.; Astola, J., Hadamard Transforms (2011), SPIE Press
[8] Arslan, F. T.; Grigoryan, A. M., Fast splitting \(α\)-rooting method of image enhancement: tensor representation, IEEE Trans. Image Process., 15, 11, 3375-3384 (2006)
[9] Bahri, M.; Ashino, R.; Vaillancourt, R., Continuous quaternion Fourier and wavelet transforms, Int. J. Wavelets Multiresolution Inf. Process., 12, 4 (2014) · Zbl 1301.42015
[10] Bahri, M.; Irwan, M.; Toaha, S., Correlation theorem for two-sided quaternion Fourier transform, Appl. Math. Sci., 8, 41, 1999-2005 (2014)
[11] Bihan, N. L.; Sangwine, S. J.; Ell, T. A., Instantaneous frequency and amplitude of orthocomplex modulated signals based on quaternion Fourier transform, Signal Process., 94, 308-318 (2014)
[12] Bujack, R.; Bie, H. D.; Schepper, N. D.; Scheuermann, G., Convolution products for hypercomplex Fourier transforms, J. Math. Image. Vis., 48, 3, 606-624 (2014) · Zbl 1292.42007
[13] Bujack, R.; Scheuermann, G.; Hitzer, E., A general geometric Fourier transform, quaternion and Clifford Fourier transforms and wavelets, Trends Math., 155-176 (2013) · Zbl 1273.15020
[15] Chen, B.; Coatrieux, G.; Chen, G.; Coatrieux, J.-L.; Full, H. S., 4-D quaternion discrete Fourier transform based watermarking for color images, Digital Signal Process., 28, 106-119 (2014)
[16] Dubey, V. R., Quaternion Fourier transform for colour images, Int. J. Comput. Sci. Inf. Technol., 5, 3, 4411-4416 (2014)
[18] Ell, T. A.; Bihan, N. L.; Sangwine, S. J., Quaternion Fourier Transforms for Signal and Image Processing (2014), Wiley-ISTE · Zbl 1314.94004
[19] Ell, T. A.; Sangwine, S. J., Hypercomplex Fourier transforms of color images, IEEE Trans. Image Process., 16, 1, 22-35 (2007) · Zbl 1279.94014
[20] Fu, Y. X., Non-harmonic quaternion Fourier transform and uncertainty principle, Integr. Transf. Spec. F., 25, 12, 998-1008 (2014) · Zbl 1302.42017
[23] Grigoryan, A. M., 2-D and 1-D multi-paired transforms: frequency-time type wavelets, IEEE Trans. Signal Process., 49, 2, 344-353 (2001) · Zbl 1369.65185
[24] Grigoryan, A. M., Fourier transform representation by frequency-time wavelets, IEEE Trans. Signal Process., 53, 7, 2489-2497 (2005) · Zbl 1370.42006
[25] Grigoryan, A. M.; Agaian, S. S., Split manageable efficient algorithm for Fourier and Hadamard transforms, IEEE Trans. Signal Process., 48, 1, 172-183 (2000) · Zbl 1010.65057
[26] Grigoryan, A. M.; Agaian, S. S., Efficient algorithm for computing the 2-D discrete Hadamard transform, IEEE Trans. Circ. Syst. II, 47, 10, 1098-1103 (2000) · Zbl 0982.65146
[27] Grigoryan, A. M.; Agaian, S. S., Shifted Fourier transform-based tensor algorithms for the 2-D DCT, IEEE Trans. Signal Process., 49, 9, 2113-2126 (2001) · Zbl 1369.65187
[28] Grigoryan, A. M.; Agaian, S. S., Multidimensional Discrete Unitary Transforms: Representation, Partitioning and Algorithms (2003), Marcel Dekker Inc.: Marcel Dekker Inc. New York · Zbl 1114.94003
[31] Grigoryan, A. M.; Agaian, S. S., Retooling of color imaging in the quaternion algebra, Appl. Math. Sci.: Int. J. (MathSJ), 1, 3, 23-39 (2014)
[32] Grigoryan, A. M.; Grigoryan, M. M., Brief Notes in Advanced DSP: Fourier Analysis with MATLAB (2009), CRC Press Taylor and Francis Group · Zbl 1167.65002
[33] Grigoryan, A. M.; Grigoryan, M. M., Image Processing: Tensor Transform and Discrete Tomography with MATLAB (2012), CRC Press Taylor and Francis Group · Zbl 1400.94017
[34] Grigoryan, A. M.; Jenkinson, J.; Agaian, S. S., Quaternion Fourier transform based alpha-rooting method for color image measurement and enhancement, Signal Process., 109, 269-289 (2015)
[35] Grigoryan, A. M.; Du, Nan, 2-D images in frequency-time representation: direction images and resolution map, J. Electronic Imag., 19, 3 (2010), (033012)
[36] Grigoryan, A. M.; Naghdali, K., On a method of paired representation: enhancement and decomposition by series direction images, J. Math. Imag. Vis., 34, 2, 185-199 (2009) · Zbl 1490.94017
[37] Guo, L.; Dai, M.; Zhu, M., Quaternion moment and its invariants for color object classification, Inf. Sci., 273, 132-143 (2014)
[38] Hitzer, E., Quaternion Fourier transform on quaternion fields and generalizations, Adv. Appl. Clifford Algebras, 17, 3, 497-517 (2007) · Zbl 1143.42006
[39] Hitzer, E., Directional uncertainty principle for quaternion Fourier transforms, Adv. Appl. Clifford Algebras, 20, 2, 271-284 (2010) · Zbl 1198.42006
[40] Hsiao, C.; Chen, Y.; Lee, C., A generalized mixed-radix algorithm for memory-based FFT processors, IEEE Trans. Circ. Syst. II, Exp. Briefs, 57, 1, 26-30 (2010)
[41] Hussain, W.; Garzia, F.; Ahonen, T.; Nurmi, J., Designing fast Fourier transform accelerators for orthogonal frequency-division multiplexing systems, Springer’s J. Signal Process. Syst., 69, 2, 161-171 (2012)
[43] Kolaman, A.; Yadid-Pecht, O., Quaternion structural similarity: a new quality index for color images, IEEE Trans. Image Process., 21, 4, 1526-1536 (2012) · Zbl 1373.94211
[46] Mohlenkamp, M. J., A fast transform for spherical harmonics, J. Fourier Anal. Appl., 5, 159-184 (1999) · Zbl 0935.65148
[47] Ouyang, J.; Coatrieux, G.; Shua, H., Robust hashing for image authentication using quaternion discrete Fourier transform and log-polar transform, Digital Signal Process., 41, 98-109 (2015)
[48] Narayanam, R.; Parimal, P.; Grigoryan, A. M., Performances of Texas Instruments DSP and Xilinx FPGAs for Cooley-Tukey and Grigoryan FFT algorithms, SOURCE J. Eng. Technol., 1, 2, 83 (2011)
[49] Pei, S. C.; Ding, J. J.; Chang, J. H., Efficient implementation of quaternion Fourier transform, convolution and correlation by 2-D complex FFT, IEEE Trans. Signal Process., 49, 2783-2797 (2001) · Zbl 1369.65190
[50] Qi, S.; Ma, J.; Li, H.; Zhang, S.; Tian, J., Infrared small target enhancement via phase spectrum of Quaternion Fourier Transform, Infrared Phys. Technol., 62, 50-58 (2014)
[51] Rabiner, L.; Gold, B., Theory and Application of Digital Signal Processing (1975), Prentice-Hall Inc.
[52] Ranganadh, N.; Grigoryan, A. M.; Tushara, B. D., Implementation of FFT by using MATLAB: SIMULINK on Xilinx Virtex-4 FPGAs: performance of a paired transform based FFT, Int. J. Adv. Comput. Res., 3, 2, 72-78 (2013)
[53] Ranganadh, N.; Guravaiah, M., Performance case study of Grigoryan FFT over Cooley-Tukey FFT using TMS DSP processors, Int. J. Adv. Comput. Res., 2, 4, 452-457 (2012)
[54] Sangwine, S. J., Fourier transforms of colour images using quaternion, or hypercomplex, numbers, Electron. Lett., 32, 21, 1979-1980 (1996)
[59] Shaneyfelt, T.; Jamshidi, M.; Agaian, S., Vision feedback robotic docking crane system with application to vanilla pollination, Int. J. Autom. Control, 7, 1, 62-83 (2013)
[61] Suh, S.; Basu, A.; Schlottmann, C.; Hasler, P. E.; Barry, J. R., Low-power discrete Fourier transform for OFDM: a programmable analog approach, IEEE Trans. Circ. Syst. I, Reg. Papers, 58, 2, 290-298 (2011)
[63] Walker, J. S., Fast Fourier Transforms (1991), CRC Press: CRC Press Florida · Zbl 0771.65101
[66] Yeh, M. H., Relationships among various 2-D quaternion Fourier transforms, IEEE Signal Process. Lett., 15, 669-672 (2008)
[67] Zhang, S.; Wang, L., A fast Fourier transform technique for pricing European options with stochastic volatility and jump risk, Math. Problems Eng., 1-17 (2012) · Zbl 1264.91142
[68] Zhang, S.; Wang, L., Fast Fourier transform option pricing with stochastic interest rate, stochastic volatility and double jumps, Appl. Math. Comput., 219, 23, 10928-10933 (2013) · Zbl 1303.91193
[69] Zhou, Y.; Cao, W.; Liu, L.; Agaian, S.; Chen, C. L.P., Fast Fourier transform using matrix decomposition, Inf. Sci., 291, 172-183 (2015) · Zbl 1355.65188
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.