Fast interp1 with 'spline'

34 visualizaciones (últimos 30 días)
Ken
Ken el 1 de Abr. de 2015
Comentada: John D'Errico el 6 de Jul. de 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.

Respuesta aceptada

John D'Errico
John D'Errico el 1 de Abr. de 2015
Editada: John D'Errico el 1 de Abr. de 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 comentarios
Adi Natan
Adi Natan el 6 de Jul. de 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
John D'Errico el 6 de Jul. de 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.

Iniciar sesión para comentar.

Más respuestas (2)

Chris McComb
Chris McComb el 1 de Abr. de 2015
Are you calling interp1 with a vector or lookup points? If not, doing so could give you a significant speed-up.
  1 comentario
Ken
Ken el 1 de Abr. de 2015
Editada: Ken el 2 de Abr. de 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?

Iniciar sesión para comentar.


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

Categorías

Más información sobre Interpolation en Help Center y File Exchange.

Community Treasure Hunt

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

Start Hunting!

Translated by