0:02

Having introduced the two-dimensional continuous fully

transform of a discrete two-dimenstional signal in

the previous segment, we can now describe and understand the operation of something.

That is, the operation of turning a continuous signal into a discrete one.

0:19

As we've discussed during the first week of

class, sampling is needed in being able to

bring a continuous signal into the discrete world,

so that it is processed by a computer.

0:40

The fundamental question, therefore, when sampling is

performed, is under what conditions can we

move back and forth between the continuous

and discrete worlds, without loss of information.

Or, under what conditions we can

reconstruct the continuous signal from its samples.

We derive these conditions which are referred to as the Nyquist Theorem.

1:16

We derive the theorem in two D.

However, it's straightforward extension of the one D subject theorem.

And it can also be extended in similar way to dimensions higher than two.

Actually, in two and higher dimensions, there

is more freedom in preforming periodic sampling.

We'll only cover here rectangular periodic sampling, but one

could use, for example, hexagonal periodic sampling in two D.

1:43

Sampling provides the intuition in understanding what happens

when we sample now the continuous Fourier domain.

It leads to the definition of the discrete Fourier series.

And also the definition of the discrete Fourier

transform, which is the topic of the next segment.

2:07

One of the important concepts in digital

signal processing is the concept of sampling.

It connects the analog to the discrete world.

It's true that with the proliferation of digital sensors, there is less

of a need for converting an analog image to a digital one.

But, the mathematical concepts of something that important,

for understanding other topics in imaging and video processing.

They're important, for example, in allowing us to understand the steps we

need to take in changing the sampling grade in the digital domain.

For example, when we up sample or down sample an image, as you'll see later.

So assume that we have an analog image like the one shown

here, such an image can appear for example on a positive photographic field.

I realize of course that for the younger people in the class you may or may

not be familiar with negative or positive fields,

it is however worthwhile continuing with this topic.

3:05

Again I present the signal in the frequency domain, and here is the

spectrum of the analog signal X sub' a' Omega One, Omega Two.

What we show here is really the region of support of this spectrum and not that

shape of this spectrum itself, but it's not

relevant the shape for the discussion that follows.

I want now to represent this image by discrete sample so, I super-impose a

grid that's shown here, and only keep the values of the image at the grid points.

So the digital image I end up with is the one shown here.

And there are two parameters of control.

This grid, the spacing in this direction T one.

And the spacing of the vertical direction, T two.

And these are referred to as a sampling periods.

4:19

It's not surprising this periodic because we do know the spectrum of a

discrete signal is periodic a property that we covered in quite some detail.

And it is formed really by performing the periodic extension of

the spectrum of the analog signal, again as shown here.

The mathematical expression to describe this, is the one shown here.

4:46

You are used to put, so far we've been

using this notation Omega One, little Omega One, Omega Two.

Denote the Fourier Transform of a discreet signal, and this is exactly called this is

since Omega One is the normalized frequency

and equals big Omega 1 Times t 1.

So Omega One is in gradients, while bigger

omega one is in gradients per unit distance.

Spatial distance, let's say, millimeters, as an example.

And t 2 is also in millimeters, so the units, the dimensions really match.

And of course, Omega Two is Given by similar expression.

5:31

So what this expression tells me again is that they take

the spectrum of the analog signal, and I periodically extend it.

So k one ranges from minus infinity to infinity.

So does k two.

And the periodic extension in the horizontal direction

is with respect to two pie over t one.

One, the vertical direction with respect to two pi divided by T2.

So this point here is two pi divided by

T1, while this point is two pi divided by T2.

[BLANK_AUDIO]

So, we see that in performing something, there

are two important parameters: the sampling periods, T1, T2.

They control the spacing of the point in

the spatial domain, and they also control how far

apart the replicas of the the analog spectrum

in this periodic extension, are going to be located.

6:40

So that when I find now the fully transform

of a discrete signal, which is formed by the periodic

extension of the spectrum of the analog signal, the

spectra here just touch, next to each other without overlapping.

6:56

And in this case, at least mathematically speaking, I can filter the base

