Cubic Spline Interpolator

[Kevin Neilson]

This isn't a question; I'm putting this here as a reference so I can find it in the future. This is how to build a cubic interpolator circuit that takes four samples and interpolates a sample between the middle two.

Given four samples, y0, y1, y2, y3, sampled with period T=1 at (arbitrary) times t={-1,0,1,2}, and given mu, where 0<mu<T, what is the cubic spline interpolation formula to find ymu, the interpolated value of y that corresponds to time t=mu (and lies somewhere between the two middle samples)?

Answer, written in Horner's Method format:

ymu = 1/6*((((-y0+3y1-3y2+y3)mu + (3y0-6y1+3y2))mu + (-2y0-3y1+6y2-y3))mu + 6y1)

Note: 1/6 = binary 0.001010101..., 6x = (x + x<<2)<<2

Abbreviated Derivation:

You are given four samples (t,y) = (-1,y0), (0,y1), (1,y2), (2,y2)

This is the cubic poly that contains those four points:

y = a*t^3 + b*t^2 + c*t + d

When you put the four points into this equations you have four equations in four unknowns. Solving yields

a = 1/6*(-y0+3y1-3y2+y3)
b = 1/6*(3y0-6y1+3y2)
c = 1/6*(-2y0-3y1+6y2-y3)
d = y1

 

[David Brown]

On 24/05/13 03:04, Kevin Neilson wrote:

This isn't a question; I'm putting this here as a reference so I can
find it in the future. This is how to build a cubic interpolator
circuit that takes four samples and interpolates a sample between the
middle two.

Given four samples, y0, y1, y2, y3, sampled with period T=1 at
(arbitrary) times t={-1,0,1,2}, and given mu, where 0<mu<T, what is
the cubic spline interpolation formula to find ymu, the interpolated
value of y that corresponds to time t=mu (and lies somewhere between
the two middle samples)?

Answer, written in Horner's Method format:

ymu = 1/6*((((-y0+3y1-3y2+y3)mu + (3y0-6y1+3y2))mu +
(-2y0-3y1+6y2-y3))mu + 6y1)

Note: 1/6 = binary 0.001010101..., 6x = (x + x<<2)<<2

Abbreviated Derivation:

You are given four samples (t,y) = (-1,y0), (0,y1), (1,y2), (2,y2)

This is the cubic poly that contains those four points:

y = a*t^3 + b*t^2 + c*t + d

When you put the four points into this equations you have four
equations in four unknowns. Solving yields

a = 1/6*(-y0+3y1-3y2+y3)
b = 1/6*(3y0-6y1+3y2)
c = 1/6*(-2y0-3y1+6y2-y3)
d = y1

This might seem a minor quibble, but that is not a cubic spline
interpolation - it is just a plain cubic curve fit and interpolation. A
cubic spline is made when you have more sample points and you put
together a step-wise cubic function consisting of multiple cubic parts
joined together. Implementing cubic splines involves quite a bit more
maths (it depends on the type of cubic spline - there are many) - making
an efficient FPGA implementation could be a fun way to spend a rainy day.

 

[Frank Buss]

David Brown wrote:

an efficient FPGA implementation could be a fun way to spend a rainy day.

Should be easy, it's 10 lines in Java:

http://www.frank-buss.de/spline.html

--
Frank Buss, http://www.frank-buss.de
electronics and more: http://www.youtube.com/user/frankbuss

 

[Kevin Neilson]

Super! Mann zieht die Stuetzpunkte mit der Maus! That is a nice applet, but it's parametric, so it seems a little different than my application. I have a function of only one variable. -Kevin

 

[Kevin Neilson]

Thanks; that is a good clarification. I just need to interpolate a point given four surrounding points so I guess I don't need the whole spline implementation. There is a wealth of information on the web about interpolation but it's difficult to find the simple extracted formula I have above. I suppose most implementations are, like you say, not well-designed for FPGAs.

 

[Frank Buss]

Kevin Neilson wrote:

Super! Mann zieht die Stuetzpunkte mit der Maus! That is a nice applet, but it's parametric,
so it seems a little different than my application. I have a function of only one variable.

The class Spline.java is a spline of only one variable. Test.java uses
it twice, for the x and y coordinate of the points.

Your example for x=-1,0,1,2 could be implemented by creating a Spline
object and initializing it with the y-samples. Then call fn, with 0, 1,
2, 3 and use t for interpolating between two points.

--
Frank Buss, http://www.frank-buss.de
electronics and more: http://www.youtube.com/user/frankbuss