Precompute weights for multidimensional linear interpolation

Question

I have a non-uniform rectangular grid along D dimensions, a matrix of logical values V on the grid, and a matrix of query data points X. The number of grid points differs across dimensions.

I run the interpolation multiple times for the same grid G and query X, but for different values V.

The goal is to precompute the indexes and weights for the interpolation and to reuse them, because they are always the same.

Here is an example in 2 dimensions, in which I have to compute indexes and values every time within the loop, but I want to compute them only once before the loop. I keep the data types from my application (mostly single and logical gpuArrays).

% Define grid
G{1} = single([0; 1; 3; 5; 10]);
G{2} = single([15; 17; 18; 20]);

% Steps and edges are reduntant but help make interpolation a bit faster
S{1} = G{1}(2:end)-G{1}(1:end-1);
S{2} = G{2}(2:end)-G{2}(1:end-1);

gpuInf = 1e10;
% It's my workaround for a bug in GPU version of discretize in Matlab R2017a.
% It throws an error if edges contain Inf, realmin, or realmax. Seems fixed in R2017b prerelease.
E{1} = [-gpuInf; G{1}(2:end-1); gpuInf];
E{2} = [-gpuInf; G{2}(2:end-1); gpuInf];

% Generate query points
n = 50; X = gpuArray(single([rand(n,1)*14-2, 14+rand(n,1)*7]));

[G1, G2] = ndgrid(G{1},G{2});

for i = 1 : 4
    % Generate values on grid
    foo = @(x1,x2) (sin(x1+rand) + cos(x2*rand))>0;
    V = gpuArray(foo(G1,G2));

    % Interpolate
    V_interp = interpV(X, V, G, E, S);

    % Plot results
    subplot(2,2,i);
    contourf(G1, G2, V); hold on;
    scatter(X(:,1), X(:,2),50,[ones(n,1), 1-V_interp, 1-V_interp],'filled', 'MarkerEdgeColor','black'); hold off;
end

function y = interpV(X, V, G, E, S)
y = min(1, max(0, interpV_helper(X, 1, 1, 0, [], V, G, E, S) ));
end

function y = interpV_helper(X, dim, weight, curr_y, index, V, G, E, S)
if dim == ndims(V)+1
    M = [1,cumprod(size(V),2)];
    idx = 1 + (index-1)*M(1:end-1)';
    y = curr_y + weight .* single(V(idx));
else
    x = X(:,dim); grid = G{dim}; edges = E{dim}; steps = S{dim};
    iL = single(discretize(x, edges));
    weightL = weight .* (grid(iL+1) - x) ./ steps(iL);
    weightH = weight .* (x - grid(iL)) ./ steps(iL);
    y = interpV_helper(X, dim+1, weightL, curr_y, [index, iL  ], V, G, E, S) +...
        interpV_helper(X, dim+1, weightH, curr_y, [index, iL+1], V, G, E, S);
end
end

Answer 1

I found a way to do this and posting it here because (as of now) two more people are interested. It takes only a slight modification to my original code (see below).

% Define grid
G{1} = single([0; 1; 3; 5; 10]);
G{2} = single([15; 17; 18; 20]);

% Steps and edges are reduntant but help make interpolation a bit faster
S{1} = G{1}(2:end)-G{1}(1:end-1);
S{2} = G{2}(2:end)-G{2}(1:end-1);

gpuInf = 1e10;
% It's my workaround for a bug in GPU version of discretize in Matlab R2017a.
% It throws an error if edges contain Inf, realmin, or realmax. Seems fixed in R2017b prerelease.
E{1} = [-gpuInf; G{1}(2:end-1); gpuInf];
E{2} = [-gpuInf; G{2}(2:end-1); gpuInf];

% Generate query points
n = 50; X = gpuArray(single([rand(n,1)*14-2, 14+rand(n,1)*7]));

[G1, G2] = ndgrid(G{1},G{2});

