2D Fourier Transform

Loading...

En provenance du cours de Northwestern University

Fundamentals of Digital Image and Video Processing

716 notes

Northwestern University

Fundamentals of Digital Image and Video Processing

716 notes

In this class you will learn the basic principles and tools used to process images and videos, and how to apply them in solving practical problems of commercial and scientific interests. Digital images and videos are everywhere these days – in thousands of scientific (e.g., astronomical, bio-medical), consumer, industrial, and artistic applications. Moreover they come in a wide range of the electromagnetic spectrum - from visible light and infrared to gamma rays and beyond. The ability to process image and video signals is therefore an incredibly important skill to master for engineering/science students, software developers, and practicing scientists. Digital image and video processing continues to enable the multimedia technology revolution we are experiencing today. Some important examples of image and video processing include the removal of degradations images suffer during acquisition (e.g., removing blur from a picture of a fast moving car), and the compression and transmission of images and videos (if you watch videos online, or share photos via a social media website, you use this everyday!), for economical storage and efficient transmission. This course will cover the fundamentals of image and video processing. We will provide a mathematical framework to describe and analyze images and videos as two- and three-dimensional signals in the spatial, spatio-temporal, and frequency domains. In this class not only will you learn the theory behind fundamental processing tasks including image/video enhancement, recovery, and compression - but you will also learn how to perform these key processing tasks in practice using state-of-the-art techniques and tools. We will introduce and use a wide variety of such tools – from optimization toolboxes to statistical techniques. Emphasis on the special role sparsity plays in modern image and video processing will also be given. In all cases, example images and videos pertaining to specific application domains will be utilized.

À partir de la leçon

Fourier Transform and Sampling

In this module we look at 2D signals in the frequency domain. Topics include: 2D Fourier transform, sampling, discrete Fourier transform, and filtering in the frequency domain.

2D Fourier Transform 25:14

Discrete Fourier Transform 16:08

Filtering in the Frequency Domain 13:52

Change of Sampling Rate 14:43

Rencontrer les enseignants

Aggelos K. Katsaggelos
Joseph Cummings Professor
Department of Electrical Engineering and Computer Science

[BLANK_AUDIO]

Welcome back.

I hope you enjoyed the first two weeks of class.

As I mentioned at the beginning of last week, in these two

weeks, weeks two and three, we'll

cover the fundamentals of two-dimensional signal systems.

Last week, we get this analysis in the spatial domain.

While this week we move to the frequency domain.

We use two-dimensional sequencing systems in our presentation.

However, all the information we provide

is also applicable to one-dimensional signals.

But those at the higher dimensional

signals that is multidimensional signals in general.

Thanks to Joseph Fourier, who lived in the

late 18th, early 19th century, we can describe any

signal of any dimensionality, and the operations of any

linear and spatially invariant system in the frequency domain.

The frequency domain is mostly familiar to

us when we refer to one-dimensional signals.

For example, we can distinguish between a baritone and the

soprano or between low and high frequencies in a music piece.

Images have similarly low and high frequencies, which

you cannot hear, of course, but we can see.

They're spacial frequencies.

We'll get familiar with the concept first and then we will take the material

and the operations of [UNKNOWN] systems we learned last week to the frequency domain.

We'll also understand what is involved when

we convert the continuous signal to discrete signal.

What we called in week one sampling.

And also when we changed the size of an image When for example we

want to display a large image on a small screen, of our cell phone.

Or a thumbnail image on a large screen.

And this is called sample grade conversion.

Equipped with this material you can understand what will follow in this class.

But also when you are interested in learning new material outside this class.

As for example, what's the process of acquiring an MRI image?

Or an x ray image of a

slice of a patient's body using computerized tomography.

It's in fact to a CT or CT scan, a term you might have heard before.

In this first segment we'll define the two dimensional

continuous Fourier transform of a two dimensional discrete signal.

And we will discuss some of its important properties.

We will then work out a number of examples which will give us a

good understanding of what constitutes a low

pass and what constitutes a high pass filter.

We'll finally talk about the important

convolution theorem which states that the convolution

operation in the special domain becomes

a multiplication operation in the frequency domain.

So, let us start covering this important material.

Let us go see the linear especially in

