最近的邻居-k-d树-Wikipedia证明 [英] nearest neighbor - k-d tree - wikipedia proof

问题描述

在 kd树的维基百科条目中，提出了一种算法在kd树上进行最近的邻居搜索.我不理解的是步骤3.2的解释.您怎么知道没有一个更近的点，仅仅是因为搜索点和当前节点的分割坐标之间的差大于搜索点和当前节点的分割坐标之间的差?

On the wikipedia entry for k-d trees, an algorithm is presented for doing a nearest neighbor search on a k-d tree. What I don't understand is the explanation of step 3.2. How do you know there isn't a closer point just because the difference between the splitting coordinate of the search point and the current node is greater than the difference between the splitting coordinate of the search point and the current best?

最近的邻居搜索的动画 用2D KD树进行NN搜索

Nearest neighbor search Animation of NN searching with a KD Tree in 2D

最近邻居(NN)算法 旨在在树上找到要点 最接近给定输入 观点.可以完成此搜索 通过使用树来有效地 快速消除大尺寸的特性 搜索空间的一部分. 在一个位置搜索最近的邻居 kd-tree进行如下操作:

The nearest neighbor (NN) algorithm aims to find the point in the tree which is nearest to a given input point. This search can be done efficiently by using the tree properties to quickly eliminate large portions of the search space. Searching for a nearest neighbor in a kd-tree proceeds as follows:

1. 从根节点开始，算法向下移动树 递归地，以相同的方式 如果搜索点是 插入(即它向右或向左移动 取决于要点是 大于或小于当前节点 在分割尺寸中).
2. 算法到达叶节点后，将该节点点保存为 目前最好的"
3. 该算法展开树的递归，执行 在每个节点上执行以下步骤: 1.如果当前节点比当前最佳节点更近，则它 成为目前最好的. 2.算法检查是否有任何点 分裂平面的另一侧 靠近搜索点 比目前最好的.在概念上 这是通过相交 用 搜索点周围的超球 半径等于当前 最近的距离.自从 超平面都是轴向对齐的 被实现为一个简单的比较 看两者之间是否有区别 搜索的分割坐标 点和当前节点小于 距离(整体坐标) 从搜索点到当前 最好. 1.如果超球面越过飞机，则可能是 另一侧的较近点 平面，因此算法必须向下移动 树的另一分支 当前节点寻找更近 点，遵循相同的递归 整个搜索过程. 2.如果超球面不与分裂平面相交， 然后算法继续走 在树上，整个树枝都在 该节点的另一侧是 被淘汰.
4. 算法完成根节点的此过程后， 搜索完成.

1. Starting with the root node, the algorithm moves down the tree recursively, in the same way that it would if the search point were being inserted (i.e. it goes right or left depending on whether the point is greater or less than the current node in the split dimension).
2. Once the algorithm reaches a leaf node, it saves that node point as the "current best"
3. The algorithm unwinds the recursion of the tree, performing the following steps at each node: 1. If the current node is closer than the current best, then it becomes the current best. 2. The algorithm checks whether there could be any points on the other side of the splitting plane that are closer to the search point than the current best. In concept, this is done by intersecting the splitting hyperplane with a hypersphere around the search point that has a radius equal to the current nearest distance. Since the hyperplanes are all axis-aligned this is implemented as a simple comparison to see whether the difference between the splitting coordinate of the search point and current node is less than the distance (overall coordinates) from the search point to the current best. 1. If the hypersphere crosses the plane, there could be nearer points on the other side of the plane, so the algorithm must move down the other branch of the tree from the current node looking for closer points, following the same recursive process as the entire search. 2. If the hypersphere doesn't intersect the splitting plane, then the algorithm continues walking up the tree, and the entire branch on the other side of that node is eliminated.
4. When the algorithm finishes this process for the root node, then the search is complete.

通常算法使用平方 避免比较的距离 计算平方根.此外， 它可以通过保存 当前最佳距离的平方 变量进行比较.

Generally the algorithm uses squared distances for comparison to avoid computing square roots. Additionally, it can save computation by holding the squared current best distance in a variable for comparison.

推荐答案

仔细查看当算法返回递归时，有可能在其所在的超平面的另一侧有一个较近的点.我们已经检查了一半，但另一半可能还要更近一点.

As the algorithm is going back up the recursion, it is possible that there is a closer point on the other side of the hyperplane that it's on. We've checked one half, but there could be an even closer point on the other half.

嗯，事实证明我们有时可以简化一下.如果在另一半上比我们当前的最佳(最近)点更近的点是不可能，那么我们可以完全跳过该超平面的一半.这种简化是在第6帧上显示的.

Well, it turns out we can sometimes make a simplification. If it's impossible for there to be a point on the other half closer than our current best (closest) point, then we can skip that hyperplane half entirely. This simplification is the one shown on the 6th frame.

通过比较超平面到我们搜索位置的距离来确定这种简化是否可行.由于超平面与轴对齐，因此从超平面到任何其他点的最短直线将沿着一个尺寸的直线，因此我们可以仅比较超平面所分割的尺寸的坐标.

Figuring out whether this simplification is possible is done by comparing the distance from the hyperplane to our search location. Because the hyperplane is aligned to the axes, the shortest line from it to any other point will a line along one dimension, so we can compare just the coordinate of the dimension that the hyperplane splits.

如果从搜索点到超平面的距离比从搜索点到您当前的最近点的距离更远，则没有理由搜索超出该分裂坐标的地方.

If it's farther from the search point to the hyperplane than from the search point to your current closest point, then there's no reason to search past that splitting coordinate.

即使我的解释无济于事，该图形也可以.祝您项目顺利！

Even if my explanation doesn't help, the graphic will. Good luck on your project!

这篇关于最近的邻居-k-d树-Wikipedia证明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！