next up previous
Next: Compression Up: Fourier Theory Previous: 2D Case

The Discrete Fourier Transform (DFT)

Images and Digital Audio are digitised !!

Thus, we need a discrete formulation of the Fourier transform, which takes such regularly spaced data values, and returns the value of the Fourier transform for a set of values in frequency space which are equally spaced.

This is done quite naturally by replacing the integral by a summation, to give the discrete Fourier transform or DFT for short.

In 1D it is convenient now to assume that x goes up in steps of 1, and that there are N samples, at values of x from 0 to N-1.

So the DFT takes the form
\begin{displaymath}
F(u) = \frac{1}{N}\sum_{x=0}^{N-1} f(x) e^{-2\pi i x u/N}, \end{displaymath} (6)
while the inverse DFT is
\begin{displaymath}
f(x) = \sum_{u=0}^{N-1} F(u) e^{2\pi i x u/N}. \end{displaymath} (7)

NOTE: Minor changes from the continuous case are a factor of 1/N in the exponential terms, and also the factor 1/N in front of the forward transform which does not appear in the inverse transform.

The 2D DFT works is similar. So for an $N\times M$ grid in x and y we have
\begin{displaymath}
F(u,v) = \frac{1}{N M}\sum_{x=0}^{N-1}\sum_{y=0}^{M-1} f(x,y) 
e^{-2\pi i (x u/N+y v/M)}, \end{displaymath} (8)
and
\begin{displaymath}
f(x,y) = \sum_{u=0}^{N-1}\sum_{v=0}^{M-1} F(u,v) e^{2\pi i (x u/N+y
v/M)}. \end{displaymath} (9)

Often N=M, and it is then it is more convenient to redefine F(u,v) by multiplying it by a factor of N, so that the forward and inverse transforms are more symmetrical:
\begin{displaymath}
F(u,v) = \frac{1}{N}\sum_{x=0}^{N-1}\sum_{y=0}^{N-1} f(x,y) 
e^{-2\pi i (x u+y v)/N}, \end{displaymath} (10)
and
\begin{displaymath}
f(x,y) = \frac{1}{N}\sum_{u=0}^{N-1}\sum_{v=0}^{N-1} F(u,v)
e^{2\pi i (x u+y v)/N}. \end{displaymath} (11)


next up previous
Next: Compression Up: Fourier Theory Previous: 2D Case
Dave Marshall
10/4/2001