Bicubic Interpolation - Computerphile
Вставка
- Опубліковано 22 лис 2016
- Scaling images is usually smoother using bicubic interpolation. Dr Mike Pound explains why.
More on bicubic: bit.ly/Computerphile_bicubic1
Wikipedia bicubic article: bit.ly/computerphile_bicubic_wiki
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/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
![ПОЛНАЯ ИСТОРИЯ ЭКЗОРЦИЗМА [Топ Сикрет]](http://i.ytimg.com/vi/qBySr6Bt0B8/mqdefault.jpg)
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?
I really dig this guy. He's got humour and a clear way of explaining stuff. more please! :)
Dr Mike Pound is probably the best communicator in the channel. Always happy to see a new video featuring him!
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.
Nothing like a cup of Dr. Mike to start the morning off right... great vid as always!
I could watch Dr. Mike explain literally anything and find it engaging.
Ahh, I love it when Spiderman does computer science :-D
lol
I like your videos with Mike. Make some more videos with Mike, please. Thanks!
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.
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
What a great teacher. Pint deserved for this dude.
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.
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
Thanks for this video, it explained a lot of problems I had with interpolation in the past.
"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).
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.
Please make a playlist for Dr Mike Pound's Computerphile videos, they're great.
Very well explained, quite enjoyed it!!!
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.
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.
keep up the awesome work. this channel and vids are a gem!
Thank you for this. Now some of the other articles ive read actually make sense!
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 UA-cam and see that you made a video about something that discreet. Freaks me out hahahaha.
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).
Such an awesome video. Exactly enough theory, exactly enough drawing and exactly enough maths :D
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.
The best explanation I've ever seen.
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
Computerphile are single-handedly keeping the tractor-feed dot-matrix printer paper manufacturers in business :P
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.
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.
Very nicely well-explained. Thank you!
Great explanation. Super clear! Cheers!
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.
Awesome Video on Image processing, hope we See more in the Future :)
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.
Very interesting video, thanks ! Can we get a video on other scaling algorithms ? (eg the ones that rely on fractals)
I didn't think I'd be happy to come across a bicubic interpolation video today, but here we are.
Explained very well. Thanks!
Mike Pound videos, instant like
Yep, same!
Is he "Like Pound" then?
that's such a cool name
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?
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
Can you do a video about reticulating splines?
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.
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 )
WOW. I need to know this equation. You just told me it...... THANK YOU!
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.
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.
he's a really great educator
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?
Does it make a difference what order you interpolate in: Horizontal then vertical, rather than vertical then horizontal?
Is it possible to create a program that mixes the methods on a case to case basis? I think that would be interesting to see.
Site on bicubic is great ! Tnx :)
thanks, was very helpful , I have data in form of (time stamp), these that collected by RFID sensors carried by persons walking through the town , now , i want to connect the routes which the people take using the time stamp i have . but i found some missed reading (some RFID tags did not work). How i can complete these missed reading ? which method or algorithm should i use? any suggestion
Can you tell me what is Cardinal Interpolation please? Would it be possible to make a video on it?
thanks.
Quick question - why do you use these old 80s printers pages as drafts ?
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.
@@airraidsiren how did you learn all this? I'd love to dive
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 ...
Hi sir, I want to ask you about bicubic convolution interpolation in image to addopt on pixel estimation on wide missing pixels. Is it possible to use 8x8 neighbour pixels to perform bicubic convolution interpolation? How about the kernel and the interpolation formula?
now this needs to be appended with explaining bicubic smooth and bicubic sharp
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.
This probably a very stupid question but does this make any sense used in a linear stream like music? Sampledata is interpolated in the DAC, ADC?
LIKED! ok time to watch the video now :D
Is it possible to use BiCubic as default, and use BiLinear only at those sharp step changes??
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.
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.
Subtitles was cut off at starting 0:35. Please fix that.
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.
Wish I watched this before doing my quiz a few months ago on cubic spline interpolation... :(
How about bi-quadratic interpolation? It is a better way to do image scaling?
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.
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?
awesome!
this guy rocks!
I'm missing something. This is strictly about interpolation, but a lot of graphics are curves, the shapes of things (i.e. vectors instead of pixels). The buildings in city builders come out of Autocad like constructions that are infinitely scalable, and can be viewed in perspective from any point of view. These systems can loop the loop, so to speak. My distant memory of cubic equations is that they cannot deal with the vertical. Is there some way of getting there from here?
What you're missing is that you're most likely thinking about a cubic function of the real line, i.e. a function of y in terms of x, where it's single-valued and continuous. Such a function can't have a vertical line, that would be a discontinuity with a single x mapping to infinitely many y values. But a cubic spline is not a function of the x-axis, it's typically parameterized between 2 points (called knots) and written as a function of t where t canonically has the domain [0,1] which represents the fraction of the way from one point to the next. So at t=0 you're right on the starting point, and t=1 you're on the end point of the spline path (which is usually the start of the next, so t=0 for the next spline section). You can have a cubic polynomial representing the path from the start to end, and it's not a function of the x-axis, but more like a function of the "axis" that is a line segment connecting the points (or at least, you can visualize it that way). No one cubic spline section can "loop the loop", but a set of connected sections certainly can.
This is really about splines in general, not so much how they are used in this context. When you're interpolating an image, you're generating a continuous surface that is also a single-valued function f(x,y). But in the CAD world, and with vector art, you have the situation where you get the loops.
I am confused by the terminology. The function is apparently defined by two points, and the tangents at those points. I haven't done the calculation, but I expect that a cubic can be uniquely defined in those terms, provided that the tangents are not vertical. I have a vague memory of B-splines being used for arbitrary curves in vector graphics. I never studied their geometry and algebra. I think it was the mention of splines in the video that is confusing me.
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).
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.
IM PINCHING AND ZOOMING
Took you long enough.
Say, did you just shoot this, or did you also shoot it back then (together with video about bilinear interpolation) and are only now publishing it?
just shot it (well a week or so ago) .... >Sean
Computerphile, could you do Lanczos and Mitchell?
+1 For Lanczos! And if you could explain the differences between separable lanczos and non separable it would be an amazing added bonus.
What happens with the pixels at the edge, that don't have pixels around them to get information from?
(this is 2 years ago but for anyone else looking thorugh the comments: you can find that if you follow the link)
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?
did you reticulate the splines...
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.
U are awesome thanks a lot
Does image rotation work any differently from rectangular resizing? Because if you rotate some number of degrees, some places may move less than one pixel's length, and not in a straight line...
Bitmap rotation uses the interpolation methods discussed in these videos, just as for rectangular resizing. You're still mapping each pixel of your result "target" image back to where its values come from in the source image, you're just replacing the x and y scaling with a rotation matrix. You transform your target pixel coordinates back to where they source from, and because these are non-integer values for all but the trivial case of 90 degree rotations, you use one of the interpolation methods to get your final value. Nearest neighbor is pretty unsightly, with a grainy look and jaggy edges, but bilinear and bicubic look nice and give the "anti-aliased" edge look to rotated lines.
[5:50] - Why is there an interpolation of Spatial coordinates? Isn't it supposed to be an interpolation of intensity values
I've got a silly question!
When it comes to watching analogue video, like Laserdiscs for example, would a mathematician use a video scaler to watch it on the big screen, or leave it alone? ;)
Using a video scaler really only makes sense if the video has already been digitized and you're trying to display it on a digital display with a higher resolution than how it was digitized. The signal path from an analog player to a digital display shouldn't resample the video at all, it should digitize it once appropriately for the display resolution.
Aloha . . thank you!
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
thanks
Could you do biquintic interpolation
Oooh, somebody got a fancy new high framerate camera.
Paper from a line printer, - that takes me back :-)
half way from X1 and X2 it will have a greater value than either one.
Wouldnt this produce bright spots ?
Binge watching this