PowerPoint Presentation
Fourier Series &
Fourier Transforms
Another way of thinking about frequency
Fourier Series
Animation by cmglee
Wikipedia – Fourier transform
Square wave (approx.)
Mehmet E. Yavuz
http://www.mathworks.com/matlabcentral/fileexchange/49533-fourier-series-animation-using-harmonic-circles
4
Sawtooth wave (approx.)
Mehmet E. Yavuz
One series in each of x and y
Generative Art, じゃがりきん, Video, 2018
Example: Music
We think of music in terms of frequencies at different magnitudes
Slide: Hoiem
Fourier analysis in images
Spatial domain images
Fourier decomposition frequency amplitude images
http://sharp.bu.edu/~slehar/fourier/fourier.html#filtering More: http://www.cs.unm.edu/~brayer/vision/fourier.html
8
Signals can be composed
+
=
http://sharp.bu.edu/~slehar/fourier/fourier.html#filtering More: http://www.cs.unm.edu/~brayer/vision/fourier.html
Spatial domain images
Fourier decomposition frequency amplitude images
Brian Pauw demo
Live Fourier decomposition images
Using FFT2 function
I hacked it a bit for MATLAB
Maru the cat: https://www.youtube.com/watch?v=2XID_W4neJo
10
Amplitude / Phase
Amplitude tells you “how much”
Phase tells you “where”
Translate the image?
Amplitude unchanged
Adds a constant to the phase.
Morse
Phase congruency edge detection: http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/OWENS/LECT7/node2.html
Magnitude Amplitude of combined cosine and sine
Phase Relative proportions of sine and cosine
Bryan Morse, BYU Computer Science
http://www.astro.umd.edu/~lgm/ASTR410/ft_ref2.pdf
11
Fourier Transform
Stores the amplitude and phase at each frequency:
For mathematical convenience, this is often notated in terms of real and complex numbers
Related by Euler’s formula
Hays
Fourier Transform
Stores the amplitude and phase at each frequency:
For mathematical convenience, this is often notated in terms of real and complex numbers
Related by Euler’s formula
Hays
Hays
Phase encodes spatial information (indirectly):
Amplitude encodes how much signal there is at a particular frequency:
Fourier Transform
Stores the amplitude and phase at each frequency:
For mathematical convenience, this is often notated in terms of real and complex numbers
Related by Euler’s formula
What about phase?
Amplitude
Phase
Efros
What about phase?
Efros
What about phase?
Amplitude
Phase
Efros
Cheebra
Zebra phase, cheetah amplitude
Cheetah phase, zebra amplitude
Efros
Mathematical definition
is hiding our old friend:
So it’s just our signal f(x) times sine at frequency w
phase can be encoded
by sin/cos pair
Fourier Transform pairs
The Convolution Theorem
The Fourier transform of the convolution of two functions is the product of their Fourier transforms
The inverse Fourier transform of the product of two Fourier transforms is the convolution of the two inverse Fourier transforms
Convolution in spatial domain is equivalent to multiplication in frequency domain!
And vice versa!
21
The frequency amplitude of natural images are quite similar
Heavy in low frequencies, falling off in high frequencies
Will any image be like that, or is it a property of the world we live in?
Most information in the image is carried in the phase, not the amplitude
Not quite clear why
Efros
Smoothing with box filter
James Hays
1
1
1
1
1
1
1
1
1
23
Smoothing with Gaussian filter
James Hays
24
Comparison
James Hays
25
When sampling a signal at discrete intervals, the sampling frequency must be 2 fmax
fmax = max frequency of the input signal
This will allows to reconstruct the original perfectly from the sampled version
good
bad
Nyquist-Shannon Sampling Theorem
2D convolution theorem example
*
f(x,y)
h(x,y)
g(x,y)
|F(sx,sy)|
|H(sx,sy)|
|G(sx,sy)|
27
Why does the Gaussian give a nice smooth image, but the square filter give edgy artifacts?
Gaussian
Box filter
Filtering
Things we can’t understand without thinking in frequency
28
Gaussian
Box Filter
Filtering in spatial domain
-1
0
1
-2
0
2
-1
0
1
*
=
Hays
Filtering in frequency domain
FFT
FFT
Inverse FFT
=
Slide: Hoiem
Low Pass filter
A low-pass filter attenuates high frequencies and retains low frequencies unchanged. The result in the spatial domain is equivalent to that of a smoothing filter; as the blocked high frequencies correspond to sharp intensity changes, i.e. to the fine-scale details and noise in the spatial domain image.
33
High Pass filter
A highpass filter, on the other hand, yields edge enhancement or edge detection in the spatial domain, because edges contain many high frequencies. Areas of rather constant gray level consist of mainly low frequencies and are therefore suppressed.
34
A Low Pass Filter: Gaussian Filter
1D
2D
N=50 samples
35
Gaussian filter
g=fspecial(‘gaussian’,50,2.5);
surf(g);
36
Fourier Transforms
Gaussian filter
g=fspecial(‘gaussian’,50,2.5); h=fft2(g);
colormap(‘gray’);imagesc(g); colormap(‘gray’); imagesc(abs(h));
37
Fourier transforms
In Matlab lower frequencies are displayed at the corners
‘fftshift’ brings the origin to the center of the image
g=fspecial(‘gaussian’,50,2.5); h=fftshift(fft2(g));
colormap(‘gray’);imagesc(g); colormap(‘gray’); imagesc(abs(h));
38
Fourier transforms
Gaussian filter
g=fspecial(‘gaussian’,50,1.5); h=fftshift(fft2(g);
colormap(‘gray’);imagesc(g); colormap(‘gray’); imagesc(abs(h));
39
High Pass Filter
A high pass filter is the frequency complement of a low pass filter
40
A few questions
Why is frequency decomposition centered in middle, and duplicated and rotated?
From Euler:
Coefficients for negative frequencies
(i.e., ‘backwards traveling’ waves)
FFT of a real signal is conjugate symmetric
i.e., f(-x) = f*(x)
https://en.wikipedia.org/wiki/Euler%27s_formula
41
Fourier Transform
of important functions
spatial domain
frequency domain
42
Lavf57.25.100
2
2
)
Im(
)
Re(
j
j
+
±
=
A
)
Re(
)
Im(
tan
1
j
j
f
–
=
)
sin(
)
cos(
x
i
x
e
x
i
w
w
w
+
=
÷
÷
ø
ö
ç
ç
è
æ
=
+
±
=
)
+
=
+
–
Q
P
Q
P
Α
x
A
x
Q
x
P
1
2
2
tan
sin(
)
sin(
)
cos(
f
f
)
+
f
w
x
sin(
]
F[
]
F[
]
F[
h
g
h
g
=
*
]
[
F
]
[
F
]
[
F
1
1
1
h
g
gh
–
–
–
*
=
]
,
[
×
×
f
/docProps/thumbnail.jpeg