I want to use Akima interpolation on series of points. I have those points in 3D [x, y, z]. But in all resources, I found, there is only f(x) and x (so [x,y]).
In Natrual Cubic Spline I am using this approach: http://mathworld.wolfram.com/CubicSpline.html (matrix 18) and I can calculate curve for 1, 2.. N dimension the same way…
Is something like this possible for Akima ? Thanks…
PS: I am not math skilled, so maybe this question is totally out.. for that, I am sorry 🙂
[Math] Akima spline interpolation
interpolationspline
Related Solutions
As you know, B-splines smooth, run between the data points. If you want to interpolate, go through the data points exactly, using a B-spline function, here's how.
In: data points $f_i$ at the integers $i = 0\ 1\ 2 \dots n$
$\ \ \ \ \ $ a cubic B-spline function $B( x; data_i )$ for $0 \leq x \leq n$
Out: a wrapper function $I( x; data_i )$ that interpolates, $I(i) = f_i$ .
Method:
we know that $B(i) = (f_{i-1} + 4 f_i + f_{i+1}) \,/\, 6, i = 0\ 1\ 2 \dots$
or in matrix form,
$\ b = A f$ with $A$ tridiagonal.
Solve $\ A y = f$
then $\ \ B(y) = B( A^{-1} f ) = f$
i.e. $\ \ \ \ \, I( x; f_i ) \equiv B( x; A^{-1} f )$ interpolates.
Notes:
Solving this tridiagonal system is fast and easy.
(You need boundary conditions such as $f_{-1} = f_0$ or $f_{-1} = 0$ ,
and similarly for $f_{n+1}$.)
A function like $(B + 2 I)\, /\, 3$ is between $B()$ and $I()$:
it smooths less than $B$, but is not as sensitive to noise as $I$ .
This particular blend is called an M-N filter, after
Mitchell and Netravali,
Reconstruction Filters in Computer Graphics,
1988, 8p.
M-N splines also have less overshoot than Interpolating splines; see
what-is-the-maximum-overshoot-of-interpolating-splines-in-d-dimensions.
A fancier way of using B-splines to interpolate, using IIR filters, is given in
M. Unser,
Splines: A perfect fit for signal and image processing ,
1999, 17p .
There are two ways (at least). A brute force way and a clever way.
The brute force way just uses interpolation techniques. The Akima curve is a cubic spline that is $C_1$ at each knot. So, all of its interior knots are double knots (multiplicity two). So, if you have $n+1$ points, $(x_0, x_1, \ldots, x_n)$, your knot sequence will have the form $(x_0, x_0, x_0, x_0, x_1, x_1, \ldots, x_i, x_i, \ldots , x_n, x_n, x_n, x_n)$. So, you have $2n+6$ knot values, and using these, you can construct $2n+2$ cubic b-spline basis functions, $B_0, \ldots, B_{2n+1}$. The b-spline we want will be $$ f(x) = \sum_{i=0}^{2n+1}\alpha_i B_i(x) $$ We can calculate the coefficients $\alpha_0, \ldots, \alpha_{2n+1}$ by interpolation. Choose $2n+2$ values $z_0, \ldots, z_{2n+1}$, and evaluate your Akima curve at these values to get $2n+2$ ordinate values $y_0, \ldots, y_{2n+1}$. Then solve the linear system $$ y_j = \sum_{i=0}^{2n+1}\alpha_i B_i(z_j) \quad (j = 0, 1, \ldots, 2n+1) $$ to get the b-spline coefficients $\alpha_0, \ldots, \alpha_{2n+1}$. You have to choose the $z_j$ values with a bit of care, or else you'll end up with a linear system that does not have a unique solution. The crucial point here is that the interpolation problem has a unique solution. Since the b-spline curve and the Akima curve are both solutions, they must be the same curve.
The clever way is to just fabricate the $\alpha$ coefficients using the end-points and end tangents of the cubic segments in the Akima curve. Suppose the points are $(x_0, x_1, \ldots, x_n)$, again, and let $(y_0, y_1, \ldots, y_n)$ and $(d_0, d_1, \ldots, d_n)$ be the values and first derivatives of the Akima curve at these points. The b-spline control points are then: \begin{align} y_0 \quad &; \quad y_0 + \tfrac13 d_0 (x_1 - x_0) \\ y_1 - \tfrac13 d_1 (x_1 - x_0) \quad &; \quad y_1 + \tfrac13 d_1 (x_2 - x_1) \\ y_2 - \tfrac13 d_2 (x_2 - x_1) \quad &; \quad y_2 + \tfrac13 d_2 (x_3 - x_2) \\ &\vdots \\ y_i - \tfrac13 d_i (x_i - x_{i-1}) \quad &; \quad y_i + \tfrac13 d_i (x_{i+1} - x_i) \\ &\vdots \\ y_n - \tfrac13 d_n (x_n - x_{n-1}) \quad &; \quad y_n \end{align} This gives you $2n+2$ coefficients, as before. The knot sequence is the same as in the brute force approach above. Here's a picture
The black points represent the coefficients. The red points are the breaks between the cubic segments. We have 5 original data points, so $n=4$. This means we will have $2n+2 = 10$ coefficients.
Best Answer
There's an original paper by Akima about this. Even though I'm not sure if he really uses 'Akima' Interpolation there, you could have a look at http://dl.acm.org/citation.cfm?id=355786.
Also, there's a R package doing exactly this. You could check out the source code of http://cran.r-project.org/web/packages/akima/.