nanoflann

1。大約

Nanoflann是一個C ++ 11個標頭庫，用於構建具有不同拓撲的數據集的KD-Trees：R ² ，R ³ （點雲），So（2），So（3）（3）（2D和3D旋轉組）。不提供大約NN的支持。 Nanoflann不需要編譯或安裝。您只需要在代碼中#include <nanoflann.hpp>即可。

該圖書館是Marius Muja和David G. Lowe的Flann圖書館的叉子，出生於Mrpt的兒童項目。按照原始許可條款， Nanoflann根據BSD許可分配。請使用錯誤，請使用“問題”按鈕或叉子，然後打開拉動請求。

引用為：

 @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}
}

有關項目更改的列表，請參見發行版ChangElog。

1.1。獲取代碼

• 最簡單的方法：克隆此git存儲庫，然後將include/nanoflann.hpp文件供您使用。
• Debian或Ubuntu（21.04或更新）用戶可以簡單地安裝它：

  $ sudo apt install libnanoflann-dev

• MacOS用戶可以與Homebrew一起安裝nanoflann ：

  $ brew install brewsci/science/nanoflann

  或者

  $ brew tap brewsci/science
  $ brew install nanoflann

  MacPorts用戶可以使用：

  $ sudo port install nanoflann

• Linux用戶還可以與LinuxBrew一起安裝： brew install homebrew/science/nanoflann
• 穩定版本列表。查看Changelog

儘管不必編譯Nanoflann本身，但您可以使用以下方式構建一些示例和測試：

$ sudo apt-get install build-essential cmake libgtest-dev libeigen3-dev
$ mkdir build && cd build && cmake ..
$ make && make test

1.2。 C ++ API參考

• 瀏覽doxygen文檔。

• 重要說明：如果使用L2規範，請注意搜索半徑和通過和返回的距離實際上是平方距離。

1.3。代碼示例

• kd-tree查找使用knnSearch()和radiusSearch() ：pointcloud_kdd_radius.cpp
• kd-tree查找點雲數據集：pointcloud_example.cpp
• 動態點雲數據集上的KD-Tree查找：Dynamic_pointCloud_example.cpp
• 旋轉組（SO2）上的KD-Tree查找：SO2_EXAMPLE.CPP
• 旋轉組（SO3）上的KD-Tree查找：SO3_EXAMPLE.CPP
• 帶有外部適配器類的點雲數據集上的KD-Tree查找：PointCloud_adaptor_example.cpp
• kd-tree直接在Eigen::Matrix<> ：matrix_example.cpp上查找
• 直接在std::vector<std::vector<T> >或std::vector<Eigen::VectorXd> ：vector_of_of_vectors_example.cpp上的KD-Tree查找
• 示例通過pkg-config使用Makefile用於使用（例如，在進行“ make install”或從Ubuntu存儲庫中安裝之後）：example_with_with_pkggconfig/
• 如何構建索引並將其保存到磁盤以供以後使用：saveload_example.cpp
• GUI示例（需要mrpt-gui ，例如sudo apt install libmrpt-gui-dev ）：
  • nanoflann_gui_example_r3

1.4。為什麼要叉？

• 執行時間效率：

  • 原始flann庫的力量來自於在不同的ANN算法之間進行選擇的可能性。這種靈活性的成本是聲明純虛擬方法，在某些情況下（在某些情況下）施加了運行時罰款。在nanoflann中，所有這些虛擬方法都被奇怪的重複模板模式（CRTP）和內線方法的組合所取代，這些方法快得多。
  • 對於radiusSearch() ，無需打電話來確定半徑內的點數，然後再次調用以獲取數據。通過將STL容器用於輸出數據，可以自動調整容器的大小。
  • 用戶可以（選項）通過模板參數在編譯時設置問題維度，從而使編譯器可以完全展開循環。
  • nanoflann允許用戶提供一個預先計算的數據框（如果有），以避免重新計算。
  • 數據點的索引已從int轉換為size_t ，在處理非常大的數據集時，它會刪除限制。

