I wanted to talk a little bit about
About image filtering. We had a video on image filtering a while ago on
Gaussian blurs and mean blurs and this kind of thing
But remember we talked about convolutions and convolutions are actually used in a lot of places. So Sobel operator for edge detection
But also in deep networks, so deep networks have convolutions in as well
So a huge problem with something like a Gaussian blur is let's suppose we want to do a really big one
Right, we want to do a huge blur to really blow out an image. So you're talking about increasing the size of the kernel
That's right
the radius of the Gaussian and the size of the window that we're sliding across is
Going to get much much bigger suppose you want to do is that even as even a relatively small standard deviation?
You're going to have a very very large window, but you're sliding across during your convolution. That's going to get slow really really quickly
Let's remind ourselves very briefly. What a convolution is so let's suppose you have an image which is agreed
I've always had bad luck drawing grids in computer file videos. They never come out parallel. I've seen what I mean
We have something called a kernel right which is our filter that we're passing over this image
So let's say we've got a very simple one which is our sobel filter or Gaussian filter, which is a three by three
Now what we do on our image has put a bounds on there we go
If we place this kernel over here over the top three and we do a sum product
So we do the multiple of this one and this one
plus this one and this one plus this one times this one plus this one times this one plus this one times this one and
So on and now for a three by three operator that's going to be pretty quick right you can write this in C or something
like that
It's gonna go really really quickly and that's broadly speaking what a deep network does just doesn't lots and lots of times
The probabilities that suppose we want to do like a big Gaussian blur or really large window
This is gonna get slow really really quickly because to every position in this image
We're doing nine
Products and then adding them all up if this window is ten by ten or twenty by twenty or a hundred by a hundred
the amount of operations per pixel is going to get
really quite large and
we're talking minutes to hours to just pass over this image and yet the thing is if you go into Photoshop or you go into
An image processing package and you perform a really really large blur. It doesn't take minutes or hours, right?
Because that's not acceptable. It goes very very quickly. And so what they're doing really is cheating, right?
Kind of what we're gonna do is we turn this kernel into an identical one in two passes
Where we have a 1 by 3 and then a 3 by 1
like that and what we're saying is if we convolve our image first by this one and then by this one
We get the exact same product as we would have got if we just did it with the 3 by 3
And we've only used 6 values and that's going to get better and better valar and larger your kernel kernel goes
Okay, let's hang a minute. Right? The first thing to note is we can't just have any
you know n by n filter and
Decompose it into 2 1 by n filters and it definitely work right we have to make sure that the process of doing horizontal
Followed by vertical or vice versa is going to perform the exact same operation as the original
Combined filter and really this is a simple matrix multiplication. So you've got a situation where you want this matrix here
However, big it is to be this one times by this one
Which means that if you convolve any image with these two, you're actually doing it with this right is easier
Isn't it on a short of it now that isn't true of every filter? It's true of a Sobel
You can split Sobel up
And it's true of gaussians and it's true of mean box blurs and so on but it's not true of any kernel you wanted to
Use right which is kind of relevant to deep learning. But but that's I'll mention that at the end. So, how does this work?
Well, let's imagine that we're convolving a pixel with this horizontal blur, right?
So we've got our image which is going to be something like this. So you can also converting fast Fourier transform. So that's another time
Right actually that is another time because because that's really fast
That is that what it's called fast?
No
All right. So let's imagine we're looking at this pixel here now
What we would normally do is we'd sort of put our our three by three kernel over here and we do this sum product
Right, but what we're going to do first is the horizontal pass
So actually we're going to do it over this one
This pixel here is going to include this one and it's going to include this one like sometimes in graphics they call this together in
this one and this one and
This one and this one but so this is going to be calculated using these three pixels
This one is going to be calculated using these three pixels
This one's going to be calculated using these three pixels. And that means that when we finally do our vertical pass here
We're actually bringing this pixel in here like this and what you can see we've brought information from these four pixels
Which we haven't our boys done
We haven't actually looked at those pixels with respect to here, but actually we've got that information and we've saved a bit of time
right
if you've got an n-by-n kernel and the number of alterations you're going to need to do for square kernel is going to be N
Squared it's going to be 2n for a vertical followed by a horizontal pass
I've coded this up and let's see how much faster it is. We need a computer. Where did I put it? I
Started writing some Python code that I was gonna I'm going to release the code, right?
So I tried to make it is, you know simple as possible. So there were libraries in Python to do this like OpenCV, right?
And they'll probably do it faster than my code. I wasn't really interested in how fast it was apart from a comparison, right and
I also wanted people to be able to see how it works
So what I've done is I've implemented it in Python
But it was too slow because python is not really suitable for you know, low-level pixel manipulations
So what I did was I then used syphon to compile this python into C. And that's much much faster
So if you want to look at the code, we'll put a link in the description. So
Essentially, this is very very simple. We load an image up. We turn it into a
An array and then we pass it off to siphon which does a convolution with any kernel that we provide and then returns a response
And at the moment what it's doing is it's doing a 2d Gaussian blur over quite a large image
So I've got this image, but I took this morning of a section of my Christmas tree
So, you know that's looks like many other people's Christmas trees. It's a ball ball on it too many bubbles actually and
At the moment. It's relatively sharp, right? But let's imagine we want to blur this image
I'm going to blur it with a two dimensional Gaussian of size 10 - oh that's a standard deviation of 10
The radius is going to be somewhere around
60 pixels something like that like to cover for the entire range of the Gaussian
So that's the one that now so I've already compiled the Python into C and the C into anyway
So this is quite a large image. I think it's something like
16 megapixels or 20 megapixels or somewhere? I don't know. I'm running on one of our servers nobody really matters
It's going to take quite a long time because for every pixel in our image
We're looking at a 60 by 60 window, right? This is the long 2d version
Right, which is why it's taking so long. In fact, we might want to go and get a coffee
Thank you
It's not dependent on what those pixels eyes just it doesn't matter about what the pixels are
The operations per pixel are the same. Obviously it matters a little bit what the size of image is it's still going
I mean we could work out roughly how many operations this has to do, but it's a lot
I mean
It's hard to know exactly how many it does because there are also bounds checks and things like this not all the time
But some of the times so we could probably you say at least this money. Yeah, I still going
It's still a big
It's muscle but yes
It is if our server yeah, we're - cause it's not motivated though GPUs would do this really really quickly
But you still shouldn't be doing 2d convolutions like this because it's incredibly slow. So it's
four nine one two pixels by
3 2 6 4 3 2 6 4
Which is 16 megapixels and for each megapixel. So for each pixel it's going to do about
60 squared operations so times
60 times 60
That's quite a lot of operations actually see 37 billion
And that's about the bounce checking and we have a business it has to do. Oh, it's finished it took 189 seconds
Is it looking person? Well, let's see
It won't know it will be I mean, can you imagine you had to wait this long to do anything in Photoshop?
It would just be really bad news. So let's have a quick look at them. Here's my output image and you can see
We've managed to obtain a slight blur like was the standard deviation of 10 on the 16 megapixel image
It's not actually that much you're going to need to do a standard deviation of into this sort of dozens before you start to know
Some real serious blur the complexity of this problem is N squared
even increasing the standard deviation by a few more will massively increase the amount of time it takes so
Let's see if we can improve things
So I'm gonna I'm going to remove that code and I'm going to instead run it in two passes
So instead of going from the image to the output I go from the original image
I do an N by 1 convolution into an intermediate image and then I convolve that with the vertical version into the final image
So there's two
Convolutions, but it won't take double the time. So let's run it still pretty big image
So the original one took 189 seconds
Eight seconds pretty good
But eight seconds is now into the point where you could if as long as you had some progress bar or something on app people
I'm gonna get too annoyed about it, right?
So let's let's increase the standard deviation of this. Let's do it a little bit more of an epic blur
so forty five in my code a
kernel of standard deviation 45 requires a window size or kernel size of
271 so for every pixel it would be doing 271 squared operations
New so let's just do a single
271 by one and then a one by 271. All right
So this one that see how long it takes this will take longer than eight seconds because it's much bigger than ten
But not a huge amount longer, right? It goes up a little bit within rather than squaring. I'm gonna guess. All right
So so quiz, I think
21 seconds
Okay, I have no, you know, I'm basing this on nothing but random guesswork path seems plausible
Yeah, how long's it been now
Course you don't know when is going to appeal my screen I could go
That took 36 seconds, so not too bad, right
That's a very large if you look at the actual blur itself, I mean you can't see anything anymore
You know, it just looks like my camera work
I'm thinking today to my yeah
for my sins eggnog latte
just once per year otherwise
Just a special treat near the end of the year