Fast interp1 with 'spline'

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.

Answer 1

[John D'Errico]

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.

[Adi Natan]

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]

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.

Answer 2

[Chris McComb]

Are you calling interp1 with a vector or lookup points? If not, doing so could give you a significant speed-up.

[Ken]

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?

Answer 3

[Philip]

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