variance system with impulses response h, n1 and 2.

We put in signal x as it's input and signal's a

complex exponential with specific frequencies omega 1 prime, omega 2 prime.

This is a two dimensional Q tone, since it only

contains again this particular frequency, omega 1 prime, omega 2 prime.

We want to find out what the output of

the LSI system for this particular input is equal to.

I did mention at some earlier point in the

course that these complex exponentials are Eigenfunctions of LSI systems.

Which simply means that such complex exponentials go

through the system without their frequencies being altered.

Of course by now we know how to find the output of an LSI system.

Its y n 1 and 2 is equal to the convolution

of the input to the system with the system's input response.

[SOUND] If I apply directly the definition of the

convolution this is equal to this double sum.

[BLANK_AUDIO]

Again.

I just applied the diffusion of the revolution.

Now we see that these terms.

[BLANK_AUDIO]

Are independent of K1 K2.

Therefore they can come outside the summation, and

all I'm left with these are these terms here.

[SOUND] So we see that the complex

exponentials appear at

the output of the system.

They just went through the system.

And this term here tells me how the system responded

to this particular complex exponential of this come, at this specific frequencies.

This here is a complex quantity.

It has a [UNKNOWN] phase.

And we see that the LSI system is able to

discriminate among sinusoidal systems on the basis of their frequencies.

So if the magnitude of this term here is equal to one, then the

sign [INAUDIBLE], goes through the system unchanged, while on the other

hand, if the money is equal to zero, the complex [INAUDIBLE] is rejected

by the system, so therefore this is the, [INAUDIBLE] of the LSI system.

With [INAUDIBLE] h, n 1 and 2 at these frequencies omega 1 prime,

omega 2 prime are denoted by capital H, omega 1 prime, omega

2 prime and this is the frequency that responds to the system.

Now since this resolve is not going to change, if I consider additional

frequencies, let's say omega one double prime, omega 2 double prime,

we have that this is again the response of the system frequency

and this capital H, omega 1 and omega 2 is the fully transform of

the impulse response of the system H and 1 and 2 were

going to say cause there will be more

things about the fourier transfer in the next slides.

We show here the two dimension of fourier transform pair.

This is here the expression for the forward

transform that will take an image from the

special domain and map it to the frequency

domain where omega 1, omega 2 continues of variables.

So x omega 1, omega 2 is the two dimensional fourier

transform or the spectrum of the image x n1 and 2.

This is the expression of the inverse fourier transform that will

take us from the frequency domain back to the spatial domain.

We see with the expression on top that even

when the image is real as it's usually the case.

The fourier transform is complex due to the presence of this complex exponentials.

Therefore, it [UNKNOWN] I can show the

magnitude and the phase of the fourier transform.

And this represents the polar representation of a complex number.

Or equivalently I can show the real.

And the marginal parts.

I see here in the expression for [INAUDIBLE]

fourier transform between the grade for minus pi

to pi in the omega 1 and minus pi to pi in the omega 2 directions.

And this is due to the first property of the fourier transform that it

is periodic With periods 2 pi, 2 pi, in the omega 1, omega 2 directions.

This is a straightforward expression to show, in essence,

we showed it when we started the complex exponentials, we

saw that they're periodic with period 2 pi, 2

pi, and this is what gives rise to this property.

Another useful property is To consider what happens, when I

shift the image by amounts m 1, m 2 in the special domain.

And what happens in the frequency domain is I get the

spectrum of the signal, but it's multiplied by this complex exponential.

So since the magnitude of the complex exponential

is one, the magnitude of the shifted image

has not changed But I have this linear

face component that, is due to the spatial shift.

The reciprocal of this property is the modulation

property that, tells me what happens if I shift the spectrum by 31, 32.

So similarly, I see that I have

this complex exponential appearing in the special domain.

Another use for property is this which

is typically the [UNKNOWN] property which tells us

that when the signal is real, then the

magnitude of the Fourier Transfer has even symmetry.

While the phase of the Fourier Transform has odd symmetry.

And finally this is the Parseval's

relational theorem which tells me that the energy of the

signal, which is found according to this expression in the

spacial domain Can also be found in the frequency domain

by integrating over one period to pi, to pi this energy

