nearest-neighbor - PCL kd-tree 实现速度极慢

Question

我正在使用基于点云库 (PCL) 的 kd-tree 最近邻 (NN) 搜索的 C++ 实现。该数据集包含约 220 万个点。我正在为每个其他点搜索 NN 点。搜索半径设置为 2.0。要完全计算它，大约需要 12 个小时!我使用的是带有 4GB RAM 的 Windows 64 位机器。 kd-tree 搜索很常见吗？不知道有没有其他c++库用于3D点云数据，速度更快。我听说过 ANN C++ 库和 CGAL，但不确定它们有多快。

Answer 1

简而言之:

您只能确定是否自己运行时间测量。

您应该确保 NN 库是否比蛮力更快，这可能是您的数据的情况。

正如安德拉斯在评论中提到的，搜索半径也起着重要作用。如果很多点落在搜索半径内，搜索会变得非常缓慢。

完整答案:

3维并不多。问题的发生是由于您拥有的点数。

ANN 代表近似最近邻搜索。当涉及到 NNS(最近邻搜索)时，接受准确性和速度之间的权衡是很常见的。

这意味着您可以更快地执行搜索，但您可能找不到确切的 NN，而是一个接近的 NN(例如，不是最近的点，而是第二个最近的点，依此类推)。更高的速度意味着更低的准确性，反之亦然。

CGAL 还有一个参数 epsilon，代表精度(ε = 0 表示完全精度)。 CGAL 旨在达到 3 维，因此您可以试一试。

我可以测试自己并发布答案。但是，这不会是 100% 安全的，因为您拥有的积分可能有一些关系。如果要利用点(可能)彼此之间的关系，这对于库的性能非常重要。

另一个需要考虑的因素，安装的简易性。

CGAL 很难安装。当我这样做时，我遵循了 these 步骤。
ANN 易于安装。
我还建议您看一下 BOOST Geometry，它可能会派上用场。

FLANN 在该领域也是一个强大的参与者，但我不建议这样做，因为它旨在处理更大维度的数据集(例如 128)。

....

好吧，我承认，我现在对自己很好奇，我要进行一些测试!

....

人工神经网络

(我没有发布代码，所以答案不会太大。文档中有示例，如果您愿意，当然可以询问!)。
输出:

//对于克莱因瓶

samaras@samaras-A15:~/Inria/nn_libs/ANN/ann_1.1.2/code$ g++ main.cpp -O3 -I ../include/ -L../lib -lANN -std=c++0x -o myExe
samaras@samaras-A15:~/Inria/nn_libs/ANN/ann_1.1.2/code$ ./myExe
N = 1000000
D = 3
ε = 0 // full accuracy
Misses: 0
creation of the tree took 1.06638 seconds.
Brute force for min: 0.009985598 seconds.
NN for 0.0           0.000078551 seconds.
Speedup of ANN for NN = 8.721533780

对于 ε = 0.1 我得到:

Misses: 1000
creation of the tree took 0.727613 seconds.
Brute force for min: 0.006351318 seconds.
NN for 0.0           0.000004260 seconds.
Speedup of ANN for NN = 8.678169573

//对于一个 shpere

ε = 0
Misses: 0
creation of the tree took 1.28098 seconds.
Brute force for min: 0.006382912 seconds.
NN for 0.0           0.000022341 seconds.
Speedup of ANN for NN = 4.897436311

ε = 0.1
Misses: 1000
creation of the tree took 1.25572 seconds.
Brute force for min: 0.006482465 seconds.
NN for 0.0           0.000004379 seconds.
Speedup of ANN for NN = 5.144413371

注意加速的差异!这与数据集的性质有关，如上所述(点之间的关系)。

CGAL:

//克莱因瓶

samaras@samaras-A15:~/code/NN$ ./myExe
ε = 0
SplitingRule = Sliding_midpoint, N = 1000000, D = 3
creation of the tree took 0.02478 seconds.
Tree statistics:
Number of items stored: 1000000
Number of nodes: 471492
 Tree depth: 34
0x80591e4
Brute force for min: 0.007979495 seconds.
NN for 0.0           0.008085704 seconds.
Speedup of cgal for NN = 0.983849423

ε = 0.1
SplitingRule = Sliding_midpoint, N = 1000000, D = 3
creation of the tree took 0.02628 seconds.
Tree statistics:
Number of items stored: 1000000
Number of nodes: 471492
 Tree depth: 34
0x80591e4
Brute force for min: 0.007852951 seconds.
NN for 0.0           0.007856228 seconds.
Speedup of cgal for NN = 0.996250305

//球体

samaras@samaras-A15:~/code/NN$ ./myExe
ε = 0
SplitingRule = Sliding_midpoint, N = 1000000, D = 3
creation of the tree took 0.025502 seconds.
Tree statistics:
Number of items stored: 1000000
Number of nodes: 465002
 Tree depth: 32
0x80591e4
Brute force for min: 0.007946504 seconds.
NN for 0.0           0.007981456 seconds.
Speedup of cgal for NN = 0.992449817


samaras@samaras-A15:~/code/NN$ ./myExe
ε = 0.1
SplitingRule = Sliding_midpoint, N = 1000000, D = 3
creation of the tree took 0.025106 seconds.
Tree statistics:
Number of items stored: 1000000
Number of nodes: 465002
 Tree depth: 32
0x80591e4
Brute force for min: 0.008115519 seconds.
NN for 0.0           0.008117261 seconds.
Speedup of cgal for NN = 0.996702679

对于我的测试，ANN 比 CGAL 更清晰，可能也适用于您的测试!

旁注:

你实际上要求每个点的神经网络。但是，图书馆不知道这一点，也没有考虑到之前对每个点所做的​​工作，这很遗憾。但是，我不知道有任何图书馆这样做。