Last updated on September 15 at 5:00 PM
where 
.
From complex analysis (Euler's formula),
so these sinusoids can also be written as
Notice that when 
, 
ranges from 0 to 
as x ranges
from 0 to 1.
When 
, 
ranges from 0 to 
as x ranges
from 0 to 1, and so forth.
As x ranges from 0 to 1, 
ranges from 0 to 
,
covering the unit circle (from 0 to 
) 
times.
Thus, each 
is a sinusoid of frequency 
.
Using this set of basis functions, Eqs. 4.17 and
4.26 become
where the weights 
can be computed by
(Notice the extra minus sign in the exponent of Eq. 5.5-this
comes from using the complex conjugate
of 
.)
Eq. 5.5 is called the Fourier Transform,
denoted 
, and
Eq. 5.4 is called the Inverse Fourier Transform,
denoted 
.
They have the same symmetry as in Eq. 4.17 and
4.18
(with the minus sign from complex conjugation).
The functions 
and associated 
are called
Fourier-transform pairs.
As the course progresses, we will encounter many Fourier-transform pairs.
The Fourier transform is simply a change of coordinates, just like any
other. The normal original coordinate system is called the time
domain for time-variant signals and the spatial domain for image
functions. The Fourier-transform space 
is called the
frequency domain. The Fourier Transform and its inverse are the means
by which we switch between the two.
In later lectures we'll see why the frequency domain is such a useful
space for analyzing images.
has real and imaginary components 
and 
respectively. That is,
where
and
This of this a single vector of length 
and rotated in the
complex plane by an angle 
.
Substituting Eq. 5.7 into Eq. 5.4 gives
or by combination of exponents
Each weight 
thus amplifies by 
and shifts
by 
the corresponding sinusoidal basis function
.
We may thus think of the Fourier transform 
as having either
separate real and imaginary parts or
separate magnitude and phase parts.
The magnitude 
of 
is called its spectrum
and the square of the magnitude (
) is called its
power spectrum.
and the frequency component
become vectors, not scalars.
The Fourier transform and its inverse become
For two dimensions, this is usually written as
and
Let us first consider the one-dimensional case:
If we take a function with limited domain N units wide and cause it to
repeat every N units,
the spectrum of the periodic function must only have components with frequencies
, 
, ... 
--all sinusoids that make up the Fourier Transform of this
periodic image must resynchronize at the edges of the image in order to
begin again.
Instead of continuous frequency space, we have a discrete one.
The Fourier transform thus becomes
(Notice that the x in the exponent from the continuous transform
becomes 
in the discrete transform so that it ranges
from 0 to 1 as one goes across the domain of the function.)
Eq. 5.16 is called the Discrete Fourier Transform and
Eq. 5.17 is corresponding inverse.
Notice that, so long as we are working with period functions, we give up nothing by moving from a continuous Fourier Transform to a discrete one. The discrete Fourier Transform is the continous Fourier Transform for a period function.
We can do this in two dimensions with an image.
Suppose that we treat the an image as periodic in all directions-when you
go off the right edge you wrap around to the left again and when you go
off the bottom edge you wrap around to the top again.
The Discrete Fourier Transform is
Questions:
© Bryan S. Morse, 1995
