16 March 2015 Algorithms of the q2r× q2r-point 2D discrete Fourier transform
Author Affiliations +
In this paper, the concept of partitions revealing the two-dimensional discrete Fourier transform (2-D DFT) of order q2r × q2r, where r > 1 and q is a positive odd number, is described. Two methods of calculation of the 2-D DFT are analyzed. The q2r × q2r-point 2-D DFT can be calculated by the traditional column-row method with 2(q2r) 1-D DFTs, and we propose the fast algorithm which splits each 1-D DFT by the short transforms by means of the fast paired transforms. Another effective algorithm of calculation of the q2r × q2r-point 2-D DFT is based on the tensor or paired representations of the image when the image is represented as a set of 1-D signals which define the 2-D transform in the different subsets of frequency-points and they all together cover the complete set of frequencies. In this case, the splittings of the q2r × q2r-point 2-D DFT are performed by the 2-D discrete tensor or paired transforms, respectively, which lead to the calculation with a minimum number of 1-D DFTs. Examples of the transforms and computational complexity of the proposed algorithms are given.
© (2015) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Artyom M. Grigoryan, Artyom M. Grigoryan, Sos S. Agaian, Sos S. Agaian, "Algorithms of the q2r× q2r-point 2D discrete Fourier transform", Proc. SPIE 9399, Image Processing: Algorithms and Systems XIII, 93990O (16 March 2015); doi: 10.1117/12.2083471; https://doi.org/10.1117/12.2083471


New 2D discrete Fourier transforms in image processing
Proceedings of SPIE (March 15 2015)
New discrete unitary Haar-type heap transforms
Proceedings of SPIE (September 19 2007)
Discrete unitary transforms generated by moving waves
Proceedings of SPIE (September 19 2007)
Super-fast Fourier transform
Proceedings of SPIE (February 15 2006)
Reversible integer 2D Fourier transform
Proceedings of SPIE (February 10 2009)

Back to Top