What are some techniques for 2-D interpolation and how do they work?

[RH10]

Hi All,

I'm working on coding some 2-D interpolation techniques. With wikikepdia's help, I've managed blinear interpolation.

What other techniques are out there? Please tell me a little about how your favourite technique works.

I've read about higher order methods, using more surrounding points, but can't get that to work. I've had no trouble extracting the 16 corners of the 3x3 grid my desired point is in form my data set, but how do I get down from 16 points to one? Using google everyone is talking about image processing, rather than the more basic task of interpolating to a number - of course images are just numbers - but I can't find the basic equations.

Thanks in advance for any help,

 

[chiro]

Hi All,

I'm working on coding some 2-D interpolation techniques. With wikikepdia's help, I've managed blinear interpolation.

What other techniques are out there? Please tell me a little about how your favourite technique works.

I've read about higher order methods, using more surrounding points, but can't get that to work. I've had no trouble extracting the 16 corners of the 3x3 grid my desired point is in form my data set, but how do I get down from 16 points to one? Using google everyone is talking about image processing, rather than the more basic task of interpolating to a number - of course images are just numbers - but I can't find the basic equations.

Thanks in advance for any help,

Hey RH10 and welcome to the forums.

For more general methods look at B-SPLINES and NURBS. They are a lot more complicated but they offer huge advantages for interpolation.

The BSPLINES work by using control points to interpolate between and they also differentiability conditions. NURBS use what is called a knot vector that gives finer control.

I haven't used these for a very long time and when I messed with them, the most I really did was use them for rendering using only one or two test examples: very nice objects though.

Also if you pick up any book on mathematical and computer animation, you'll see things like Catmull-Rom, Hermite, and standard Lagrange interpolation. Lagrange is the easiest to understand, but NURBS are where its at if you have the processing power and the ability to define what you had in mind. With NURBS, you can model very very accurately the arc of a circle which is pretty impressive (it's general enough that this is only a fraction of it's descriptive ability).

Here is the wiki for NURBS:

http://en.wikipedia.org/wiki/Non-uniform_rational_B-spline

If you want an implementation and thorough discussion, a guy working at Intel actually coded up a NURBS renderer in C++ and it's where I actually learned this kind of thing initially. (Not a renderer per se, but a surface generation and normal vector computation procedure with triangulation code [very trivial since the whole is parameterized]).

http://software.intel.com/en-us/articles/using-nurbs-surfaces-in-real-time-applications/

 

[RH10]

Hi Chiro,

Thanks for your links, reading about B-Spines is very interesting. Much of the intel website went over my head unfortunately, so can you point me to the basic equations for this? How do I go about actually interpolating in a square matrix?

Thanks,

 

[chiro]

Hi Chiro,

Thanks for your links, reading about B-Spines is very interesting. Much of the intel website went over my head unfortunately, so can you point me to the basic equations for this? How do I go about actually interpolating in a square matrix?

Thanks,

It sounds like you want to interpolate over a volume, rather than a surface or a line. Is this correct?

 

[RH10]

It sounds like you want to interpolate over a volume, rather than a surface or a line. Is this correct?

No, the problem is a 2-D one. That is I have a square matrix (n x n x 1) which represents my data set and the challenge is to interpolate in it. Nearest neighbour is obviously no sweat.

Extracting part of the data set and using bilinear interpolation wasn't too hard, but I'm reading about more accurate methods (probably involving extracting a larger chunk of the data set) but don't understand them fully enough to code them. Thanks for writing back.