問題タブ [approximate-nn-searching]

特徴記述子 [SIFT、SURF など] を使用する場合 - 近似最近傍は画像間のマッチングを行うための最速の方法ですか?

100 次元空間に 500,000 点のデータベースがあり、最も近い 2 点を見つけたいと考えています。どうすればいいのですか？

更新: スペースはユークリッドです。申し訳ありません。そして、すべての答えに感謝します。ところで、これは宿題ではありません。

アイテムが 3 次元空間で別のアイテムに十分に近いかどうかを調べる STL マップを作成したいと考えています。これまでのところ、私の "less-than-functor" は非常にうまく機能しており、次のリンクに貼り付けられています。

現在、この問題は「最近傍」問題ではありません。むしろ「少し離れたところに隣人がいるか」という問題です。

私の例は、単一の次元を示しています。わかりやすくするために、Y/Z 寸法をスキップしました。

これまでの私の試み：

まれに、つまり、非常にまれですが、位置が重複している場合に、マップが一致するエントリを見つけられないことがあります。

まだSTLコンテナを使用していますが、これを実装するためにもっとうまくできることはありますか?

私は、128 次元記述子との特徴マッチングを実行するコードに取り組んでいます。

画像のすべての記述子は std::vector に格納されます。ここで InterestPoint には記述子ベクトルであるメンバー *double desc が含まれます。

次に、Flann マトリックスでこの構造を使用して、後で近似最近傍フィーチャ マッチングを実行します。これを次のように初期化します。

この flann::Matrix を ip1 ベクトルのすべての要素の *double desc メンバーで満たすにはどうすればよいですか? これは私が試したものです：

コンパイルしましたが、うまくいきませんでした。flann は、演算子 [] を使用して、flann::Matrix のすべての行にアクセスする方法を提供します。したがって、Matrix クラスは行優先です。

前もって感謝します、

私が解決しようとしている問題は、この質問で説明されています: O(1) でプレフィックス ツリーを使用して、単一の最近傍を検索しますか?

私の質問は、その質問ページの提案された解決策セクションに関するものです。そのセクションでは、ノードから開始してツリーをトラバースすることにより、各プレフィックス ツリーから最近傍を見つけることが言及されています。プレフィックスツリーにキーが存在するかどうかを調べるのは簡単ですが、最も類似したキーを取得することはまったくわかりません。これを達成する方法は？

誰かがこれを私に説明してくれたらいいのにと思いますが、グラフィックではない場合 (これが好ましいです)、少なくともいくつかの詳細を説明してください。

編集：

これが論文のコードです。これは Python で書かれていますが、残念ながら私は Python を使ったことがありません。誰かが python に精通していて、コードを検索して、プレフィックス ツリーを使用して最近傍を見つける方法を確認できる場合。https://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/nearest_neighbor_lsh.py

https://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/classes.py

コースのスライドから、次のことがわかりました。

R^D のセット P とクエリ ポイント q を考えると、NN は P のポイント p_0 です。

同様に、近似係数が 1 > ε > 0 の場合、ε-NN は p_0 であり、次のようになります。

(なぜ ε が 1 にならないのだろうか)。

KD ツリーを構築し、次のアルゴリズムを使用して NN を検索します。 これは、私の考えとテストの限りでは正しいです。

近似最近傍検索 (ANNS) を実行するには、上記のアルゴリズムをどのように変更すればよいですか?

私の考えでは、現在のベスト (リーフの更新部分) を ε で​​乗算し、残りのアルゴリズムはそのままにしておくことです。ただし、これが正しいかどうかはわかりません。誰か説明できますか？

PS - NN の検索の仕組みを理解しています。

Computer Science のサイトで質問したのに、何も得られなかったことに注意してください。

I have read few sources on VP-tree for similarity knn. No one wrote about adding an element to exists tree, which is required for maintenance. Explanation of adding element will be just great.