Transcription
One and Two Dimensional Fourier AnalysisTolga TasdizenECEUniversity of Utah1
Fourier Series J. B. JosephFourier, 1807– Any periodic functioncan be expressed asa weighted sum ofsines and/or cosinesof differentfrequencies.What is the period of this function?2 1992–2008 R. C. Gonzalez & R. E. Woods
Fourier Series f(t) periodicsignal withperiod T Frequency ofsines andcosinesThe complex exponentials form an orthogonal basisfor the range [-T/2,T/2] or any other interval withlength T such as [0,T]3
Types of functionsContinuousf(t)Discretef(n)PeriodicFourier series DiscreteFourier ransform4
Fourier Transform Pair The domain of the Fourier transform isthe frequency domain.– If t is in seconds, mu is in Hertz (1/seconds) The function f(t) can be recovered fromits Fourier transform.5
Fourier Transform example Fourier transform of the box function is thesinc function. In general, the Fourier transform is a complexquantity. In this case it is real. The magnitude of the Fourier transform is areal quantity, called the Fourier spectrum (orfrequency spectrum).6 1992–2008 R. C. Gonzalez & R. E. Woods
Convolution and Fourier Trans.Can see this by change of variables t’ t - Τ7
Convolution in time domain ismultiplication in frequency domain Multiplication in time domain isconvolution in frequency domain8
Unit impulse function Properties– Unit area– Sifting9
Unit discrete impulse x: Discrete variable Properties10
Fourier Transform of Impulses11
Impulse train Periodic function(period ΔT) so canbe represented as aFourier sum12 1992–2008 R. C. Gonzalez & R. E. Woods
Fourier Trans. of Impulse TrainSubstitute for cnLinearity of FouriertransformDualityFT of an impulsetrain is an impusetrain!13
Proof of duality for impulsesFrom beforeTake Fourier Trans.of both sides14
Discrete Sampling and Aliasing Digital signals and images are discreterepresentations of the real world– Which is continuous What happens to signals/images when wesample them?– Can we quantify the effects?– Can we understand the artifacts and can we limitthem?– Can we reconstruct the original image from thediscrete data?15
Sampling We can samplecontinuous functionf(t) by multiplicationwith an impulse train16 1992–2008 R. C. Gonzalez & R. E. Woods
Fourier trans. of sampled func. What does this mean?17
Fourier Transform of A Discrete Samplingu18
Fourier Transform of A Discrete SamplingFrequencies getmixed. Theoriginal signal isnot recoverable.uEnergy from higherfreqs gets folded backdown into lower freqs –Aliasing
What if F(u) is Narrower in the Fourier Domain? No aliasing! How could we recover the original signal?u20
Fourier transformof band-limitedsignal Over-sampling Critically-sampling Under-sampling21 1992–2008 R. C. Gonzalez & R. E. Woods
What Comes Out of This Model Sampling criterion for complete recovery An understanding of the effects of sampling– Aliasing and how to avoid it Reconstruction of signals from discrete samples22
Sampling theorem When can we recoverf(t) from its sampledversion?– f(t) has to be bandlimited– If we can isolate asingle copy of F(µ)from the Fouriertransform of thesampled signal.Nyquist rate 1992–2008 R. C. Gonzalez & R. E. Woods23
Sampling Theorem Quantifies the amount of information in a signal– Discrete signal contains limited frequencies– Band-limited signals contain no more information thentheir discrete equivalents Reconstruction by cutting away the repeatedsignals in the Fourier domain– Convolution with sinc function in space/time24
Function recovery from sampleWhat is this function in time?It is a sinc function25 1992–2008 R. C. Gonzalez & R. E. Woods
Reconstruction Convolution with sinc functionrect ( Tu)Note: Sinc function has infiniteduration. Why?Ideal reconstruction is not feasiblein practiceWhat happens if you truncate thesinc?26
Aliasing examplef (t) sin(π t)Figure:Samplingrate less thanNyquist ratePeriod 2, Frequency 0.5Nyquist rate 2 x 0.5 1Sampling rate must be strictly greater than the Nyquistrate. What happens if we sample this signal at exactly theNyquist rate?27 1992–2008 R. C. Gonzalez & R. E. Woods
Inevitable aliasing No function of finite duration can beband-limited!! Assume we have a band-limited signalof infinite duration. We limit the durationby multiplication with a box function:– We already know the Fourier transform ofthe box function is a sinc function infrequency domain which extends to infinity.– Multiplication in time domain is convolutionin frequency domain. Therefore, wedestroyed the band-limited property of theoriginal signal28
Two-dimensional FourierTransform PairProperties from 1D carry over to 2D:Shifting in space - Multiplication with a complexexponentialDuality of multiplication and convolutionEtc.29
2D impulse function630
2D sampling 2D impulse train as sampling function Sampling theorem– Band-limited– Sampling rate limits31
Aliasing in imagesOver-sampledUnder-sampledAliasing32 1992–2008 R. C. Gonzalez & R. E. Woods
Aliasing example Digitizing a checkerboard pattern with 96 x 96sample array.– We can resolve squares that have physical sides onepixel long or longer8 pixels16 pixels0.4798pixels0.9174pixels33 1992–2008 R. C. Gonzalez & R. E. Woods
Aliasing in images No time or space limited signal can beband limited Images always have finite extent(duration) so aliasing is always present Effects of aliasing can be reduced byslightly defocusing the scene to bedigitized (blurring continuous signal) Resampling a digital image can alsocause aliasing.– Blurring (averaging) helps reduce these34effects
Overcoming Aliasing Filter data prior to sampling– Ideally - band limit the data (conv with sinc function)– In practice - limit effects with fuzzy/soft low pass35
Overcoming alising due to imageresampling36 1992–2008 R. C. Gonzalez & R. E. Woods
Discrete Fourier Transform Fourier transform of sampled data wasderived in terms of the transform of theoriginal function: We want an expression in terms of thesampled function itself. From thedefinition of the Fourier Transform:37
38
Discrete Fourier Trans. (DFT) Notice that the Fourier transform of thediscrete signal fn is continuous andperiodic! What is the period? We only need to sample one period ofthe Fourier transform. This is the DFT:– Samples taken at– m 0,1,.,M-139
Discrete Fourier Transform PairDiscrete signal f0, , fM-1m 0,1,.,M-1n 0,1,.,M-140
2D Discrete Fourier Transform Notation: From now on we will use x,y and u,v todenote discrete variables. f(x,y) is a M x N digital image F(u,v) is also a 2D matrix of size M x N. Itselements are complex quantities.41
Spatial and frequency intervals The entire range of frequenciesspanned by the DFT is The relationship between the spatialand frequency intervals is42
Periodicity of DFT and 2D DFT Above result holds because k and x areintegers. This also implies f(x) obtainedby the inverse DFT is periodic! For 2D:– F( u, v ) F( u k1M , v k2N )– f( x, y ) f( x k1M , y k2N )– k1 and k2 integers43
Fourier spectrum and phase Since the DFT is a complex quantity itcan also be expressed in polarcoordinates:4-quadrant arctangent, atan2 command in MATLAB44
Fourier SpectrumImageRetiled with originIn centerFourier spectrumOrigin in cornersLog of spectrum45
Translation properties Translation in space Translation in frequencyNote: Centering the Fourier transform is a shift in frequency with u0 M/2and v0 N/2 which is a multiplication by (-1)x y in space46
Centering the DFTWe want halfperiod (M/2)shift in thefrequencydomain:47
In 2D.48
Translation and rotation Translation inspace onlyeffects thephase but notthe spectrum ofthe DFT Rotation inspace rotatesthe DFT (andhence thespectrum) bythe same angle49 1992–2008 R. C. Gonzalez & R. E. Woods
Phase information Phase angle is not intuitive, but it iscritical. It determines how the variousfrequency sinusoids add up. This gives50result to shape! 1992–2008 R. C. Gonzalez & R. E. Woods
Importance of phase angle51 1992–2008 R. C. Gonzalez & R. E. Woods
Two-dimensional Fourier Transform Pair Properties from 1D carry over to 2D: Shifting in space - Multiplication with a complex exponential Duality of multiplication and convolution Etc. 30 2D impulse function 6
