Bicubic Interpolation - Computerphile

Key Takeaways

Well, we covered bilinear interpolation and nearest neighbor interpolation. Um, which obviously see a lot of use in any kind of imagery sampling. But of course, the one we all use now is by cubic. And I kind of left that one hanging. So, let's talk about how that works. Thinking back to where we were before, we're looking at some pixels side on. And what we're doing really is trying to find some values in between where the pixels are, right? Because if we're resizing an image or we're moving an image, the new locations we've got won't necessarily match up with the previous ones. So if this is our image here, so these are my four actual pixels, right? Nearest neighbor will just sample between these pixels depending on which one's nearest. So it'll sort of go along like this and then it'll go like this, like that. Okay, which is why you get these sort of square pixelated edges and nearest neighbor. That's very fast to do that. Um, and as I said last time, we haven't made up any data doing that. This is our sample. This stretches to here in some ways. So, you know, that's good. Bilinear takes literally a linear interpolation between these points. So, it'll be like this and then this and then this, right? And then maybe this will go off in this direction depending on what the other pixels are. Now, this works fine sometimes, right? But if we've got step changes or weird areas of contrast changes and funny shapes, like maybe this goes up and then down suddenly, this starts to look not very smooth. It's quite a jagged edge. you could find it sort of would look a bit like a sort of pyramid shape and might look a bit ugly. Now, we have to remember that we're talking about between one or two pixels. So, you know, you got to zoom in a long way for this. But on the other hand, if we can improve this, why wouldn't we? What linear interpolation does is take this value here, this value here, and then find any of these intermediate values you want depending on how far along you are. By cubic does the exact same thing, except it does it in a much more smooth way. And it does it by knowing first of all where these two points are and then two extra bits of information which is what the orientation or the gradient at these positions are. So if we know that the gradient let's use my blue pen. How about that? If we know that the gradient is here and the gradient of this one is sort of this direction, we can kind of come in like that and make it a bit smoother. So let's have a little look at how that would work in an image. What we're actually fitting here is a sort of piewise cubic spline. A spline is basically a small section of a curve that goes between two end points, right? This one here will be a different spline to this one, although they will obviously join on in some sense. Splines are used a lot of the time for 3D modeling and things like this. You get uniform basis splines and things um and bezier curves and hermite splines. They have lots of different names. They all do similar things. So what we're fitting here is a third degree polomial equation. Right now, I'll I'll draw out the the equation and then we'll leave it there. Right, the derivation of this math is not absolutely complicated and we'll put a link in the description that you can follow along if if you're that way inclined, but I'll try and talk a bit about more the intuition of how it works. So we've got a value here at x kn and we've got a value here at x1 and we're going between x0 and x1. And the value of y at this position is going to be some polomial that we have to find which is a x cubed + b x 2 + c x + d. There are four unknowns here. X we know because we're going between 0 and one. So it's going to be some value between 0 and one. These four unknowns. Now given the gradients at these locations or the derivatives, we can rearrange this formula in a fairly convoluted way and basically find out what A, B, C, and D are. So what are A, B, C, and D in this in this equation? Um, well, you'll have to look at the formula. They're based on a combination of these positions and the derivatives of these positions. So for example, C is equal to X, right? That's a simple formula, but they get more complicated than that. Again, follow the link in the description if you want to know about these things. Um but the way it works is that once we've rearranged the formula, we can find the position of any point between these two points based on only these two positions and the two tangents. So the question then remains, how do we calculate these two derivatives? Right? How do we calculate the slope at these positions? That's fairly straightforward on an image because we know what this position is. So intuitively, if we're going from here to here and then to there, it's going to be sort of some way between the two, right? So in essence, the derivatives or the gradient at these positions are going to depend on the next two pixels along. So unlike linear interpolation where we only cared about two points, we now care about the next two points outwards so that we can get the gradients right. So if this position moves down here, then this is going to become more like this. And so this is going to come out more. And if this goes up here, this is going to be more like this and it's going to be smoother. So these two positions now have a big impact on the shape of this curve. Once we have this formula, extending it to uh two dimensional images is exactly the same as the extension for bilinear interpolation. So let me have a look. Right, if I take this off, we had for linear interpolation or bilinear interpolation, we had four points here. And remember what we did to find out what some other point was is we interpolated between these to get our intermediate points and then we interpolate again. The problem is just extended. So now we have 16 points all the way along. They're not very evenly spaced. We won't worry about that. I ran out of page. So for this set of 16 points, I've missed one. For this set of 16 points, we're only now interpolating within this small square in the middle. To do it with this one, we'll have to have more points over this end. So we're moving around. What we do is we interpolate this point here by using these. So maybe these have a curve like this and maybe this has a curve like this and this has a curve like this and this has a curve like this. And then we get some points on here and finally we can interpolate this smooth curve to get our final interpolated point. So all of these 16 points are going to have an effect and so it's going to look a lot smoother and it can do more complex shapes than linear interpolation can do. In actual fact, what we can do is we can combine this sort of one dimension followed by another dimension operation into one matrix multiplication. So it can be very easily optimized and performed very very quickly. You can see that derivation on the web as well. I think I leave my Photoshop setting to auto. So is is it always going to pick this though? Um so I can't answer that because I haven't seen the source code for Photoshop, but almost always. So they might be doing something clever. There are times when biocubic isn't strictly better than bilinear, right? It does some things that you wouldn't expect. So for example, if we have a sharp change in direction. So we have a pixel here, a pixel here. So we're looking at the pixels from the side again. And so a pixel here and here and here. Right? Now by linear interpolation, we'll sort of come along here and draw a nice line like this. Right? Which might be a bit jagged but actually is broadly representative of what this image does. By cubic we'll actually overshoot these two signals. So it will come in like this. It'll probably undersshoot here depending where the other one is. Come up and go over these signals and down like this. Now in some ways that's smoother, but actually that is now brighter than these pixels were. Now maybe that's what the image did in that position, but I don't know. We're starting to make up a bit of data there. And also if these are at maximum intensity, we clip this. So we have to go all right. Well, we can't go over 255 in the RG&B, so we'll just sort of crop it there and get rid of that, right? Which is not ideal. We we do it here as well. M. So it isn't always ideal. Now in most images, you aren't using necessarily the full range all of the time. You're not going between N and 255 all the time sharply. So this hardly ever comes up in images and which is why it looks good, but it might. And if you've got a sharp change step change in intensity, you're going to see a little bit of overshoot possibly just beyond your edge, which you won't necessarily want. Right? So if you see if you have black to white or or dark gray to light gray and you see a little bit of a peak, you know what it is, right? That's what by by cubic will do. Remember, we're again we're talking about single pixels zoomed right in. So maybe you know only specific special images that you can't yourself just to test it might might show these problems, but they are there and they are something to bear in mind. It's very difficult for a firewall or something to notice this because these are valid HTTP requests. They're just super slow, right? And um you know, maybe I've just got a really bad internet connection, maybe. Yeah. Um now, this doesn't affect every web server. It mostly affects Apache.