Mise en œuvre PCL KD-tree extrêmement lente
j'utilise la bibliothèque Point Cloud (PCL) basée sur l'implémentation C++ de la recherche du plus proche voisin(nn) de l'arbre kd. L'ensemble de données contient environ 2,2 millions de points. Je cherche NN points pour chaque autre point. Le rayon de recherche est fixé à 2.0. Entièrement calculer, il faut environ 12 heures! J'utilise windows 64 bit machine avec 4 Go de RAM. Est-ce très commun pour la recherche d'arbres kd? Je me demande s'il existe une autre bibliothèque c++ pour les données 3D point cloud, ce qui est plus rapide. J'ai entendu parler D'ANN c++ bibliothèque et CGAL, mais je ne sais pas à quelle vitesse ceux-ci sont.
1 réponses
en bref:
Vous ne pouvez être sûr que si vous exécutez vous-même les mesures de temps.
vous devez vous assurer si la bibliothèque NN est plus rapide que la force brute, ce qui est probablement le cas pour vos données.
Comme anderas mentionnées dans le commentaire, le rayon de recherche joue également un rôle important. Si beaucoup de points tombent dans le rayon de recherche, la recherche peut devenir vraiment lente.
réponse complète:
3 dimensions ne sont pas beaucoup. Le problème se produit en raison du nombre de points que vous avez.
ANN signifie recherche du voisin le plus proche. Il est très courant d'accepter le compromis entre la précision et la vitesse lorsqu'il s'agit de NNS (recherche du voisin le plus proche).
cela signifie que vous effectuez la recherche plus rapidement, mais vous ne pouvez pas trouver le NN exact, mais un proche (par exemple pas le point le plus proche, mais le deuxième plus proche et ainsi de suite). Plus de vitesse signifie moins de précision et vice versa.
CGAL a aussi un paramètre epsilon, qui signifie précision (ε = 0 signifie pleine précision). CGAL est destiné à aller jusqu'à 3 dimensions, donc vous pouvez lui donner une chance.
je pourrais juste me tester et poster les réponses. Cependant, ce ne serait pas sûr à 100%, puisque les points que vous avez peuvent avoir une certaine relation. Il est très important pour la performance de la bibliothèque, si elle va exploiter la relation les points (peut) ont à l'autre.
autre facteur à prendre en compte, facilité d'installation.
CGAL est difficile à installer. Quand je l'ai fait, j'ai suivi ces . ANN est facile à installer. Je vous suggère également de jeter un oeil à la géométrie de BOOST, qui peut être utile.
FLANN est aussi un joueur fort dans le domaine, mais je ne suggérerais pas il, car il est destiné à traiter des ensembles de données de dimensions beaucoup plus grandes (comme 128 par exemple).
....
OK je l'admets, je suis maintenant curieux moi-même et je vais faire quelques tests!
....
ANN
(Je ne Poste pas le code, de sorte que la réponse ne devient pas trop grande. Il y a des exemples dans la documentation, et vous pouvez demander bien sûr, si vous voulez!). Sortie:
/ / pour une bouteille Klein
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
Pour ε = 0.1 j'ai eu:
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
// pour un 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
remarquez la différence dans l'accélération! Cela a à voir avec la nature des ensembles de données, comme expliqué ci-dessus (la relation les points ont).
CGAL:
/ / bouteille Klein
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
// Sphere
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 est plus claire, plus rapide que CGAL pour mes tests, c'est probablement pour le vôtre aussi!
Une note:
vous demandez en fait le NN de chaque point. Cependant, la bibliothèque ne le sait pas et ne tient pas compte des travaux antérieurs effectués pour chaque point, ce qui est dommage. Cependant, je n'ai connaissance d'aucune bibliothèque qui fasse cela.