nanoflann
v1.6.2
Nanoflann ist eine C ++ 11-Header-Bibliothek für die Erstellung von KD-Bäumen von Datensätzen mit unterschiedlichen Topologien: R 2 , R 3 (Punktwolken), also (2) usw. (3) (2D- und 3D-Rotationsgruppen). Es wird keine Unterstützung für ungefähre NN bereitgestellt. Nanoflann muss nicht zusammengestellt oder installiert werden. Sie müssen nur #include <nanoflann.hpp> in Ihrem Code.
Diese Bibliothek ist eine Gabel der Flann Library von Marius Muja und David G. Lowe und als Kinderprojekt von MRPT geboren. Nach den ursprünglichen Lizenzbedingungen wird Nanoflann unter der BSD -Lizenz verteilt. Bitte verwenden Sie für Fehler die Button oder Gabel für Fehler und öffnen Sie eine Pull -Anfrage.
Zitieren als:
@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}
}
In der Release -ChangeLog finden Sie eine Liste der Projektänderungen.
include/nanoflann.hpp -Datei für die Verwendung, wo Sie sie benötigen.$ sudo apt install libnanoflann-devnanoflann mit Homebrew installieren mit: $ brew install brewsci/science/nanoflann$ brew tap brewsci/science
$ brew install nanoflann$ sudo port install nanoflannbrew install homebrew/science/nanoflann installierenObwohl Nanoflann selbst nicht zusammengestellt werden muss, können Sie einige Beispiele und Tests erstellen mit:
$ sudo apt-get install build-essential cmake libgtest-dev libeigen3-dev
$ mkdir build && cd build && cmake ..
$ make && make testDurchsuchen Sie die Doxygen -Dokumentation.
Wichtiger Hinweis: Wenn L2 -Normen verwendet werden, beachten Sie, dass der Suchradius und alle bestandenen und zurückgegebenen Entfernungen tatsächlich quadratische Entfernungen sind.
knnSearch() und radiusSearch() : pointcloud_kdd_radius.cppEigen::Matrix<> : matrix_example.cppstd::vector<std::vector<T> > oder std::vector<Eigen::VectorXd> : vector_of_vectors_example.cppMakefile für die Verwendung über pkg-config (z. B. nach einer "Installation" oder nach der Installation von Ubuntu-Repositories): Beispiel_With_Pkgconfig/mrpt-gui , z. B. sudo apt install libmrpt-gui-dev ):
Ausführungszeiteffizienz :
flann -Bibliothek ergibt sich aus der Möglichkeit, zwischen verschiedenen Ann -Algorithmen zu wählen. Die Kosten dieser Flexibilität sind die Erklärung reine virtuelle Methoden, die (unter bestimmten Umständen) Laufzeitstrafen auferlegen. In nanoflann wurden alle diese virtuellen Methoden durch eine Kombination aus merkwürdig rezidivierendem Template -Muster (CRTP) und eingebrachten Methoden ersetzt, die viel schneller sind.radiusSearch() müssen keinen Anruf tätigen, um die Anzahl der Punkte im Radius zu bestimmen und ihn dann erneut aufzurufen, um die Daten zu erhalten. Durch die Verwendung von STL -Containern für die Ausgabedaten werden die Container automatisch geändert.nanoflann können Benutzer ein vorberechtigtes Begrenzungsfeld der Daten bereitstellen, falls verfügbar, um eine erneute Berechnung zu vermeiden.int zu size_t konvertiert, wodurch beim Umgang mit sehr großen Datensätzen eine Grenze entfernt wird. Speichereffizienz : Anstatt eine Kopie des gesamten Datensatzes in eine benutzerdefinierte flann -ähnliche Matrix vor dem Erstellen eines KD -Tree -Index zu machen, ermöglicht nanoflann den direkten Zugriff auf Ihre Daten über eine Adapterschnittstelle , die in Ihrer Klasse implementiert werden muss.
Weitere Informationen finden Sie in den folgenden Beispielen oder auf die C ++ - API von Nanoflann :: Kdtreesingledexadaptor <> für weitere Informationen.
::knnSearch()num_closest Nächsten Nachbarn zu query_point[0:dim-1] . Ihre Indizes werden im Ergebnisobjekt gespeichert. Sehen Sie sich einen Beispielnutzungscode an.::radiusSearch()query_point[0:dim-1] . Die Ausgabe wird als Vektor von Paaren angegeben, von denen das erste Element ein Punktindex und der zweite der entsprechende Abstand ist. Sehen Sie sich einen Beispielnutzungscode an.::radiusSearchCustomCallback()Eigen::Matrix<> Klassen (Matrizen und Vektoren Vektoren).R^N : euklidische Räume:L1 (Manhattan)L2 ( quadratische euklidische Norm, die SSE2 -Optimierung bevorzugt).L2_Simple ( quadratische euklidische Norm für niedrigdimensionale Datensätze wie Punktwolken).SO(2) : 2D -Rotationsgruppemetric_SO2 : Absolute Winkelunterschiede.SO(3) : 3D -Rotationsgruppe (besseres Support, das in zukünftigen Veröffentlichungen bereitgestellt werden muss)metric_SO3 : inneres Produkt zwischen Quaternionen. Sie können die Datei nanoflann.hpp in Ihrem Projekt direkt fallen lassen. Alternativ ist auch die CMake -Standardmethode verfügbar:
CMAKE_INSTALL_PREFIX auf einen richtigen Pfad und führen Sie dann make install (Linux, OSX) aus oder erstellen Sie das INSTALL Target (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 Sie können vorgefertigte Binärdateien für nanoflann installieren oder sie mit Conan aus der Quelle erstellen. Verwenden Sie den folgenden Befehl, um die neueste Version zu installieren:
$ conan install --requires= " nanoflann/[*] " --build=missingAusführliche Anweisungen zur Verwendung von Conan finden Sie in der Conan -Dokumentation.
Das Rezept von nanoflann Conan wird von Conan -Betreuern und Community -Mitwirkenden auf dem neuesten Stand gehalten. Wenn die Version veraltet ist, erstellen Sie bitte eine Ausgabe- oder Zuganfrage im ConancenterIndex -Repository.
vcpkgSie können Nanoflann mit dem VCPKG -Abhängigkeitsmanager herunterladen und installieren:
$ git clone https://github.com/Microsoft/vcpkg.git
$ cd vcpkg
$ ./bootstrap-vcpkg.sh
$ ./vcpkg integrate install
$ ./vcpkg install nanoflannDer Nanoflann -Port in VCPKG wird von Microsoft -Teammitgliedern und Community -Mitwirkenden auf dem Laufenden gehalten. Wenn die Version veraltet ist, erstellen Sie bitte eine Ausgabe- oder Pull -Anfrage im VCPKG -Repository.
NANOFLANN_FIRST_MATCH : Wenn definiert und zwei Punkte den gleichen Abstand haben, wird der mit dem niedrigsten Index zuerst zurückgegeben. Ansonsten gibt es keine bestimmte Reihenfolge.NANOFLANN_NO_THREADS : Wenn definiert, werden Multithreading -Funktionen deaktiviert, damit die Bibliothek ohne Verknüpfung mit PThreads verwendet werden kann. Wenn man versucht, mehrere Threads zu verwenden, wird eine Ausnahme geworfen. KDTreeSingleIndexAdaptorParams::leaf_max_sizeEin KD-Baum ist ... na ja, ein Baum :-). Und als solches hat es einen Wurzelknoten, eine Reihe von Vermittlerknoten und schließlich "Blatt" Knoten, die ohne Kinder sind.
Punkte (oder richtige Punktindizes) werden nur in Blattknoten gespeichert. Jedes Blatt enthält eine Liste, von denen Punkte in seinen Bereich fallen.
Beim Bau des Baumes werden die Knoten rekursiv geteilt, bis die Anzahl der Punkte im Inneren gleich oder unter einem Schwellenwert ist. Das ist leaf_max_size . Während der Abfragen endet der "Baumalgorithmus" mit der Auswahl von Blattknoten und der linearen Suche (einseitig) nach dem nächsten Punkt zur Abfrage in allen im Blatt.
Also muss leaf_max_size als Kompromiss festgelegt werden:
Welche Anzahl Sie wirklich auswählen sollten, hängt von der Anwendung und sogar von der Größe des Prozessor -Cache -Speichers ab. Im Idealfall sollten Sie ein paar Benchmarking durchführen, um die Effizienz zu maximieren.
Um jedoch als Faustregel einen guten Wert auszuwählen, stelle ich die folgenden zwei Benchmarks an. Jedes Diagramm repräsentiert die Baumbauten (horizontal) und die Abfrage (vertikale) Zeiten für verschiedene leaf_max_size -Werte zwischen 1 und 10k (als 95% ige Unsicherheit, die aufgrund der logarithmischen Skala deformiert sind).
float -Koordinaten):scan_071_points.dat vom Datensatz des Freiburg Campus 360 hat jeder Punkt (x, y, z) float -Koordinaten): Es scheint also, dass ein leaf_max_size zwischen 10 und 50 in Anwendungen optimal wäre, bei denen die Kosten für Abfragen dominieren (z. B. ICP). Derzeit beträgt sein Standardwert 10.
KDTreeSingleIndexAdaptorParams::checks Dieser Parameter wird in nanoflann wirklich ignoriert, wurde jedoch für die Rückwärtskompatibilität mit der ursprünglichen Flann -Schnittstelle aufbewahrt. Ignoriere es einfach.
KDTreeSingleIndexAdaptorParams::n_thread_build Dieser Parameter bestimmt die maximale Anzahl von Fäden, die während der Konstruktion des KD -Baumes gleichzeitig aufgerufen werden können. Der Standardwert beträgt 1. Wenn der Parameter auf 0 gesetzt ist, bestimmt nanoflann automatisch die Anzahl der zu verwendenden Threads.
Sehen Sie sich diese Pull -Anfrage an ein Benchmarking an, das zeigt, dass die Verwendung der maximalen Anzahl von Threads nicht immer der effizienteste Ansatz ist. Machen Sie Benchmarking für Ihre Daten!
nanoflann : schneller und weniger Speicherverbrauch Beziehen Sie sich auf die "Warum eine Gabel?" Abschnitt oben für die Hauptoptimierungsideen hinter nanoflann .
Beachten Sie, dass es in nanoflann keine expliziten SSE2/SSE3-Optimierungen gibt, aber die intensive Verwendung von inline und Vorlagen in der Praxis wird automatisch vom Compiler generierten SSE-optimierten Code generiert.
flann gegen nanoflannDer zeitaufwändigste Teil vieler Punkt-Cloud-Algorithmen (wie ICP) ist, einen KD-Baum für die nächsten Nachbarn abzufragen. Diese Operation ist daher am kritischsten.
nanoflann bietet einen Zeitraum von ~ 50% in Bezug auf die ursprüngliche flann -Implementierung (die Zeiten in diesem Diagramm sind für jede Abfrage in Mikrosekunden):
Obwohl der größte Teil des Gewinns aus den Abfragen stammt (aufgrund der großen Anzahl von ihnen in einem typischen Betrieb mit Punktwolken), wird auch einige Zeit gespeichert, während der KD-Tree-Index auf dem Vorgang des templatisierten Codes erstellt wurde, aber auch zur Vermeidung der Duplikation der Daten in einer Auxiliary-Matrix (Zeiten in der nächsten Tabelle sind in Millisekunden):
Diese Leistungstests sind nur für unsere Tests repräsentativ. Wenn Sie sie wiederholen möchten, lesen Sie die Anweisungen in Perf-Tests
Hinweis: Das Projektlogo ist auf Zedern
Mitwirkende