density

spectrum.

There are clearly additional properties, quite a few of them, that one can find in

a standard image processing textbook, but these are some of the more useful ones.

Let us consider a simple example.

We are given a system with an impulse response depicted here.

And we want to find the frequency response of this system.

So, we apply the definition of the Fourier transform

and the frequency response is equal to this double summation

[BLANK_AUDIO]

[SOUND] h n1, n2, e to

the minus j omega1 n1, e to the minus j omega2 n2.

Now for the given impulse response, you see that we have only five samples.

So we have the.

H minus 1 0 sample.

h 0 0, h 1 0,

h 0 minus 1 and h 0 1.

So out of this infinite sum, I only have these five terms.

So h 0 0, multiplied by e to

the Minus J zero which is one plus

H minus one zero multiplied by this term

[INAUDIBLE]

[SOUND] And

now I substitute the, I substitute the given values of h.

So this is one-third and all the rest are one-sixth.

[SOUND]

So equal

to 1 3rd.

Now we will observe here that due to Euler's formula, e to the plus j omega

one, plus e to the minus j omega 1 will give me two times cosine omega,

and similarly, the other two terms will give me two

times cosine omega 2, and they can further simplify this as.

1/3, 1 plus cosine omega 1, plus cosine omega 2.

So we see that, for this particular example,

the frequency response of the system is 3l.

This should come as no surprise, since one of the propositions of the Fourier

transform is that if the signal has

even symmetry Then the fullier transfer is real.

This means that the magnitude is the absolute value of the stem, and therefore

the phase is zero at both frequencies except when the stem here

becomes negative, in which case I have a plus or minus pi phase jumps, hence

minus one has absolute value one And phase plus minus five.

So lets see how this frequency response looks like.

So I brought there the magnitude on the vertical axis and they show it over

period the mega 1 for minus pi to pi and the mega to for minus pi to pi.

This actual magnitude has even symmetry, which is also, should come as

no surprise, because we saw in the previous slide that one of

the properties of the Fourier transform is that if the signal is

real, then the magnitude has even symmetry, and the phase odd symmetry.

So if I look at this magnitude, I see that H Zero, zero is equal to one, right.

Cosign zero is one so you have three over three.

And also you observe that at

certain frequencies the magnitude becomes exactly zero.

So for example if I look at the frequency, mine was pie.

Pi over 2.

I have 1 plus cosine minus pi, which is minus 1, so they cancel out, 0.

Plus cosine of pi over 2, which is 0.

And therefore this is 0.

This is actually the frequency over here, right?

So by and large, this is a low pass filter.

Is passes the 0, 0 frequency unchanged.

Attenuate slightly the low frequencies, but as

the frequencies increase, the continuation becomes, greater.

We show here, and example similar to the previous one, where given the

impulse response of a system, and

well distributed to find its frequency response.

The Form that h n 1 and 2 is the depicted slightly different

from the previous case and shown here as a 3 by 3 matrix.

It should be understood that this is the h 0 0 sample.

This one, the h 1 1, while let's say, this one is Is the h minus 1, 1, and so forth.

This actually approximates a Gaussian shaped

function in this three by three window.

After a point, when you look at this impulse

response which is again, is symmetric, has even symmetry.

One should be able to identify terms in

the frequency response, so for example, this and this

term, should give rise in the frequency response of

a 2 times cosine omega 1 times the coefficient

while the diagonal terms This term and this term should

give rise to a term like this in the frequency response.

2 times cosine omega 1 plus omega 2.

So if you work out the example you should find out

that this is the frequency response of this system as shown here.

[BLANK_AUDIO]

It's again, a real signal which should come as

no surprise because hn1 and 2 shares even symmetry.

If we plot the magnitude of the stem It looks like this.

Here a plot of the vertical axis that 10 times log base 10 of the magnitude, so

one can see more clearly small values of the magnitude of the frequency response.

Again, if I look at H(0,0) this is the sum of

the values of the impulse response and they sum up to 1.

And therefore, the logarithm of this value is equal to zero.

So this term here, that's the zero, zero, it's equal to zero.

We'll see again that this is a low pass filter.

It, Attenuates slightly the low

frequencies and considerably the higher frequencies.

