가장 가까운 이웃 - KD 트리 -Wikipedia Proof

StackOverflow https://stackoverflow.com/questions/1627305

  •  06-07-2019
  •  | 
  •  

문제

에 KD 나무를위한 위키 백과 진입, KD 트리에서 가장 가까운 이웃 검색을 위해 알고리즘이 제공됩니다. 내가 이해하지 못하는 것은 3.2 단계의 설명입니다. 검색 지점의 분할 좌표와 현재 노드의 차이가 검색 지점의 분할 좌표와 현재 최고의 차이보다 크기 때문에 더 가까운 점이 없다는 것을 어떻게 알 수 있습니까?

2D에서 KD 트리로 검색하는 NN의 가장 가까운 이웃 검색 애니메이션

가장 가까운 이웃 (NN) 알고리즘은 주어진 입력 지점에 가장 가까운 트리의 지점을 찾는 것을 목표로합니다. 이 검색은 트리 특성을 사용하여 검색 공간의 많은 부분을 신속하게 제거하여 효율적으로 수행 할 수 있습니다. KD-Tree에서 가장 가까운 이웃을 검색하면 다음과 같이 진행됩니다.

  1. 루트 노드부터 시작하여 알고리즘은 검색 지점이 삽입되는 것과 같은 방식으로 트리를 재귀 적으로 아래로 이동합니다 (즉, 포인트가 분할 치수).
  2. 알고리즘이 리프 노드에 도달하면 해당 노드 포인트가 "현재 최고"로 저장됩니다.
  3. 알고리즘은 트리의 재귀를 풀고 각 노드에서 다음 단계를 수행합니다. 1. 현재 노드가 현재 최고보다 가까운 경우 현재 최고가됩니다. 2. 알고리즘은 분할 평면의 반대편에 현재 최고보다 검색 지점에 가까운 지점이 있는지 확인합니다. 개념적으로, 이것은 분할 하이퍼 플레인을 현재 가장 가까운 거리와 동일한 반경을 갖는 검색 지점 주위의 초기와 교차하여 수행됩니다. 하이퍼 플레인이 모두 축 정렬되기 때문에 검색 지점의 분할 좌표와 현재 노드의 차이가 검색 지점에서 현재 최고까지 거리 (전체 좌표)보다 낮은 지 여부를 확인하기 위해 간단한 비교로 구현됩니다. 1. hypersphere가 평면을 가로 지르는 경우 평면의 다른쪽에 더 가까운 지점이있을 수 있으므로 알고리즘은 현재 노드에서 트리의 다른 분기를 아래로 이동해야합니다. 전체 검색. 2. hypersphere가 분할 평면과 교차하지 않으면 알고리즘이 계속 나무를 걸어 가고 해당 노드의 다른쪽에있는 전체 분기가 제거됩니다.
  4. 알고리즘이 루트 노드 의이 프로세스를 완료하면 검색이 완료됩니다.

일반적으로 알고리즘은 제곱 거리를 사용하여 사각형 루트를 계산하지 않도록 비교합니다. 또한 비교를 위해 제곱 전류 최상의 거리를 유지하여 계산을 절약 할 수 있습니다.

도움이 되었습니까?

해결책

6 번째 프레임을주의 깊게 살펴보십시오 해당 페이지의 애니메이션.

알고리즘이 재귀를 되돌려 놓으면, 과정 평면의 다른쪽에 더 가까운 지점이있을 수 있습니다. 우리는 절반을 확인했지만 나머지 절반에는 더 가까운 지점이있을 수 있습니다.

글쎄, 우리는 때때로 단순화를 만들 수 있다는 것이 밝혀졌습니다. 그렇다면 불가능한 나머지 절반의 현재 가장 가까운 (가장 가까운) 지점보다 가까운 지점이 있기 때문에, 우리는 그 과자를 절반으로 완전히 건너 뛸 수 있습니다. 이 단순화는 6 번째 프레임에 표시된 것입니다.

이 단순화가 가능한지 여부를 알아내는 것은 하이퍼 플레인에서 검색 위치로의 거리를 비교하여 수행됩니다. 하이퍼 플레인이 축에 정렬되기 때문에, 가장 짧은 선은 다른 지점으로의 가장 짧은 선이 한 차원을 따라 줄이되므로 하이퍼 플레인이 분할하는 치수의 좌표 만 비교할 수 있습니다.

검색 지점에서 하이퍼 플레인까지 검색 지점에서 가장 가까운 지점까지 더 멀리있는 경우 해당 분할 좌표를 과거로 검색 할 이유가 없습니다.

내 설명이 도움이되지 않더라도 그래픽은 의지합니다. 프로젝트에 행운을 빕니다!

다른 팁

예, Wikipedia의 KD 트리에서 NN (가장 가까운 이웃) 검색에 대한 설명은 따라 가기가 조금 어렵습니다. 그것은 도움이되지 않습니다 많은 NN KD 트리 검색의 최고 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 알고리즘을 수정하려고합니다.)

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

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;
};
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top