問題タブ [kdtree]

2 つの類似した画像内の特定のキーポイント間の一致を見つけるための最近傍アルゴリズムの実装に出会いました。キーポイントは、SIFT アルゴリズムによって生成されました。ポイントは 128 次元のベクトルで記述され、両方の画像にそのようなポイントが多数あります。

マッチング アルゴリズムは最近傍検索を使用し、1 つのイメージ内の各ポイントに対して、もう 1 つのイメージ内の対応する最も近いポイントを計算します。「近さ」は、ポイントのベクトル間の最小ユークリッド距離によって表されます。そのような最良の一致は、距離が特定のしきい値を下回るポイントのペアのみを取得することによって選択されます。

しかし、私が遭遇した実装では、一方の画像のキーポイントのすべてのベクトルをもう一方の画像のベクトルと乗算し、積の行列を形成します。次に、積が所定のしきい値よりも高い点を見つけます。

この実装は正しい結果をもたらしますが、それがどのように機能するか知りたいです。ベクトル間の相関をメトリックとして使用しますか、それともここで何か他のことが起こっていますか?

KD-tree(libkdtree++) を使用して多次元データ セットを格納しました。ここでの要件は、このデータ セットがさまざまな次元で上位 k/範囲クエリをサポートできることです。たとえば、KDTree<3, Point> ツリー: Point[1](y 軸) の値が最も高い上位 100 個のポイントを検索します。

libkdtree++ の実装から、似ているのは「find_within_range」関数ですが、ここでは max(x_dist, max(y_dist, z_dist)) に等しい「マンハッタン距離」に基づいてカウントされます。1 つのディメンションで範囲クエリを使用するにはどうすればよいですか?

OpenGL/GLSL で kd ツリーを実装する方法を理解しようとして 1 日を過ごした後、私はかなりイライラしています ...

GLSL で KD ノードを次のように宣言します。

SplitPoint は kd ツリーの分割点を保持し、ベクトルの 4 番目の要素は 3d 空間で平面を形成する splitDirection を保持します。DataPtr は現在、ツリーの葉にあるランダムな値のみを保持しています。

配列全体がAhnentafel Listを形成します。

C++ では、構造は次のようになります。

私はそれが正しいと信じており、構築されたツリーをバッファにアップロードします。チェックとして、バッファをメインメモリにマップし、値を調べます。

よく見えます (実際には、ノード 0 の y 方向に (0,256,0) でボリュームが分割されていると表示されます。-1 はデータがないことを示します)。

ツリートラバーサルのために、私はこれを試しました:

この時点で、画面上にランダムな色のパターンが表示されます。しかし、ほとんどの場合、目に見えるものは何もありません。

ノードから直接値を取得して正しい結果を得ようとしました...だから、均一なブロックデータの動的インデックス付けに何か問題があると思います。

誰かがここで私を助けてくれることを願っています...アイデアが不足しているため:/

フロリアン

kdtree に対する範囲クエリとは何ですか? Python ではどのように行われますか?

データ ポイントのセットを指定すると、kdtreeが作成されますが、この kdtree は一意のものですか?

友人と私は、位置認識サービスへのアプリケーションを念頭に置いて、分散KDツリーのプロジェクトに取り組んでいます。

誰かがこれに関連する論文を私たちに指摘できますか？

ありがとう

ポイントを保存するために kd-trees が伝統的に使用されていることは知っていますが、代わりにラインを保存したいと考えています。kd ツリーの分割とすべての交点で線を分割するのが最善でしょうか? または、最近傍を見つけるためにエンドポイントだけを kd-suffice に保存しますか?

KD ツリー (静的ケース) を構築しようとしています。ポイントは x 座標と y 座標の両方でソートされていると仮定します。

再帰の深さを均一にするために、セットは中央の x 座標を通る垂直線で 2 つのサブセットに分割されます。

再帰の深さが奇数の場合、セットは 2 つのサブセットに分割され、水平線は中央の y 座標を通過します。

中央値は、x / y 座標に従ってソートされたセットから決定できます。このステップは、セットを分割する前に行っています。そして、それがツリーの構築を遅らせる原因になっていると思います。

1. コードをチェックして最適化するのを手伝ってくれませんか?
2. k 番目の最近傍が見つかりません。誰かコードを手伝ってくれませんか?

あなたの助けと忍耐に感謝します...

サンプル コードを参照してください。

私は、C++ で 2 次元 kd ツリー構築アルゴリズムを実装する個人プロジェクトに取り組んでいます。
すでにこれを行っているライブラリがあることは知っていますが、C++ プログラミングの経験を積みたいです
(示す個人的なプロジェクトがある場合は、履歴書に役立ちます)。

入力: ポイントの数、およびポイント自体 (入力はコマンド ラインから読み取ることができます)

これを O(n log n) 時間で実行したいのですが、実行できますか? そうであれば、誰かが私を始めるのに役立つ疑似コードを提供してくれませんか? 事前に感謝します。

KD-tree と R-tree の定義を見てみました。それらはほとんど同じであるように私には思えます。

KD ツリーと R ツリーの違いは何ですか?