MATLAB Answers

Ken
0

Fast interp1 with 'spline'

Asked by Ken
on 1 Apr 2015
Latest activity Commented on by 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.

  0 Comments

Sign in to comment.

3 Answers

John D'Errico
Answer by John D'Errico
on 1 Apr 2015
Edited by John D'Errico
on 1 Apr 2015
 Accepted Answer

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

Natan
on 6 Jul 2015
I've tried to play with spline and ppval, however for bigger vectors this method becomes much less efficient. Consider for example
xev = rand(1,1e4)*2 - 1;
and see.
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.


Answer by 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
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.


Answer by Philip
on 8 Jun 2015

griddedInterpolant is a lot faster than interp1, interp2, etc. routines.

  0 Comments

Sign in to comment.