The Frequency Domain, without tears Somewhere in Cinque Terre, May 2005 CS194: Image Manipulation & Computational Photography Many slides borrowed Alexei Efros, UC Berkeley, Fall 2017 from Steve Seitz
Salvador Dali Gala Contemplating the Mediterranean Sea, which at 30 meters becomes the portrait of Abraham Lincoln, 1976 A nice set of basis Teases away fast vs. slow changes in the image.
This change of basis has a special name Jean Baptiste Joseph Fourier (1768-1830) ...the manner in which the author arrives at had crazy idea (1807): these equations is not exempt of difficulties Any univariate function can and...his analysis to integrate them still leaves something to be desired on the score of
be rewritten as a weighted generality and even rigour. sum of sines and cosines of different frequencies. Dont believe it? Neither did Lagrange,
Laplace, Poisson and other big wigs Not translated into English until 1878! Laplace But its (mostly) true!
called Fourier Series Lagrange Legendre A sum of sines Our building block:
Asin(x Add enough of them to get any signal f(x) you want! How many degrees of freedom? What does each control? Which one encodes the coarse vs. fine structure of
the signal? Fourier Transform We want to understand the frequency of our signal. So, lets reparametrize the signal by instead of x: f(x)
Fourier Transform F() For every from 0 to inf, F() holds the amplitude A and phase of the corresponding sine Asin(x
How can F hold both? F ( ) R( ) iI ( ) 2 2 1 I ( ) A R( ) I ( ) tan
R( ) We can always go back: F() Inverse Fourier Transform
f(x) Time and Frequency example : g(t) = sin(2pf t) + (1/3)sin(2p(3f) t) Time and Frequency example : g(t) = sin(2pf t) + (1/3)sin(2p(3f) t)
= + Frequency Spectra example : g(t) = sin(2pf t) + (1/3)sin(2p(3f) t) =
+ Frequency Spectra Usually, frequency is more interesting than the phase Frequency Spectra
= = + Frequency Spectra
= = + Frequency Spectra
= = + Frequency Spectra
= = + Frequency Spectra
= = + Frequency Spectra
1 = A sin(2 kt ) k 1 k Frequency Spectra FT: Just a change of basis
M * f(x) = F() * . . .
= IFT: Just a change of basis M-1 * F() = f(x) * .
. . = Finally: Scary Math Finally: Scary Math
ix not really scary: e cos(x ) i sin(x ) is hiding our old friend: sin(x phase can be encoded by sin/cos pair
P cos( x ) Q sin( x ) A sin( x P 2 Q 2 P tan 1 Q So its just our signal f(x) times sine at frequency
Extension to 2D = Image as a sum of basis images Extension to 2D
in Matlab, check out: imagesc(log(abs(fftshift(fft2(im))))); Fourier analysis in images Intensity Image Fourier Image
http://sharp.bu.edu/~slehar/fourier/fourier.html#filtering Signals can be composed + =
http://sharp.bu.edu/~slehar/fourier/fourier.html#filtering More: http://www.cs.unm.edu/~brayer/vision/fourier.html Man-made Scene Can change spectrum, then reconstruct
Local change in one domain, courses global change in the other Low and High Pass filtering The Convolution Theorem The greatest thing since sliced (banana) bread! The Fourier transform of the convolution of two functions is the product of their Fourier transforms
F[ g h] F[ g ] F[h] The inverse Fourier transform of the product of two Fourier transforms is the convolution of the two inverse Fourier transforms 1 1
1 F [ gh] F [ g ] F [h] Convolution in spatial domain is equivalent to multiplication in frequency domain! 2D convolution theorem example
|F(sx,sy)| f(x,y) * h(x,y) |H(sx,sy)|
g(x,y) |G(sx,sy)| Filtering Why does the Gaussian give a nice smooth image, but the square filter give edgy artifacts?
Gaussian Box filter Fourier Transform pairs Gaussian
Box Filter
