3

私はグーグルにkd-treesと画像比較に関するいくつかの資料を問い合わせてきましたが、kd-treesを使用して画像比較のための技術間の「リンク」を作成できませんでした。最初に、ランダム化されたkdツリーによる速度の向上について説明している記事をいくつか見つけました。次にSIFTを紹介しました。基本的にSIFTの仕組みを理解した後、最近傍探索について読みました。

私の本当の質問は、SIFTからのポイントのメッシュがある場合、すべての画像に対してkdツリーを作成することです。最近傍検索はどのように画像を比較するのに役立ちますか？最初は、画像をツリーと比較すると、ツリー構造と、画像Aと画像Bの同じノード内のポイントからすべてのポイントがどれだけ近いかをチェックするアルゴリズムで機能すると思いました。

質問があまりにも馬鹿げている場合は、検索用の資料またはトピックを提案してください。

ありがとうございました！

4

3 に答える 3

8

kdtreeを使用せずに、最初に低速の機能マッチングを理解することをお勧めします。

  • 入力：顔や花などの1000個の参照フィーチャ。これらをF1と呼びます..F1000
  • クエリ機能Q：どの顔または花の機能が最も似ているか、最も近いか、Q？

ご存知のように、 SIFT は画像の特徴を128個の8ビット数に減らし、
  類似度（特徴F、特徴Q）=ユークリッド距離（SIFT（F）、SIFT（Q））になるようにスケーリングします。

F1 .. F1000のどれがQに最も似ているかを見つける最も簡単な方法は、F1、F2...を1つずつ調べることです。

# find the feature of F1 .. F1000 nearest Q
nearestdistance = infinity
nearestindex = 0
for j in 1 .. 1000:
    distance = Euclideandistance( SIFT(Fj), SIFT(Q) )  # 128 numbers vs. 128 numbers
    if distance < nearestdistance:
        nearestdistance = distance
        nearestindex = j

（もちろん、ループの外側でSIFT番号を計算します。）

Kdtree は、近くのベクトルをすばやく見つける方法にすぎません。一致しているもの（...を表す数値のベクトル）や方法（ユークリッド距離）とはほとんど関係ありません。現在、kdtreeは2d、3d ...おそらく20dまでは非常に高速ですが、20dを超えるすべてのデータの線形スキャンよりも高速ではない可能性があります。では、kdtreeは128dの機能に対してどのように機能するのでしょうか？主なトリックは、検索を早期に終了することです。MujaとLoweによる論文、 自動アルゴリズム構成を使用した高速近似最近傍、 2009、10pは、128dSIFT機能を照合するための複数のランダム化kdtreeについて説明しています。（LoweはSIFTの発明者です。）

2つの画像IとQを比較するために、それぞれの特徴ベクトルのセット（数百から数千のSIFTベクトル）を見つけ、これらのセットのほぼ一致するものを探します。（画像を分子、特徴を原子と考えることができます。ほぼ一致する分子は、ほぼ一致する原子よりもはるかに困難ですが、原子をすばやく一致させるのに役立ちます。）

お役に立てれば。

于 2011-04-19T15:16:43.740 に答える
0

高次元での近似NN検索にkd-treesを使用することを計画している場合は、ここで実験を確認することをお勧めします：http: //zach.in.tu-clausthal.de/software/approximate_nn/

于 2011-07-13T15:57:15.107 に答える
0

各画像のカラーコード値を抽出し、それらの特徴ベクトルを使用してKDツリーを作成することをお勧めします。

次のMATLABコードを使用して、カラーコードの特徴を抽出できます。

im = imread('image.jpg');

len = size(im,3);
if(len == 1)
    im = ind2rgb(im, colourMap);
    im = uint8(im.*255);
end

im(logical(  0 <= im & im <=  63)) = 0;
im(logical( 64 <= im & im <= 127)) = 1;
im(logical(128 <= im & im <= 191)) = 2;
im(logical(192 <= im & im <= 255)) = 3;
im = im(:,:,1) * 16 + im(:,:,2) * 4 + im(:,:,3);

imHist = histc(im(:),0:63);
于 2013-02-13T05:15:24.040 に答える