Fourier Series• J. B. Joseph Fourier, 1807– Any periodic function can be expressed as a weighted sum of sines and/or cosines of different frequencies.1© 1992–2008 R. C. Gonzalez & R. E. Woods f(t)=∞!n=−∞cnej2πnTtcn=1T!T/2−T/2f(t)e−j2πnTtdtFourier Series• f(t) periodic signal with period T• Frequency of sines and cosines2f(t)=∞!n=−∞cnej2πnTtThe complex exponentials form an orthogonal basis for the range [-T/2,T/2] or any other interval with length T such as [0,T]Types of function f(t)3ContinuousDiscretePeriodicFourier seriesDiscrete Fourier seriesNon-periodicFourier transformDiscrete Fourier transformf(t)=F−1{F (µ)} =!µ=∞µ=−∞F (µ)ej2πµtdµF (µ)=F{f(t)} =!∞−∞f(t)e−j2πµtdtFourier Transform Pair• The domain of the Fourier transform is the frequency domain.– If t is in seconds, mu is in Hertz (1/seconds)• The function f(t) can be recovered from its Fourier transform.4Fourier Transform example5• Fourier transform of the box function is the sinc function.• In general, the Fourier transform is a complex quantity.• The magnitude of the Fourier transform is a real quantity, called the Fourier spectrum (or frequency spectrum).© 1992–2008 R. C. Gonzalez & R. E. Woodsδ(t)=!∞ if t =00 if t "=0!∞−∞δ(t)dt =1Unit impulse function• Properties– Unit area– Sifting6!∞−∞f(t)δ(t)dt = f(0)!∞−∞f(t)δ(t − to)dt = f(to)Unit discrete impulse• x: Discrete variable• Properties7x=∞!x=−∞δ(x)=1x=∞!x=−∞f(x)δ(x − xo)=f(xo)δ(x)=!1 if x =00 if x !=0F{δ(t)} =!∞−∞δ(t)e−j2πµtdt= e−j2πµ0= e0=1F{δ(t − to)} =!∞−∞δ(t − to)e−j2 πµtdt= e−j2 πµto= cos 2πµto− j sin 2πµtoFourier Transform of Impulses8cn=1∆T!∆T/2−∆T/2δ(t)e−j2πn∆Ttdt=1∆Te0=1∆TImpulse train• Periodic function so can be represented as a Fourier sum9s∆T(t)=∞!n=−∞cnej2πn∆Tts∆T(t)=∞!n=−∞δ(t − n∆T )© 1992–2008 R. C. Gonzalez & R. E. Woodss∆T(t)=1∆T∞!n=−∞ej2πn∆TtDuality : if F{f(t)} → F (µ)then F{F (t)} → f(−t)F{s∆T(t)} = F!1∆T∞"n=−∞ej2πn∆Tt#=1∆T∞"n=−∞F$ej2πn∆Tt%=1∆T∞"n=−∞δ&µ −n∆T'Fourier Trans. of Impulse TrainSubstitute for cnLinearity of Fourier transformDuality10F−1{δ(µ − a)} =!∞−∞δ(µ − a)ej2πµtdµ=!∞−∞δ(−µ + a)ej2πµtdµ=!∞−∞δ(µ#+ a)e−j2πµ!tdµ#= ej2πatF"F−1{δ(µ − a)}#= F{ej2πat}δ(µ − a)=F{ej2πat}F{δ(t − to)} = e−j2πµtoProof of duality for impulsesFrom beforeTake Fourier Trans. of both sides11f(t) ! h(t)=!∞−∞f(τ )h(t − τ )dτF{f(t) ! h(t)} =!∞−∞"!∞−∞f(τ )h(t − τ )dτ#e−j2πµtdt=!∞−∞f(τ )"!∞−∞h(t − τ )e−j2πµtdt#$ %& 'F{h(t−τ )}=H(µ)e−j2πµτdτ=!∞−∞f(τ )H(µ)e−j2πµτdτ= H(µ)!∞−∞f(τ )e−j2πµτdτ = H(µ)F (µ)Convolution and Fourier Trans.12f(t) ! h(t) ⇐⇒ H(µ)F (µ)f(t)h(t) ⇐⇒ H(µ) ! F (µ)• Convolution in time domain is multiplication in frequency domain• Multiplication in time domain is convolution in frequency domain13Sampling• We can sample continuous function f(t) by multiplication with an impulse train14˜f(t)=f(t)s∆T(t)=∞!n=−∞f(t)δ(t − n∆T )fk= f(k∆T )=!∞−∞f(t)δ(t − k∆T )dt© 1992–2008 R. C. Gonzalez & R. E. Woods˜F (µ)=F{f(t)s∆T(t)}= F (µ) ! S(µ)=1∆T!∞−∞F (τ )∞"n=−∞δ#µ − τ −n∆T$dτ=1∆T∞"n=−∞!∞−∞F (τ )δ#µ − τ −n∆T$dτ=1∆T∞"n=−∞F#µ −n∆T$Fourier trans. of sampled func.• What does this mean? 15• Fourier transform of band-limited signal• Over-sampling• Critically-sampling• Under-sampling16© 1992–2008 R. C. Gonzalez & R. E. WoodsF (µ)=0 ∀µ > µmaxwhere µmax< ∞1∆T> 2µmaxSampling theorem• When can we recover f(t) from its sampled version?– f(t) has to be band-limited– If we can isolate a single copy of F(mu) from the Fourier transform of the sampled signal.17Nyquist rate© 1992–2008 R. C. Gonzalez & R. E. WoodsFunction recovery from sample18© 1992–2008 R. C. Gonzalez & R. E. WoodsF (µ, ν )=!∞−∞!∞−∞f(t, z)e−j2 π(µt+ν z)dtdzf(t, z)=!∞−∞!∞−∞F (µ, ν )ej2π(µt+ν z)dµdνTwo-dimensional Fourier Transform Pair19F (µ, ν )=AT Z!sin(πµT )πµT"!sin(πνZ)πνZ"Fourier transform of 2D box20© 1992–2008 R. C. Gonzalez & R. E. Woods• Properties– Unit area– Sifting2D impulse function21δ(t, z)=!∞ if t = z =00 if otherwise6!∞−∞!∞−∞δ(t, z)dtdz =1!∞−∞f(t, z)δ(t − to,z− zo)dt = f(to,zo)2D sampling• 2D impulse train as sampling function• Sampling theorem– Band-limited– Sampling rate limits22s∆T ∆Z(t, z)=∞!m=−∞∞!n=−∞δ(t − m∆T, z − n∆Z)F (µ, ν )=0for µ > µmaxor ν > νmax1∆T> 2µmax1∆Z> 2νmax23Aliasing• What happens if a band-limited function is sampled at a rate less than the Nyquist frequency? – High-frequency components of original signal appear as if they are low-frequency components of the sampled function– Alias: false-identity© 1992–2008 R. C. Gonzalez & R. E. Woods24Aliasing example© 1992–2008 R. C. Gonzalez & R. E. Woods Figure: Sampling rate less than Nyquist ratef (t) = sin(πt)Period = 2, Frequency = 0.5Nyquist rate = 2 x 0.5 = 1Sampling rate must be strictly greater than the Nyquist rate. What happens if we sample this signal at exactly the Nyquist rate?25Aliasing in imagesOver-sampled Under-sampledAliasing© 1992–2008 R. C. Gonzalez & R. E. Woods26Aliasing example• Digitizing a checkerboard pattern with 96 x 96 sample array. – We can resolve squares that have sides one pixel long or longer© 1992–2008 R. C. Gonzalez & R. E. Woods27Aliasing in images• Images always have finite extent (duration) so aliasing is always present• Effects of aliasing can be reduced by slightly defocusing the scene to be digitized.– This has to be done before the image is sampled!• Resampling a digital image can also cause aliasing.– Blurring (averaging) helps reduce these effects28Alising due to image shrinking© 1992–2008 R. C. Gonzalez & R. E. Woods29Jagged edges© 1992–2008 R. C. Gonzalez & R. E. Woods30Inevitable aliasing• No function of finite duration can be band-limited!! • Assume we have a band-limited signal of infinite duration. We limit the duration by multiplication with a box function:– We already know the Fourier transform of the box function is a sinc function in