PCL kd-tree 实现极其缓慢。

Question

PCL kd-tree 实现极其缓慢。

nearest-neighborpoint-cloud-librarycgalkdtree

7

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

- ayan.c

1

我会给一个+1，因为这个问题很难。不过，下次请考虑自行测试并询问时间结果。 - gsamaras

1

你提到你的搜索半径设置为2.0。你的数据是如何分布的（例如，在XYZ方向上覆盖了哪个范围）？如果有很多点落在搜索半径内，搜索可能会变得非常缓慢。 - anderas

使用搜索半径为2.0，点的近似数量约为7-80。但是数据不是均匀分布的。最近邻点数在10-150之间变化。我认为问题不在于维度，而在于数据的分布。 - ayan.c

你打算对这个答案发表意见吗？ - gsamaras

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- gsamaras · Accepted Answer

简而言之：只有自己运行时间测量才能确定。

您应该确保NN库比蛮力更快，这可能适用于您的数据。

正如andreas在评论中提到的那样，搜索半径也起着重要作用。如果许多点落入搜索半径内，则搜索可能变得非常缓慢。

完整回答：

3个维度并不多。问题出现在您拥有的点数上。

ANN代表近似最近邻搜索。在进行最近邻搜索（NNS）时，接受精度和速度之间的权衡是非常常见的。

这意味着您可以更快地执行搜索，但可能无法找到确切的NN，而是一个接近的NN（例如不是最接近的点，而是第二接近的点等）。更快的速度意味着更少的准确性，反之亦然。

CGAL还具有一个参数epsilon，它代表准确度（ε = 0表示完全准确）。CGAL旨在进行3维，因此您可以尝试一下。

我可以测试自己并发布答案。然而，这样做并不是100%安全的，因为你所拥有的点可能会存在某种关系。如果要利用点之间（可能）存在的关系，这对于库的性能非常重要。

另一个要考虑的因素是安装的便捷性。

安装CGAL很困难。当我安装时，我按照这些步骤进行了操作。 ANN易于安装。我还建议您查看BOOST Geometry，这可能会很方便。

FLANN在该领域也是强劲的竞争者，但我不建议使用它，因为它的目的是处理更大维度的数据集（例如128）。

....

好的，我承认，我现在也很好奇，我将运行一些测试！

....

ANN

(我不会发布代码，这样答案就不会太大。文档中有示例，当然你也可以问！). 输出:

// 对于克莱因瓶

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

// 用于球体

ε = 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更清晰更快，可能对您也是如此！

一则旁注：

实际上，您要求每个点的NN。然而，该库不知道这一点，并且不考虑已为每个点完成的先前工作，这是遗憾的。但是，我不知道是否有任何库可以做到这一点。