标签: kdtree

我想比较一个图像(A)中的SURF描述符和几个其他图像(B,C,D,..)中的描述符,以找到与A最相似的图像.描述符有64个维度.

使用C#和Emgu,匹配是通过将A的描述符与B,然后是C,然后是D'等进行比较来完成的.当图像数超过10时,这非常慢,因为必须搜索许多不相关的描述符.

为了加快这个过程,正确的方法(根据文章)似乎是为(B,C,D,..)中的描述符构建一个kd树,以快速匹配在A中找到描述符.kd -tree根据级别进行尺寸分割.第一次分割由第一维度决定,第二次分割由第二维度等决定.但是,对于描述符(64),在维度数量高的情况下,使用KD树的好处变小.

所以我的问题是:使用KD树/其他方法将SURF描述符从一个图像(A)与几个图像(B,C,D ......)匹配时,您有什么经验或知识.什么运作良好,不太好,你做过这样的事情吗？

FLANN将是一个选项,因为OpenCV使用它,但我找不到C#的版本.近似最近的Neightboor也可以选择加速kd树,但这对匹配图像有效吗？

最好的问候莫滕

我正在编写一个使用kd树在二维空间中查找点的应用程序.在开发过程中,能够"看到"每个点周围的最近邻区域会很好.

在附图中,红点是kd树中的点,并且围绕每个点的蓝线限定了最近邻搜索将返回包含点的区域.

图像是这样创建的:

for each point in the space:
  da = distance to nearest neighbor
  db = distance to second-nearest neighbor
  if absolute_value(da - db) < 4:
    draw blue pixel

该算法有两个问题:

• (更重要的是)我的(相当快的Core i7)计算机速度很慢.
• (不太重要)它很草率,正如你可以看到蓝线的不同宽度.

什么是一组点的"可视化"？

有哪些好算法可以创建这样的可视化？

我将编写一个KDTree的模板化实现,现在它只能作为四叉树或八叉树用于BarnesHut实现.

这里的关键点是设计,我想指定树被定义为模板参数的维数,然后简单地声明一些常用方法,它们会自动表现出正确的方式(我认为当时需要一些模板专业化).

我想专门化模板,以便有2 ^ 2(四叉树)或2 ^ 3(八叉树)节点.

有人有一些设计理念吗？我想避免继承,因为它限制我做动态内存分配而不是静态分配.

这里N可以是2或3

template<int N>
class NTree
{
public:
    NTree<N>( const std::vector<Mass *> &);
    ~NTree<N>()
    {
       for (int i=0; i<pow(2,N); i++)
          delete nodes[i];
    }
 private:
    void insert<N>( Mass *m );
    NTree *nodes[pow(2,N)]; // is it possible in a templatized way?
};

另一个问题是四叉树有4个节点但是2维,八叉树有8个节点,但是3维,即节点数是2^dimension.我可以通过模板元编程指定吗？我想保留4号和8号,这样循环展开器可以更快.

谢谢!

有2个图像A和B.我从中提取关键点(a [i]和b [i]).
我想知道如何有效地确定[i]和b [j]之间的匹配？

我遇到的一个明显的方法是将A中的每个点与B中的每个点进行比较.但是对于大型图像数据库而言,它过于耗时.我怎样才能将a [i]与b [k]进行比较,其中k是小范围的？

我听说kd-tree可能是个不错的选择,不是吗？关于kd-tree有什么好的例子吗？

还有其他建议吗？

我想知道是否可以在创建后从 scikit-lern KD-Tree 实例中添加或删除数据点？

例如：

from sklearn.neighbors import KDTree
import numpy as np
X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
kdt = KDTree(X, leaf_size=30, metric='euclidean')

'''
Do another stuff

'''
# Then, I want to add [8,3] point to kdt without rebuilding it again
# How to remove [-2,-1] from kdt ?

我在KD-Tree文档中没有找到此类信息

我有一大堆二维点,并希望能够快速查询二维空间中任何点的k-最近邻居的集合.由于它是低维的,因此KD树似乎是一种很好的方法.我的初始数据集只会很少更新,所以查询点的时间对我来说比构建时更重要.但是,每次运行程序时,我都需要重新加载对象,因此我还需要一个可以快速保存和重新加载的结构.

现有的两个选择是SciPy和SciKit-learn中的KDTree结构.下面我分析了这两个中的两个,用于在大量列表长度上构建速度和查询速度.我还挑选了SciKit-learn结构并显示了从pickle重新加载对象的时间.这些在图中进行比较,下面包括用于生成时序的代码.

正如我在图中所示,从酸洗中加载比从头开始加载大N的半个数量级更快,这表明KDTree适合我的用例(即频繁重载但很少重新构建) ).

用于比较构建时间的代码:

# Profiling the building time for the two KD-tree structures and re-loading from a pickle
import math, timeit, pickle, sklearn.neighbors

