PCL kd-tree实现极其缓慢

Question

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

Answer 1

简而言之：

您只能确定自己进行时间测量。

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

正如评论中的安德拉斯（Anderas）所述，搜索半径也起着重要作用。如果很多点落在搜索半径内，搜索可能会变得很慢。

完整答案：

3个尺寸不多。出现此问题是由于您拥有的积分数。

ANN代表近似最近邻居搜索。当涉及到NNS（最近邻居搜索）时，通常要接受准确性和速度之间的权衡。

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

CGAL还有一个参数epsilon，代表精度（？= 0表示完全精度）。CGAL可以处理3个维度，因此您可以尝试一下。

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

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

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

FLANN也是该领域的佼佼者，但我不建议这样做，因为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

//拍一拍

? = 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。但是，图书馆不知道这一点，也没有考虑到以前在每个方面所做的工作，这很可惜。但是，我不知道任何执行此操作的库。