Paper
16 March 2015 Algorithms of the q2r× q2r-point 2D discrete Fourier transform
Author Affiliations +
Proceedings Volume 9399, Image Processing: Algorithms and Systems XIII; 93990O (2015) https://doi.org/10.1117/12.2083471
Event: SPIE/IS&T Electronic Imaging, 2015, San Francisco, California, United States
Abstract
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 and 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); https://doi.org/10.1117/12.2083471
Advertisement
Advertisement
RIGHTS & PERMISSIONS
Get copyright permission  Get copyright permission on Copyright Marketplace
KEYWORDS
Transform theory

Fourier transforms

Image processing

Image compression

Image enhancement

Matrices

Signal processing

Back to Top