稀疏快速Clifford傅里叶变换

王瑞; 周轶轩; 金彦亮; 曹文明

doi:10.1631/FITEE.1500452

Your Location：

Home >

Browse articles >

稀疏快速Clifford傅里叶变换

常规文章 | Updated：2022-05-19

- 稀疏快速Clifford傅里叶变换
- Sparse fast Clifford Fourier transform
- 信息与电子工程前沿（英文） 2017年18卷第8期页码：1131-1141
- Affiliations：
  
  School of Communication and Information Engineering, Shanghai University, Shanghai 200444, China
  College of Information Engineering, Shenzhen University, Shenzhen 518060, China
  Department of Electrical and Computer Engineering, University of Missouri, Columbia 65211, USA
- Author bio：
  
  Wen-ming CAO, E-mail: wmcao@szu.edu.cn
- Funds：
  
  Project supported by the National Natural Science Foundation of China (Nos. 61301027, 61375015, and 11274226)
- DOI：10.1631/FITEE.1500452
  中图分类号： TP391
- 收稿：2015-12-09，
  
  修回：2017-;8-24，
  
  纸质出版：2017-08
- Accepted：
Scan QR Code
王瑞, 周轶轩, 金彦亮, 等. 稀疏快速Clifford傅里叶变换[J]. 信息与电子工程前沿（英文）, 2017,18(8):1131-1141.

