Convolution, and cross-correlation, are two important operations that come up over, and over, and over in cryo-em, and all microscopy and structural biology in general. And we'll talk about them now, after studying Fourier transforms. Because they're calculated in Fourier space, and best understood with reference to Fourier transforms. So, let's start with convolution. Now, let's suppose we have one function, which is just a series of delta functions. At different positions along the axis. And let's call this function f of x. And let's suppose that we have a second function, which has this kind of a shape. And let's call this function h of x. Then what it means to convolve. F of x, and h of x is everywhere that f of x has a value to essentially map or place the function h of x in that location. So here we have f of x as a delta function. And so, if we placed. H of x there and then we make another copy of h of x over here and where these functions overlap they'll just pile up, and then we skip over to here and we reproduce h of x in this location as well, so that's the convolution of h of x and f of x. And so it would look something complicated there, another complication there. Then basically flat, and then another version of h of x, another version of h of x. Okay, so that would be the convolution. And we call that f convolved. That's the symbol we use for convolution. Convolved with eh, h. And the formula is. Let's say, g of i. If g of i is the convolution of f and h, well then it's equal to the inner growth from negative infinity to positive infinity of f of some dummy variable x times h. Of i minus x, the x. Now, while the concept of what is happening in a convolution, and it's formula is relatively simple, in one dimension. It's practical relevance may not be so clear. For that, let's move into the two dimensional case. Imagine there was an image, say an image of a duck, as shown here. And that image was convolved with a lattice. So this is like a second image, but what I am trying to depict here with the red dots are delta functions. And the delta functions are placed in a regular 2-d lattice. So if you convolved a particular image with a two dimensional lattice, the result would be a crystal of that unit cell laid down in the pattern dictated by the lattice. So a crystal. Can be understood as the convolution of two different functions. One, the density of a one single unit cell convolved with the lattice of the crystal. And so as you'll see later, all of the processing that we might do on data. Collected from a crystal involves this understanding that, that data comes from the convolution of two different functions. Now, another way that convolution comes up in any kind of microscopy is in the idea of a point spread function. Now, let's imagine that we have a very fine image. In this case, this is the image of an eyeball, but it's very finely pixellated as you can see each of these dots. It's a very high detail pixellated image here. And if we were to convolve that image with a Gaussian spreading function, you might call it, the result. Is what appears to be a much smoother image of the eye because each of these distinct, sharp peaks is smeared by this Gaussian blurring function. And we call this a point spread function, which I'll abbreviate many times as point spread function PSF. And conceptually, it describes how each point in the original image is smeared in the final picture. In the context of microscopy, this happens because the original image is an object of interest, and unfortunately, electron microscopes, nor any other kind of microscope, can produce a perfect image of the object. Instead, the image that you always obtain is the original structure, smeared by the point spread function of that particular microscope, which gives you a lower resolution version of the image. Now mathematically, if the function G is the convolution. G of i and j is equal to the convolution of some function f convolved with the function h, which are both two dimensional. Then we can write that as that it's a double integral of f of say, two dummy variables x, y times h of i minus x, j minus y. Dx, dy. But it turns out that if g is the convolution of f and h then the Fourier transform of G is equal to the Fourier transform of f times the Fourier transform. Of h. And this is what's called the convolution theorem. And because this is true, then another way to calculate g is to take the inverse Fourier transform of the Fourier transform of f. Times the Fourier transform of h. So what this means is that to calculate this function g, which is the convolution of two other functions. The fastest way computationally to do it is to take the Fourier transform of the first function, and the Fourier transform of the second function. And multiply them pixel by pixel in reciprocal space, and then calculate the inverse Fourier transform of that result and that gives you the convolution. Now a very closely related, and also fundamentally important, operation is cross correlation. Cross-correlation is used to assess how similar are two different functions. So, for instance, in this example, from Hecht's book, Optics, one function is given as an image of a city. A black and white image of a city from above. And then a second function would be a small part of that image. And cross correlation can be used to ask how similar is this image to this image. And more specifically, where in this larger image. Does this feature appear? Now, conceptually, cross-correlation takes all the values of the, let's call this the probe image, and it compares. Pairs them, position by position, with all of the values of the test image. Let's call this the test image. And so, it compares this probe image with the test image in the upper left corner. And then it moves over one pixel. And it compares it to the test image in the next position. And then it moves it over one pixel and compares it to the image in the next one, and the next one, et cetera, et cetera, et cetera, until it tests this. Furthest position. And then it moves down one pixel, and tests the next level. And so it would test this region. And then moving over, over, over, over. Every pixel until eventually it tests this final corner. And it simply asks the question in each position how much does this probe image. Look like the test image in that region. Now obviously if you do that, with this probe and this test, you see that there is going to be one strong hit right here in the middle. Because the image right here matches very well, to the probe. And so for this example, the cross-correlation coefficient, which assesses the similarity of the probe and the test, is essentially zero at all these positions across the test image except one, right here. It has a very high value right there which represents that position because that's where the match is. And mathematically, we could say that the cross correlation as a function of variable, say, i and j would be equal to the double integral of the test image f, with dummy variables x and y. Times the probe image, h, displaced by the dummy variables, x and y. Meaning that we build up a cross-correlation map, you know, with indices I and j covering this whole map and. For each pixel of this map, you know, some value of i and j. As we raster across the image each pixel, what we're doing is integrating the product of the probe image with variables x and y with the test image in some location centered at i and j. And the first pixel of the probe image is multiplied against the first pixel of the test image. And its product is added to the product of the next pixel times the next pixel. Plus the product of the next pixel times the next pixel, et cetera, et cetera. And that entire sum of those products is the cross-correlation coefficient or the value of the cross-correlation map at that particular position. Now the reason that the sum of products is so effective to asses the similarity of the probe image and the test image. It's because imagine that in, in one pixel in this image, lets say, the probe has a very high positive value, and in the equivalent pixel of the test image it also has a high positive value then their. Their product will be a very large positive number. Then let's imagine we're in a, a pixel over here where the probe image is very negative. And if that superimposes perfectly on a position where the test image is also very negative, two very negative numbers, their product is again a very large positive number. And so every time you have a match, then it adds substantially to the sum. On the other hand if the test image has a negative value and the probe image has a positive value their product is a negative number subtracting away from the cross-correlation coefficient, so it's showing those images didn't really match very well. As you can see the mathematical form of the cross-correlation is very similar. To a convolution. The only difference is that in a convolution one of the functions is, is flipped before being multiplied with the second. In the case of a cross-correlation neither one is flipped. But, never the less, the best way to calculate a cross-correlation map, is again by taking advantage of the convolution theorem. And the best way to calculate the cross correlation map is to calculate the inverse Fourier transform of the Fourier transform of f times the Fourier transform of h. Getting all the signs of the dummy variables right so that it is a cross-correlations. And just to give you a sense of one of the ways that cross-correlation will be use in cryo-em, let me show you this image of hemocyanin particles. Hemocyanin is a very large macromolecular complex that looks like a barrel. So from the top it looks like a circle, and from the side view it looks like a, a barrel. And so, supposing we had these particles frozen in a thin layer of ice. And then we took an EM image it, it would look like this. In fact that's what this image is. Now, if we wanted to search for all the particles in the image computationally, we could take one example image. Of, say, a top view, and another example image of a side view and, then, we can calculate the cross-correlation map of this top view with this whole original image. Here, just the top peaks of that correlation map are shown with white x's showing that it's possible to computationally find the examples of the top views. Furthermore, if we took an example side view. And calculated the cross-correlation of that side view with the original image. It would show us the highest peaks would be here on the side views present. And, so, you can computationally find all of these side views. Now, note. A side view would have to be rotated into all possible orientations, and each orientation could be cross-correlated with the original image to find all the different orientations. But nevertheless, this is the concept of how a cross-correlation is used-. To find particles in a cryo-em image. It has other uses as well, as we'll see later on.
