16

kd treesのウィキペディアのエントリでは、kd ツリーで最近傍検索を行うためのアルゴリズムが提示されています。私が理解していないのは、ステップ 3.2 の説明です。検索ポイントと現在のノードの分割座標の差が、検索ポイントの分割座標と現在のベストの差よりも大きいという理由だけで、より近いポイントがないことをどのように知ることができますか?

最近傍探索 2D の KD ツリーを使用した NN 探索のアニメーション

Nearest Neighbor (NN) アルゴリズムは、特定の入力ポイントに最も近いツリー内のポイントを見つけることを目的としています。この検索は、ツリー プロパティを使用して検索スペースの大部分をすばやく除外することで効率的に実行できます。kd ツリー内の最近傍の検索は、次のように進みます。

  1. ルート ノードから始めて、検索ポイントが挿入された場合と同じ方法で、アルゴリズムは再帰的にツリーを下に移動します (つまり、ポイントが現在のノードよりも大きいか小さいかに応じて、右または左に移動します)。次元を分割します)。
  2. アルゴリズムがリーフ ノードに到達すると、そのノード ポイントを「現在のベスト」として保存します。
  3. アルゴリズムは、ツリーの再帰を巻き戻し、各ノードで次の手順を実行します。 1. 現在のノードが現在のベストよりも近い場合、それが現在のベストになります。2. アルゴリズムは、分割面の反対側に、現在の最適なポイントよりも検索ポイントに近いポイントがあるかどうかを確認します。概念的には、これは、現在の最も近い距離に等しい半径を持つ検索ポイントの周りの超球と分割超平面を交差させることによって行われます。超平面はすべて軸が揃っているため、これは単純な比較として実装され、検索ポイントと現在のノードの分割座標の差が、検索ポイントから現在のベストまでの距離 (全体の座標) より小さいかどうかを確認します。1. 超球が平面を横切る場合、平面の反対側により近い点がある可能性があるため、アルゴリズムは現在のノードからツリーの他のブランチを下に移動して、より近い点を探し、検索全体と同じ再帰プロセスに従います。 . 2. 超球が分割面と交差しない場合、アルゴリズムはツリーを上っていき、そのノードの反対側のブランチ全体が削除されます。
  4. アルゴリズムがルート ノードのこのプロセスを終了すると、検索が完了します。

通常、このアルゴリズムでは、平方根の計算を避けるために、比較に二乗距離が使用されます。さらに、現在の最適距離の 2 乗を変数に保持して比較することで、計算を節約できます。

4

2 に答える 2

15

そのページのアニメーションの6番目のフレームを注意深く見てください。

アルゴリズムが再帰をバックアップしているため、超平面の反対側に、それが存在するより近いポイントがある可能性があります。半分をチェックしましたが、残りの半分にはさらに近いポイントがある可能性があります。

まあ、私たちは時々単純化することができることがわかりました。現在の最良の（最も近い）点よりも残りの半分に近い点が存在することが不可能な場合は、その超平面の半分を完全にスキップできます。この簡略化は、6番目のフレームに示されているものです。

この単純化が可能かどうかを判断するには、超平面から検索位置までの距離を比較します。超平面は軸に位置合わせされているため、超平面から他の点までの最短線は1つの次元に沿った線になります。したがって、超平面が分割する次元の座標だけを比較できます。

検索ポイントから現在の最も近いポイントまでよりも検索ポイントから超平面までの距離が遠い場合は、その分割座標を超えて検索する理由はありません。

私の説明が役に立たなくても、グラフィックは役に立ちます。あなたのプロジェクトに頑張ってください！

于 2010-01-10T08:12:05.517 に答える
9

はい、ウィキペディアの KD ツリーでの NN (Nearest Neighbour) 検索の説明は、理解するのが少し難しいです。NN KD Tree 検索で上位に表示される Google 検索結果の多くが単純に間違っていることは役に立ちません。

これを正しく行う方法を示す C++ コードを次に示します。

