In image processing applications Fast Fourier Transforms (FFTs) and related transformations are sometimes applied to two-dimensional images. We have used the Wolf program from the hpjdk release as an example in earlier chapters.
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 sketched in Figure 4.3 This implementation assumes the availability of a function for calculating FFTs on one-dimensional sequential multiarrays. A section dimension naturally inherits the sequential property (the asterisk in the type signature) from the associated dimension of the parent array. The method fft1d() implements a standard sequential algorithm--we don't reproduce it here. You can find the complete code in the hpjdk release under hpjdk/examples/PPHPJ/EgFourier2d.hpj. Because Java doesn't have complex numbers, we store real and imaginary parts in pairs of arrays whose names are prefixed re and im. Another possibility would be to add an extra dimension of extent 2 to the arrays. After processing all columns, the data is remapped so that each row is a sequential subarray, and these are processed in the same way.
The Wolf program itself, under hpjdk/examples/fft2d/ contains a generalized version for non-square images.