MATLAB Answers

Fast interp1 with 'spline'

47 views (last 30 days)
Ken
Ken on 1 Apr 2015
Commented: John D'Errico on 6 Jul 2015
Now I am programming a matlab toolbox for computer vision. I use a lot the function 'interp1(, , ,'spline')', and this step actually accounts for 50% of the whole computation time. Just wondering if there is any faster approach to compute this, and something like mex file, etc. Thank you very much.

Accepted Answer

John D'Errico
John D'Errico on 1 Apr 2015
Edited: John D'Errico on 1 Apr 2015
Well, the simple answer is to not use interp1. Just use spline and then ppval.
The problem is that for a spline interpolant, every time you call interp1, it must effectively call spline inside on your data. By calling spline once, this makes it more efficient.
For example...
x = linspace(-1,1,100);
y = exp(x);
xev = rand(1,1000)*2 - 1;
S = spline(x,y);
timeit(@() interp1(x,y,xev,'spline'))
ans =
0.0003005
timeit(@() ppval(S,xev))
ans =
0.00025177
Not as big of a difference as I thought it might be, but some.
You MIGHT also gain some time if you are willing to pre-interpolate the function to a finer interval, so that then you could do linear interpolation. Since linear interpolant will be faster to do, this should see some gain too.
x = linspace(-1,1,10);
y = exp(x);
xfine = linspace(-1,1,1000);
yfine = interp1(x,y,xfine,'spline');
xev = rand(1,1000)*2 - 1;
timeit(@() interp1(x,y,xev,'spline'))
ans =
0.00028546
timeit(@() interp1(xfine,yfine,xev))
ans =
0.00022313
You can also see some gain by using pchip instead of spline, as that is a faster way to build the spline, though sometimes not quite as smooth.
timeit(@() interp1(x,y,xev,'pship'))
ans =
0.00026064
Finally I recall seeing some tools on the file exchange that tried to give a speedup for interp1, but they were mostly for linear interpolation.
Finally, while you could certainly use a mexfile to improve the time, that presumes that your skills are sufficient to write a spline interpolant, and to do so efficiently in C. I'm afraid that compiled MATLAB code would gain you nothing here.
  2 Comments
John D'Errico
John D'Errico on 6 Jul 2015
Because interp1 now uses griddedInterpolant, which is faster than ppval. Nothing stops you from doing the same however, and still get a speedup, since there is no need to recompute the spline in every call.
xev = rand(1,1e4)*2 - 1;
S = griddedInterpolant(x,y,'spline');
timeit(@() S(xev))
ans =
0.00014841
timeit(@() interp1(x,y,xev,'spline'))
ans =
0.00051963
Things do change.

Sign in to comment.

More Answers (2)

Chris McComb
Chris McComb on 1 Apr 2015
Are you calling interp1 with a vector or lookup points? If not, doing so could give you a significant speed-up.
  1 Comment
Ken
Ken on 1 Apr 2015
I call interp1 to compute the spline interpolation of a curve on a 2d plane. For example,
new_points = round(interp1(t,points,ts,'spline'));
where 'points' is an matrix of size alpha*2, representing alpha points on the 2d plane and each point with a coordinate as a row of 'points'. Any better solution?

Sign in to comment.


Philip
Philip on 8 Jun 2015
griddedInterpolant is a lot faster than interp1, interp2, etc. routines.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!