• 內存效率： nanoflann在構建KD -TREE索引之前，沒有將整個數據集的flann狀矩陣，而是允許通過適配器接口直接訪問您的數據，該界面必須在類中實現。

有關更多信息，請參見下面的示例或Nanoflann :: Kdtreesingleindexadaptor <>的C ++ API。

1.5。 Nanoflann可以做什麼？

• 用單個索引構建KD樹（沒有隨機的KD-Trees，沒有近似搜索）。
• 快速，線程安全的查詢，以查詢KD-Trees上最接近的鄰居。入口點是：
  • nanoflann :: kdtreesingleindexadaptor <> ::knnSearch()
    • 找到num_closest最近的鄰居到query_point[0:dim-1] 。它們的索引存儲在結果對像中。請參閱示例用法代碼。
  • nanoflann :: kdtreesingleindexadaptor <> ::radiusSearch()
    • 在最大半徑內找到所有鄰居query_point[0:dim-1] 。輸出作為對向量給出，其中第一個元素是點索引，第二個元素是相應距離。請參閱示例用法代碼。
  • nanoflann :: kdtreesingleindexadaptor <> ::radiusSearchCustomCallback()
    • 可用於接收範圍中發現的每個點的回調。在某些情況下，這可能更有效，而不是與結果建立大量的對矢量。
• 使用2D和3D點雲或N維數據集。
• 直接與Eigen::Matrix<>類（矩陣和向量向量）一起工作。
• 使用動態點雲，而無需重建整個KD-Tree索引。
• 使用距離指標：
  • R^N ：歐幾里得空間：
    • L1 （曼哈頓）
    • L2 （平方歐幾里得規範，有利於SSE2優化）。
    • L2_Simple （對於諸如點雲之類的低維數據集，平方的歐幾里得規範）。
  • SO(2) ：2D旋轉組
    • metric_SO2 ：絕對角度差異。
  • SO(3) ：3D旋轉組（以後發行中提供更好的支持）
    • metric_SO3 ：四元組之間的內部產品。
• 保存並加載內置索引到磁盤。
• 基於GUI的支持對多個KD-Tree庫，即Nanoflann，Flann，Fastann和Libkdtree。

1.6。 Nanoflann不能做什麼？

• 除了L1，L2，SO2和SO3外，請使用其他距離指標。
• 支持SE（3）組。
• 僅存在C ++接口：不支持C，Matlab或Python。
• 沒有自動算法配置（如原始Muja＆Lowe的紙張中所述）。

1.7。通過CMAKE在您的項目中使用

您可以將nanoflann.hpp文件直接放入項目中。另外，也可以使用CMAKE標準方法：

• 構建並“安裝”納米蘭恩。將CMAKE_INSTALL_PREFIX設置為適當的路徑，然後執行make install （Linux，OSX）或構建INSTALL目標（Visual Studio）。
• 然後，將類似的內容添加到您項目的CMake腳本中：

 # 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)

1.8。包裝經理

使用conan

您可以為nanoflann安裝預構建的二進製文件，也可以使用柯南從源構建它。使用以下命令安裝最新版本：

$ conan install --requires= " nanoflann/[*] " --build=missing

有關如何使用柯南的詳細說明，請參考柯南文檔。

nanoflann Conan食譜由Conan維護者和社區貢獻者保持最新狀態。如果該版本已過時，請在ConancentErindex存儲庫上創建問題或提取請求。

使用vcpkg

您可以使用VCPKG依賴項管理器下載並安裝Nanoflann：

$ git clone https://github.com/Microsoft/vcpkg.git
$ cd vcpkg
$ ./bootstrap-vcpkg.sh
$ ./vcpkg integrate install
$ ./vcpkg install nanoflann

Microsoft團隊成員和社區貢獻者保持最新的VCPKG Nanoflann端口。如果該版本已過時，請在VCPKG存儲庫上創建問題或拉出請求。

1.9。編譯時間定義

