nanoflann
v1.6.2
Nanoflann est une bibliothèque d'en-tête C ++ 11 pour la construction d'arbres KD des ensembles de données avec différentes topologies: R 2 , R 3 (nuages ponctuels), donc (2) et donc (3) (groupes de rotation 2D et 3D). Aucun support pour NN approximatif n'est fourni. Nanoflann ne nécessite pas de compilation ou d'installation. Il vous suffit de #include <nanoflann.hpp> dans votre code.
Cette bibliothèque est une fourche de la bibliothèque Flann de Marius Muja et David G. Lowe, et née en tant que projet d'enfant de MRPT. En suivant les conditions d'origine de licence, Nanoflann est distribué sous la licence BSD. S'il vous plaît, pour les bogues, utilisez le bouton des problèmes ou la fourche et ouvrez une demande de traction.
Citez comme:
@misc{blanco2014nanoflann,
title = {nanoflann: a {C}++ header-only fork of {FLANN}, a library for Nearest Neighbor ({NN}) with KD-trees},
author = {Blanco, Jose Luis and Rai, Pranjal Kumar},
howpublished = {url{https://github.com/jlblancoc/nanoflann}},
year = {2014}
}
Voir la version Changelog pour une liste des changements de projet.
include/nanoflann.hpp pour une utilisation là où vous en avez besoin.$ sudo apt install libnanoflann-devnanoflann avec Homebrew avec: $ brew install brewsci/science/nanoflann$ brew tap brewsci/science
$ brew install nanoflann$ sudo port install nanoflannbrew install homebrew/science/nanoflannBien que Nanoflann lui-même n'ait pas à être compilé, vous pouvez construire quelques exemples et tests avec:
$ sudo apt-get install build-essential cmake libgtest-dev libeigen3-dev
$ mkdir build && cd build && cmake ..
$ make && make testParcourez la documentation Doxygen.
Remarque importante: Si les normes L2 sont utilisées, remarquez que le rayon de recherche et toutes les distances passées et retournées sont en fait des distances carrés .
knnSearch() et radiusSearch() : PointCloud_kdd_radius.cppEigen::Matrix<> : matrix_example.cppstd::vector<std::vector<T> > ou std::vector<Eigen::VectorXd> : vector_of_vectors_example.cppMakefile pour l'utilisation via pkg-config (par exemple, après avoir fait une "fabrication d'installation" ou après l'installation à partir des référentiels Ubuntu): Exemple_With_pkgConfig /mrpt-gui , par exemple sudo apt install libmrpt-gui-dev ):
Efficacité du temps d'exécution :
flann d'origine vient de la possibilité de choisir entre différents algorithmes Ann. Le coût de cette flexibilité est la déclaration de méthodes virtuelles pures qui (dans certaines circonstances) imposent des pénalités d'exécution. Dans nanoflann toutes ces méthodes virtuelles ont été remplacées par une combinaison du modèle de modèle curieusement récurrent (CRTP) et des méthodes inclinées, qui sont beaucoup plus rapides.radiusSearch() , il n'est pas nécessaire de passer un appel pour déterminer le nombre de points dans le rayon, puis de l'appeler à nouveau pour obtenir les données. En utilisant des conteneurs STL pour les données de sortie, les conteneurs sont automatiquement redimensionnés.nanoflann permet aux utilisateurs de fournir une boîte de délimitation pré-composée des données, si disponible, pour éviter la recomputation.int à size_t , ce qui supprime une limite lors de la gestion de très grands ensembles de données. Efficacité de la mémoire : au lieu de faire une copie de l'ensemble de données dans une matrice de type flann personnalisée avant de créer un index KD-Tree, nanoflann permet un accès direct à vos données via une interface d'adaptateur qui doit être implémentée dans votre classe.
Reportez-vous aux exemples ci-dessous ou à l'API C ++ de Nanoflann :: KdtreesingleIndexAdaptor <> pour plus d'informations.
::knnSearch()num_closest de query_point[0:dim-1] . Leurs indices sont stockés à l'intérieur de l'objet résultat. Voir un exemple de code d'utilisation.::radiusSearch()query_point[0:dim-1] dans un rayon maximal. La sortie est donnée sous forme de vecteur de paires, dont le premier élément est un index ponctuel et le second la distance correspondante. Voir un exemple de code d'utilisation.::radiusSearchCustomCallback()Eigen::Matrix<> Classes (matrices et vecteurs de vecteurs).R^N : espaces euclidiens:L1 (Manhattan)L2 (norme euclidienne au carré , favorisant l'optimisation SSE2).L2_Simple (norme euclidienne carrée , pour les ensembles de données de faible dimensionnalité comme les nuages ponctuels).SO(2) : groupe de rotation 2Dmetric_SO2 : Différence angulaire absolue.SO(3) : Group de rotation 3D (MEILLEUR SUPPORT à fournir dans les versions futures)metric_SO3 : produit intérieur entre les quaternions. Vous pouvez supprimer directement le fichier nanoflann.hpp dans votre projet. Alternativement, la méthode CMake Standard est également disponible:
CMAKE_INSTALL_PREFIX sur un chemin approprié, puis exécutez make install (Linux, OSX) ou créez la cible INSTALL (Visual Studio). # Find nanoflannConfig.cmake:
find_package (nanoflann)
add_executable (my_project test .cpp)
# Make sure the include path is used:
target_link_libraries (my_project nanoflann::nanoflann)conan Vous pouvez installer des binaires prédéfinis pour nanoflann ou le construire à partir de la source à l'aide de Conan. Utilisez la commande suivante pour installer la dernière version:
$ conan install --requires= " nanoflann/[*] " --build=missingPour des instructions détaillées sur la façon d'utiliser Conan, veuillez vous référer à la documentation de Conan.
La recette de nanoflann Conan est tenue à jour par les maintenseurs de Conan et les contributeurs communautaires. Si la version est obsolète, veuillez créer une demande de problème ou d'extraction sur le référentiel CongencerIndex.
vcpkgVous pouvez télécharger et installer Nanoflann à l'aide du gestionnaire de dépendance VCPKG:
$ git clone https://github.com/Microsoft/vcpkg.git
$ cd vcpkg
$ ./bootstrap-vcpkg.sh
$ ./vcpkg integrate install
$ ./vcpkg install nanoflannLe port Nanoflann de VCPKG est tenu à jour par les membres de l'équipe Microsoft et les contributeurs communautaires. Si la version est obsolète, veuillez créer une demande de problème ou d'extraction sur le référentiel VCPKG.
NANOFLANN_FIRST_MATCH : s'il est défini et deux points ont la même distance, celui avec l'index le plus bas sera renvoyé en premier. Sinon, il n'y a pas d'ordre particulier.NANOFLANN_NO_THREADS : si défini, les capacités de lecture multithre seront désactivées, afin que la bibliothèque puisse être utilisée sans lier avec PTHEADS. Si l'on essaie d'utiliser plusieurs threads, une exception sera lancée. KDTreeSingleIndexAdaptorParams::leaf_max_sizeUn kd-arbre est ... eh bien, un arbre :-). Et en tant que tel, il a un nœud racine, un ensemble de nœuds intermédiaires et enfin, des nœuds "feuilles" qui sont ceux sans enfants.
Les points (ou, correctement, les indices ponctuels) ne sont stockés que dans les nœuds de feuilles. Chaque feuille contient une liste dont les points se situent dans sa plage.
Lors de la construction de l'arbre, les nœuds sont divisés récursivement jusqu'à ce que le nombre de points à l'intérieur soit égal ou inférieur à un seuil. C'est-à-dire leaf_max_size . En faisant des requêtes, "l'algorithme d'arbre" se termine en sélectionnant les nœuds de feuilles, puis en effectuant une recherche linéaire (un par un) pour le point le plus proche de la requête dans tous ceux de la feuille.
Ainsi, leaf_max_size doit être défini comme un compromis :
Le nombre à sélectionner dépend vraiment de l'application et même de la taille de la mémoire du cache de processeur, donc idéalement, vous devriez faire du benchmarking pour maximiser l'efficacité.
Mais pour aider à choisir une bonne valeur en règle générale, je fournis les deux repères suivants. Chaque graphique représente la construction d'arbre (horizontale) et les temps de requête (verticale) pour différentes valeurs leaf_max_size entre 1 et 10k (comme des ellipses d'incertitude à 95%, déformés en raison de l'échelle logarithmique).
float ):scan_071_points.dat à partir de l'ensemble de données FreiBurg Campus 360, chaque point a (x, y, z) coordonnées float ): Ainsi, il semble qu'un leaf_max_size entre 10 et 50 serait optimal dans les applications où le coût des requêtes domine (par exemple ICP). À l'heure actuelle, sa valeur par défaut est de 10.
KDTreeSingleIndexAdaptorParams::checks Ce paramètre est vraiment ignoré dans nanoflann , mais a été conservé pour une compatibilité arrière avec l'interface Flann d'origine. Ignorez-le.
KDTreeSingleIndexAdaptorParams::n_thread_build Ce paramètre détermine le nombre maximal de threads qui peuvent être appelés simultanément lors de la construction de l'arbre KD. La valeur par défaut est 1. Lorsque le paramètre est défini sur 0, nanoflann détermine automatiquement le nombre de threads à utiliser.
Voir cette demande d'attraction pour une analyse comparative montrant que l'utilisation du nombre maximal de threads n'est pas toujours l'approche la plus efficace. Faites l'analyse comparative sur vos données!
nanoflann : utilisation plus rapide et moins mémoire Reportez-vous à la "pourquoi une fourche?" Section ci-dessus pour les principales idées d'optimisation derrière nanoflann .
Notez qu'il n'y a pas d'optimisations explicites SSE2 / SSE3 dans nanoflann , mais l'utilisation intensive des inline et des modèles dans la pratique se transforme en code optimisé automatiquement généré par le compilateur.
flann original vs nanoflannLa partie la plus longue de nombreux algorithmes de nuages de points (comme ICP) consiste à interroger un kd-arbre pour les voisins les plus proches. Cette opération est donc la plus critique de temps.
nanoflann offre une épargne de temps de ~ 50% par rapport à l'implémentation d'origine flann (les temps dans ce graphique sont en microsecondes pour chaque requête):
Bien que la majeure partie du gain provienne des requêtes (en raison du grand nombre d'entre elles dans toute opération typique avec des nuages ponctuels), il y a aussi un certain temps lors de la construction de l'indice KD-Tree, en raison du code templatisé mais aussi pour éviter les données dans une matrice auxiliaire (les temps dans le prochain graphique sont en millisecondes)::
Ces tests de performance ne sont représentatifs que de nos tests. Si vous voulez les répéter, lisez les instructions dans les tests perf
Remarque: le logo du projet est dû au cedasseed
Contributeurs
