voisin le plus proche - k-d tree - preuve de wikipedia

Question

Dans entrée Wikipedia pour les arbres kd , un algorithme est présenté pour faire une recherche de voisin le plus proche sur un arbre de kd. Ce que je ne comprends pas, c’est l’explication de l’étape 3.2. Comment savez-vous qu'il n'y a pas de point plus proche simplement parce que la différence entre la coordonnée de division du point de recherche et le nœud actuel est supérieure à la différence entre la coordonnée de division du point de recherche et le meilleur actuel?

  

Recherche du voisin le plus proche Animation de   NN recherche avec un arbre KD en 2D

     

L'algorithme du plus proche voisin (NN)   vise à trouver le point dans l'arbre   qui est le plus proche d'une entrée donnée   point. Cette recherche peut être faite   efficacement en utilisant l'arbre   propriétés pour éliminer rapidement les grandes   des parties de l'espace de recherche.   Rechercher un voisin proche dans un   kd-tree procède comme suit:

     

  
1. À partir du nœud racine, l'algorithme descend dans l'arborescence.   récursivement, de la même manière qu'il   serait si le point de recherche étaient   inséré (c'est-à-dire qu'il va à droite ou à gauche   selon que le point est   supérieur ou inférieur au nœud actuel   dans la dimension scindée).
  
2. Une fois que l'algorithme atteint un nœud feuille, il enregistre ce point en tant que   le "meilleur actuel"
  
3. L’algorithme défait la récursion de l’arbre en effectuant la   les étapes suivantes à chaque noeud:        1. Si le noeud actuel est plus proche que le meilleur actuel, alors il   devient le meilleur actuel.        2. L’algorithme vérifie s’il peut y avoir des points sur   de l'autre côté du plan de fractionnement   qui sont plus proches du point de recherche   que le meilleur actuel. En concept,   cela se fait en coupant la   fractionnement hyperplan avec un   hypersphère autour du point de recherche   qui a un rayon égal au courant   distance la plus proche. Depuis le   les hyperplans sont tous alignés les uns sur les autres cette   est mis en œuvre à titre de comparaison simple   pour voir si la différence entre   la coordonnée de division de la recherche   le point et le noeud actuel est inférieur à   la distance (coordonnées globales)   du point de recherche au courant   meilleur.              1. Si l'hypersphère traverse l'avion, il pourrait y avoir   des points plus proches de l'autre côté de la   avion, donc l'algorithme doit descendre   l'autre branche de l'arbre de la   noeud actuel à la recherche de plus près   points, en suivant le même récursif   traiter comme la recherche entière.              2. Si l'hypersphère ne coupe pas le plan de division,   alors l'algorithme continue à marcher   l'arbre, et la branche entière sur   l'autre côté de ce noeud est   éliminé.
  
4. Lorsque l'algorithme termine ce processus pour le nœud racine, le   la recherche est terminée.
  

     

Généralement, l'algorithme utilise le carré   distances à comparer pour éviter   calcul des racines carrées. Aditionellement,   il peut sauver le calcul en tenant le   courant carré meilleure distance dans un   variable pour comparaison.

Answer 1

Regardez attentivement la 6ème image de la animation sur cette page. .

Alors que l'algorithme remonte la récursion, il est possible qu'il y ait un point plus proche de l'autre côté de l'hyperplan sur lequel il se trouve. Nous avons vérifié une moitié, mais il pourrait y avoir un point encore plus proche sur l'autre moitié.

Eh bien, il s'avère que nous pouvons parfois faire une simplification. S'il est impossible qu'il y ait un point sur l'autre moitié plus proche que notre meilleur point (le plus proche), nous pouvons alors ignorer complètement cet hyperplan. Cette simplification est celle illustrée à la 6ème image.

Pour déterminer si cette simplification est possible, vous devez comparer la distance entre l'hyperplan et notre emplacement de recherche. Étant donné que l'hyperplan est aligné sur les axes, la ligne la plus courte qui le relie à un autre point est une ligne le long d'une dimension. Nous pouvons donc comparer uniquement les coordonnées de la dimension divisée par l'hyperplan.

Si le point de recherche par rapport à l'hyperplan est plus éloigné que le point de recherche par rapport au point le plus proche, il n'y a aucune raison de rechercher au-delà de cette coordonnée de fractionnement.

Même si mon explication ne m'aide pas, le graphique le sera. Bonne chance dans votre projet!

Answer 2

Oui, la description de la recherche NN (le plus proche voisin) dans un arbre KD sur Wikipedia est un peu difficile à suivre. Cela n'aide en rien qu'un lot des meilleurs résultats de recherche Google sur les recherches NN KD Tree soient tout simplement faux!

Voici du code C ++ pour vous montrer comment bien faire les choses:

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);
        }
    }
}

API de recherche NN sur un arbre KD:

// 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;
}

Fonction de distance par défaut:

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);
}

Modifier: certaines personnes demandent également de l’aide pour les structures de données (et pas seulement pour l’algorithme NN). Voici donc ce que j’ai utilisé. Selon votre objectif, vous voudrez peut-être modifier légèrement les structures de données. (Remarque: mais vous ne voudrez certainement pas modifier l'algorithme NN.)

Classe KDPoint:

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;
};

Classe 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;
};

Classe KDTree: (Remarque: vous devrez ajouter une fonction membre pour construire / remplir votre arbre.)

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;
};