Welcome back. 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. 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. In most cases they're also interested in bringing the discrete signal back to the continuous world. So that we can see it, or so that we're able to hear it. 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. A [UNKNOWN] signal can be reconstructed from its samples if it is sampled with frequency at least twice as large as the highest frequency of the signal in each dimension. 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. 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. So let us now have a closer look at this exciting material. 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. 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. I can now represent this descrete signal in the frequency domain. I can take the fully transfer of this signal as we've done already in this class, and if I find this spectrum, it looks like this. 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. 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. 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. We say that the analog image is critical example, if I use the appropriate T1, T2 here, sampling periods. 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. 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. 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. 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. In performing sampling, an important question is what should the samplings periods t1 and t2 be quelled to. So that, I'm able to go back from the discrete samples to the analog image. 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. So, this low pass filter, let's say, f omega 1 Omega 2 should be equal to T 1 T 2 as long as Omega 1 is less than pi over T 1 and Omega 2 less than pi over T 2, and 0 otherwise. 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, 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. 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. Now the Nyquist frequency, [BLANK_AUDIO] For the signal, it's either 1.8 hertz or 2 pi times 1.8 radians per second. 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. 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. 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. So, when I reconstruct this aliased signal using the low pas signal shown here. I end up reconstructing the signals shown here on the left with frequency 0.1 Hertz or 1 cycle in this 10 second interval, I'm starting. 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. 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. 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 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. And this is material we have covered so far in the previous slides. Now an interesting question that arises is what will happen in the special domain if I sample the Fournier transfer of the split image. 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 Series representation. The discrete spectrum is often referred to as a line spectrum. 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. So we see that if I have an N1 by N2 image, I can represent it uniquely by an N1 by N2 samples of the frequency domain of the spectrum of this image. 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.
