8

近似最近傍探索ライブラリ FLANN を研究しています。

LSH メソッドの場合、これらは unsigned int の配列としてオブジェクト (検索空間内のポイント) を表します。なぜ彼らがこれを行うのか、点を単純に double 配列 (多次元ベクトル空間の点を表す) として表さないのかはわかりません。LSHがバイナリ機能に使用されているためでしょうか？この場合、誰かが unsigned int の使用の可能性についてもっと共有できますか? 各機能に 0 と 1 しか必要ないのに、なぜ unsigned int なのですか?

ありがとう

4

1 に答える 1

10

flann-1.8.3最新の FLANN リリース、つまり執筆時点のものを参照することに注意してください。

LSH メソッドの場合、これらは unsigned int の配列としてオブジェクト (検索空間内のポイント) を表します

いいえ：これは間違っています。このLshIndexクラスにはbuildIndexImpl、LSH インデックス作成を実装するメソッドが含まれています。LSH は基本的にハッシュ テーブルのコレクションであるため、効果的なインデックス作成はLshTableクラスで行われます。

基本的な索引付け方法、つまり、一度に 1 つの特徴ベクトル (別名記述子または点) を索引付けする方法は次のとおりです。

/** Add a feature to the table
 * @param value the value to store for that feature
 * @param feature the feature itself
 */
void add(unsigned int value, const ElementType* feature) {...}

注: このbuildIndexImplメソッドは、単純に機能を繰り返し処理する代替バージョンを使用し、それぞれで上記のメソッドを呼び出します。

ご覧のとおり、このメソッドにはペアである 2 つの引数があります(ID, descriptor)。

  1. valueこれはunsigned int、特徴ベクトルの一意の数値識別子 (別名特徴インデックス)を表します
  2. feature特徴ベクトルそのものを表す

実装を見ると、最初のステップは、記述子の値をハッシュして、関連するバケット キー (= この記述子 ID が格納されるバケットを指すスロットの識別子) を取得することであることがわかります。

BucketKey key = getKey(feature);

実際には、getKeyハッシュ関数はバイナリ記述子、つまり次の配列として表すことができる記述子に対してのみunsigned char実装されます。

// Specialization for unsigned char
template<>
inline size_t LshTable<unsigned char>::getKey(const unsigned char* feature) const {...}

LSHがバイナリ機能に使用されているためでしょうか？

はい: 上記のように、FLANN LSH の実装は、バイナリ記述子のハミング空間で機能します。

実際の値を持つ記述子を使用する場合 ( R**d) 、ハミング空間とハッシュ関数を使用するために特徴ベクトルをバイナリ文字列に変換する方法の詳細が記載されている元の論文を参照する必要があります。

この場合、誰かが unsigned int の使用の可能性についてもっと共有できますか? 各機能に 0 と 1 しか必要ないのに、なぜ unsigned int なのですか?

上記を参照してください。unsigned int値は、各特徴ベクトルの関連 ID を格納するためにのみ使用されます。

于 2013-01-13T20:24:13.247 に答える