How Convolution Works

Key Takeaways

convolutional neural networks are the workhorse behind a lot of what we call artificial intelligence today and the nugget the computational piece that makes them work is the convolution operation and we're going to step through that right here to perform a convolution you need an image and a kernel an image is a two-dimensional array of numbers a grid with rows and columns so what we're seeing here is a 14 row by 14 column array of numbers most of which are zeros but a few of which are ones in the pattern of an o then we have our kernel which is also a two-dimensional array of numbers we also can think of it as an image and the very first thing we're going to do is reverse it we're going to flip it top to bottom and left to right or you can get the same result by just spinning the whole thing 180 degrees what was the lower right becomes the upper left what was the upper right becomes the lower left and what was in the center stays in the center this kernel also maps numbers to colors so we have a zero mapped to black minus one mapped to red one mapped to white this lets us see it visually but there's numbers underneath it the convolution operation is taking this reverse kernel and moving it row by row and column by column matching it to that patch in the image multiplying all of the elements one at a time by each other and adding up the result that's the convolution when we do this across all the rows and all the columns we get the result of our convolution which we can use for a few interesting things that we'll showcase later let's dig down to the next level of what's going on here look at this position where the reversed kernel is in the first column but the second row from the top and we want to go element by element and multiply each of those pixel values together we can see in the image the only pixel value that's not zero is the lower right it's a one all of those other elements are zero they get multiplied by the corresponding pixel values in the reversed kernel all times 0 equals 0. the only thing that's non-zero is this lower right value in the reversed kernel so we have 1 times 1 and we can see that element by element product in the next panel all zeroes except for a one in the lower right hand corner and then when we add all that up we get a one it's scaled down a little bit so it's represented as gray and the convolution result but that's the result of this particular position now if we move forward a few positions into the second column and the third from the bottom row we can see a little bit more interesting result here going element by element we can look at the non-zero elements in the image our ones those white pixels and we can multiply those by the value in the reversed kernel so the top center value in the reverse kernel is 0.5 times 1 gets us a 0.5 the center value is a 0 times 1 is 0. the value on the right in the center is a 0.5 times a 1 gives us a 0.5 and then the lower right again is a 1 times a 1 gives us 1. so within the product we can see the the results of the multiplications of each of those matched elements then when we add those up we get a 1 plus a 0.5 plus a minus 0.5 which again gives us a one like we saw before looking at yet another position the third column and the fourth row from the top we can see how our reversed kernel now the parts that line up with the bright spots in the image with the non-zero valued elements of the image are all negative and it gives us a negative result so going element by element we have a minus one times one gives us minus one minus point five times one gives minus point five zero times zero minus point five times one gives us a minus point five and then everything else has a zero in either the reverse kernel or the image so it gives us zeros everywhere else so our product then has a minus one a minus point five and a minus point five when we add all that up we get a minus two and then that gets represented over in our convolutional result as a bright red pixel for minus two so you can see how going through each row each column lining up the reversed kernel with the corresponding image patch doing element by element multiplication to get a product and then summing up the result of that product gets the convolution result this taking the product element by element and adding it up is something that happens often enough that has its own name it's called a dot product dot product sounds fancier but anytime you hear it just think oh multiply everything and then add it the result of these simple operations being strung together is pretty striking though by the time we're done we can see how this kernel which has a gradient meaning it starts at -1 on one side and then smoothly transitions to a plus one on the other side pulls out a certain pattern out of our image and it ends up being a kernel that detects changes along a diagonal so you can see where it's brightest where it's bright white here and bright red here so highly positive and highly negative is on the upper and lower side of the roughly diagonal portions of this circle and it's there are other places where it's not zero but that's where it's the strongest so it pulls out these diagonal elements so this in this sense this kernel is a detector of a feature this is what makes convolution useful in convolutional neural networks you can imagine a collection of different kernels and each one pulls out a different aspect of an image for instance you can imagine a different kernel where that gradient lines up with a vertical pattern going smoothly from left to right in that case it pulls out the vertical elements of the image and you can see here that when we run it on a circle that sure enough the parts that are the brightest white and the brightest red are the leading and trailing edges of these roughly vertical parts of the circle so between these two feature detectors we can pull out the right leaning diagonal parts of the circle and the vertical parts of the circle you can imagine other kernels pulling out horizontal parts of the circle and the left leaning diagonal parts of the circle and other types of features as well and it's exactly what convolutional neural networks do except it a convolutional neural network will learn these kernels based on what's most useful in getting it to get the right result here we see an even more striking example of convolution as a feature detection so we have our diagonal gradient kernel we reverse it and we convolve it with this image of an x and as expected it matches the right leaning arm really strongly both on the leading edge where it goes from dark to light and on the trailing edge where it goes from light to dark we see a nice bright white streak along one end and a bright red negative streak along the other edge it doesn't pick up the left leaning arm of the x at all it's completely blind to it so it pulls out one particular feature of this image now you can imagine if we paired this with a left leaning kernel that it would pull out the other arm of the x and that together these two features would do a pretty good job of representing what was going on in this image of an x convolution has been around for a long time has lots of good uses in math it also is really useful in image processing an alternative way to understand it instead of being a feature detector is to see it as a replicator you take your kernel and everywhere the image has any signal it makes little copies of your kernel so you can see this emphasized where our image is just a single pixel a single one in a sea of zeros and as we move our kernel over it what happens is a copy of this kernel gets made and what we're left with is you can imagine taking any kind of kernel copied and pasting it wherever there is a pixel that's not zero in our image and we can see the final result here a copy and paste of the kernel and we can do this with any type of kernel so here's a more irregular kernel and as it goes through the reversed kernel gets convolved with this single pixel that's a one and as it does you can see what happens here it gets flipped top to bottom and left to right this is why we go through the imaginations of standing on our head of taking our original kernel and reversing it before convolving it it really aids in this interpretation so that when we're all done we can say here's our kernel here's our image the convolution is just taking our original kernel and using our image to make copies of it we can make more than one copy if we want you can imagine taking our square box and taking an image with several non-zero pixels and running it over the result and getting what looks like a bunch of copied and pasted versions of our kernels and you can see doing the same thing with our irregular kernel getting a bunch of copied and pasted versions of it whenever you do a convolution you're taking your kernel your base pattern and wherever the image is positive you're making a positive copy of it and wherever your image is negative you're making an inverse a negative copy of it it's worth noting that kernels don't have to be small and they don't have to be simple and they don't have to be pretty you can take any pairs of images and convolve one with the other so in this case we have a kernel that's three by five and the pattern is not anything that's immediately obvious to our eye but the same thing happens when we convolve it with an image in this case a single pixel we see of the original kernel reproduced at that location this irregularly shaped kernel is a great illustration too of why the convolution result is smaller than the original image we can only calculate the dot product where we have elements to compare so that means we can only scoot the kernel as far left as it can go until its left edge lines up with the left edge of the image and we can only scoot it as far right as it can go until its right edge hits the right side of the image so that means the result will be the size of it'll have this the number of columns as the image minus the number of columns of the kernel plus one same with the number of rows so the result will always be smaller there are tricks you can do where you can go back to the original image and pad it you can add a border of zeros or a border of other values that are similar to what's in the rest of the image so that your result will be the same size as the original image for a more detailed discussion of this i recommend visiting the one dimensional convolution tutorial that's linked to in the notes it shows the results of using different types of padding either using zero padding or extending the image out by using the nearest value on the edge and just extending that or reflecting what's in the image into the border to continue it there are pluses and minuses of each in every case you're making a conscious decision to add additional data of some sort to your original image and that doesn't come for free it doesn't come without consequences so the safest way to avoid doing that is to only perform what's called a valid computation a valid convolution so only go and calculate the convolution where the kernel completely overlaps the image but there are lots of times where computationally it's very desirable to have a result the same size as the original image also there are a lot of instances where making an assumption of a border of zero or a border that matches the edge of the image is a pretty mild assumption and you can get away with that just fine but just keep in mind that when you do that you are adding data and make sure you're ready to accept the consequences of that now a lot of the fun with convolution comes when you don't have images that are just isolated pixels but you have images that are complex and have a whole structure to them when you run certain kernels over them different things happen here's an example of a blurring kernel it has this non-zero value in the center but it also has it's tough to see in this image because the values are small but the pixels around it are not quite black they're not quite zero when we convolve that with our original image what it does is it takes and makes copies of this kernel which tends to spread out each individual pixel it takes a little bit of its lightness and distributes it around to his neighbors and when you do that over and over again what you get in the result is a slightly blurred version of the original image so it's pretty subtle to see in this instance with this o but we can use it on an actual natural image here's a slightly larger kernel instead of a three by three pixel it's a five by five pixel and here you can see how this blurred kernel takes some of the value from the center and distributes it to some of its neighboring pixels and then the further away it gets the lower those values get and if you look at this example on a high enough resolution display you can see that the original image is quite sharp but the result of the convolution has been blurred it takes every one of those pixel values is a tiny copy of this kernel which spreads its lightness so that means if you have a single light spot its light will get spread to its neighboring pixels a little bit and the result is a blur you can also use kernels as feature detectors so here we have our diagonal gradient that we can take and apply to a natural image and now in the resulting image you can see the bright white lines and the bright red areas the white shows areas where there's a diagonal gradient going from dark to light see along the top of the pup's head here going from the slightly darker carpet to the lightness of the pup's head and then you can see the red where it goes from the lightness of the fur to the darkness of the eyes from the lightness of the fur to the darkness of the nose along a diagonal so this you can start to see how given a natural image and given a kernel that represents a feature it'll pull out these interesting features which then a neural network can use to infer the shape of the object and from that build a pattern recognizer to be able to pull out the identity of what that is here are a couple of other kernels detecting other features in this image of a pup horizontal and left-leaning diagonals and when you look at the results together you can see how they emphasize different aspects of what's going on and you can start to get a feel for what the algorithm might be paying attention to when you look at the kernels that it uses and how that transforms the image that you feed it this is something we'll be diving more into in course 322 in two-dimensional neural networks there's a link to that below as well here's an example of sharpening so because the values are so close to zero you still can't see well what's going on in that kernel but there is a large positive value in the center and then small negative values surrounding it in this 5 pixel by 5 pixel kernel what that does when you convolve it with the image is that it takes whatever value is at the center and subtracts a little bit of the values that surround it so it does the opposite of the smoothing which takes and spreads the center value around a little bit this emphasizes any difference between that center pixel and the values around it the result is a sharpening filter so you can compare these two images and the image on the right is much sharper in the sense that all of the lines are brighter the lights and the darks have greater differences between them you can see it looks like individual pieces of fur and individual threads of carpet that were not clearly visible in the original so more fun with convolution all of the animations and the illustrations in this video were made using some code that i uh put up in gitlab feel free to pull it down and reuse it you can take any kernel and any image and just run this on your own machine and get the results it's pretty fun to play with now having seen all this there's a few natural follow-up questions like how do i represent this in math how would i represent it in code say in python how would i implement it in a deep neural network in a convolutional neural network and specifically how would i calculate the gradients so that i can implement back propagation for convolutional layers well the answers to all of these questions and more are at course 322 in the end to end machine learning school there's a link below and i hope you'll come check it out there's a few free preview lectures if you want to see what you're getting into hope to see you there