Geek asks and answers

Minimizing distance to a weighted grid

Suppose you have a grid of 1000x1000 positive integer weights W.

We want to find a cell that minimizes the average weighted distance. Every cell.

Most likely, this is done to iterate over each candidate cell and calculate the distance:

int best_x, best_y, best_dist;

for x0 = 1:1000,
    for y0 = 1:1000,

        int total_dist = 0;

        for x1 = 1:1000,
            for y1 = 1:1000,
                total_dist += W[x1,y1] * sqrt((x0-x1)^2 + (y0-y1)^2);

        if (total_dist < best_dist)
            best_x = x0;
            best_y = y0;
            best_dist = total_dist;

It takes ~ 10 ^ 12 operations that are too long.

Is there a way to do this in about ~ 10 ^ 8 or so?

+5
source share
1 answer

Theory

This is possible using filters in O (nm log nm), where n, m are the grid sizes.

2n + 1 x 2m + 1, () 3n x 3m. , , (n,m):

 F(i,j) = sqrt((n-i)^2 + (m-j)^2)

W ( ), 3n x 3m.

(cross-correlation)

 R = F o W

total_dist, min R ( , W), x0, y0.

(.. ) , matlab, imfilter.

, , , convolution , F . , , , .

O (nm log nm) , 2D FFT.

Matlab, , :

m=100;
n=100;
W0=abs(randn(m,n))+.001;

tic;

%The following padding is not necessary in the matlab code because
%matlab implements it in the imfilter function, from the imfilter
%documentation:
%  - Boundary options
% 
%        X            Input array values outside the bounds of the array
%                     are implicitly assumed to have the value X.  When no
%                     boundary option is specified, imfilter uses X = 0.

%W=padarray(W0,[m n]);

W=W0;
F=zeros(2*m+1,2*n+1);

for i=1:size(F,1)
    for j=1:size(F,2)
        %This is matlab where indices start from 1, hence the need
        %for m-1 and n-1 in the equations
        F(i,j)=sqrt((i-m-1)^2 + (j-n-1)^2);
    end
end
R=imfilter(W,F);
[mr mc] = ind2sub(size(R),find(R == min(R(:))));
[mr, mc]
toc;

tic;
T=zeros([m n]);
best_x=-1;
best_y=-1;
best_val=inf;
for y0=1:m
    for x0=1:n

        total_dist = 0;

        for y1=1:m
            for x1=1:n
                total_dist = total_dist + W0(y1,x1) * sqrt((x0-x1)^2 + (y0-y1)^2);
            end
        end

        T(y0,x0) = total_dist;
        if ( total_dist < best_val ) 
            best_x = x0;
            best_y = y0;
            best_val = total_dist;
        end

    end
end
[best_y best_x]
toc;

diff=abs(T-R);
max_diff=max(diff(:));
fprintf('The max difference between the two computations: %g\n', max_diff);

800x800 , , , , FFT 700 . , .

, , , ​​ . , CUDA FFT library, 2D FFT , CPU. , , , .

, , best_x,bext_y floor(n/2)+-1. , , , , total_dist 4 , !

+5

More articles:


All Articles