5

正の整数の重みWの1000x1000グリッドがあると仮定します。

各セルまでの平均加重距離を最小化するセルを見つけたいと思います。

これを行うためのブルートフォースの方法は、各候補セルをループして距離を計算することです。

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;

これには約10^12の操作が必要ですが、これは長すぎます。

〜10 ^ 8程度の操作でこれを行う方法はありますか？

4

1 に答える 1

5

仮説

これは、O（nm log nm）時間のフィルターを使用して可能です。ここで、n、mはグリッドの次元です。

サイズのフィルターを定義する必要があり2n + 1 x 2m + 1、元のウェイトグリッドをサイズのゼロのグリッドに（中央に）埋め込む必要があります3n x 3m。フィルタは、原点からの距離の重み付けである必要があります(n,m)。

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

サイズWがゼロのグリッドに埋め込まれた元のウェイトグリッド（中央）を示します3n x 3m。

次に、フィルタリングされた（相互相関）結果

 R = F o W

total_distグリッドが表示されます。 min R（Wに追加された余分な埋め込みゼロを無視して）最適なx0, y0位置を見つけるだけです。

画像（つまりグリッド）フィルタリングは非常に標準的であり、imfilterコマンドを使用して、matlabなどのさまざまな既存のソフトウェアで実行できます。

上記の相互相関を明示的に使用しましたが、フィルターが対称であるという理由だけで、畳み込みでも同じ結果が得られることに注意してください。F2つの操作は非常に類似していますが、一般に、画像フィルターは畳み込みではなく相互相関です。

O（nm log nm）ランタイムの理由は、2DFFTを使用して画像フィルタリングを実行できるためです。

実装

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グリッドの場合、確かに最速ではない私のPCでは、FFT法は700秒強で評価されます。強引な方法は数時間後に完了せず、私はそれを殺さなければなりません。

さらなるパフォーマンスの向上という点では、GPUなどのハードウェアプラットフォームに移行することでそれらを達成できます。たとえば、CUDAのFFTライブラリを使用すると、CPUにかかる時間の何分の1かで2DFFTを計算できます。重要な点は、計算を行うためにより多くのハードウェアを投入するとFFT法がスケーリングするのに対し、ブルートフォース法ははるかに悪化するということです。

観察

これを実装している間、ほとんどの場合、best_x,bext_y値はの1つであることがわかりfloor(n/2)+-1ました。これは、距離項が計算全体を支配している可能性が高いことを意味します。したがって、total_dist4つの値のみの値を計算する必要がなくなり、このアルゴリズムは簡単になります。

于 2012-06-29T21:11:18.280 に答える