Image Processing

Appendix A

AN ALGORITHM OF THE TWO-DIMENSIONAL FOURIER TRANSFORM¹

GRIGORYAN A. M.

A new algorithm for calculating the two-dimensional Fourier transform is proposed, by constructing the tensor of the third order. It is shown, that such an algorithm requires operations of multiplication by 1.6-2 times fewer, than known algorithms and does not require an additional temporary storage for saving intermediate results of calculations.

Consider an arbitrary array {f_n,k} of the discrete signal, whose size for simplicity of exposition will be considered equal, i.e., n, k = 1 : N, for an integer number N.

At each point (p, s) of the spectrum, the Fourier transform of the signal up to the normalized factor equals

$F_{p,s}={\displaystyle \sum _{n=1}^N{\displaystyle \sum _{k=1}^N{f}_{n,k}{W}^{np+ks},}}$

(A.1)