bond of the spectrum of the discrete signal, and then this will give

me back the spectrum of the analog signal, therefore, I will be able to go from the

discrete weld, but the continuous weld without losing any information.

7:20

If I use a smaller t one, t two sampling periods than in the previous case,

then when I look at the spectrum of

the discrete signal, is going to look like this.

And, in this case I've used more sample

I needed to represent accurately the continuous image.

I therefore, I have oversampled.

[SOUND]

If I go the other direction, and use sampling periods here t1, t2,

which are greater than the periods used for critical sampling Then if I

look at the spectrum of the discrete image, it looks like this, while my new

periodic extension, one replica overlaps with another replica, and this phenomenon

is referred to as aliasing.

8:13

Which means that the high frequencies here alias

themselves as low frequencies the use of false identity.

Under this case, it's not possible to recover the original signal.

I am not able to untangle the low and high frequencies that can be, mixed up.

8:53

Intuitively, one should expect that how close together the samples are

should be a function of the spatial frequency in an image.

If the image intensity varies a lot and rapidly, which

means that there's a lot of high-frequency energy Then, intuitively,

one should use samples that are close together, so that

all of these first variations of intensity have captured the property.

If on the other hand, they have another flat image, then a few

samples will suffice, and this is exactly what the Nyquist theorem tells us.

So here is again the support of the spectrum of the analog image,

and lets call Omega n1 the highest frequency in the horizontal

direction and Omega n2 the highest frequency in the vertical direction.

After I sample this image, the spectrum of the

discrete image is desirable but it looks like this.

So in other words, there is no aliasing.

So this point is two pi over t1 and therefore the

point in here is two pi t1 minus Omega and one.

So clearly, as long as the ordering of these two points is as shown here.

So, as long as two pi over T1 minus omega n1 is greater or equal than

omega and one, there's no aliasing in the horizontal direction.

And this gives us the condition that the something frequency should be

at least twice as high as the highest frequency in the image.

And they can obtain the similar condition in the vertical direction, so the

something frequency in the vertical direction should

be greater equal then omega and two.

So if these two conditions are satisfied, then I can recover the analog image

from the discrete one by using a low pass filter, as shown here.

11:38

This T 1 T 2 gain is here because if you look back, a few slides back, at the

relationship between the spectrum of the discrete signal and

the analog signal, there's 1 over t1 t2 factor there.

So I need this gain to bring back the signal It's original values.

So this frequency, this is for example, minus pi over T1,

12:06

this is pi over T2, so this is the filter that is shown exactly here.

So in summary what the Nyquist Theorem is telling me is that if I

have an unlimited analog signal I can

sample it with frequencies that satisfies these conditions.

And then I can recover the analog signal from the

discrete one using a filter like this on the frequency domain.

And what this means in the spatial domain is

that I perform bundling with the Interpolation with a

candle, which is the Fourier transform of this ideal

low pass filter, and this is a two-dimensional sync function.

A sine x over x function.

12:52

In illustrating the concept of sampling, oversampling, undersampling Let us

consider a simple one dimensional signal, the cosine depicted here.

It has frequency equal to 0.9

Hertz, or in Omega units, 2 pi f

1.85 radiums per second.

So, in a ten second interval shown here,

there are nine cycles of this particular cosine.

If I take the one dimensional fully transfer of the signal now.

I see that its spectrum looks like this, it

consists of two impulses at 1.8 pi minus 1.8 pi.

And clearly, this tells me that there's only one

frequency present in the signal, it's therefore a pure tone.

14:12

So, here, with the grid examples, we show the

sample version of this cosine when we grade the over-sample.

If you recall from the previous slide, the Omega Nyquist, with a note like

this, was, 1.8, times two pi,

radius per second So, 3.6,

by Rads per second, so

instead of using the Nyquist, I use a 60 pi rads a second or the

sampling period is run a 30th of a second, so therefore I get 30 samples per second.

There are ten seconds in this interval, so there are 300 samples shown here.

14:57

So, if I look at the spectrum of the signal, then as we know, we take

the spectrum of the other analog signal, these

