Transcript Fourier Transform

Fourier Transform – Chapter 13
Image space
• Cameras (regardless of wave lengths) create images
in the spatial domain
• Pixels represent features (intensity, reflectance, heat,
etc.) from the “real 3D world”
Image space
• All operations we’ve looked at so far are
applied in the spatial domain
–
–
–
–
–
–
–
–
–
Histogram (statistical) operations
Point operations
Filter (convolution) operations
Edge operations
Corner (feature) operations
Line (curve) detection
Morphological operations
Region operations
Color space
Frequency domain
• As it turns out, all the spatial domain
“signals” can be represented in the
frequency domain
• And, some of the previously mentioned
operations can be performed more
efficiently in the frequency domain
– Convolution
– Filtering
– Compression
The Fourier Transform
• The Fourier Transform provides the
means from moving between the spatial
and frequency domains
• Developed in the area of sound
processing
– Decomposition of sound waves into
elementary harmonic functions
Preliminaries
Sine and Cosine functions
• You’ve seen these many times before
1.5
1
0.5
0
-0.5
-1
-1.5
f ( x)  cos( x)
f ( x)  cos( x)  cos( x  2 )  cos( x  k 2 )
Sine and Cosine functions
• Frequency – cycles on horizontal axis
T
2

T  period
  angular frequency
1.5
1
0.5
0
-0.5
-1
-1.5
f ( x)  cos(3x)
Sine and Cosine functions
• Angular frequency and “common”
frequency (f)
1 
f  
T 2
  2f
Sine and Cosine functions
• Amplitude – increasing on vertical axis
2.5
2
1.5
1
0.5
0
-0.5
-1
-1.5
-2
-2.5
f ( x)  2  cos( x)
Sine and Cosine functions
• Phase – shifting on horizontal axis
f ( x)  cos( x   )
1.5
1
0.5
0
-0.5
-1
-1.5
f ( x)  cos( x   4)
Sine and Cosine functions
• Orthogonality
– We can combine sine and cosine
waveforms with varying frequency,
amplitude, and phase parameters to create
other sine and cosine waveforms
A  cos(x)  B  sin( x)  C  cos(x   )
C
A B
2
2
  tan
1
B
 
 A
Sine and Cosine functions
• Orthogonality example
3  cos( x)  2  sin( x)
4
3
2
1
0
-1
-2
-3
-4
3  cos( x)
2  sin( x )
Sine and Cosine functions
• Vector representation
sin( x)
B
A  sin( x)  B  cos(x)
C

A
vector length ≡ amplitude
cos(x )
• Complex number representation
z  a  bi
• Euler notation (complex numbers on the unit circle)
i
z  e  cos( )  i  sin(  )
e  2.71828
Euler notation
• Euler notation
i
z  e  cos( )  i  sin(  )
e  2.71828
• This brings us to the “complex-valued sinusoid”
i
Re{e }  cos( )
i
Im{e }  sin(  )
• Since it’s on a unit circle the amplitude is
i
i
i
a e  a  e  a
e  1 so
• And the phase is
 




e
e e
• That is, multiplying by a real value alters the
amplitude, multiplying by a complex value alters the
phase
i(

)
i
i
Fourier Series
• Not only can sinusoidal functions [of
varying frequency, amplitude, and
phase] be combined to create other
sinusoidal functions but…
• They can be combined to create almost
and periodic function

g ( x)  

k 0
0
A cos(k 
k
0
x)  Bk sin( k  0 x)
 fundamental frequency

Fourier Series

g ( x)  

k 0
0
A cos(k 
k
0
x)  Bk sin( k  0 x)
 fundamental frequency
• Frequencies kω0x are harmonics
(multiples) of the fundamental
• Ak and Bk are derived via Fourier
Analysis

Fourier Integral
• But that wasn’t enough…Fourier wanted
to cover non-periodic functions too
• Requires more than just integer
multiples (harmonics) of the
fundamental frequency
• Requires infinitely many frequencies
g ( x)  

0
A cos(x)  B sin( x)d
Fourier Integral
• To solve for the amplitudes Aω and Bω we
need the following integrals
1
A  A( )   


1
B  B( )   


g ( x)  cos(x)dx
g ( x)  sin( x)dx
• Aω and Bω form continuous functions of
coefficients (corresponding to infinitely many,
densely spaced frequencies)
• Aω and Bω form the Fourier Spectrum
Fourier Transform
• Apply the Fourier Series to complexvalued functions using Euler’s notation
to get the Fourier Transform
1
G ( ) 
2



ix
g ( x)  e
dx
• And the inverse Fourier Transform
1
g ( ) 
2



ix
G ( x)  e dx
Fourier Transform
• In general
– A real-valued function yields a complexvalued Fourier Transform
– A complex-valued function yields a readvalued Fourier Transform
Fourier Transform
• For example, lots of sinusoidal waves
can make up a square wave
Fourier Transform
• Transform pairs are unique, one-to-one
Dirac (delta) function
Fourier Transform
• Properties
– There are a bunch of properties that you
can read about, but only one is “surprising”
• Convolution Property
– Convolution in the spatial domain is pointby-point multiplication in the frequency
domain
Convolution Property
• Spatial domain
– Perform a slide/multiply-accumulate
operation with a kernel and the image
• Frequency domain
– Fourier Transform kernel → spectrum
– Fourier Transform image → spectrum
– Multiply the two spectrums
– Inverse Fourier Transform product →
filtered image
Discrete Signals
• So how do we apply these integrals to
digital (discrete) images?
Discrete Signals
Next time