问题标签 [kdtree]

我遇到了最近邻算法的实现，用于查找两个相似图像中某些关键点之间的匹配。关键点由 SIFT 算法生成。这些点由一个 128 维向量描述，并且在两幅图像中都有很多这样的点。

匹配算法使用最近邻搜索，并且对于一幅图像中的每个点，计算另一幅图像中对应的最近点。“接近度”由点的向量之间的最小欧几里德距离来描述。通过仅采用距离低于某个阈值的那些点对来选择最佳匹配。

然而，我遇到的实现将一个图像中关键点的所有矢量与另一图像中的矢量相乘，从而形成一个产品矩阵。然后它会找到乘积高于给定阈值的点。

这个实现给出了正确的结果，但我想知道它是如何工作的。它是使用向量之间的相关性作为度量还是这里发生了其他事情。

我曾经使用KD-tree(libkdtree++)来存储一个多维数据集，这里的要求是这个数据集可以支持不同维度的top-k/range查询。例如，KDTree<3, Point> 树：查找具有最高 Point[1]（y 轴）值的前 100 个点。

从 libkdtree++ 的实现来看，类似的是“find_within_range”函数，但是它是根据“曼哈顿距离”计算的，这里等于 max(x_dist, max(y_dist, z_dist))。如何只在一维上使用范围查询？

在试图弄清楚如何在 OpenGL/GLSL 中实现 kd-tree 一天之后，我感到非常沮丧......

我在 GLSL 中这样声明我的 KD 节点：

SplitPoint 保存 kd-tree 分裂点，向量的第四个元素保存 splitDirection 在 3d 空间中形成一个平面。DataPtr 当前仅在树的叶子中保存随机值。

整个数组形成一个Ahnentafel List。

在 C++ 中，结构如下所示：

我相信这是正确的，我将构建的树上传到缓冲区中。作为检查，我将缓冲区映射到主内存并检查值：

到目前为止看起来不错（它实际上表示体积在节点 0 的 y 方向上在 (0,256,0) 处拆分，-1 是没有数据的标志）。

现在对于树遍历，我尝试了这个：

此时屏幕上应该有一个随机颜色的图案。但在大多数情况下，什么都看不到。

我试图直接从节点获取值并获得正确的结果......所以我相信统一块数据的动态索引有问题。

我希望有人可以在这里帮助我......因为我的想法不多了：/

弗洛里安

What is a range query over a kdtree and how is it done by python?

给定一组数据点，在它们之上创建一个kdtree，但是这个 kdtree 是唯一的吗？

我和我的朋友正在开发一个分布式 KD-tree 项目，并考虑到位置感知服务的应用程序。

谁能指出与此相关的论文？

谢谢

我知道 kd-trees 传统上用于存储点，但我想存储线。用kd-tree的分割在每个交叉点分割线会更好吗？还是仅将端点存储到 kd 中就可以找到最近的邻居？

我正在尝试构建 KD 树（静态案例）。我们假设点在 x 和 y 坐标上都排序。

对于均匀的递归深度，该集合被分成两个子集，垂直线穿过中值 x 坐标。

对于奇数递归深度，该集合被分成两个子集，水平线穿过中值 y 坐标。

中位数可以根据 x / y 坐标从排序集中确定。我在每次拆分集合之前执行此步骤。而且我认为它会导致树的构建缓慢。

1. 请你能帮我检查一下并优化代码吗？
2. 我找不到第 k 个最近的邻居，有人可以帮我写代码吗？

非常感谢您的帮助和耐心...

请看示例代码：

我正在从事一个个人项目，以在 C++ 中实现二维 kd-tree 构造算法。
我知道有些库已经这样做了，但我想获得 C++ 编程方面的经验
（如果你有个人项目要展示，这有助于简历）

输入：点数和点本身（可以从命令行读取输入）

我希望它在 O(n log n) 时间内运行，可以这样做吗，如果可以的话，有人可以提供一些伪代码来帮助我开始，在此先感谢。

我查看了 KD-tree 和 R-tree 的定义。在我看来，它们几乎是一样的。

KD树和R树有什么区别？