template <class T, std::size_t N>
void KDTree<T,N>::nearest (
    const const KDNode<T,N> &node,
    const std::array<T, N> &point, // looking for closest node to this point
    const KDPoint<T,N> &closest,   // closest node (so far)
    double &minDist,
    const uint depth) const
{
    if (node->isLeaf()) {
        const double dist = distance(point, node->leaf->point);
        if (dist < minDist) {
            minDist = dist;
            closest = node->leaf;
        }
    } else {
        const T dim = depth % N;
        if (point[dim] < node->splitVal) {
            // search left first
            nearest(node->left, point, closest, minDist, depth + 1);
            if (point[dim] + minDist >= node->splitVal)
                nearest(node->right, point, closest, minDist, depth + 1);
        } else {
            // search right first
            nearest(node->right, point, closest, minDist, depth + 1);
            if (point[dim] - minDist <= node->splitVal)
                nearest(node->left, point, closest, minDist, depth + 1);
        }
    }
}

KD ツリーでの NN 検索の API:

// Nearest neighbour
template <class T, std::size_t N>
const KDPoint<T,N> KDTree<T,N>::nearest (const std::array<T, N> &point) const {
    const KDPoint<T,N> closest;
    double minDist = std::numeric_limits<double>::max();
    nearest(root, point, closest, minDist);
    return closest;
}

デフォルトの距離関数:

template <class T, std::size_t N>
double distance (const std::array<T, N> &p1, const std::array<T, N> &p2) {
    double d = 0.0;
    for (uint i = 0; i < N; ++i) {
        d += pow(p1[i] - p2[i], 2.0);
    }
    return sqrt(d);
}

編集: 一部の人々は、(NN アルゴリズムだけでなく) データ構造についても助けを求めているので、ここで私が使用したものを示します。目的によっては、データ構造を少し変更したい場合があります。(注: ただし、ほとんどの場合、NN アルゴリズムを変更したくないでしょう。)

KD ポイント クラス:

template <class T, std::size_t N>
class KDPoint {
    public:
        KDPoint<T,N> (std::array<T,N> &&t) : point(std::move(t)) { };
        virtual ~KDPoint<T,N> () = default;
        std::array<T, N> point;
};

KDNode クラス:

template <class T, std::size_t N>
class KDNode
{
    public:
        KDNode () = delete;
        KDNode (const KDNode &) = delete;
        KDNode & operator = (const KDNode &) = delete;
        ~KDNode () = default;

        // branch node
        KDNode (const T                       split,
                std::unique_ptr<const KDNode> &lhs,
                std::unique_ptr<const KDNode> &rhs) : splitVal(split), left(std::move(lhs)), right(std::move(rhs)) { };
        // leaf node
        KDNode (std::shared_ptr<const KDPoint<T,N>> p) : splitVal(0), leaf(p) { };

        bool isLeaf (void) const { return static_cast<bool>(leaf); }

        // data members
        const T                                   splitVal;
        const std::unique_ptr<const KDNode<T,N>>  left, right;
        const std::shared_ptr<const KDPoint<T,N>> leaf;
};

KDTree クラス: (注: ツリーを構築/埋めるためにメンバー関数を追加する必要があります。)

template <class T, std::size_t N>
class KDTree {
    public:
        KDTree () = delete;
        KDTree (const KDTree &) = delete;
        KDTree (KDTree &&t) : root(std::move(const_cast<std::unique_ptr<const KDNode<T,N>>&>(t.root))) { };
        KDTree & operator = (const KDTree &) = delete;
        ~KDTree () = default;

        const KDPoint<T,N> nearest (const std::array<T, N> &point) const;

        // Nearest neighbour search - runs in O(log n)
        void nearest (const std::unique_ptr<const KDNode<T,N>> &node,
                      const std::array<T, N> &point,
                      std::shared_ptr<const KDPoint<T,N>> &closest,
                      double &minDist,
                      const uint depth = 0) const;

        // data members
        const std::unique_ptr<const KDNode<T,N>> root;
};
于 2016-05-09T02:33:29.977 に答える