[PDF] [PDF] Fourier Transform Introduction - School of Computer Science and

[PDF] Fourier Analysis - MathWorks

In Matlab the expression fft(x) computes the finite Fourier transform of The finite , or discrete, Fourier transform of a complex vector y with n elements is another 

[PDF] Evaluating Fourier Transforms with MATLAB - CSUN

In this case, the Fourier transform is a purely real function Thus, we can plot it as shown above In general, Fourier transforms are complex functions and we 

[PDF] Fourier series in MATLAB

you how you can easily perform this analysis using MATLAB an FFT of a real number data set (i e no complex numbers in the original data) the positive and 

[PDF] FFT Tutorial

Figure 1 shows the DFT (implemented with Matlab's FFT function) of a cosine with distinguishing between real and imaginary components N1 = 64; N2 = 128;

[PDF] Preparation Course MATLAB Programming - International Audio

5 3 Discrete Fourier Transform (DFT) 5 4 Short-Time Fourier Transform (STFT) (A complex number is indicated in MATLAB by assigning the Attribute 

[PDF] Fourier Transform Introduction - School of Computer Science and

transformation, via Fourier Transform (FT), from More complex signals will give more complex decompositions Recall MATLAB: phi = angle(fft(X,N)) 29 / 66 

[PDF] Fourier Transform Handout - MIT OpenCourseWare

22 sept 2011 · The Discrete Fourier Transform and Its Use 4 Using the FFT in Matlab 7 unraveling such complicated and seemingly noisy patterns

[PDF] Fourier representation of signals (MATLAB tutorial) - Montefiore

19 fév 2020 · MATLAB tutorial series (Part 1 1) frequency components, that is, complex exponentials https://nl mathworks com/help/matlab/ref/fft html

[PDF] Using a Fast Fourier Transform Algorithm

complex exponential multiplications it is possible to achieve substantial experiment you will use the Matlab fft() function to perform some frequency domain

Signals and Systems with MATLABR

MATLAB and Simulink product information, please contact: The MathWorks complex numbers, differentiation, and integration), differential equations, Laplace Fourier series), CTFT (continuous-time Fourier transform), DFT (discrete-time

[PDF] compo géo la france en ville

[PDF] composite materials are classified based on

[PDF] composition geo la france en ville

[PDF] comprehensive list of linux commands

[PDF] comprendre le langage corporel du chat

[PDF] comprendre le langage de la queue du chat

[PDF] comprendre le langage des humains

[PDF] comprendre le langage mathématique

[PDF] comprendre le langage mathématique pdf

[PDF] comprendre les équations du premier degré

[PDF] comprendre les normes comptables internationales ias/ifrs au maroc

[PDF] comptabilité les opérations courantes

[PDF] compte ants et france connect

[PDF] compte franceconnect ameli point permis

[PDF] compte franceconnect ameli retraite

CM2208: Scientic Computing

Fourier Transform 1:

Digital Signal and Image Processing

Fourier Theory

Prof. David Marshall

School of Computer Science & Informatics

Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

Fourier Transform

Moving into the Frequency Domain

TheFrequency domaincan be obtained through the

transformation, viaFourier Transform (FT), fromone (Temporal (Time)orSpatial) domain to the otherFrequencyDomainWe do not think in terms of signal or pixel intensities but rather underlying sinusoidal waveforms of varying frequency, amplitude and phase. 2/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

Applications of Fourier Transform

Numerous Applications including:

Essential tool for Engineers, Physicists,

Mathematicians and Computer ScientistsFundamental tool for Digital Signal Processing and

Image ProcessingMany types of Frequency Analysis:

Filtering

Noise Removal

Signal/Image Analysis

Simple implementation ofConvolutionAudioand ImageEects Processing.Signal/Image Restoration |e.g.

DeblurringSignal/Image Compression |-MPEG

(Audio and Video),JPEGuse related techniques.Many more::::::3/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

Introducing Frequency Space

1D Audio Example

Lets consider a 1D (e.g. Audio) example to see what the dierent domains mean: Consider acomplicated soundsuch as the achordplayed on apianoor aguitar.

We can describe this sound in two related ways:

Temporal Domain

: Sample the amplitudeof the sound many times a second, which

gives an approximation to the sound as afunctionoftime.Frequency Domain: Analysethe sound in terms of thepitchesof the notes, or

frequencies, which make the sound up, recording theamplitude ofeachfrequency .Fundamental Frequencies

D[: 554.40Hz

F : 698.48Hz

A[: 830.64Hz

C:

10 46.56Hz

plus harmonics/partial frequencies .... 4/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

Back to Basics

An 8 Hz Sine Wave

A signal that consists of asinusoidalwave

at8 Hz.8 Hz means that wave is completing

8 cycles in 1 secondThefrequencyof that wave is 8 Hz.

From thefrequency domainwe can see

that the composition of our signal isone peakoccurring with a frequency of 8 Hz | there is only one sine wave here.with amagnitude/fractionof

1.0i.e. it is thewhole signal.5/66

Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

2D Image Example

What do Frequencies in an Image Mean?

Now images are no more complex really:

Brightnessalong alinecan be recorded as a set ofvalues

measured atequallyspaceddistances apart,Orequivalently, at asetofspatial frequency values.Each of these frequency values is afrequency component.An image is a 2D array of pixel measurements.

We form a 2D grid of spatial frequencies.

A given frequency component now species what contribution is made by data which is changing with speciedxandy direction spatial frequencies. 6/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

Frequency components of an image

What do Frequencies in an Image Mean? (Cont.)

Large values athighfrequency components then the data is

changing rapidly on a short distance scale.e.g.apage of textHowever,Noisecontributes (very)High FrequenciesalsoLargelowfrequency components then the large scale features

of the picture are more important. e.g.a single fairly simple object which occupies most of the image. 7/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

Visualising Frequency Domain Transforms

Sinusoidal Decomposition

Any digital signal (function) can bedecomposedinto purelysinusoidal componentsSine waves of dierent size/shape | varyingamplitude,frequencyand

phase.Whenaddedbacktogethertheyreconstitutetheoriginal signal.TheFourier transformis the tool that performs such an operation.

8/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms Summing Sine Waves. Example: to give a Square(ish) WaveDigital signals are composite signals made up of many sinusoidal frequenciesA 200Hz digital signal (square(ish) wave) may be a composed of 200, 600, 1000,etc.sinusoidal signals which sum to give: 9/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

Summary so far

So What Does All This Mean?

Transforming a signal into the frequency domain allows us To see what sine waves make up our underlying signal E.g.

One part sinusoidal wave at 50 Hz and

Second part sinusoidal wave at 200 Hz.

Etc. Morecomplexsignals will give more complex decompositions but the idea is exactly the same. 10/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

How is this Useful then?

Basic Idea of Filtering in Frequency Space

Filtering now involvesattenuatingorremovingcertain frequencies |easily performed:Low pass lter|Ignorehigh freq uencynoise components | makezeroor a very low value.Only store lower frequency components High Pass Filter|opposite of aboveBandpass Filter| onlyallowfrequencies in acertain range.11/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

Visualising the Frequency Domain

Think Graphic Equaliser

An easy way to visualise what is happening is to think of a graphic equaliser on a stereo system (or some software audio players,e.g. iTunes). 12/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

So are we ready for the Fourier Transform?

We have all the Tools....

This lecture, so far, (hopefully) set the context for Frequency decomposition.

Past Maths Lectures:

Odd/Even Functions:sin( x) =sin(x),cos( x) = cos(x)Complex Numbers:Phasor Formrei=r(cos+isin)CalculusIntegration:Rekxdx=ekxk

Digital Signal Processing:

Basic Waveform Theory. Sine Wavey=A:sin(2:n:Fw=Fs) where:A= amplitude,Fw= wave frequency,Fs= sample frequency,nis the sample index.Relationship between Amplitude, Frequency and Phase:

Cosine is a Sine wave 90

out of phaseImpulse Responses DSP + Image Proc.: Filters and other processing, Convolution 13/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

Fourier Theory

Introducing The Fourier Transform

The tool whichconvertsaspatialortemporal(real space)descriptionof audio/imagedata, for example, into one in terms of itsfrequency componentsis called theFourier transform The new version is usually referred to as theFourier space descriptionof the data.

We then essentially process the data:E.g.forlteringbasically this means attenuating or setting certain

frequencies to zero We then need toconvert data back(orinvert) torealaudio /imagery to use in our applications. The correspondinginversetransformation which turns a Fourier space description back into a real space one is called theinverse Fourier transform.15/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

1D Fourier Transform

1D Case (e.g.Audio Signal)Considering acontinuousfunctionf(x)of a single va riablexrepresenting

distance (or time). TheFourier transformof that function is denotedF(u),whereurepresents spatial(ortemporal)frequencyis dened by:

F(u) =Z

1 1 f(x)e2ixudx: Note: In generalF(u) will be acomplex quantit yeven thoughthe original data is purelyreal.The meaning of this is that not only is themagnitudeof eachfrequency present important, but that itsphase relationshipistoo.RecallPhasorsfromComplex Number Lectures.e

2ixuabove is aPhasor.16/66

Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

Inverse Fourier Transform

Inverse 1D Fourier Transform

TheinverseF ouriertransfo rmfor regeneratingf(x)from F(u)is given by f(x) =Z 1 1

F(u)e2ixudu;

which is rather similar to the (forward) Fourier transformexcept that theexponential term has the opposite sign.It isnot negative17/66

11Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

Fourier Transform Example

Fourier Transform of a Top Hat Function

Let's see how we compute a Fourier Transform: consider a particular functionf(x) dened as f(x) =1ifjxj 1

0otherwise,1118/66

Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

The Sinc Function (1)

We derive the Sinc function

So its Fourier transform is:

F(u)= Z

1

1f(x)e2ixudx

Z 1

11e2ixudx

12iu(e2iue2iu)

Now (refer toComplex NumbersLectures/Maths Formula SheetHandout) sin=eiei2i ;So:

F(u)= sin2uu:

In this case,F(u)is purely real , which is a consequence of the original data beingsymmetricinxandx.f(x)is an evenfunction.

A graph ofF(u)is sho wnoverleaf.

This function is often referred to as theSinc function.19/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

The Sinc Function Graph

The Sinc Function

The Fourier transform of a top hat function, theSinc function:-6-4-20246 0.5 0 0.5 1 1.5 2 u sin(2 → u)/(→ u)20/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

The 2D Fourier Transform

2D Case (e.g.Image data)Iff(x;y)is a function, fo rexample intensitiesin animage, its

Fourier transformis given by

F(u;v) =Z

1 1Z 1 1 f(x;y)e2i(xu+yv)dx dy; and theinverse transform, as might be expected, is f(x;y) =Z 1 1Z 1 1

F(u;v)e2i(xu+yv)du dv:21/66

Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

The Discrete Fourier Transform

But All Our Audio and Image data are Digitised!!

Thus, we need adiscreteformulation of the Fourier transform:Assumesregula rlyspaced data values, andReturnsthevalueof the Fourier transform for a set of values

in frequency space which areequally spaced. This is done quite naturally by replacing the integral by a summation, to give thediscrete Fourier transformorDFTfor short. 22/66
Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

1D Discrete Fourier transform (DFT)

1D Case:

In 1D it is convenient now to assume thatxgoes up in steps of1 , and that there are

Nsamples, at values ofxfrom0 to N1.

So the DFT takes the form

F(u) =1N

N1X x=0f(x)e2ixu=N; while the inverse DFT is f(x) =N1X u=0F(u)e2ixu=N: NOTE:Minor changes from the continuous case are a factor of1 =Nin the exponentialterms, and also the factor1 =Nin front of the forward transform which does not appearin theinversetransform.23/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

2D Discrete Fourier transform

2D Case

The2D DFTworks is similar.

So for anNMgrid inxandywe have

F(u;v) =1NM

N1X x=0M1X y=0f(x;y)e2i(xu=N+yv=M); and f(x;y) =N1X u=0M1X v=0F(u;v)e2i(xu=N+yv=M):24/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

Balancing the 2D DFT

Most Images are Square

OftenN=M, and it is then it is more convenient to redene F(u;v)b ymultiplying it b ya facto rof N, so that theforwardand inversetransforms are moresymmetric:

F(u;v) =1N

N1X x=0N1X y=0f(x;y)e2i(xu+yv)=N; and f(x;y) =1N N1X u=0N1X v=0F(u;v)e2i(xu+yv)=N:25/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

Fourier Transforms in MATLAB

fft()andfft2()MATLAB provides functions for 1D and 2DDiscrete Fourier Transforms (DFT): t(X) is the 1D discrete F ouriertransfo rm(DFT) of vectorX. For matrices, the FFT operation is applied toeach column|NOT a 2D DFT transform. t2(X) returns the 2D F ouriertransfo rmof matrix X. If X is a vecto r,the result will have the same orientation. tn(X) returns the N-D discrete F ouriert ransformof the N-D arrayX .

Inverse DFTit(),it2(),itn()perform theinverseDFT.

See appropriate MATLABhelp/docpages forfull details. Plenty of examples to Follow.See also:MALTAB DocsImage Pro cessing!User's Guide !Transforms!Fourier Transform 26/66

0246810121416

1 0 1 n → a)

Cosine signal x(n)

0246810121416

0 0.5 1 k → b)

Magnitude spectrum |X(k)|

00.511.522.533.5

x 10 4 0 0.5 1 f in Hz → c)