• NANOFLANN_FIRST_MATCH ：如果定義並且兩個點具有相同的距離，則最低點的距離將首先返回。否則就沒有特定的順序。
• NANOFLANN_NO_THREADS ：如果定義，將禁用多線程功能，以便可以使用庫而無需與pthreads鏈接。如果一個人試圖使用多個線程，則將拋出一個例外。

---

2。選擇KD-Tree參數有任何幫助嗎？

2.1。 KDTreeSingleIndexAdaptorParams::leaf_max_size

kd-tree是...好吧，一棵樹:-)。因此，它具有一個根節點，一組中間節點，最後是“葉”節點，即沒有孩子的那些節點。

點（或正確的是點索引）僅存儲在葉節點中。每個葉子都包含一個列表，其中哪個點屬於其範圍內。

在建造樹時，節點會遞歸分配，直到內部的點數相等或低於某個閾值。那就是leaf_max_size 。在進行查詢時，“樹算法”結束了結束，然後選擇葉子節點，然後對葉子中所有的查詢最接近的查詢進行線性搜索（一對一）。

因此，必須將leaf_max_size設置為權衡：

• 較大的值意味著將樹木建造得更快（因為樹將較小），但是每個查詢都會較慢（因為葉片中的線性搜索要在更多點上進行）。
• 小值會構建樹的速度慢得多（會有很多樹節點），但是查詢將更快……最高的一點，因為搜索的“樹零件”（對數複雜性）仍然具有很大的成本。

選擇什麼數字真正取決於應用程序，甚至取決於處理器緩存內存的大小，因此理想情況下，您應該做一些基準測試以最大化效率。

但是，為了幫助選擇良好的經驗價值，我提供以下兩個基準。每個圖代表不同leaf_max_size值1至10K之間的樹的構建（水平）和查詢（垂直）時間（作為對數尺度的95％不確定性橢圓形，變形）。

• 100K點雲，均勻分佈（每個點都有（x，y，z） float坐標）：

• 來自真實數據集的〜150K點雲（ scan_071_points.dat ，來自弗雷堡校園360數據集，每個點都有（x，y，z） float坐標）：

因此，在查詢成本主導（例如ICP）的應用中， leaf_max_size在10到50之間是最佳的。目前，其默認值為10。

2.2。 KDTreeSingleIndexAdaptorParams::checks

該參數在nanoflann中確實被忽略了，但是保留了與原始Flann接口的向後兼容。只是忽略它。

2.3。 KDTreeSingleIndexAdaptorParams::n_thread_build

此參數確定在KD樹構造過程中可以同時調用的最大線程數。默認值為1。當將參數設置為0時， nanoflann自動確定要使用的線程數。

請參閱此拉的請求，以表明使用最大線程數並不總是最有效的方法。對您的數據進行基準測試！

---

3。性能

3.1。 nanoflann ：更快，更少的內存使用

請參閱“為什麼要叉？”上面的部分是nanoflann背後的主要優化思想。

請注意， nanoflann中沒有明確的SSE2/SSE3優化，但是在實踐中inline和模板的大量用法變成了編譯器生成的自動SSE優化代碼。

3.2。基準：原始flann vs nanoflann

許多點雲算法（例如ICP）中最耗時的部分是向最近的鄰居查詢KD-Tree。因此，此操作是最關鍵的時間。

nanoflann相對於原始flann實施提供了約50％的節省時間（此圖表中的時間為每個查詢的微秒）：

儘管大部分收益來自查詢（由於在任何典型操作中使用點雲的數量大量），但由於構建KD-Tree索引時，還可以節省一些時間，這是由於模板化的代碼，也可以避免在輔助Matrix中重複數據（在下一張圖表中，在毫秒中是在毫秒中）

這些性能測試僅代表我們的測試。如果您想重複它們，請以完整的測試閱讀說明

---

4。其他KD-Tree項目

• Flann -Marius Muja和David G. Lowe（不列顛哥倫比亞大學）。
• Fastann -James Philbin（牛津大學VGG）。
• Ann -David M. Mount和Sunil Arya（馬里蘭大學）。
• libkdtree ++ -Martin F. Krafft等。

注意：項目徽標是由於Cedarsed引起的

貢獻者