Rui WANG, Yi-xuan ZHOU, Yan-liang JIN, et al. Sparse fast Clifford Fourier transform[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(8): 1131-1141.
王瑞, 周轶轩, 金彦亮, 等. 稀疏快速Clifford傅里叶变换[J]. 信息与电子工程前沿（英文）, 2017,18(8):1131-1141. DOI： 10.1631/FITEE.1500452.

Rui WANG, Yi-xuan ZHOU, Yan-liang JIN, et al. Sparse fast Clifford Fourier transform[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(8): 1131-1141. DOI： 10.1631/FITEE.1500452.

摘要

Clifford傅里叶变换（Clifford Fourier transform

CFT）可以应用于矢量场和标量场，但无法有效解决大数据问题，因为该算法是基于每个信号量计算的。稀疏快速傅里叶变换（sparse fast Fourier transform

sFFT）理论通过选择性地使用输入数据来处理大数据问题。受之启发，我们提出一个称为稀疏快速Clifford傅里叶变换（sparse fast CFT

SFCFT）的算法，该算法能够大幅度提高在标量场和矢量场中的计算性能。实验对标量场、灰度图和彩色图像数据进行处理，通过与FFT，CFT和sFFT进行比较，表明SFCFT可以有效提升多矢量信号处理的性能。

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.

关键词

Keywords

references

T. Batard , , , M. Berthier , , , C. Saint-Jean . . Clifford–Fourier transform for color image processing. In : Bayro-Corrochano E, Scheuermann, G. (Eds.), Geometric Algebra Computing , , : : London, UK Springer London , , 2010 . . p.135 - - 162 . . DOI: 10.1007/978-1-84996-108-0_8 http://doi.org/10.1007/978-1-84996-108-0_8 . .

R. Bujack , , , G. Scheuermann , , , E. Hitzer . . Demystification of the geometric Fourier transforms and resulting convolution theorems . . Math. Meth. Appl. Sci. , , 2015 . . 39 ( ( 7 ): ): 1877 - - 1890 . . DOI: 10.1002/mma.3607 http://doi.org/10.1002/mma.3607 . .

W.M. Cao , , , H. Feng . . Geometric Algebra in Biomimetic Pattern Recognition and Signal Processing , , : : Beijing, China Science Press , , 2010 . . .

W.M. Cao , , , H. Liu , , , C. Xu , , , 等 . . 3D medical image registration based on conformal geometric algebra . . Sci. China Inform. Sci. , , 2013 . . 43 ( ( 2 ): ): 254 - - 274 . . DOI: 10.1360/112012-592 http://doi.org/10.1360/112012-592 . .

J. Ebling , , , G. Scheuermann . . Clifford convolution and pattern matching on vector fields . . IEEE Visualization , , 2003 . . p.193 - - 200 . . DOI: 10.1109/VISUAL.2003.1250372 http://doi.org/10.1109/VISUAL.2003.1250372 . .

J. Ebling , , , G. Scheuermann . . Clifford Fourier transform on vector fields . . IEEE Trans. Visual. Comput. Graph. , , 2005 . . 11 ( ( 4 ): ): 469 - - 479 . . DOI: 10.1109/TVCG.2005.54 http://doi.org/10.1109/TVCG.2005.54 . .

C.J. Evans , , , S.J. Sangwine , , , T.A. Ell . . Colour-sensitive edge detection using hypercomplex filters . . 10th European Signal Processing Conf. , , 2000 . . p.1 - - 4 . . . .

M. Frigo , , , S.G. Johnson . . The design and implementation of FFTW3 . . Proc. IEEE , , 2005 . . 93 ( ( 2 ): ): 216 - - 231 . . DOI: 10.1109/JPROC.2004.840301 http://doi.org/10.1109/JPROC.2004.840301 . .

A. Gilbert , , , P. Indyk . . Sparse recovery using sparse matrices . . Proc. IEEE , , 2010 . . 98 ( ( 6 ): ): 937 - - 947 . . DOI: 10.1109/JPROC.2010.2045092 http://doi.org/10.1109/JPROC.2010.2045092 . .

A.C. Gilbert , , , P. Indyk , , , M. Iwen , , , 等 . . Recent developments in the sparse Fourier transform: a compressed Fourier transform for big data . . IEEE Signal Process. Mag. , , 2014 . . 31 ( ( 5 ): ): 91 - - 100 . . DOI: 10.1109/MSP.2014.2329131 http://doi.org/10.1109/MSP.2014.2329131 . .

H. Hassanieh , , , F. Adib , , , D. Katabi , , , 等 . . Faster GPS via the sparse Fourier transform . . Proc. 18th Annual Int. Conf. on Mobile Computing and Networking , , 2012a . . p.353 - - 364 . . DOI: 10.1145/2348543.2348587 http://doi.org/10.1145/2348543.2348587 . .

H. Hassanieh , , , P. Indyk , , , D. Katabi , , , 等 . . Nearly optimal sparse Fourier transform . . Proc. 44th Annual ACM Symp. on Theory of Computing , , 2012b . . p.563 - - 578 . . DOI: 10.1145/2213977.2214029 http://doi.org/10.1145/2213977.2214029 . .

H. Hassanieh , , , P. Indyk , , , D. Katabi , , , 等 . . Simple and practical algorithm for sparse Fourier transform . . Proc. 23rd Annual ACM-SIAM Symp. on Discrete Algorithms , , 2012c . . p.1183 - - 1194 . . DOI: 10.1137/1.9781611973099.93 http://doi.org/10.1137/1.9781611973099.93 . .

H. Hassanieh , , , L. Shi , , , O. Abari , , , 等 . . GHz-wide sensing and decoding using the sparse Fourier transform . . Proc. IEEE INFOCOM , , 2014 . . p.2256 - - 2264 . . DOI: 10.1109/INFOCOM.2014.6848169 http://doi.org/10.1109/INFOCOM.2014.6848169 . .

D. Hestenes . . New Foundations for Classical Mechanics , , : : New York, USA Springer , , 1999 . . .

D. Hestenes , , , G. Sobczyk . . Clifford Algebra to Geometric Calculus , , : : New York, USA Springer , , 1984 . . .

E. Hitzer . . Introduction to Clifford's geometric algebra . . SICE J. Contr. Meas. Syst. Integr. , , 2012 . . 4 ( ( 1 ): ): 1 - - 11 . . . .

E. Hitzer . . The Clifford Fourier transform in real Clifford algebras . . Int. Conf. on the Applications of Computer Science and Mathematics in Architecture and Civil Engineering , , 2013 . . p.227 - - 240 . . . .

E. Hitzer , , , B. Mawardi . . Clifford Fourier transform on multivector fields and uncertainty principles for dimensions n =2 (mod 4) and n =3 (mod 4) . . Adv. Appl. Clifford Alg. , , 2008 . . 18 ( ( 3-4 ): ): 715 - - 736 . . DOI: 10.1007/s00006-008-0098-3 http://doi.org/10.1007/s00006-008-0098-3 . .

E. Hitzer , , , S.J. Sangwine . . Quaternion and Clifford Fourier transforms and wavelets . . In : Hitzer E, Stephen J, Sangwine, S.J. (Eds.), Trends in Mathematic. Springer Basel, Basel, Switzerland , , 2013 . . DOI: 10.1007/978-3-0348-0603-9 http://doi.org/10.1007/978-3-0348-0603-9 . .

E. Hitzer , , , J. Helmstetter , , , R. Abłamowicz . . Square roots of –1 in real Clifford algebras . . In : Hitzer E, Stephen J, Sangwine, S.J. (Eds.), Trends in Mathematic. Springer Basel, Basel, Switzerland , , 2013 . . DOI: 10.1007/978-3-0348-0603-9_7 http://doi.org/10.1007/978-3-0348-0603-9_7 . .

M.A. Iwen . . Combinatorial sublinear-time Fourier algorithms . . Found. Comput. Math. , , 2010 . . 10 ( ( 3 ): ): 303 - - 338 . . DOI: 10.1007/s10208-009-9057-1 http://doi.org/10.1007/s10208-009-9057-1 . .

H.B. Li . . Conformal geometric algebra—a new framework for computational geometry . . J. Comput. Aid. Des. Comput. Graph. , , 2005 . . 17 ( ( 11 ): ): 2383 - - 2393 . . . .

B. Mishra , , , P. Wilson , , , R. Wilcock . . A geometric algebra co-processor for color edge detection . . Electronics , , 2015 . . 4 ( ( 1 ): ): 94 - - 117 . . DOI: 10.3390/electronics4010094 http://doi.org/10.3390/electronics4010094 . .

A. Mueen , , , S. Nath , , , J. Liu . . Fast approximate correlation for massive time-series data . . Proc. ACM SIGMOD Int. Conf. on Management of Data , , 2010 . . p.171 - - 182 . . DOI: 10.1145/1807167.1807188 http://doi.org/10.1145/1807167.1807188 . .

E. Porat , , , M.J. Strauss . . Sublinear time, measurement-optimal, sparse recovery for all . . Proc. 23rd Annual ACM-SIAM Symp. on Discrete Algorithms , , 2012 . . p.1215 - - 1227 . . DOI: 10.1137/1.9781611973099.96 http://doi.org/10.1137/1.9781611973099.96 . .

W. Reich , , , G. Scheuermann . . Analyzing real vector fields with Clifford convolution and Clifford–Fourier transform . . In : Bayro-Corrochano E, Scheuermann, G. (Eds.), Geometric Algebra Computing. Springer, London, UK , , 2010 . . p.121 - - 133 . . DOI: 10.1007/978-1-84996-108-0_7 http://doi.org/10.1007/978-1-84996-108-0_7 . .

M. Schlemmer , , , I. Hotz , , , V. Natarajan , , , 等 . . Fast Clifford Fourier transformation for unstructured vector field data . . Proc. Int. Conf. on Numerical Grid Generation in Computational Field Simulations , , 2005 . . p.101 - - 110 . . . .

J. Schumacher , , , M. Puschel . . High-performance sparse fast Fourier transforms . . IEEE Workshop on Signal Processing Systems , , 2014 . . p.1 - - 6 . . DOI: 10.1109/SiPS.2014.6986055 http://doi.org/10.1109/SiPS.2014.6986055 . .

L. Shi , , , H. Hassanieh , , , A. Davis , , , 等 . . Light field reconstruction using sparsity in the continuous Fourier domain . . ACM Trans. Graph. , , 2014 . . 34 ( ( 1 ): ): Article 12 DOI: 10.1145/2682631 http://doi.org/10.1145/2682631 . .

J.O. Smith . . Spectral Audio Signal Processing , , : : London, U W3K Publishing , , 2011 . . .

R. Wang , , , L.B. Jing , , , L. Tao , , , 等 . . Digital watermarking algorithm for 3D point cloud model based on Clifford algebra . . J. Shanghai Jiao Tong Univ. , , 2013 . . 47 ( ( 12 ): ): 1863 - - 1869 . . . .

R. Wang , , , X. Zhang , , , W.M. Cao . . Clifford fuzzy support vector machines for classification . . Adv. Appl. Clifford Alg. , , 2015 . . 26 ( ( 2 ): ): 1 - - 22 . . DOI: 10.1007/s00006-015-0616-z http://doi.org/10.1007/s00006-015-0616-z . .

W. Xie , , , W.M. Cao , , , S. Meng . . Coverage analysis for sensor networks based on Clifford algebra . . Sci. China Inform. Sci. , , 2008 . . 51 ( ( 5 ): ): 460 - - 475 . . DOI: 10.1007/s11432-008-0048-7 http://doi.org/10.1007/s11432-008-0048-7 . .

C. Xu , , , H. Liu , , , C.J. Ouyang , , , 等 . . Theory and application of Clifford pseudo-differential operator on multispectral image . . Sci. Sin. Inform. , , 2011 . . 41 ( ( 12 ): ): 1423 - - 1435 . . DOI: 10.1360/zf2011-41-12-1423 http://doi.org/10.1360/zf2011-41-12-1423 . .

浏览量

363

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据