Welcome back. Now that we've covered and understood something in the previous segments, we address in this segment the change of something great of a discrete signal. In many applications we are interested in either increasing the number of samples in an image referred to as up-sampling or interpolation or reducing the number of samples referred to as down-sampling or decimation. We analyze in this segment these operations in the discrete frequency domain. We see for example, that down-sampling introduces aliasing, and the way to minimize the effect of aliasing is to low-pass filter the image first with an appropriate filter before reducing its spatial resolution. Similarly, we show one of the possible ways to perform up-sampling using discrete frequency domain filtering. Sampling rate conversion is an important operation with many applications. For example, in image and video compression. Multirate signal processing is an important sub-area of signal processing. The rate conversion in general can be performed by a non integer factor. So we are touching the tip of the iceberg in some sense in this segment on this very important topic. Let us now proceed and look at the details. Sampling is an important topic and the same thing goes for the continuous world to the discrete world. Equally important is the process of resampling or changing the sampling grade in the discrete world. It's often we need to change the size of an image either make it larger, up-sample it or smaller down-sample it. All of this is an interesting and rather broad topic that we'll be revisiting during the course. We want to mention a few ideas here as they relate to what you've been covering so far. Again, I will not be showing or deriving any equations, but pictorially provide some information of what's taking place. For those of you interested to look further into this they can find this material in any standard book on image processing or one dimensional digital signal processing. So given an image, I'm interested in reducing it's size by two in each direction and here you see an eight by eight image. But I wanna reduce it to a four by four image. We also show the spectrum of this image here, so this is 2 pi, 2 pi and let's call this frequency omega 1 maximum in the 1 dimension omega 2 maximum in the vertical direction. A simple or naive way to perform this down-sampling is to remove every other column and every other row of the image as shown here. So therefore I end up with a 4 by 4 image. What happens in the frequency domain is shown here. The spectrum is squeezed down, the height is reduced of course, don't show the height here I just show the support. But also we see that the maximum frequency moves to this point in the horizontal and to this point in the vertical direction. So because of that, we see that aliasing high frequencies alias themselves as low frequencies. And this again, manifests itself in the special domain in the form of jagged edges. So if this is my form of down-sampling throwing away in other words, every other column and every other row. In order to avoid aliasing, I should be low pulse filtering the image before down-sampling. And I should be low pulse filtering with a filter with cut off frequencies, pi over m on the one and pi over m in the other direction where m is the down-sampling factor. So if you see an example here of the down-sampling process we just described. The original image is a 4200 by 3000 pixels. It's too large. It's not shown here. And they show that the result of down-sampling with and without prerobust filtering. So on the left, you see the image that resulted by just again, throwing away every nine columns and every nine rows since the down-sampling factor is ten in this particular case. And the editing effect, as I already mentioned manifests itself here if we look at edges or high frequency components we see that low and high frequencies are mixed up. It appears everywhere in this building, this is a picture of the Chicago Skyline while the flat regions, like the regions here, don't show any effect of anything as expected. On the right, I show the down-sampled image to the same size as the one on the left. But in this case, before down-sampling the image was low pass filtered by a Gaussian filter of support 11 by 11 pixels. And the Gaussian means that the impulse support has some Gaussian shade within this original support. So in this case, you see that the high frequencies available are preserved. Of course, we lost some high frequencies due to the low bus filtering, but we were able to preserve some of them. It's just if you compare all kind of different regions here you can easily see the difference. So let us see what is a way now for up-sampling an image based on what we have learned so far. So we're shown here in this toy example a 4 by 4 image. And we are interested in turning it into an 8 by 8 image. We show the spectrum here of this image, so this is 2 pi, this is 2 pi the vertical direction. The first step towards up-sampling is to introduce columns and rows of zeros in-between the existing samples. So clearly now, we have an 8 by 8 image. What takes place in the frequency domain is that I see a frequency scaled version of the original spectrum. So here we have a replica a scaled replica of the original spectrum appeared here at pi, another one at pi in this direction and I only have one replica between 0 and 2 pi, because the up-sampling factor is equal to 2. All I'm interested in is keeping the base band of the spectrum of the image and they can do that by utilizing the low-pass filter indicated here. So what happens in the spatial domain is that convolving the image with in transfer of this low-pass filter which is referred to as the idea low-pass interpolation filter. So the zero values that they have introduce will change now to specific values based on the existing neighboring pixels. Let us look at the up-sampling example. A 128 by 128 image is shown here. And would like to increase its resolution by a factor of two in both directions, so end up with a 256 by 256 image. We show here the spectrum of the image, it's a 256 by 256 spectrum which was obtained by zero parting that original image to the 256 by 256 size. We want to show the spectrum so that they can see how the result is after we follow the steps of up-sampling. So the first towards up-sampling is to insert zero columns and zero rows to the original 128 by 128 image, so that the resulting image is now is a 256 by 256 image. If I look at the spectrum of this image, I see this replicas of the base band appear here. This is pi, pi for example due to the insertion of zeros. The final step is to low pulse filter the spectrum so that I only keep the base bond. While rejecting all other frequencies. So the blue areas here represent zero values. Now, if bring this back to the special domain I see the interpolated image I show here. An alternative way to up-sample the image is perform the convolution on the special domain with interpolating filter like the one show here. So this disables part of the filter. This is the h 0, 0 point. So first of all, let's see what this filter is doing. So if I have in the low resolution image, let say four values a, b, c, d. As we saw the first step is to introduce rows and columns of zeros. And the idea of the interpolation is to change these values of zero to some other values. So if I perform the convolution again of this filter here with this image, we see that this 0 here will be replaced by a plus b over 2. This might be b plus d over 2, while this pixel here will be replaced by a plus b plus c plus d divide by 4. I just take the sparse of this, it's metrics [INAUDIBLE] around and it will stay the same. And I place the one center, the pixel location I try to find it's value and we see that this is indeed the case. Now what's happening in the frequency domain is that the spectrum of the low resolution, let's call it 128 by 128 image, the 256 by256 spectrum which again we find by padding it with zeros as I showed earlier, is multiplied by the frequency response of the filter. And what's the frequency response of this one? Is by now, we should be able to look at it and by observation we know that it's 1 plus cosine omega 1 plus cosine omega 2 plus one-half cosine omega 1 plus omega 2 plus one-half cosine omega 1 minus omega 2. So this filter, we showed actually the magnet of this at an earlier point looks like, is going to multiply the spectrum of the image and this is the resulting spectrum of this up-sampled image. So we see that what happens is exactly what I had before. In other words, this is a low-pass filter, so that replicas here in the middle of the spectrum are rejected and I only keep just one replica of the spectrum at the base band. However now, I'm not using a sharp low-pass filter as in the previous example, but the filter here is the shape that is expressed by this equation here. H omega 1, omega 2 and it's depicted here as an image. So this brings us to the end of the third week. By now, when we look at an image, we do not only see its bright and dark regions or its different colors. But we can distinguish between high and low spatial frequencies regions where the intensity values transition in a fast way or regions where they transition slowly respectively. During this week we learned that there exist computationally efficient ways called fast Fourier transforms that allow us to represent any given image in the discrete frequency domain. And therefore, distinguish between high and low and intermediate frequency. We also learned that we can now implement an LSI system or perform filtering in the discrete frequency domain. For filters with large support of their impulse response, this is indeed a much faster way to carry out filtering. We finally learned how the Fourier tools can help us in analyzing sampling or sampling rate conversion. The Fourier tools are of the most fundamental and useful tools one interested in working with the good signals can get equipped with. They're actually the same tools whether we're interested in processing speech or audio, images, video or videos of three dimensional objects. I'm certain that the tools that you've acquired in these two weeks will serve you will for the rest of your signal processing related career. We will actually cover next week another tool, you might call it so motion estimation which is of the utmost usefulness when we process video. We'll also cover next week some of the fundamental notions of colored image processing. So with that, I'll see you all next week.
