0:02

The main drawback of the Continuous Fourier Transform with the

discrete signal is that this is not a computable transform.

Unless the image has a close form

expression, its Fourier Transform cannot be computed.

0:16

Based on the material of the previous segment, we'll

go show in the segment that a sample version

of one period of the continuous Fourier Transfer is

all that is needed to represent the discrete image.

This represents the Discrete Fourier Transform, or

DFT, which maps m by m samples of

an image in the spatial domain, into m

by m samples in the discrete frequency domain.

0:43

In addition, what makes the DFT such a useful tool is that there are fast ways to

compute it, collectively referred as Fast Fourier transforms or FFTs.

We will look at some examples of spectra of images in this segment using FFTs.

1:01

So, let us proceed with this interesting and useful material.

[BLANK_AUDIO]

Let us in more detail some of the parts we covered in the previous slide.

Here, again, is the definition of the continuous Fourier

transform of a discrete time signal x N1 N2.

It's an N1 by N2, signal.

That's a support of the signal.

1:27

This is, a very useful transform, and we'll spend quite some time talking about

it because it allows us to describe,

characterize, analyze images in the frequency domain.

1:38

The main drawback of it however is that it is not a computable transform.

I have to find X at all possible

frequencies omega 1, omega 2 are continuous quantities.

So, if I have an analytic for x N1, N2,

then it is possible to find a closed form expression

for x omega 1 omega 2, as was the case

with the simple examples we did in the previous slides.

If, however, I want to find the continuous Fourier transform of an

image that I acquired with my digital camera then clearly I don't

have an analytical expression for the image and therefore am not able

to find an analytical expression for x omega 1 omega mega 2.

So what you saw in the previous slide is that I can sample the

Fourier transform x omega 1 omega 2 at equally spaced frequencies.

And the spacing between frequencies is 2 pi over N1 in

the horizontal direction and 2 pi over N2 in the vertical direction.

2:43

And by doing this sampling of the frequency domain I only keep one period.

So, k1 is from zero to N1 minus one, k2 between zero

and N2 minus one and again this is for a N1 by N2 image.

So, if I substitute two pi over N one for omega one, and two pi over N

3:11

two for omega two here, I end up with

this expression, which is the fourier Discrete Fourier Transform, DFT.

It gives me a description of the image and the discrete frequency

domain, k one, k two when k one, k two range over

one period is shown here and this is clearly a computable transfer because

it only involves the finite summation, therefore in finite number of operations.

3:44

The inverse Fourier transform shown here, takes me from the

frequency, the discrete frequency domain, back to the discrete spatial domain.

Algorithmically, it has the same structure as the Fourier transform.

The only difference being that here I have e to the plus j.

The exponential while is to the minus j.

And I also have this normalization factor in the front.

4:10

So this here is the Discrete Fourier Transform pair.

[SOUND] That maps N1 by N2 discrete space images, samples, to N1 by N2 samples

of the Fourier domain, of the Fourier transform in the frequency domain.

It's an exact transform.

I can go back and forth between x k1 k2 and x N1 N2 with, with no error.

And it makes sense, since an N1 by N2

4:41

image is mounted to another N1 by N2 image,

both discrete, and therefore I don't need infinitely many

frequencies to represent the signal in the frequency domain.

Actually, even if the image is real, the DFT is complex, so it seems

that a mapping N1 by N2 real numbers into N1 by N2 complex numbers.

However, the property of the Fourier transform that the emission property that

we start, started holds through here for the DFT that is when x N1 N2 is real.

The magnitute of x k1 k2 has even symmetry while the phase has odd symmetry.

Therefore I'm mapping N1 by N2 real numbers

into N1 by N2 over four complex numbers.

And assuming that one complex number corresponds to two real numbers,

I have the same number of numbers in, in both domains.

5:38

The DFT and the Fourier transform share many, if not all, of their properties.

One main difference, however, is that the linear shifts [SOUND]

in the Fourier transform become when it comes to DFT circular shift.

[SOUND] One way to perform in the extend fourier shift is to

periodically extend the image, and then they form linear

shift, but only keep the central part of the image, the base bond

or the image that is defined by N1, N2, in this window here.

[SOUND]

By knowing the description of a Fourier Transform

it is clear that it is a computable transform.

It involves a finite number of compu, computations.

The same statement is true also for the inverse discrete Fourier transform.

6:40

However, what made the DFT, very popular, you

might say, transform is the fact that there

exists efficient computation, efficient algorithms to compute it,

which collectively are referred to as Fast Fourier Transforms.

So an FFT is not yet another transform,

it's simply an efficient way to compute the DFT.

