Transcript Fourier Transforms - - NCMI (cryo-EM)

Automation
Fourier Transforms,
Filtering and Convolution
Mike Marsh
National Center for Macromolecular Imaging
Baylor College of Medicine
Single-Particle Reconstructions and Visualization
EMAN Tutorial and Workshop
March 14, 2007
Fourier Transform is an invertible operator
Image
Fourier Transform
FT
v2 will display image or its transform
Fourier Transform is an invertible operator
Image
Fourier Transform
Ny ⁄ 2
Ny
F(kx,ky)
y
f(x,y)
0
x
Nx ⁄ 2
Nx
{F(kx,ky)} = f(x,y)}
{f(x,y)}
= F(kx,ky)
Continuous Fourier Transform

F ( s )   f ( x)e i 2xs dx

f(x) = F(s)

f ( x)   F ( s)ei 2xs ds

F ( s)  

f ( x)e ixsdx

1
f ( x) 
2
1
2
1
f ( x) 
2
F ( s) 
Euler’s Formula









F ( s )eixsds
f ( x)e ixsdx
F ( s)eixsds
Some Conventions
• Image Domain
• Fourier Domain
–
–
–
–
Reciprocal space
Fourier Space
K-space
Frequency Space
• Forward Transform
• Reverse Transform,
Inverse Transform
• f(x,y,z)
• g(x)
• F
• F(kx,ky,kz)
• G(s)
• F
Math Review - Periodic Functions
If there is some a, for a function f(x), such that
f(x) = f(x + na)
then function is periodic with the period a
a
0
2a
3a
Math Review - Attributes of cosine wave
5
3
f(x) = cos (x)
1
-10
-5
-1 0
5
10
5
10
5
10
-3
-5
5
4
Amplitude
3
f(x) = 5 cos (x)
2
1
0
-10
-5
-1 0
-2
-3
-4
-5
5
Phase
f(x) = 5 cos (x + 3.14)
3
1
-10
-5
-1 0
-3
-5
Math Review - Attributes of cosine wave
5
4
3
Amplitude
f(x) = 5 cos (x)
2
1
0
-10
-5
-1 0
5
10
5
10
5
10
-2
-3
-4
-5
5
Phase
3
f(x) = 5 cos (x + 3.14)
1
-10
-5
-1 0
-3
-5
5
Frequency f(x) = 5 cos (3 x + 3.14)
3
1
-10
-5
-1 0
-3
-5
Math Review - Attributes of cosine wave
5
3
f(x) = cos (x)
1
-10
-5
-1 0
-3
-5
f(x) = A cos (kx + )
Amplitude, Frequency, Phase
5
10
Math Review - Complex numbers
• Real numbers:
1
-5.2

• Complex numbers
4.2 + 3.7i
9.4447 – 6.7i
-5.2 (-5.2 + 0i)
i  1
Math Review - Complex numbers
• Complex numbers
4.2 + 3.7i
9.4447 – 6.7i
-5.2 (-5.2 + 0i)
• Amplitude
A = | Z | = √(a2 + b2)
• Phase
 =  Z = tan-1(b/a)
• General Form
Z = a + bi
Re(Z) = a
Im(Z) = b
Math Review – Complex Numbers
• Polar Coordinate
Z = a + bi

A
• Amplitude
A=
√(a2
+
b 2)
• Phase
 = tan-1(b/a)

a
b

Math Review – Complex Numbers and Cosine Waves
• Cosine wave has three properties
– Frequency
– Amplitude
– Phase
• Complex number has two properties
– Amplitude
– Wave
• Complex numbers to represent cosine waves at varying frequency
– Frequency 1:
– Frequency 2:
– Frequency 3:
Z1 = 5 +2i
Z2 = -3 + 4i
Z3 = 1.3 – 1.6i
Fourier Analysis
Decompose f(x) into a series of cosine
waves that when summed reconstruct
f(x)
Fourier Analysis in 1D. Audio signals
5
4
Amplitude Only
3
2
1
0
-1 0
200
400
600
800
1000
1200
1400
-2
-3
5
10
(Hz)
15
5
10
(Hz)
15
-4
-5
5
4
3
2
1
0
-1 0
-2
-3
-4
-5
200
400
600
800
1000
1200
1400
Fourier Analysis in 1D. Audio signals
5
4
3
2
1
0
-1 0
200
400
600
800
1000
1200
1400
-2
-3
-4
-5
Your ear performs fourier analysis.
5
10
(Hz)
15
Fourier Analysis in 1D. Spectrum Analyzer.
iTunes performs fourier analysis.
Fourier Synthesis
Summing cosine waves reconstructs the
original function
Fourier Synthesis of Boxcar Function
Boxcar function
Periodic Boxcar
Can this function be reproduced with cosine waves?
k=1. One cycle per period
A1·cos(2kx + 1)
k=1
 A ·cos(2kx +  )
1
k
k=1
k
k=2. Two cycles per period
A2·cos(2kx + 2)
k=2
 A ·cos(2kx +  )