[W, I] = interpIW(X, G, E, S); % Precompute weights W and indexes I

for i = 1 : 4
    % Generate values on grid
    foo = @(x1,x2) (sin(x1+rand) + cos(x2*rand))>0;
    V = gpuArray(foo(G1,G2));

    % Interpolate
    V_interp = sum(W .* single(V(I)), 2);

    % Plot results
    subplot(2,2,i);
    contourf(G1, G2, V); hold on;
    scatter(X(:,1), X(:,2), 50,[ones(n,1), 1-V_interp, 1-V_interp],'filled', 'MarkerEdgeColor','black'); hold off;
end

function [W, I] = interpIW(X, G, E, S)
global Weights Indexes
Weights=[]; Indexes=[];
interpIW_helper(X, 1, 1, [], G, E, S, []);
W = Weights; I = Indexes;
end

function [] = interpIW_helper(X, dim, weight, index, G, E, S, sizeV)
global Weights Indexes
if dim == size(X,2)+1
    M = [1,cumprod(sizeV,2)];
    Weights = [Weights, weight];
    Indexes = [Indexes, 1 + (index-1)*M(1:end-1)'];
else
    x = X(:,dim); grid = G{dim}; edges = E{dim}; steps = S{dim};
    iL = single(discretize(x, edges));
    weightL = weight .* (grid(iL+1) - x) ./ steps(iL);
    weightH = weight .* (x - grid(iL)) ./ steps(iL);
    interpIW_helper(X, dim+1, weightL, [index, iL  ], G, E, S, [sizeV, size(grid,1)]);
    interpIW_helper(X, dim+1, weightH, [index, iL+1], G, E, S, [sizeV, size(grid,1)]);
end
end

Answer 2

To do the task the whole process of interpolation ,except computing the interpolated values, should be done. Here is a solution translated from the Octave c++ source. Format of the input is the same as the frst signature of the interpn function except that there is no need to the v array. Also Xs should be vectors and should not be of the ndgrid format. Both the outputs W (weights) and I (positions) have the size (a ,b) that a is the number of neighbors of a points on the grid and b is the number of requested points to be interpolated.

function [W , I] = lininterpnw(varargin)
% [W I] = lininterpnw(X1,X2,...,Xn,Xq1,Xq2,...,Xqn)
    n     = numel(varargin)/2;
    x     = varargin(1:n);
    y     = varargin(n+1:end);
    sz    = cellfun(@numel,x);
    scale = [1 cumprod(sz(1:end-1))];
    Ni    = numel(y{1});
    index = zeros(n,Ni);
    x_before = zeros(n,Ni);
    x_after = zeros(n,Ni);
    for ii = 1:n
        jj = interp1(x{ii},1:sz(ii),y{ii},'previous');
        index(ii,:) = jj-1;
        x_before(ii,:) = x{ii}(jj);
        x_after(ii,:) = x{ii}(jj+1);
    end
    coef(2:2:2*n,1:Ni) = (vertcat(y{:}) - x_before) ./ (x_after - x_before);
    coef(1:2:end,:)    = 1 - coef(2:2:2*n,:);
    bit = permute(dec2bin(0:2^n-1)=='1', [2,3,1]);
    %I = reshape(1+scale*bsxfun(@plus,index,bit), Ni, []).';  %Octave
    I = reshape(1+sum(bsxfun(@times,scale(:),bsxfun(@plus,index,bit))), Ni, []).';
    W = squeeze(prod(reshape(coef(bsxfun(@plus,(1:2:2*n).',bit),:).',Ni,n,[]),2)).';
end

Testing:

x={[1 3 8 9],[2 12 13 17 25]};
v = rand(4,5);
y={[1.5 1.6 1.3 3.5,8.1,8.3],[8.4,13.5,14.4,23,23.9,24.2]};

[W I]=lininterpnw(x{:},y{:});

sum(W.*v(I))
interpn(x{:},v,y{:})

Thanks to @SardarUsama for testing and his useful comments.