Magnitude spectrum |X(f)|Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

Visualising the Fourier Transform

Visualising the Fourier Transform

Having computed a DFT it might be

useful to visualise its result:It's useful to visualise the Fourier

TransformStandard tools

Easily plotted in MATLAB

0246810121416

1 0 1 n → a)

Cosine signal x(n)

0246810121416

0 0.5 1 k → b)

Magnitude spectrum |X(k)|

00.511.522.533.5

x 10 4 0 0.5 1 f in Hz → c)

Magnitude spectrum |X(f)|27/66

Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

The Magnitude Spectrum of Fourier Transform

Recall that the Fourier Transform of ourrealaudio/image data is always complexPhasors: This is how we encode thephaseof the underlying signal's Fourier Components.How can we visualise a complex data array?

Back to Complex Numbers:

Magnitude spectrumCompute the absolute value of the complex data: jF(k)j=qF

2R(k) +F2I(k)fork= 0;1;:::;N1

whereFR(k)is the realpart andFI(k)is the imaginarypart of theNsampled

Fourier Transform,F(k).

Recall MATLAB:Sp = abs(fft(X,N))/N;

(Normalised form)28/66 Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

The Phase Spectrum of Fourier Transform

The Phase Spectrum

Phase Spectrum

The Fourier Transform also represent phase, the

phase spectrumis given by: '= arctanFI(k)F

R(k)fork= 0;1;:::;N1

Recall MATLAB:phi = angle(fft(X,N))29/66

Frequency DomainFourier TransformDiscrete Fourier TransformSpectraProperties of Fourier Transforms

Relating a Sample Point to a Frequency Point

Whenplotting graphsofFourier Spectraand doing other DFT processing we may wish toplotthex-axis inHz(Frequency) rather thansample pointnumberk= 0;1;:::;N1

There is asimple relationbetween the two:The sample points go in stepsk= 0;1;:::;N1For a given sample pointkthe frequency relating to this is

given by: f k=kfsN wherefsis thesampling frequencyandNthenumberof samples.Thus we haveequidistantfrequency steps offsN ranging from 0 Hz toquotesdbs_dbs9.pdfusesText_15