So let's see how many multiplications we need if we directly compute the DFT.

So we see that for each frequency k1 k2 we need N1 N2

complex multiplications to do the multiplication

of the signal by this complex exponential.

Since I have N1 N2 frequencies, I

need N1 squared N2 squared complex multiplications.

Clearly if N1 equals N2 equals N, then I

need in this case N to the fourth complex multiplications.

7:38

I can do better than that by rewriting,

reorganizing the terms in the definition of the DFT.

So I see that what's inside the brackets is

that one dimensional DFTof the signal with respect to n2.

So if here is my image.

So N1, N2 is the rotation of the axis, so X n1,

n2, what the summation inside, inside the bracket is doing is computing

the one dimension of the DFT of the rows of the image.

This signal then inside the bracket is I can call it G

is a function of N1 Nk2.

With this I can then rewrite the DFT as shown here.

And what this last expression tells me is that if I take G N1,

k2 is a function of N1 and k2, according to this summation

I know but form the one dimensional DFT of each of the columns of the signal.

8:48

Here's the name Row-Column Decomposition.

First, we take one dimension of the FFTs of the

rows, followed by one one dimension of the FFTs columns.

So let's see how many computations we need of this Row-Column

Decomposition if I direct the compute the one dimension the FFTs.

So what we've done is to first take N1 and 2.1dimensional

FFTs and if again directly computed I need N2 squared multiplications.

And then we take N2 and N 1.0

DFTs, and for that I need N1 squared multiplications.

This is clearly equal to this.

[BLANK_AUDIO]

So again for N1 equals N2 equals N, I

see that I need 2N to the third multiplications.

So, by just exploiting this decomposability

structure of the DFT, I see

I can bring the number of multiplications down by an order of magnitude.

I can do even better than that since I have fast Fourier transforms

to compute one dimension of the FFTs and this transfers date back to the mid60s.

So 1965, Couley [SOUND]

and Turkey were the first people to invent such

fast Fourier transforms and by enlarge they developed meant gave a big push to

the whole field of DFT since now we were able to

efficiently maybe real time in some cases, implement algorithms that were very

hard to implement before that.

So, using one of those, FFTs, I can compute them N1.1

dimensional DFT by using N 2 over 2, locg 2, N2 multiplications.

And then for computing the n1 point

DFTs I need n1 over 2 [SOUND] log n1.

And this is clearly equal to n1 n2 over 2 [SOUND] log n1 n2.

11:08

So we see here that for N1 equals N2 equals

N, I need N squared log 2 N multiplications.

So we brought down the number of

multiplications by anoth, another order of magnitude.

And this is actually in most cases the way to implement the two-dimensional DFT

by following the Row-Column Decomposition and then

utilizing efficient algorithms to compute the one-dimensional DFT.

I can do better than that if I use a so-called

radix [SOUND] two by two FFT [SOUND] and I bring down the

computations to three fourths N squared, log 2 N.

12:03

And with the DFT, which is a computable transfer, and even

more specifically with an FFT, a fast way to implement it.

I can see how an image looks in the frequency domain.

So here is the orientation of the axis, N1, N2.

And this is a 392 by 294 pixel image.

And they are 8 bits per pixel.

13:08

So in the middle you see the mesh plot of the DFT, the magnitude of the DFT

while on the right you see an image version and it's cover code.

And so, red, here, is high values, and blue are the lower code values.

13:27

So we can see that there is a lot of energy at low frequencies.

This is the zero zero.

There's a pink there, and the magnitude of

the DFT drops off as I approach higher frequencies.

[SOUND]

So here we see the same image again on the left, but often it's

more informative if the magnitude of the spectrum of the image is centered.

So, in other words, the zero, zero point is around about here.

And therefore here is minus pi, pi, and minus pi, pi in the other direction.

14:45

So this is a checkerboard pattern.

It alternates between minus one and one.

And y would search a multiplication center of the spectrum, because

this is clearly to, e to the minus j pi, N1 plus N2.

15:05

So, in the spacial domain, I multiply my signal with this complex exponential.

And, one of the properties of the DFT is that

this introduces a circular shift of the DFT by pi pi.

We saw this property actually, I believe, when

we talked about the Fourier transformed and there the

complex explanation, the spetial domain gave rise to

a linear shift but here it's a circular shift.

So, circular shift, one of the ways again to look

at it is that I take the spectrum, I periodically

extend it, I shift it linearly by pi pi in

both directions but then I only maintain the base period.

The one shown here, right, from zero to

three ninety two and zero to two ninety four.

And again here you see the spectrum as an image so the high value is at

zero zero centered and again this provides in

most cases a better visualization of the spectrum.