One of the most important operations in signal processing at any dimensionality, is the operation of convolution performed by LSI systems. This is the topic of this segment. LSI systems are uniquely defined by their impulse response. That is, the response of the system to a two-dimensional impulse. Then the output of an LSI system to any input, is simply the convolution of the input with the impulse response of the system. We will illustrate these two dimensional convolution with an animated example. The impulse response of a system may be known. Or it might have to be measured if the system is available. Or it might have to be identified from the data collected by this system. In the second case, all we have to do is image a point source, a delta and what we obtain is a response of the system to an impulse, or the impulse response of the system. It is indeed a quite powerful result, that is by simply imaging the point source, we're able to fully describe the system. That is, we're able to find the output of the system to any input. So for example, in characterizing the Hubble Space Telescope, this powerful telescope that provided so much. Useful information to the astronomical community. They pointed the telescope to a distant star in the dark sky, and the image they recorded is the two-D impulse response of the system of the telescope. If the system is not available, and all we are given is a blurred image, then we have to design and utilize algorithms. That will identify this blurr, and this a topic we'll address at some high level during week seven. So, let's discuss some convolutions. Let us derive now some expression for the two dimensional convolution. Before we do that. Let's observe that I can write any signal x as this infinity general sum, of shifted deltas. These deltas are shifted at all possible pixel locations in an image, and the height of the delta, is just the value of the signal at the location of the delta, or the intensity values of these pixels. Pictorially, what this expression tells me, is that if I have the story signal here. Let's say it has all these, it has only these four pixels with values say one, two, three, four. Right. You can clearly see that I can decompose the signal as a signal like this, so it's a delta at the origin, with height two, plus this signal's signal, but here's a value one here, plus [SOUND] this signal, it only has a pixel here, a delta here with value three plus finally this signal. [BLANK_AUDIO] Which is value four here at this location. Right? So it's as simple as that. Now, I can write this, this is a delta at the origin. So delta N one and two. The height of the delta is two, and this two is clearly the value of my signal x at zero, zero. Okay? So similarly, I have the value of the signal at minus one, zero equal to one, delta, N one plus one N two. Plus the value of the signal at location one, zero and that's, the delta here, right? Plus the last signal is the value of this signal. It's zero, one and the delta is at location N one a, N two minus one, okay? So I'll make use of this composition right way in deriving the convolution sum. So, I have a system, y is the output. T, I denote the system by T, but here's x as its input. I'll use the above expression, the composition, and write x as this sum k one, k two. [SOUND] Alright? So far, whatever I've written applies to any signal. Now, I know the system is linear and especially, invariant. Now the system accepts inputs that are function of N, function of N. So these deltas, are the signals that the system recognizes, operates on, processes, right? While this x k one, k two here, since it's independent of N one, N two, act as a weight, as a constant, right? So, the system sees this weighted sum of signals. And since it's linear, the output of the system, so due to linearity,the output of the system is going to be this sum here, or the weighted individual outputs. So the weights are k one, k two, and the output is T with delta, shifted deltas at the input. Alright? And now recall, we called the response of the system to a delta. That's the impulse response we denoted by h. And now since the system is spatially invariant [SOUND] and the input is shifted, the delta is shifted, the output h is going to be shifted by the same amount. So, the output would be shifted by k one, k two. So this is the super position sum the convolution to the measuring convolution of x with h. And I, as I already mentioned convolution commutes so this is equal to h convoled with x and you can obtain the second equation by substituting variables, [INAUDIBLE] for example N one minus k one, k one prime and working the equations to confirm that indeed the the convolution is [INAUDIBLE]. Let us now walk graphically through the convolution of two simple signals, an x N one, N two shown here in blue, and an h N one, N two shown in red. If I look at the superposition sum, which is highlighted here. I see that they have to first rename the independant axis from N one, N two to k one, k two, I do it for x. I also do it for h. But for h I, find the deflection of it with respect to the horizontal and the vertical axis. Due to this minus sign. Then, I shift this reflected version by amounts N one, N two. And for each shift, I find the product of h with x, and I sum up this product for [UNKNOWN] to infinity. So, then for this particular shift I'll find the output, the value of the output at N one, N two. I have to perform all possible shifts in order to find y in all possible pixels loca, pixel locations, N one, N two. So let's look at the steps that are imposed by this superposition sum more specifically. So again, the first step is to rename the axis. So now we have x of k one, k two, and they do the same for h, but I reflect it with respect to the vertical and horizontal axis of the reflective version is shown here. I put a zero here to indicate that the shift, if I just reflect, is zero. So this is N one and this is N two. I am going to now superimpose the signals, use them in the same graph as shown here. And then, for this particular location, since h is sifted by zero, zero, right? I'm going to find the product of the two signals, and I'll sum it up and I'll find the value of y at zero, zero. We see that for this particular situation, the overlap is only at one pixel, the pixel here, which has changed color. So, x is in blue, h is in red and where they overlap the, the color is purple, right? So, in this particular case, there is overlap of only one pixel, and when I sum it up. I have one, and therefore this is the value of the output at the location zero, zero. The next shift is by one in the horizontal and zero in the vertical direction, so this is the picture that you see here on the left. So, the overlap now is at these two pixel locations. The shift is one, zero so, I'm going to find the output at one, zero. I carry out the multiplication and the summation and I see that the value of y one, zero is equal to three. I'm looking at the next possible shift, N one equals two,N two equals zero. Therefore, if I find the output at two, zero. I see that now these two pixels overlap, and therefore if, I carry out the multiplication and the summation right? I multiply the values of the pixels that overlap and this one right [UNKNOWN] the summation. There are only two of this particular case. I see that the value of the output of at two, zero equals to five. Shift three, zero, I do the same thing. The value of the output is equal to three, the next location is here, the shift is zero, one. Therefore the overlap is these two pixels. I see that the value of the output is equal to five. Shift one, one, I have four pixels overlapping, therefore the summation involves four products, and the value of this pixel is equal to 12. [SOUND] Shift to one, four pixels overlapping, the value equals 16, [SOUND] shift three, one [SOUND] two pixels overlapping. The result of the summation equals nine, zero two, one pixel overlapping, that's the value of the output. one two, two pixels overlapping [SOUND] the result of the summation. Two, two, the result of the summation equals 11. And finally three, two, the result of the summation equals six. Any other shift of h will result in no overlap between the blue and the red pixels, between x and the shifted h, and therefore the value of y is going to be equal to zero. So summarizing, we see that the result of the convolution of x with h is the signal y as depicted here. An important observation is that the signal y, the image y has larger support than any of the support of the signals, x and h. One can show in general, that if I have a signal that can support, [SOUND] as shown here and determined by these points, p one, q one, r one. And this signal is convolved with another signal that can support [SOUND] p two, as determined by these points, p two, q two, r two. Then, the resulting signal from this two D convolution, will have support [SOUND], as shown here and, determined by this point, this point is p one plus p two. This is q one plus q two, and this is r one plus r two. So, for the specific example we worked out, we see that this point is the zero, zero point. This is the two, zero point and this is the zero, one point. And similarly, this is the zero, zero point, one zero, zero, one. Therefore, the result of the convolution y here can support zero, zero plus zero, zero is this point. And this point is two, zero plus one, zero, three, zero. And this point up here is one, zero plus one, zero, I'm sorry zero, one, plus zero, one, zero, two. Okay, so this is something important to keep in mind that will come and revisit. And the second observation here is that clearly. Because we work these very simple signals, we could graphically solve the convolution, kind of take all the steps and find the the values of the output one by one. But if I have an analytical expression of the signals then, I need to evaluate that double summation. For the parts of the shifts where the two signals overlap and therefore the, the product is non-zero.
