Discrete Fourier Transform

Overview

When working with digital images, we are never given a continuous function, we must work with a finite number of discrete samples. These samples are the pixels that compose an image. Computer analysis of images requires the discrete Fourier transform.

The discrete Fourier transform is a special case of the continuous Fourier transform. Figure 7.7 shows how data for the Fourier transform and the discrete Fourier transform differ. In Figure 7.7(a), the continuous function can serve as a valid input into the Fourier transform. In Figure 7.7(b), the data is sampled. There is still an infinite number of data points. In Figure 7.7(c), the data is truncated to capture a finite number of samples on which to operate. Both the sampling and truncating process cause problems in the transformation if not treated properly. I will address those problems shortly.

The formula to compute the discrete Fourier transform on an M x N size image is



The formula to return to the spatial domain is


Again it can be seen that the operations for the DFT and inverse DFT are very similar. In fact, the code to perform these operations can be the same taking note of the direction of the transform and setting the sign of the exponent accordingly.

There are problems associated with data sampling and truncation. Truncating a data set to a finite number of samples creates a ringing known as Gibb's phenomenon. This ringing distorts the spectral information in the frequency domain. The width of the ringing can be reduced by increasing the number of data samples. This will not reduce the amplitude of the ringing. This ringing can be seen in either domain. Truncating data in the spatial domain causes ringing in the frequency domain. Truncating data in the frequency domain causes ringing in the spatial domain.

The discrete Fourier transform expects the input data to be periodic, and the first sample is expected to follow the last sample. The amplitude of the ringing is a function of the difference between the amplitude of the first and last samples. To reduce this discontinuity, we can multiply the data by a windowing function (sometimes called window weighting functions) before the Fourier transform is performed.

There are a number of window functions, each with its set of advantages and disadvantages. Figure 7.8 shows some popular window functions. N is the number of samples in the data set. The Bartlett window is the simplest to compute requiring no sine or cosine computations. Ideally the data in the middle of the sample set is attenuated very little by the window function.

The equation for the Bartlett window is



The equation for the Manning window is


The equation for the Hamming window is


The equation for a Blackman window is


Just like many other functions, 1-dimensional windows can be converted into 2-dimensional windows by the following equation.



The Fourier transform works on periodic functions, expecting its input data to be periodic. Figure 7.9 shows a function and that function truncated. The Fourier transform now expects that the original data be periodic. There are some great discontinuities at the truncation edges. Window functions attenuate all values at the truncation edges. These great discontinuities are hence removed. Figure 7.9 also shows the truncated function after windowing.

Window functions attenuate the original image data. Window selection requires a compromise between how much you can afford to attenuate image data and how much spectral degradation you can tolerate.

Related Links:
Introduction to the Frequency Domain
Fast Fourier Transform
Fast Fourier Transform (FFT) Examples
IMAQ Automatic Focus Example

Reader Comments | Submit a comment »