Abstract
The Clifford Fourier transform (CFT) can be applied to both vector and scalar fields. However, due to problems with big data, CFT is not efficient, because the algorithm is calculated in each semaphore. The sparse fast Fourier transform (sFFT) theory deals with the big data problem by using input data selectively. This has inspired us to create a new algorithm called sparse fast CFT (SFCFT), which can greatly improve the computing performance in scalar and vector fields. The experiments are implemented using the scalar field and grayscale and color images, and the results are compared with those using FFT, CFT, and sFFT. The results demonstrate that SFCFT can effectively improve the performance of multivector signal processing.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Batard, T., Berthier, M., Saint-Jean, C., 2010. Clifford–Fourier transform for color image processing. In: Bayro-Corrochano, E., Scheuermann, G. (Eds.), Geometric Algebra Computing. Springer London, London, UK, p.135–162. https://doi.org/10.1007/978-1-84996-108-0_8
Bujack, R., Scheuermann, G., Hitzer, E., 2015. Demystification of the geometric Fourier transforms and resulting convolution theorems. Math. Meth. Appl. Sci., 39(7): 1877–1890. https://doi.org/10.1002/mma.3607
Cao, W.M., Feng, H., 2010. Geometric Algebra in Biomimetic Pattern Recognition and Signal Processing. Science Press, Beijing, China (in Chinese).
Cao, W.M., Liu, H., Xu, C., et al., 2013. 3D medical image registration based on conformal geometric algebra. Sci. China Inform. Sci., 43(2): 254–274. https://doi.org/10.1360/112012-592
Ebling, J., Scheuermann, G., 2003. Clifford convolution and pattern matching on vector fields. IEEE Visualization, p.193–200. https://doi.org/10.1109/VISUAL.2003.1250372
Ebling, J., Scheuermann, G., 2005. Clifford Fourier transform on vector fields. IEEE Trans. Visual. Comput. Graph., 11(4): 469–479. https://doi.org/10.1109/TVCG.2005.54
Evans, C.J., Sangwine, S.J., Ell, T.A., 2000. Colour-sensitive edge detection using hypercomplex filters. 10th European Signal Processing Conf., p.1–4.
Frigo, M., Johnson, S.G., 2005. The design and implementation of FFTW3. Proc. IEEE, 93(2): 216–231. https://doi.org/10.1109/JPROC.2004.840301
Gilbert, A., Indyk, P., 2010. Sparse recovery using sparse matrices. Proc. IEEE, 98(6): 937–947. https://doi.org/10.1109/JPROC.2010.2045092
Gilbert, A.C., Indyk, P., Iwen, M., et al., 2014. Recent developments in the sparse Fourier transform: a compressed Fourier transform for big data. IEEE Signal Process. Mag., 31(5): 91–100. https://doi.org/10.1109/MSP.2014.2329131
Hassanieh, H., Adib, F., Katabi, D., et al., 2012a. Faster GPS via the sparse Fourier transform. Proc. 18th Annual Int. Conf. on Mobile Computing and Networking, p.353–364. https://doi.org/10.1145/2348543.2348587
Hassanieh, H., Indyk, P., Katabi, D., et al., 2012b. Nearly optimal sparse Fourier transform. Proc. 44th Annual ACM Symp. on Theory of Computing, p.563–578. https://doi.org/10.1145/2213977.2214029
Hassanieh, H., Indyk, P., Katabi, D., et al., 2012c. Simple and practical algorithm for sparse Fourier transform. Proc. 23rd Annual ACM-SIAM Symp. on Discrete Algorithms, p.1183–1194. https://doi.org/10.1137/1.9781611973099.93
Hassanieh, H., Shi, L., Abari, O., et al., 2014. GHz-wide sensing and decoding using the sparse Fourier transform. Proc. IEEE INFOCOM, p.2256–2264. https://doi.org/10.1109/INFOCOM.2014.6848169
Hestenes, D., 1999. New Foundations for Classical Mechanics. Springer, New York, USA.
Hestenes, D., Sobczyk, G., 1984. Clifford Algebra to Geometric Calculus. Springer, New York, USA.
Hitzer, E., 2012. Introduction to Clifford’s geometric algebra. SICE J. Contr. Meas. Syst. Integr., 4(1): 1–11.
Hitzer, E., 2013. The Clifford Fourier transform in real Clifford algebras. Int. Conf. on the Applications of Computer Science and Mathematics in Architecture and Civil Engineering, p.227–240.
Hitzer, E., Mawardi, B., 2008. Clifford Fourier transform on multivector fields and uncertainty principles for dimensions n=2 (mod 4) and n=3 (mod 4). Adv. Appl. Clifford Alg., 18(3–4): 715–736. https://doi.org/10.1007/s00006-008-0098-3
Hitzer, E., Sangwine, S.J., 2013. Quaternion and Clifford Fourier transforms and wavelets. In: Hitzer, E., Stephen, J., Sangwine, S.J. (Eds.), Trends in Mathematic. Springer Basel, Basel, Switzerland. https://doi.org/10.1007/978-3-0348-0603-9
Hitzer, E., Helmstetter, J., Abłamowicz, R., 2013. Square roots of–1 in real Clifford algebras. In: Hitzer, E., Stephen, J., Sangwine, S.J. (Eds.), Trends in Mathematic. Springer Basel, Basel, Switzerland. https://doi.org/10.1007/978-3-0348-0603-9_7
Iwen, M.A., 2010. Combinatorial sublinear-time Fourier algorithms. Found. Comput. Math., 10(3): 303–338. https://doi.org/10.1007/s10208-009-9057-1
Li, H.B., 2005. Conformal geometric algebra—a new framework for computational geometry. J. Comput. Aid. Des. Comput. Graph., 17(11): 2383–2393.
Mishra, B., Wilson, P., Wilcock, R., 2015. A geometric algebra co-processor for color edge detection. Electronics, 4(1): 94–117. https://doi.org/10.3390/electronics4010094
Mueen, A., Nath, S., Liu, J., 2010. Fast approximate correlation for massive time-series data. Proc. ACM SIGMOD Int. Conf. on Management of Data, p.171–182. https://doi.org/10.1145/1807167.1807188
Porat, E., Strauss, M.J., 2012. Sublinear time, measurementoptimal, sparse recovery for all. Proc. 23rd Annual ACM-SIAM Symp. on Discrete Algorithms, p.1215–1227. https://doi.org/10.1137/1.9781611973099.96
Reich, W., Scheuermann, G., 2010. Analyzing real vector fields with Clifford convolution and Clifford–Fourier transform. In: Bayro-Corrochano, E., Scheuermann, G. (Eds.), Geometric Algebra Computing. Springer, London, UK, p.121–133. https://doi.org/10.1007/978-1-84996-108-0_7
Schlemmer, M., Hotz, I., Natarajan, V., et al., 2005. Fast Clifford Fourier transformation for unstructured vector field data. Proc. Int. Conf. on Numerical Grid Generation in Computational Field Simulations, p.101–110.
Schumacher, J., Puschel, M., 2014. High-performance sparse fast Fourier transforms. IEEE Workshop on Signal Processing Systems, p.1–6. https://doi.org/10.1109/SiPS.2014.6986055
Shi, L., Hassanieh, H., Davis, A., et al., 2014. Light field reconstruction using sparsity in the continuous Fourier domain. ACM Trans. Graph., 34(1), Article 12. https://doi.org/10.1145/2682631
Smith, J.O., 2011. Spectral Audio Signal Processing. W3K Publishing, London, UK.
Wang, R., Jing, L.B., Tao, L., et al., 2013. Digital watermarking algorithm for 3D point cloud model based on Clifford algebra. J. Shanghai Jiao Tong Univ., 47(12): 1863–1869.
Wang, R., Zhang, X., Cao, W.M., 2015. Clifford fuzzy support vector machines for classification. Adv. Appl. Clifford Alg., 26(2): 1–22. https://doi.org/10.1007/s00006-015-0616-z
Xie, W., Cao, W.M., Meng, S., 2008. Coverage analysis for sensor networks based on Clifford algebra. Sci. China Inform. Sci., 51(5): 460–475. https://doi.org/10.1007/s11432-008-0048-7
Xu, C., Liu, H., Ouyang, C.J., et al., 2011. Theory and application of Clifford pseudo-differential operator on multispectral image. Sci. Sin. Inform., 41(12): 1423–1435. https://doi.org/10.1360/zf2011-41-12-1423
Author information
Authors and Affiliations
Corresponding author
Additional information
Project supported by the National Natural Science Foundation of China (Nos. 61301027, 61375015, and 11274226)
Rights and permissions
About this article
Cite this article
Wang, R., Zhou, Yx., Jin, Yl. et al. Sparse fast Clifford Fourier transform. Frontiers Inf Technol Electronic Eng 18, 1131–1141 (2017). https://doi.org/10.1631/FITEE.1500452
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1631/FITEE.1500452
Key words
- Sparse fast Fourier transform (sFFT)
- Clifford Fourier transform (CFT)
- Sparse fast Clifford Fourier transform (SFCFT)
- Clifford algebra