Two-dimensional Fourier transform

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.