Tuesday, December 19, 2017

Published December 19, 2017 by with 1 comment

How Do I Do Fast Bilinear Interpolation In Matlab When Interp2 Is Slow?

In working on CityProjections, I have to do bilinear interpolation constantly. Is there a fast way to do it in MATLAB?


I'll compare two methods here:
interp2 is the one I defaulted to originally. I noticed it was typically the bottleneck though so I looked for alternatives almost immediately. griddedInterpolant was significantly faster and is fast enough that it's no longer a bottleneck, so I stopped looking at that point. To show the performance difference, I put together a really short example that's listed below.

For a quick background, the example generates a 1000x1000 grid and assigns random values to each point. It then tries to find the interpolated values at 200 random x/y locations completely contained in the grid. E.g., it might try to find the value at x = 1.56, y = 98.14 while the values are actually known when x and y are integers.

I do this interpolation four different ways, output the time each method takes, and output a check that they returned the same values.


clear all
close all

%Setup 1000 x 1000 grid and create random numbers for the V(x,y) you'll
%interpolate
x = -1000:1:1000;
y = -1000:1:1000;

[X, Y] = meshgrid(x, y);
[A, B] = ndgrid(x, y);
V = rand(length(x));

%setup smaller set of random x/y locations where you want the interpolated
%value
xi = zeros(200, 1);
yi = zeros(200, 1);
for i = 1:length(xi);
    xi(i) = 2000*rand() - 1000;
    yi(i) = 2000*rand() - 1000;
end

%avoid unnecessary operations in the interpolations
W = V';
Vi = zeros(1, length(xi));
Vj = zeros(length(xi), 1);
Vk = zeros(length(xi), 1);
Vl = zeros(length(xi), 1);

%super-slow interp2 method
t = cputime;
for i = 1:length(xi)
    Vi(i) = interp2(X, Y, W, xi(i), yi(i));
end
cputime - t

%faster interp2 method
testTime = zeros(100, 1);
for i = 1:length(testTime)
    t = cputime;
    Vj = interp2(X, Y, W, xi, yi);
    testTime(i) = cputime - t;
end
mean(testTime)

%slower griddedInterpolant method
for i = 1:length(testTime)
    t = cputime;
    F = griddedInterpolant(A, B, V);
    for j = 1:length(xi)
        Vk(j) = F([xi(j) yi(j)]);
    end
    testTime(i) = cputime - t;
end
mean(testTime)

%faster griddedInterpolant method
for i = 1:length(testTime)
    t = cputime;
    F = griddedInterpolant(A, B, V);
    Vl = F(xi, yi);
    testTime(i) = cputime - t;
end
mean(testTime)

%make sure the results agree
sum(Vl - Vk)
sum(Vk - Vj)
sum(Vj - Vi')

On my laptop, running this yields the following times:

  • slow interp2: 17,594 ms
  • fast interp2: 114 ms
  • slow griddedInterpolant: 17 ms
  • fast griddedInterpolant: 11 ms
There are probably even faster ways to do this, but this was more than enough for my use case so I figured I'd share it.

      edit

1 comment:

  1. Wallet slots is another service that gamblers online slot games Probably better known in the name of Slotxo. Transfer via wallet. No minimum. is a service provider

    ReplyDelete