What is a convolution?
Let’s say you have the two following lists:
- a = [1,2,3,4]
- b = [5,6,7,8]
How many ways can you combine them together to create a new list or function? One simple way that comes to mind would be to simply add the numbers term by term. In a similar sense you could also multiply each of the terms.
There is actually another combination just as fundamental as those but a lot less commonly discussed known as a convolution. Unlike the previous examples it is not an operation you can just do to numbers. It’s something new for the context of lists and functions but it shows up in image processing and is a core concept in probability. It is also used in differential equations and multiplying polynomials.
Now let’s say we are rolling a pair of dice and figuring out the chances of seeing various different sums. Each of the two dice have six different possible outcomes which gives us a total of 36 distinct possible pairs. If we look through them all we can count up how many pairs have a given sum and arrange them all.
Now if you arrange them in a grid the ones with the same sums will be on each diagonal which allows for one to easily calculate the probability. But are there any other ways that we could visualize the same question.
Now let’s assume you have 6 dice in one row showcasing the possible amounts from 1–6. Then in the second row you have the possible amounts shown from 6–1. All of the different pairs that add up to 7 lines vertically now. Now if we slide the bottom row all the way to the right so that only the ones are lining up now we have the only pair that adds up to 2. Now if we move the existing bottom row one unit to the right now we have the 2 pairs that add up to 3. This is another method that could be used to find the possible sums.
Now these methods assume that there is an equal chance for the faces to come up. Lets now say I have a special set of dice which is not uniform.
Now in this case if you wanted to see the probability of rolling a two you would multiply the probability of each of the ones on dice. You continue to multiply the corresponding probabilities of the numbers that will create that possible sum and add them up.
In general this process where we are taking two arrays of numbers, flipping the second one around, then lining them up at various different off set values, taking a bunch of pairwise and adding them up is actually one of the fundamental ways of thinking of a convolution.
Just to sum this up a little more exactly, through this process we just generate probabilities for seeing two, three and four on and on up until twelve. We got them by mixing one list of values, A and another list of values, B. Hence we would say the convolution of (ai) and (bi) gives us this new sequence of eleven values each of which look like some sum of pairwise products.
This is what the notation would look like. The star symbol “*” shows” means the convolution of a and b is a new list and the nth element of that list is the sum of all the different pairs of indices(i and j) so that the sum of those indices is equal to n.
Now let’s try to further understand this with an example. Let’s assume n was six.
Now lets see how the notation would look:
If you are still feeling confused don’t worry as we are going to go through another super simple example.
Lets say you want to know what is the convolution of (1,2,3) and (4,5,6). You might label them a1, a2, a3, and b1, b2, b3. Then we repeat the process by flipping around the second one and then starting with it slid all the way over to the left.
The pairs that align are 1 and 4 and multiply thoes to get 4, then slide it one more to the right. We get the pairs that align are 1 and 5 and 2 and 4. We multiply the pairs and add them together to get 13 which is the next entry in our output. Slide things over another time to get the pairs the align are 1 and 6, 5 and 2 and 4 and 3. We multiply each of the numbers in the pairs and add them together to get 28. If we do another slide we get 6 and 2 to line up along with 3 and 5. We multiply each of the numbers in the pairs and add them together to get 27. We do one last slide so that 3 and 6 line up. We multiply them together to get the last number 18.
Another common example would be a moving average. Imagine you have a long list of numbers and you take a smaller list of numbers that all add up to one.
Now lets do this sliding window convolution that we learned earlier about. By doing this we are taking an average of our data inside this little window and by the end we have a smoothed out version of the original data.
Get Brain_Boost’s stories in your inbox
Join Medium for free to get updates from this writer.
You can modify this and use a different list of little numbers and as long as that list adds up to 1 you can still interoperate it as a moving average.
You can still interoperate this as a moving average but here in this example we would be giving more weight to the central value. It also results in a much more smoothed out version of the data.
The same thing can even be seen in image process. In compute science each pixel is a vector of three values. Then to blur a image we could multiply each of these pixels by 1/9.
This gives us an average along each color channel which results in each one to bleed into its neighbors and give that blurred effect. The new blurred image would be the convolution of the original image.
If we modify this slightly we can get a better blurring affect by choosing a different set of values.
Here we have a five by five grid but the change in size is not what makes this a better blurring tool but rather the fact that the center value is far larger than the outer values and this stays true for values that are closer to the center as compared to the edge. These numbers all have been sampled from a normal distribution.
But there is so much more than burring you can do with this idea.
So lets take this grid with some positive values on the left and negative values on the right. In this convolution it is possible to get negative values.
At this point over here the left half of the grid sit entire on top of black pixels which would have a value of zero but the negative values all sit on top of white pixels which would have a value of one hence the result will be very negative.
This negative result is then displayed with the image by coloring negative values red and positive values blue.
Now when have the grid o a spot where the color is entirely the same then the sum of the values in our little grid becomes zero. This process then detects variation in the pixel values creating a vertical edge detector. Similarly if we rotated the grid so varies as you from the top to the bottom now we would have horizontal edge detector. This grid is called a kernel and there so many other affects that you can get such as sharpening.
Lets quickly touch up on length. For things such as the moving average you might only want to think about the terms when both of widows fully align with each other or in the image processing example you may want the final image to be the same size. Convolutions unless the array has the length of one always produces a larger result then the amount you started with. In certain situations you may reduce that to only the true overlaps.
Its important to note that in the sense of computer science the idea of flipping a kernel may not make much sense and feel weird but that's what is inherited from the pure math context.
Moving on from image processing convolution can also be seen in multiplying polynomials. We can use the grid method from earlier but just replace it with the values of the polynomial.
Then when you add up along the diagonal. Convolution corresponds to the collecting all like terms.
This means that if you take two functions and multiply them together it is the same as if you first extracted the coefficients(assuming they are polynomials) and took the convolution it would be the same!