two impulses, and periodically extend it with period 65.

So here one replica here at 60 pi and other minus 60 pi and so on and so forth.

And in this case, I can go back and forth between the continuous and discrete

worlds by just using a low bus filter pulling out these two impulses.

And, in the time domain, I'm going to

get continuous cosine signal that I started with.

15:38

I sample now my analog cosine I'm working

with with period one second or frequency one halves.

Or, an Omega with 2 pi radians per second, we call that the Nyquist, where

the signal Omega band is 3.6 pi radians

per second.So with this sampling period in this interval of ten seconds,

I have 11 actual samples, since I also sample at equals 0.

Let's see how this sample signal looks in the frequency domain.

Here is the spectrum of the analog signal, and I know that the sample signal is

a spectrum which is a periodic extension of the spectrum with periods 2 pi.

So here's one, the first replica of the spectrum,

a second replica, and so on and so forth.

So clearly, the sky frequency component in the original

signal alias as itself, as a low frequency component.

17:02

You can, look at this signal also, the one that results from

the first sample signal, where I had over sampled, I had 300 samples

there, in this interval, and if I down sampled by a factor of

30, so, I throw away 30 samples, I keep one, throw away 30.

And so on, then, this is the signal that, we'll end up.

So we can either think of this signal here as resulting from the down-sampling

of the original analog sample or down-sampling the

sample, the digital sample, right, so with the down-sampling in the discrete domain.

17:44

We would like now to pictorially connect what we've

learned so far and what, is going to follow.

I will not be showing any equations.

Since they can be found in any

book on image processing of multidimensional signal processing.

17:59

I think it's important to see what the

situation is behind the various concepts underlining the

special frequency domains, and just focus on the

elements that are of primary importance in image processing.

So we started with analog image, such like the one shown here.

Which we represented also in the frequency domain.

So, here see the continuous spectrum of the continuous image in the Omega one and

Omega two, axis and of course we show

here, just the unit's apart of the spectrum.

So then we sample this image.

[UNKNOWN] disagreed and we kept the values at the grid points.

And we also can represent as we know

by now, this discrete image in the frequency domain.

We know by now that the fully transfer of the discrete signal is periodic

18:50

And is formed by the periodic extension of the spectrum of the analog image.

I can present the spectrum in the bigger Omega One, Omega Two

domains, the continuous frequencies, or the

normalized frequencies, little Omega One, Omega Two.

In going back and forth between the continuous and discrete worlds,

I need to know the sampling periods, or the sampling frequencies.

If however, all we are given is a discrete image, or a two-dimensional

array of numbers, we don't know what

is the spatial distance between these numbers.

Between the big cells, and therefore, I can only express the spatial

frequency content in terms of the

normalized continued frequency in the domain.

19:45

We saw before that sampling in the spatial domain results

in periodic extension of the spectrum in the figurative domain.

So our intuition tells us that the similar operation should take place

now in the special domain now that there's something in the frequency domain.

In other words the image should be periodically extended.

And this is exactly what happens as we can show mathematically.

So we can see the periodic discrete spectrum

corresponds to a periodic discreet two dimensional signal.

Of course, the density of sampling in the frequency domain will

determine the period in the periodic extension in the special domain.

If I under sample in the frequency domain,

aliasing will take place in the spatial domain.

So we see that a discreet periodic signal

has a discreet periodic representation in the frequency domain.

And this is, indeed the Fourier Series.

Going from here to here is the Fourier

21:02

Now one period in the frequency domain

corresponds to one period in the spatial domain.

And in Showing this here, I have chosen the

sampling in the frequency domain to be done critically,

so I have the same number of samples in

one period in both the spatial and frequency domains.

So, we see here that, and then one, let's say, by m 2,

period image corresponds when one and two samples in

the frequency domain, and this mapping here is that

discrete fullier transfer mapping that we will study next in quite some detail.

22:06

So it's important to keep in mind that behind the

DFT, there are discrete periodic

two-dimensional signals in both the spatial

and frequency domain Since the number of the properties of the

D.F.T. can be derived and understood, by considering these, periodic extensions.