Two-dimensional Fourier transform

In image processing applications Fast Fourier Transforms (FFTs) and related transformastions are sometimes applied to two-dimensional images. A two-dimensional FFT can be broken down into a series simpler one-dimensional FFTs--the one-dimensional transform is simply applied to every row of the image, then to every column. All rows can be transformed in parallel, then all columns can be transformed in parallel. An implementation is given in Figure 4.3 This implementation assumes the availability of a function for calculating FFTs on one-dimensional collapsed arrays (ie, a sequential one-dimensional FFT). Because Java doesn't have complex numbers, we store real and imaginary parts in pairs of arrays whose names are prefixed re and im. Alternatively a an extra dimension of extent 2 could be added to the arrays. After processing all columns, the data is remapped so that each row is a collapsed subarray. A section dimension naturally inherits the sequential property (the asterisk in the type signature) from the associated dimension of the parent array.

Figure 4.3: A two-dimensional Fourier Transform.