Bicubic Interpolation - Computerphile
ฝัง
- เผยแพร่เมื่อ 24 ส.ค. 2024
- Scaling images is usually smoother using bicubic interpolation. Dr Mike Pound explains why.
More on bicubic: bit.ly/Computer...
Wikipedia bicubic article: bit.ly/computer...
Resizing Images (Bilinear & Nearest Neighbour): • Resizing Images - Comp...
Slow Loris Attack: • Slow Loris Attack - Co...
Quantum Computing: • Quantum Computing 'Mag...
Babbage's Analytical Engine: • Babbage's Analytical E...
Sorting Secret: • Sorting Secret - Compu...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscom...
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
We need a video on the "CSI: Crime Scene Investigation" interpolation.
Enhance !
Pan! Uncrop!
look behind the camera
Can you get a face from that reflection in the coffee mug?
There is a project on GitHub (alexjc/neural-enhance), which uses neural network to 'enhance' images; it's based on the joke itself.
i like this dude
he's dank
I like the explanations etc. but I don't like his voice :/ I know that it is something completely personal and that is not going to chance soon, but I don't like it
Very educated Frodo Baggins
thanks for ex-splining that.
Duncan Ellis Come on, you can do bezier than that
Duncan Ellis I should've node better
You're really ahead of the curve on these puns.
You are all setting a bad ex-sample.
Mind if I join you, hermit-e-s?
Dr Mike Pound is probably the best communicator in the channel. Always happy to see a new video featuring him!
I really dig this guy. He's got humour and a clear way of explaining stuff. more please! :)
OMG, i just love the way how Dr Mike Pound sounds.
Computerphile, please, make more videos with Dr.Mike Pound.
HE IS AWESOME.
I really like the videos with Dr Mike Pound. They are the best
I agree.
i didnt know his name. but i agree
The name of the interviewee is always in the description text of the video.
He's... sound as a Pound! ^_^
I do like Dr. Pound, but professor Brailsford is better.
Ahh, I love it when Spiderman does computer science :-D
lol
Nothing like a cup of Dr. Mike to start the morning off right... great vid as always!
What is also interesting with respect to this technique is that CNN-based superresolution models perfrom *significantly* better if the training input has been downscaled using bicubic interpolation rather than cruder methods.
I like your videos with Mike. Make some more videos with Mike, please. Thanks!
I could watch Dr. Mike explain literally anything and find it engaging.
7:17 If you operate in high-dynamic range formats like EXR, which has floating-point pixel components, you have room to both overshoot and undershoot. Then you can renormalize the image using a filmic response curve or something without clipping.
Even then you can have overshoot past black into *negative* brightness values, which is still a problem.
Computerphile are single-handedly keeping the tractor-feed dot-matrix printer paper manufacturers in business :P
I'd like to say, that relatively new effect in these videos, where the piece of paper is distorted to look like a top down view, is cool.
Yes, worth talking about Lanczos. Also worth talking about the general principle of image/signal reconstruction using the sinc function, because all resampling techniques are basically shortcuts to avoid the high computational expense of sinc.
Today at work (I'm a software engineer), a co-worker was talking to another one of my co-workers about animating an element within the software we are working on. I know that some forms of animation use linear interpolation, so I got on Wikipedia and read a little bit about it to brush up on the subject (I usually study things that just come to mind :P). Anyways, as I was studying, I noticed Bi-Cubic Interpolation, something I had never heard of, as I haven't taken a high enough math class to really get into that. It was so damn strange to just get on TH-cam and see that you made a video about something that discreet. Freaks me out hahahaha.
What a great teacher. Pint deserved for this dude.
"auto" most likely changes the resizing algorithm being used when sizing up vs sizing down, or when resizing is minimal (1.1 times) vs when it is a large change (5 times or so).
I use Hermite interpolation (x * x * (3 - 2x)) in my games all the time. It eases in and out evenly near 0 and 1 cheaply, and makes blending look so much better in most circumstances
2:15 Originally, a “spline” was an actual rod made of some flexible material, that a draughtsperson would use to draw curves on paper with a pencil. Then the term was carried over to mathematical operations for doing the same sort of thing.
Very well explained, quite enjoyed it!!!
I'm impressed of how much this man knows. Every time i'm googling some complex stuff explanation, i see his tutorials in the results. :D
one example where interpolation (of any kind) is terrible is resizing barcodes. Those should be resized using nearest-neighbor (sometimes called "none" when selecting interpolation method).
Thank you for this. Now some of the other articles ive read actually make sense!
I didn't think I'd be happy to come across a bicubic interpolation video today, but here we are.
These videos have made digital photography so much more interesting than my five years at the Art Academy, which basically made me turn into a film snob lol
Do a video on the Lanczos filter
Yes! More on video/picture scaling algorithms!
you would think that lazy people would only want to downscale
swifterik
Not exactly, but I'm too lazy to explain anything to you.
Then we'll finally know how to pronounce it :D
+swifterik, I google stuff like that all the time! :D
Scaling pixel art and imagens based on 8-bit aesthetics are good examples of situations where nearest neighbor works better than bilinear or bicubic interpolation. The final image should keep the hard edges.
I can see all your pictures covered in Moiré.
Eventually, this series of interpolation videos will come a full circle back to convolutional neural networks when it reaches the Waifu2x upscaling software.
The overshoot of the cubic interpolation is mostly due to the fact that the derivative at a point is taken as the arithmetic mean of the two slopes that unite with the neighboring points:
derivative_at_point = ( prev_slope + next_slope ) / 2
This overshoot can be mitigated by averaging the *angles* of those slopes instead of the slopes themselves:
derivative_at_point = TAN ( ( ATAN (prev_slope) + ATAN (next_slope) ) / 2 )
No wonder AE to PR upscaling can take so long when taking a clip from 1080 to 4K. Thank you sir !
Every single frame has to be converted into a wave and the quantized to get a pixel image again.
So, I know this is not Numberphile, but there are distinctly different things called "cubic interpolation", and I think it's worth mentioning because in this video Mike is talking generally about cubic spline interpolation where you have a different polynomial between each pair of points. Normally this is done in image editing programs with Hermite splines that join end to end to make a C1 continuously differentiable function. But you can also make piecewise cubic functions that are not continuously differentiable (non-osculatory), which is what is shown on the first page linked to in the description. This is not normally done on images, and I personally wouldn't recommend anyone implementing this in 2D for photos. Cubic Hermite spline interpolation is also flexible, and you can adjust for more smoothness or more overshoot. I mention this because it was asked below what the difference is between Photoshop's bicubic (smoother) and bicubic (sharper), and the answer is the tension parameter of the splines which determines how sharp or gradual your slope approximations are at the sample (control) points.
Photoshop has "Bicubic sharper" and "Bicubic smoother" I don't know what the difference is, but I do know that the "auto" setting uses smoother when upsampling, and sharper when downsampling. In both cases it uses some sort of bicubic algorithm. It also has a plain "Bicubic" setting. Adobe says this is the "most precise", but the slowest.
Thanks for this video, it explained a lot of problems I had with interpolation in the past.
Mike Pound videos, instant like
Yep, same!
Is he "Like Pound" then?
that's such a cool name
In Photoshop you can explicitly tell it which algorithm to apply when resizing up or down, so in auto mode the code would use the resizing up/down to determine which algorithms is best for scaling an image up/down.
I used to use an old paint program, I found that the option to resample image instead of resizing gave a smoother less jagged edge image, looked smooth as silk. less newspaper dot effect or wavy lines in images made up of visible dots or grain like scans of old photos.
After watching this video, I now have an explanation for some of the artifacts that appear when I'm resizing pixel-art. Thanks for helping me to better understand the world
Knows a lot for a guy with only 10 books lol
Plasmaboo or these are only books he didn't have time to read yet.
I think he uses bicubic interpolation of those books contents, then uses some permutation, combinatory and use case statistics to refine his response further down .
Those are the books that he is reading that day.
I have that C++ book. Not as useful as the actual language reference.
“WPF In C# 2010” ... I sincerely hope that is not being used much any more ...
Please make a playlist for Dr Mike Pound's Computerphile videos, they're great.
IM PINCHING AND ZOOMING
I would differ on his statement that nearest neighbor(and only nearest neighbor) doesn't create information. All three types(nearest neighbor, bilinear, bicubic) guess at what the middle values are. It's just that nearest neighbor is a very simplistic guess. So they all create data without truly discovering new information.
What about sinc- and Lanczos-Interpolation? As far as I know, the latter is used to reduce the ringing artefacts.
maybe also talk about xBR, HQ and Sparse Coding methods for upscaling too?
also neural network real time scalers, NNDI3 and other very interesting things about video rendering of today
oh boy I could talk about ANNets all day.
When people talk of sinc interpolation w.r.t. images, they usually mean a Lanczos type windowed sinc interpolation. It is very smooth, which works well for some images, but the tradeoffs are the much large kernel size (thus slower computation) and also the fact that optimally smooth is not always perceptually the best result. A bit of overshoot gives increased acutance, which can make the image look "sharper" or crisper. This is often desirable, especially when downsizing. Also, FWIW, you can do bicubic Hermite spline interpolation without ringing, or with lots of ringing, to taste, depending on how you calculate your slopes. It's fully adjustable via the "tension" parameter of cardinal splines.
@@shiphorns how did you learn all this? I'd love to dive
he's a really great educator
The best explanation I've ever seen.
For images, I've found that xBRZ scaling looks better and preserves the edges making the result sharper. This is better when you want to scale an image up for print or if you want to vectorize it after scaling. Or if you just wish to increase the resolution without blurring the edges.
In addition to the ones dealt with so far, GIMP has a resize mode called "Sinc(Lanczos3)." Any plans for explaining that one?
It's a signal-processing type approach. One way of thinking about it, might be like this: whereas cubic interpolation fits a third-degree polynomial curve by using the 4 nearest pixels, Lanczos interpolation is more like fitting a Fourier series to a much larger area (ideally infinite, but in practice not). That's not what actually happens (it's actually using a "Lanczos kernel", which has an effect similar to attaching a Sinc-windowed Sinc wavelet (yes, two sincs) to each source pixel, and then summing up all the wavelets at each destination point), but at least to me it's simpler to think of it that way. So it's even smoother than bicubic, but may very well cause overshoot and sharp-edge artifacts worse than bicubic.
@ I appreciate you taking the time to explain this to me. Unfortunately, a lot of those words carry no meaning for me with my current knowledge, and so I'd presumably have to do a lot of additional reading in order to fully understand your explanation. When asking about an explanation for the mode, I was hoping for more of a visual explanation in the style of these videos since I find those a lot easier to, if not necessarily *understand* what's going on, at least quickly get a sense of what's going on.
@@AlexanderKrivacsSchrder Yeah, I was trying to say a couple of things: 1) A video explaining the mathematics behind Lanczos interpolation in a simple way does not seem very likely to me, and 2) if you don't care about the mathematics, and don't care about the mathematical difference between a polynomial curve and a Fourier curve, then you probably don't even need such a video. It works just like a bicubic curve, it just uses many more points at a time, and tries to fit a smooth curve over them using a more complicated formula based on sums of sine curves. Beyond that, you can think of them as pretty much the same. As mentioned, both methods even handle sharp edges somewhat poorly. But if you are interested in some mathematics, like the sums-of-sine-curve aspect, then maybe check out a video or two on wavelets. Alternatively, there's a Mike Pound video on JPEG DCT. You can watch it, then imagine that to scale something, the source image is first converted with such a DCT (Discrete Cosine Transform). Sine/cosine curves are smooth, after all. Then, once you have the DCT matrix, you now consider the cosine curves to be continuous, so that they can be sampled at the in-between points when you create the scaled image. That should give a reasonable idea of the principle, I think.
Does it make a difference what order you interpolate in: Horizontal then vertical, rather than vertical then horizontal?
now this needs to be appended with explaining bicubic smooth and bicubic sharp
Such an awesome video. Exactly enough theory, exactly enough drawing and exactly enough maths :D
I just realized that 'reticulating splines' basically means that Sim City is busy determining the splines between each tile to form natural hills and so on.
My respect for the engineers of Photoshop has increased 1000 times
I'm always amazed when I see people draw X's by drawing two curves butted against one another (as opposed to drawing two intersecting lines). To each his own.
Thomas Eding quite common when writing mathematical formulae: it's to differentiate the cross product × from the algebraic variable x (which often appears in this curved style in italics)
Interesting. Thanks for the replies.
It's also pretty much how you write a cursive x, without taking your pen off the page. It's how I was taught it in primary school (in Australia).
I love that he’s using dot matrix printer paper
keep up the awesome work. this channel and vids are a gem!
Incredible! An entire video on the discussion of bicubic vs linear interpolation and NOT A SINGLE EXAMPLE of how the effects look like in a picture. Besides, the few slides being shown which should illustrate a point disappear faster than you can see them. Even faster than you can press the pause button. Does airtime on youtube cost money??
Can you do a video about reticulating splines?
Very nicely well-explained. Thank you!
I feel this should be followed up by a Numberphile video when the professor does not want to get into the math of explaining it.
Trusting the "auto" preset isn't always the best thing. Some versions of photoshop made a "sharper" version of bicubic the default, which gave horible ringing halos. They have probably improved the defaults, but in that version (I believe it was 8.0) the sharper had absolutely no application. If you were to clip the range then you wouldn't actually observe the overshoots, and have no problem. They do show up often on screenshots or textual captions or dark trees against light sky.
Awesome Video on Image processing, hope we See more in the Future :)
WOW. I need to know this equation. You just told me it...... THANK YOU!
Binge watching this
Explained very well. Thanks!
[5:50] - Why is there an interpolation of Spatial coordinates? Isn't it supposed to be an interpolation of intensity values
Very interesting video, thanks ! Can we get a video on other scaling algorithms ? (eg the ones that rely on fractals)
Oooh, somebody got a fancy new high framerate camera.
Theoretically, should scaling an image down using bicubic interpolation ALWAYS result in a sharper image? I have been told the answer is yes.
Resizing something from 2000 pixels wide to 1000 pixels wide, this obviously makes sense to me, but lets say I have a 2001 pixel wide image, and shrink it to 2000 pixels wide. How is that possible without losing quality/sharpness?
Great explanation. Super clear! Cheers!
With the number of people taking screenshots of text, then pasting it in, and saving it as a jpeg, I'm surprised that you didn't cover this situation.
Like, when the text of something has become so ridiculously blurry and spread out, that it starts to have sharp edges tens of pixels away...
Compounding error. :P
I need some help. Whats the best way to scale down a raster image? I have some images I want to send to print but I'm concerned it may be too pixelated. Is there a better, sharper way than just using the standard scale function in gimp?
did you reticulate the splines...
But how do you reduce an image size? How you decide what is NOT important and can be neglected?
I believe Photoshop always uses bicubic resizing algorithm with the Auto setting. The Auto just picks Bicubic Sharper when shrinking the image size and Bicubic Smoother when enlarging.
Yup exactly
Paper from a line printer, - that takes me back :-)
that's weird why wouldn't they just say the gradient at the max and min (256 and 0) are 0 like they teach everyone in calc one? maybe it takes too much computing power to override the linear estimate of the gradient.
Now i'm really curious what it would look like if you went way overboard with this and started estimating inflection points ect and a bunch of other stuff like that.
legend
Wish I watched this before doing my quiz a few months ago on cubic spline interpolation... :(
Well, what about Bresenham?
Aloha . . thank you!
@3:43 surely d = x_0 and not c... c would be the derivative at x_0.
7:42 I've noticed that some optimized images look as though they've been filtered with an unsharp mask (or something of the sort) on the scale of a pixel or two. Could this unintentional contrast be a paradoxical byproduct of the "overshooting" and "undershooting" which can occur with bicubic interpolation?
I'm aware you'd get diminishing returns but couldn't you do a bi-(nth degree polynomial)-ic interpolation for any odd n using progressively higher derivatives, capped at a point so you don't use too much computational resources?
Site on bicubic is great ! Tnx :)
awesome!
thanks
Shouldn't that visualization at 5:52 be 3-dimensional? Otherwise it seems kinda confusing to me.
I'm wondering if there are interpolation techniques that will vary throughout the image. For example, most of the image might be best suited for bi-cubic interpolation but portions might be better for bi-linear interpolation.
i was wondering that aswell
You can always use more calculation-effort and try to predict better. For example: You could set some threshhold and look further. If the values are within the threshold you would use more points to define the gradient -> Essentially weighting the curve to respect larger areas more.
Or more visual: Use the example at 2:00. The 4th point is on the same level as 2 and 3. This meets your threshold and your gradient would be more horizontally - essentially having the resulting curve be steeper and farther out on the right side. This probably creates more problems with "overshooting", thugh you can try to counteract this, because you know that you were within the threshold and act accordingly.
There are hybrid algorithms that are more sophisticated and do things like treating hard edges differently from gradual gradients, but I've never seen one that includes bilinear in the mix. Bilinear is most often a comprise that's made for quality vs processing time (like for realtime interpolation when bicubic is too costly for the hardware to do). For typical use cases on photos and video, bilinear is rarely the most appealing option visually.
Is it possible to use BiCubic as default, and use BiLinear only at those sharp step changes??
half way from X1 and X2 it will have a greater value than either one.
Wouldnt this produce bright spots ?
Is there a way to do this while keeping sharp edges sharp? Imagine you have an area of black meeting an area of white. Is there a way to scale this with smooth edges without introducing intermediate color? I don't think this is exactly nearest neighber. The best I can think of, and it sounds complicated, is vectorizing the image (somehow), scaling it, and then re-rasterizing it again. I'd imagine something that did this would take some sort of threshold. Colors closer together than the threshold would be scaled together using something like bicubic, but further apart would be considered essentially seperate images sharing a (possibly curved) seam.
There are other algorithms... maybe you want to look at algorithms intended to upscale pixel art (maybe see Wikipedia article "Pixel art scaling algorithms" which describes several). Understand though that whatever the algorithm you create pixels that aren't in the source data, the result is never going to be "perfect".
I think it should work if you create two images, one by nearest neighbor, the other by bicubic, then combine them, where you weigh each pixel by the output of an edge detector.
are there any systems designed to work with high contrast edges between regions of limited variability. the most obvious example being text.
I am thinking first detect lines between regions, create a function to define the line including identification of sharp corners. scale up the region boundary lines so they remain crisp then scale up each region without considering any information from other regions.
How about bi-quadratic interpolation? It is a better way to do image scaling?
Subtitles was cut off at starting 0:35. Please fix that.
this guy rocks!
Is there a technique to tell how inaccurate the algorithms are and compare them? For example with bilinear and bicubic magnify by 2.3 and then shrink with the algorithm again to get the same original image size. Are there standard ways to give a value showing which one on the "round trips" is closer to the original and by how much with a quantitative analysis?
Yes. Do the process you describe, and then diff the result of the round-trip interpolated version with the original, pixel by pixel. The difference should be small if you enlarge then shrink, but it will obviously be considerable if you do it the other way round. In Photoshop, you can do this difference by putting the two images in separate layers and setting the top one to blend type "difference" (which is the absolute value of their subtraction). Because the resulting differences are small, you'll need to either merge the layers and normalize (auto levels), or use a level adjustment layer on top of them to see it clearly.
Can you tell me what is Cardinal Interpolation please? Would it be possible to make a video on it?
What he drew on the piece of paper makes no sense to me. What sort of image is this? Why no grid for the pixels or something? What's it supposed to even represent?
excuse me , sir , I understand how I can use Bicubic Interpolation to enlarge our image through your video , but I can't understand how Bicubic Interpolation work in shrinking the image,can you please explain that?