Correlation and Convolution

Let’s talk now about how we would actually apply the kernel to an image. What is the algorithm that we would need to apply? And this is what it looks like; it is a summation over the input window which is designated by the symbol W. And inside the summation we have the input image I and the kernel K. The indices I and J both range over values from -H to +H. What we have written here mathematically is the definition of a two dimensional correlation.

There is a related operation called convolution, and 2D convolution is represented mathematically this way. It is very similar to the correlation we just looked at; in fact, the only differences are these negative signs here. For correlation they were positive signs. Now convolution is the same as correlation if the kernel is symmetric. The Gaussian kernel we just looked at, for example, is indeed symmetric. An advantage of convolution is that it can be written in operator form. So what this says is the output image is equal to the kernel convolved with the input image I. So the symbol of a cross inside a circle represents the operation of convolution.

What are some of the properties of convolution? Well for a start it is commutative, so A convolved with B is the same as B convolved with A. It is also associative and this is a property that we will use in some upcoming slides. We say it is distributive. And it is also linear. So these are important mathematical properties of convolution.

Now, what are the advantages of associativity? Well consider the case where I convolve an image with a Gaussian and then I convolve with a Gaussian again. So if you like, I can think of this as adding an image, I smooth it by applying a Gaussian to it and then I smooth it again. This is the same as convolving the image with a kernel which is the Gaussian convolved with itself.

And convolving a Gaussian with another Gaussian results in a Gaussian. And the standard deviation of the result Gaussian is a function of a standard deviation of the two Gaussians that are multiplying, as shown over here on the left.

So in order to convolve an image with a very large Gaussian which would require a very big kernel, it is actually equivalent to convolving the image with a small Gaussian multiple times consecutively. And there may be some computational advantages of doing that.