Asked by Ken
on 1 Apr 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.

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.

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

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.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.