2
k
k=1
k
k=3. Three cycles per period
A3·cos(2kx + 3)
k=3
 A ·cos(2kx +  )
3
k
k=1
k
Fourier Synthesis. N Cycles
A3·cos(2kx + 3)
k=3
 A ·cos(2kx +  )
N
k
k=1
k
Fourier Synthesis of a 2D Function
An image is two dimensional
data.
Intensities as a function of x,y
White pixels represent the
highest intensities.
Greyscale image of iris
128x128 pixels
Fourier Synthesis of a 2D Function
F(2,3)
Fourier Filters
• Change the image by changing which
frequencies of cosine waves go into the
image
• Represented by 1D spectral profile
• 2D Profile is rotationally symmetrized
1D profile
• Low frequency terms
– Close to origin in Fourier Space
– Changes with great spatial extent (like ice
gradient), or particle size
• High frequency terms
– Closer to edge in Fourier Space
– Necessary to represent edges or highresolution features
Frequency-based Filters
•
Low-pass Filter (blurs)
–
•
High-pass Filter (sharpens)
–
•
Restricts data to high-frequency-componenets
Band-pass Filter
–
•
Restricts data to low-frequency components
Restrict data to a band of frequencies
Band-stop Filter
–
Suppress a certain band of frequencies
Cutoff Low-pass Filter
Image is blurred
Sharp features are lost
Ringing artifacts
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.2
0.4
0.6
0.8
1
Butterworth Low-pass Filter
Flat in the pass-band
Zero in the stop-band
No ringing
Gaussian Low-pass Filter
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.2
0.4
0.6
0.8
1
Butterworth High-pass Filter
• Note the loss of solid
densities
How the filter looks in 2D
unprocessed
bandpass
lowpass
highpass
Filtering with EMAN2
LowPass Filters
filtered=image.process(‘filter.lowpass.guass’, {‘sigma’:0.10})
filtered=image.process(‘filter.lowpass.butterworth’, {‘low_cutoff_frequency’:0.10, ‘high_cutoff_frequency’:0.35})
filtered=image.process(‘filter.lowpass.tanh’, {‘cutoff_frequency’:0.10, ‘falloff’:0.2})
HighPass Filters
filtered=image.process(‘filter.highpass.guass’, {‘sigma’:0.10})
filtered=image.process(‘filter.highpass.butterworth’, {‘low_cutoff_frequency’:0.10, ‘high_cutoff_frequency’:0.35})
filtered=image.process(‘filter.highpass.tanh’, {‘cutoff_frequency’:0.10, ‘falloff’:0.2})
BandPass Filters
filtered=image.process(‘filter.bandpass.guass’, {‘center’:0.2,‘sigma’:0.10})
filtered=image.process(‘filter.bandpass.butterworth’, {‘low_cutoff_frequency’:0.10, ‘high_cutoff_frequency’:0.35})
filtered=image.process(‘filter.bandpass.tanh’, {‘cutoff_frequency’:0.10, ‘falloff’:0.2})
Convolution
Convolution of some function f(x) with
some kernel g(x)
Continuous
Discrete
*
=
Convolution in 2D
x
x x

=
x

=
x x
x x x x
x xx x
x x
Microscope Point-Spread-Function is Convolution
Convolution Theorem
fg=
{FG}
f=
FG
G
Convolution in image domain
Is equivalent to multiplication in fourier domain
Contrast Theory
Power spectrum
PS = F2(s) CTF2(s) Env2(s) + N2(s)
Incoherant average of transform
obs(x) = f(x)  psf(x)  env(x) + n(x)
observed image
f(x) for true particle
noise
envelope function
point-spread function
Lowpass Filtering by Convolution
fg=
1
{FG}
0.9
0.8
0.7
0.6
• Camera shake
• Crystallographic B-factor
0.5
0.4
0.3
0.2
0.1
0
0
0.2
0.4
0.6
0.8
1
Review
Fourier Transform is invertible operator
Math Review
Periodic functions
Amplitude, Phase and
Frequency
Complex number
Amplitude and Phase
Fourier Filters
Low-pass
High-pass
Band-pass
Band-stop
Convolution Theorem
Fourier Analysis (Forward Transform)
Decomposition of periodic signal
into cosine waves
Fourier Synthesis (Inverse Transform)
Summation of cosine waves into
multi-frequency waveform
Fourier Transforms in 1D, 2D, 3D, ND
Image Analysis
Image (real-valued)
Transform (complex-valued,
amplitude plot)
Deconvolute by Division in
Fourier Space
All Fourier Filters can be
expressed as real-space
Convolution Kernels
Lens does Foureir transforms
Diffraction Microscopy
Further Reading
• Wikipedia
• Mathworld
• The Fourier Transform and its
Applications. Ronald Bracewell
Lens Performs Fourier Transform
Gibbs Ringing
• 5 waves
• 25 waves
• 125 waves