點云處理繞不開的算法！如何高效搜索最近鄰？開源工具庫匯總
本文經自動駕駛之心公眾號授權轉載，轉載請聯系出處。
一、ANN benchmark
鏈接：https://github.com/erikbern/ann-benchmarks
在高維空間中快速搜索最近的鄰居是一個越來越重要的問題，盡管顯然需要這樣來推動優化，但很少有實證嘗試以客觀的方式比較方法。
該項目包含用于對所選度量的近似最近鄰（ANN）搜索的各種實現進行基準測試的工具。已經預先生成了數據集（HDF5格式），并為每個算法準備了Docker容器，以及一個驗證功能完整性的測試套件。
二、PCL
知名點云庫 Point Cloud Library | The Point Cloud Library ，這個就不多說了，里面的功能非常豐富，支持多類點云處理算法。
三、ikdtree
鏈接：https://github.com/hku-mars/ikd-Tree
香港大學開源，ikd樹是為機器人應用程序設計的增量k-d樹。ikd樹只使用新的到來點來增量更新k-d樹，從而比現有的靜態k-d樹的計算時間低得多。除了逐點操作外，ikd樹還支持一些功能，如逐box操作和下采樣，這些功能在機器人應用中非常有用。
相關參考論文：
- ikd-Tree: An Incremental K-D Tree for robotic applications
- FAST-LIO2: Fast Direct LiDAR-Inertial Odometry
四、nanoflann
nanoflann只有頭文件方便集成，nanoflann是一個僅限C++11頭的庫，用于構建具有不同拓撲結構的數據集的KD樹：R2、R3（點云）、SO（2）和SO（3）（2D和3D旋轉組）。不支持approximate NN。nanoflann不需要編譯或安裝，只需要在代碼中#包含<nanoflan.hpp>。
五、libpointmatcher:
ETH 點云 icp 庫，libpointmatcher用于實現點云對齊的迭代最近點（ICP）算法。它同時支持點對點和點對平面ICP。使用前者，它不僅可以解決剛性變換，還可以解決云之間的比例變化（即相似性變換）。
鏈接：https://libpointmatcher.readthedocs.io/en/latest/#developer
六、Open3D
英特爾實驗室點云處理庫：https://www.open3d.org/
Open3D是一個開源庫，支持處理3D數據的軟件的快速開發。Open3D前端公開了一組精心選擇的C++和Python數據結構和算法。后端經過高度優化，并設置為并行化。它可以在不同的平臺上進行設置，并以最小的工作量從源代碼進行編譯。代碼干凈、風格一致，并通過清晰的代碼審查機制進行維護。Open3D已被用于許多已發表的研究項目，并積極部署在云中。里面也集成了各類最近鄰匹配算法、ICP等配準算法。
七、Faiss
Meta 用于高效相似性搜索和密集向量聚類，鏈接：https://github.com/facebookresearch/faiss。
Faiss包含幾種相似性搜索方法。它假設實例被表示為向量，并由整數標識，并且向量可以與L2（歐幾里得）距離或點積進行比較。與查詢向量相似的向量是與查詢向量具有最低L2距離或最高點積的向量。它還支持余弦相似性，因為這是歸一化向量上的點積。
一些方法，如基于二進制矢量和緊湊量化碼的方法，僅使用矢量的壓縮表示，不需要保留原始矢量。這通常是以不太精確的搜索為代價的，但這些方法可以在單個服務器的主存中擴展到數十億個向量。其他方法，如HNSW和NSG，在原始向量的頂部添加索引結構，以提高搜索效率。
GPU實現可以接受來自CPU或GPU存儲器的輸入。在具有GPU的服務器上，GPU索引可以用作CPU索引的插入式替換（例如，用GpuIndexFlatL2替換IndexFlatL2），并且自動處理到GPU存儲器的副本/從GPU存儲器的復制。然而，如果輸入和輸出都保持在GPU上，結果將更快。同時支持單GPU和多GPU使用。
八 ivox
基于LRU機制可DIY，鏈接：https://github.com/gaoxiang12/faster-lio
Faster LIO是一種用于激光雷達姿態跟蹤和點云測繪的輕型激光雷達慣性里程計。它是在FastLIO2的基礎上開發的，可提供約1.5-2倍的速度提升。對于固態激光雷達，它可以達到近1k-2k赫茲，對于典型的32線旋轉激光雷達，可以達到超過100赫茲。
論文：https://github.com/gaoxiang12/faster-lio/blob/main/doc/faster-lio.pdf
九 nmslib
高效的相似性搜索庫、用于評估通用非度量空間的 k-NN 方法的工具包。
鏈接：https://github.com/nmslib/nmslib
非度量空間庫（NMSLIB）是一個高效的跨平臺相似性搜索庫，也是評估相似性搜索方法的工具包。核心庫沒有任何第三方依賴項。它最近越來越受歡迎。該項目的目標是創建一個有效和全面的工具包，用于在通用和非度量空間中進行搜索。盡管該庫包含各種度量空間訪問方法，但我們的主要關注點是通用和近似搜索方法，特別是非度量空間的方法。NMSLIB可能是第一個原則上支持非度量空間搜索的庫。
NMSLIB是一個可擴展的庫，這意味著可以添加新的搜索方法和距離函數。NMSLIB可以直接在C++和Python中使用（通過Python綁定）。此外，還可以構建一個查詢服務器，該服務器可以從Java（或Apache Thrift（0.12版本）支持的其他語言）使用。Java有一個本機客戶端，即它可以在許多平臺上工作，而不需要安裝C++庫。
