DOCUMENTATION CENTER SEARCH

User's Guide

Image Transforms

8.2 Discrete Fourier Transform

The discrete Fourier transform (DFT) is a frequency domain representation of finite-extent sequences. The DFT is a decomposition of a finite-extent sequence by a family of complex exponential sequences. The DFT of a discrete-time sequence of length N is itself a sequence of length N.

The DFT plays a central role in the implementation of many signal and image processing algorithms. Particularly important has been the discovery of a fast algorithm, the fast Fourier transform (FFT) [Coo65], that reduces the number of complex multiplications needed to compute an N-point DFT by a factor of

Transform	Short
DiscreteFourierTransform[img]	DFT[img]	discrete Fourier transform of img
InverseDiscreteFourierTransform[coef]	IDFT[coef]	inverse discrete Fourier transform of coef
FourierMatrix[n]		returns an n × n matrix of n- Fourier basis sequences

Image transforms.

The 1D discrete Fourier transform (1D DFT) is a unique decomposition of a discrete-time, finite-length signal onto a finite family (basis) of discrete, periodic, complex exponential sequences of the form

, where k,n,N

(integers). The ratio

is the fundamental frequency. The symmetric DFT formulation is given by the following pair of equations:

X[k] is known as the N-point DFT of the sequence x[n]. Equations (8.2.1) and (8.2.2) are the analysis and synthesis equations, respectively.

This loads the ImageProcessing package.

In[1]:=

We conclude this section with a couple of examples of computing the DFT. We first calculate the DFT of the following sequence:

Here is the sequence x[n] of length 32 and its DFT.

In[2]:=

Out[2]=

The 2D discrete Fourier transform (2D DFT) is a straightforward extension of the 1D formulation. The DFT X[k₁,k₂] of a 2D sequence x[n₁,n₂] , with

, is defined as

for 0≤k₁≤N₁-1, 0≤k₂≤N₂-1 and

for 0≤ n₁≤N₁-1, 0≤n₂≤N₂-1.

Next we obtain the DFT of a 2D sequence defined by the following formula:

Here is the N×N matrix representation of this sequence (N=8).

In[3]:=

Out[3]//MatrixForm=

Here is the 32-point DFT of the sequence x[n₁,n₂].

In[4]:=

Here we plot the magnitude and phase of the 2D example sequence.

In[5]:=

Out[5]=

Finally, we compute the 2D DFT of one of the example images.

In[6]:=

Here is the original image.

In[7]:=

Out[7]=

Here we display the magnitude (left) and phase (right) spectra of the image.

In[8]:=

Out[8]=

In visualizing the frequency response of a sequence, it is common to use a centered DFT domain.

In[9]:=

Out[9]=

The energy compaction property of the DFT is clearly visible. Most of the signal's energy is concentrated at the four corners of the DFT magnitude matrix, which are the low-frequency zones of the transform domain. Note that a large majority of the Fourier coefficients have relatively small values and therefore contribute little to the signal's total energy.

THIS IS DOCUMENTATION FOR AN OBSOLETE PRODUCT.