4

まず第一に、私はSiftの機能マッチングの背後にある理論をよく知っています。私の問題は、むしろ技術的な問題です。

そこで、最初の画像のベクトルと2番目の画像のすべてのベクトルの間のユークリッド距離を計算し、最大の2つの値の比率が特定のしきい値よりも大きい場合は一致するものを計算します。

それが私のコードです

distRatio = 0.5;   
for i = 1:size(des1,1)
    eucl = zeros(size(des2,1));
    for j=1:size(des2,1)
           eucl(j) = sqrt(sum((des1(i,:)-des2(j,:)).^2));
    end;

    [vals,indx] = sort(eucl);        
    if (vals(1) < distRatio * vals(2))
      match(i) = indx(1);
    else
      match(i) = 0;
    end
end;

問題はそれが非常に遅いということです、そして私は理由を知っています、それはネストされたループのために遅いです、それを最適化する方法はありますか？申し訳ありませんが、Matlab構文の経験が不十分です。

4

1 に答える 1

6

ユークリッド距離を計算するときによく使用できる巧妙なトリックの 1 つは、アルゴリズムを変更して、代わりにユークリッド距離の2 乗で動作するようにすることです。これにより、たとえば、最大またはセット内の最短距離。

したがって、内側のループは次のようになります。

distSquared(j) = sum((des1(i, :) - des2(j, :)).^2);

あなたの場合、変更するのが難しいのは行です

if (vals(1) < distRatio * vals(2))

これはに相当します

if (vals(1)^2 < (distRatio * vals(2))^2)

または

if (vals(1)^2 < (distRatio^2) * (vals(2)^2))

distSquaredの代わりにから値を取得している場合はeucl、次を使用できます。

if (valSquared(1) < (distRatio^2) * valSquared(2))

最後に、次のように減算を書き直すことで、内側のループを取り除くことができます。

countRowsDes2 = size(des2, 1); % this line outside the loop

%... now inside the loop
    des1expand = repmat(des1(i, :), countRowsDes2, 1); % copy this row

    distSquared = sum((des1expand - des2).^2, 2);      % sum horizontally

repmat行をコピーするために使用した場所で、2 番目の次元引数を使用して水平次元で作業を行いましたdes1(i, :)。sum

すべてを一緒に入れて

distRatio = 0.5;
distRatioSq = distRatio^2; % distance ratio squared
countRowsDes1 = size(des1, 1); % number of rows in des1
countRowsDes2 = size(des2, 1); % number of rows in des2

match = zeros(countRowsDes1, 1); % pre-initialize with zeros

for i = i:size(des1, 1)
    des1expand = repmat(des1(i, :), countRowsDes2, 1); % copy row i of des1
    distSquared = sum((des1expand - des2).^2, 2);      % sum horizontally

    [valsSquared, index] = sort(distSquared);

    if (valsSquared(1) < distRatioSq * valsSquared(2))
        match(i) = index(1);
    % else zero by initialization
end
于 2012-12-18T03:35:43.760 に答える