Fourier Transforms of Real Data in Two and Three Dimensions

Two-dimensional FFTs are particularly important in the field of image processing. An image is usually represented as a two-dimensional array of pixel intensities, real (and usually positive) numbers. One commonly desires to filter high, or low, frequency spatial components from an image; or to convolve or deconvolve the image with some instrumental point spread function. Use of the FFT is by far the most efficient technique. In three dimensions, a common use of the FFT is to solve Poisson's equation for a potential (e.g., electromagnetic or gravitational) on a three-dimensional lattice that represents the discretization of three-dimensional space. Here the source terms (mass or charge distribution) and the desired potentials are also real. In two and three dimensions, with large arrays, memory is often at a premium. It is therefore important to perform the FFTs, insofar as possible, on the data " in place. " We want a routine with functionality similar to the multidimensional FFT routine fourn (§12.4), but which operates on real, not complex, input data. We give such a routine in this section. The development is analogous to that of §12.3 leading to the one-dimensional routine realft. (You might wish to review that material at this point, particularly equation 12.3.5.) It is convenient to think of the independent variables n 1 ,. .. , n L in equation (12.4.3) as representing an L-dimensional vector n in wave-number space, with values on the lattice of integers. The transform H(n 1 ,. . ., n L) is then denoted H(n). It is easy to see that the transform H(n) is periodic in each of its L dimensions. Equation (12.5.1) holds for any input data, real or complex. When the data is real, we have the additional symmetry H(− n) = H(n)* (12.5.2)