5. Multidimensional DFTs
Society for Industrial and Applied Mathematics eBooks · 1995
5.1. Introduction Up until this point every ounce of attention has been devoted to the uses and properties of the one-dimensional DFT. However, in terms of practical occurrences of the DFT and in terms of the overall computational effort spent on DFTs, the problem that arises even more frequently is that of computing multidimensional DFTs. We must now imagine input that consists of an array of data that may be arranged in a plane (for the two-dimensional case), a parallelepiped (for the three-dimensional case), or even higher-dimensional configurations. It is not difficult to appreciate how such higher-dimensional arrays of data might arise. The image on a television screen, the output of a video display device, or an aerial photograph may all be regarded as two-dimensional arrays of pixels (picture elements). A tomographic image from a medical scanning device is a two- or three-dimensional array of numbers. The solution of a differential equation in two or more spatial dimensions is generally approximated at discrete points of a multidimensional domain. A statistician doing a multivariate study of the causes of a particular disease may collect data in 20 or 30 variables and then look for correlations. All of these applications require the computation of DFTs in two or more dimensions. Fortunately, not one bit of the time spent on one-dimensional DFTs will be wasted: almost without exception, the properties of the one-dimensional DFT can be used and extended in our discussions of multidimensional DFTs. The primary task is to present the two-dimensional DFT and make sure that it is well understood. The generalization to three and more dimensions is then absolutely straightforward. It is a lovely excursion with analytical, geometrical, and computational sights in all directions. With that promise, let's begin this important and most relevant subject.