the_lengths = [100, 1000, 10000, 100000, 1000000]

theSciPyBuildTime = []
theSklBuildTime = []
theRebuildTime = []

for length in the_lengths:
    dim = 5*int(math.sqrt(length))
    nTimes = 50
    from random import randint
    listOfRandom2DPoints = [ [randint(0,dim),randint(0,dim)] for x in range(length)]

    setup = """import scipy.spatial
import sklearn.neighbors
length = """ + str(length) + """
dim = """ + …

我试图实现KNN进行手写字符识别，结果发现执行代码要花费很多时间。当将参数leaf_size添加为值400时，我观察到代码执行所需的时间大大减少了。

原始代码：

knn = KNeighborsClassifier(n_neighbors=3)

新代码：

knn = KNeighborsClassifier(n_neighbors=3,leaf_size=400)

我读了很少的有关KDtree / Balltree的leaf_size参数的文档和文章，但是找不到有关如何安全调整此参数而又没有任何准确性和信息丢失的足够好的参考。

如果有人可以就上述问题分享一些见解，那将是非常友善的。

我提到的相关文章：
1.）http://scikit-learn.org/stable/modules/genic/sklearn.neighbors.KDTree.html
2.）https://jakevdp.github.io/blog/2013/04 / 29 / benchmarking-nearest-neighbor-searches-in-python /
3.）http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html

我正在寻找一种高性能算法，根据以下数据结构按位置、性别和年龄匹配大量人员：

• 经度（表示该人的位置）
• 纬度（表示人的位置）
• 性别（表示人的性别）
• 出生日期（表示该人的出生日期）
• LookForGender（表示该人正在寻找的性别）
• LookForMinAge（表示该人正在寻找的最低年龄）
• LookForMaxAge（表示该人正在寻找的最大年龄）
• LookForRadius（表示该人正在寻找的最大距离）
• 已处理（表示此人已经处理了哪些其他人）

对于任何人 P，算法应返回适用的候选人 C：

• C 的性别必须相同 P.LookingForGender
• P 的性别必须相同 C.LookingForGender
• C 的出生日期必须介于 P.LookingForMinAge 和 P.LookingForMaxAge 之间
• P 的出生日期必须介于 C.LookingForMinAge 和 C.LookingForMaxAge 之间
• P 和 C 之间的纬度/经度距离必须小于或等于 P.LookingForRadius
• P 和 C 之间的纬度/经度距离必须小于或等于 C.LookingForRadius
• 加工后的P不得含有C

该算法应按距离（纬度/经度）顺序返回前 100 个候选 C。该算法应该针对搜索和更新进行优化，因为人们可能经常改变他们的位置。

我目前的想法是，kd 树可能比局部敏感哈希更适合这些需求，我应该朝这个方向发展。

您对我有什么建议？我应该寻找什么？您看到什么风险？

谢谢！

更新：

• 我是否愿意牺牲空间复杂度来获得更好的时间复杂度？是的，我更愿意牺牲空间复杂性。然而，我更喜欢有一个我真正理解并且可以维护的 O(log n) 解决方案，而不是一个我无法掌握的 O(1) 解决方案:)
• 数据是否适合主存？不，不是的。数据将分布在分布式文档数据库（Azure Cosmos DB SQL API）的不同节点上。
• 您想要精确的结果还是近似的结果？近似结果是可以的，但是应该精确过滤年龄/性别。
• 在算法中添加了“已处理”，抱歉错过了！
• 人们多久改变一次位置？用户每当启动应用程序并寻找候选人时都会改变他们的位置。因此，每日活跃用户每天会更改一次或多次位置。然而，位置变化可能很小，只有几公里。在 …

问题陈述：

我在 3D 空间中有 150k 个点，它们的坐标存储在尺寸为 [150k, 3]（以毫米为单位）的矩阵中。

我想找到给定点p在半径范围内的所有邻居r。我想以最准确的方式做到这一点。

我应该如何选择我的leafsize参数？

from scipy.spatial import KDTree
import numpy as np

pts = np.random.rand(150000,3)

T1 = KDTree(pts, leafsize=20)
T2 = KDTree(pts, leafsize=1)

neighbors1= T1.query_ball_point((0.3,0.2,0.1), r=2.0)
neighbors2= T2.query_ball_point((0.3,0.2,0.1), r=2.0)

np.allclose(sorted(neighbors1), sorted(neighbors2))
True

给定一个点列表，如何在 KDTree 中获取它们的索引？

from scipy import spatial
import numpy as np

#some data
x, y = np.mgrid[0:3, 0:3]
data = zip(x.ravel(), y.ravel())

points = [[0,1], [2,2]]

#KDTree
tree = spatial.cKDTree(data)

# incices of points in tree should be [1,8]

我可以做这样的事情：

[tree.query_ball_point(i,r=0) for i in points]

>>> [[1], [8]]

这样做有意义吗？