PCL kd-tree实施非常慢 [英] PCL kd-tree implementation extremely slow
问题描述
我正在使用基于点云库(PCL)的C ++实现的kd树最近邻居(NN)搜索.该数据集包含约220万个点.我正在为每一个其他点搜索NN点.搜索半径设置为2.0.要完全计算，大约需要12个小时！我正在使用具有4GB RAM的Windows 64位计算机. kd树搜索是否很常见?我想知道是否还有用于3D点云数据的其他c ++库，这种库速度更快.我听说过ANN C ++库和CGAL，但不确定这些速度有多快.
I am using Point Cloud Library (PCL) based C++ implementation of kd-tree nearest neighbour(NN) searching. The data set contains about 2.2 million points. I am searching NN points for every other point. The search radius is set at 2.0. To fully compute that, it takes about 12 hours! I am using windows 64 bit machine with 4GB RAM. Is it very common for kd-tree searching? I wonder if there is any other c++ library for 3D point cloud data, which is faster. I heard about ANN C++ library & CGAL, but not sure how fast these are.
推荐答案
简而言之:
您只能确定自己是否进行时间测量.
You can only be sure if you run yourself the time measurements.
您应该确保NN库是否比蛮力要快，这可能就是您的数据的情况.
You should ensure if the NN library is faster over brute force, which probably is the case for your data.
正如评论中提到的安德拉斯(Anderas)，搜索半径也起着重要作用.如果很多点落在搜索半径内，搜索可能会变得很慢.
As anderas mentioned in the comment, the search radius plays also a significant role. If a lot of points fall into the search radius, the search can become really slow.
完整答案:
3个维度并不多.发生此问题是由于您拥有的积分数.
3 dimensions are not much. The problem occurs due to the number of points you have.
ANN代表近似最近邻居搜索.在涉及NNS(最近邻搜索)时，通常会接受准确性和速度之间的权衡.
ANN stands for approximate nearest neighbour searching. It is very common to accept the trade-off between accuracy and speed when it comes to NNS (Nearest Neighbour search).
这意味着您可以更快地执行搜索，但是您可能找不到确切的NN，而是找到一个接近的NN(例如，不是最近的点，而是第二个最近的点，依此类推).更高的速度意味着更低的精度，反之亦然.
This means that you perform the search faster, but you may not find the exact NN, but a close one (for example not the closest point, but the second closest one and so on). More speed means less accuracy and vice versa.
CGAL还有一个参数epsilon，代表精度(ε= 0表示完全精度). CGAL可以处理3个维度，因此您可以尝试一下.
CGAL has also a parameter epsilon, which stands for accuracy (ε = 0 means full accuracy). CGAL is meant to go till 3 dimensions, so you could give it a shot.
我可以测试一下自己并发布答案.但是，这并不是100％安全的，因为您拥有的要点可能有一定关系.如果要利用这些点(可能)彼此之间的关系，对于库的性能非常重要.
I could just test myself and post the answers. However, this would not be 100% safe, since the points you have may have some relation. It is very important for the performance of the library, if it is going to exploit the relation the points (may) have to each other.
要考虑的另一个因素是安装的简便性.
Another factor to take into account, easiness of installation.
CGAL很难安装.完成此操作后，我遵循了这些步骤. 人工神经网络易于安装. 我还建议您看一下BOOST Geometry，它可能会派上用场.
CGAL is hard to install. When I did it, I followed these steps. ANN is easy to install. I would also suggest you to take a look at BOOST Geometry, which may come in handy.
FLANN也是该领域的佼佼者，但我不建议这样做，因为FLANN可以处理更大尺寸的数据集(例如128个).
FLANN is also a strong player in the field, but I would not suggest it, since it's meant to handle datasets of much bigger dimensions (like 128 for example).
....
好吧，我承认，我现在很好奇我自己，我要进行一些测试！
OK I admit it, I am now curious myself and I am going to run some tests!
....
人工神经网络
(我没有发布代码，所以答案不会太大.文档中有示例，您当然可以问是否要！). 输出:
(I am not posting the code, so that the answer is not getting too big. There are examples in the documentation and you can ask of course if you want!). Output:
//对于一个克莱因瓶
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
请注意加速差异！如上所述，这与数据集的性质有关(点之间的关系).
Notice the difference in the speedup! This has to do with the nature of the datasets, as explained above (the relation the points have).
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更清晰，可能也适用于您！
ANN is clearer faster than CGAL for my tests, probably it is for yours too!
旁注:
您实际上在询问每个点的NN.但是，图书馆不知道这一点，也没有考虑到以前在每个方面所做的工作，这很可惜.但是，我不知道有哪个库可以做到这一点.
You actually asking for the NN of every point. However, the library doesn't know that and doesn't take into account the previous work done for every point, which is a pity. However, I am not aware of any library that does this.
这篇关于PCL kd-tree实施非常慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