And of course the zero zero frequency goes

through the system unchanged of, of the input signal.

Here's a final example.

We're given a system with impulses [UNKNOWN] depicted

here And, we're going to find its frequency responds.

The comments I made earlier apply here as well.

So this is the eight zero zero sample.

We see actually that this simple response differs

in some sense from the previous ones in

the sense that I take differences now between

the center Sample here nine in the neighboring sample.

So we should expect that the shape of the frequency response should be different.

So following exactly the same steps that we

followed in the previous two examples one can

find that the frequency response of this filter

of this to the system is shown here.

Its real again because h(n1,n2) has even symmetry If I plot this.

So I plot here the magnitude in the vertical dimension and I plot again the 10

log 10 magnitude so that I am able to see smaller difference.

Anylsis.

We see that now the shape is different in the sense

that the low frequencies are attenuated while the high frequencies are amplified.

We can easily that the h 0 0 is equal to

1, and therefore the log of this Is equal to zero.

While if I look at, some frequencies.

For example, the h 0 pi frequency, which is the frequency over here.

This is equal to 13, while the H pi pi is equal to nine.

So, considerably higher values than 1 at high frequencies and small values At zero.

Again low frequencies are attenuated, high frequencies are amplified

high special frequencies and [UNKNOWN] are represented by the edges.

Therefore the edges are allowed to go through the

system while the flat regions are rejected or greatly attenuated.

And therefore, a filter like this performs edge detection on an image.

One of the important properties of the Fourier transform is

the convolution property, or, as also referred to, the convolution theorem.

It describes the input output relationships of

an LSI system in the frequency domain.

So given a system with impulse points h, and x in, the input, y, the output,

we know that, the input output relationships in

the spatial domain are through the to the convolutions.

So, the output equals the convolution of

the input with impulse response of the system.

Clearly, I can take each of these quantities through the frequency domain.

So I can find the spectrum of the signal.

I can find the fully transform of the impulse

response, which is the frequency response of the system.

And I can find the fully transform of the output signal.

Since the signals are clearly related in the spatial domain

one expects that they should be related in the frequency domain.

And what the Convolution Theorem tells us is

that indeed the spectrum of the output signal

equals the spectrum of the input signal times

multiplied by the frequency response of the system.

So convolution in the spatial domain becomes multiplication.

The frequency domain, and actually the reverse is also true.

Multiplication, the time domain, becomes convolution in the [UNKNOWN] domain.

Of course, here, we have to talk

about periodic convolution since the signals are periodic.

So, let's see that indeed, this is the case.

So, if I, derive the output of the system, as the system

T, let me call the system T operating on the input signal x n1, n2,

and then I'll replace the signal by its inverse Fourier transform.

So this is equal to this double integral of X

omega 1 omega 2 e to the J omega 1 n 1 and

to the the J omega 2 n 2 d omega 1 d omega 2.

Actually,

the inverse Fourier transform tells me that You

can think of any signal x, n1, n2 as

the weighted sum of this complex exponentials where the

weights are indeed the values of the Fourier transform.

Now since the system is, is linear, and assuming all the signals here are

well-defined, I can Interchange the order of integration and, the operation

of the system, and the system operates on signals that are functions of N1 and

2, therefore they're fully transferred the weight as I called them.

constant, as constants as far as the system is concerned.

So, I am left with this expression.

Now, we have started The,

expression, this expression we know that this

complex exponentials are Eigen functions of lsi systems.

So they go through the systems unchanged and they're multiplied

by the frequency response of the system, So therefore, this expression.

Becomes equal to this one, so if the

frequency response of the system times the complex exponentials.

[SOUND]

So now this is the expression for the

inverse for the transfer of y, and therefore

this signal here is the fully transfer of y, so this is y omega 1, omega 2.

So, indeed, we showed that y omega 1, omega 2

equals x, omega 1, omega 2 times the frequencies.

And so this is.

[SOUND]

We are rooted to this operation when we talk about the example.

So therefore all this tells me that looking at the frequency response of the

system, I have to just process each frequency one at a time, right?

So if H here is 0 at certain frequencies then the output Y is going to be 0.

Therefore those frequencies of the input signal would not go through the system.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play