本文經(jīng)自動駕駛之心公眾號授權(quán)轉(zhuǎn)載，轉(zhuǎn)載請聯(lián)系出處。

一、ANN benchmark

鏈接：https://github.com/erikbern/ann-benchmarks

在高維空間中快速搜索最近的鄰居是一個越來越重要的問題，盡管顯然需要這樣來推動優(yōu)化，但很少有實證嘗試以客觀的方式比較方法。

該項目包含用于對所選度量的近似最近鄰（ANN）搜索的各種實現(xiàn)進(jìn)行基準(zhǔn)測試的工具。已經(jīng)預(yù)先生成了數(shù)據(jù)集（HDF5格式），并為每個算法準(zhǔn)備了Docker容器，以及一個驗證功能完整性的測試套件。

二、PCL

知名點(diǎn)云庫 Point Cloud Library | The Point Cloud Library ，這個就不多說了，里面的功能非常豐富，支持多類點(diǎn)云處理算法。

三、ikdtree

鏈接：https://github.com/hku-mars/ikd-Tree

香港大學(xué)開源，ikd樹是為機(jī)器人應(yīng)用程序設(shè)計的增量k-d樹。ikd樹只使用新的到來點(diǎn)來增量更新k-d樹，從而比現(xiàn)有的靜態(tài)k-d樹的計算時間低得多。除了逐點(diǎn)操作外，ikd樹還支持一些功能，如逐box操作和下采樣，這些功能在機(jī)器人應(yīng)用中非常有用。

相關(guān)參考論文：

• ikd-Tree: An Incremental K-D Tree for robotic applications
• FAST-LIO2: Fast Direct LiDAR-Inertial Odometry

四、nanoflann

nanoflann只有頭文件方便集成，nanoflann是一個僅限C++11頭的庫，用于構(gòu)建具有不同拓?fù)浣Y(jié)構(gòu)的數(shù)據(jù)集的KD樹：R2、R3（點(diǎn)云）、SO（2）和SO（3）（2D和3D旋轉(zhuǎn)組）。不支持approximate NN。nanoflann不需要編譯或安裝，只需要在代碼中#包含<nanoflan.hpp>。

五、libpointmatcher:

ETH 點(diǎn)云 icp 庫，libpointmatcher用于實現(xiàn)點(diǎn)云對齊的迭代最近點(diǎn)（ICP）算法。它同時支持點(diǎn)對點(diǎn)和點(diǎn)對平面ICP。使用前者，它不僅可以解決剛性變換，還可以解決云之間的比例變化（即相似性變換）。

鏈接：https://libpointmatcher.readthedocs.io/en/latest/#developer

六、Open3D

英特爾實驗室點(diǎn)云處理庫：https://www.open3d.org/

Open3D是一個開源庫，支持處理3D數(shù)據(jù)的軟件的快速開發(fā)。Open3D前端公開了一組精心選擇的C++和Python數(shù)據(jù)結(jié)構(gòu)和算法。后端經(jīng)過高度優(yōu)化，并設(shè)置為并行化。它可以在不同的平臺上進(jìn)行設(shè)置，并以最小的工作量從源代碼進(jìn)行編譯。代碼干凈、風(fēng)格一致，并通過清晰的代碼審查機(jī)制進(jìn)行維護(hù)。Open3D已被用于許多已發(fā)表的研究項目，并積極部署在云中。里面也集成了各類最近鄰匹配算法、ICP等配準(zhǔn)算法。

七、Faiss

Meta 用于高效相似性搜索和密集向量聚類，鏈接：https://github.com/facebookresearch/faiss。

Faiss包含幾種相似性搜索方法。它假設(shè)實例被表示為向量，并由整數(shù)標(biāo)識，并且向量可以與L2（歐幾里得）距離或點(diǎn)積進(jìn)行比較。與查詢向量相似的向量是與查詢向量具有最低L2距離或最高點(diǎn)積的向量。它還支持余弦相似性，因為這是歸一化向量上的點(diǎn)積。

一些方法，如基于二進(jìn)制矢量和緊湊量化碼的方法，僅使用矢量的壓縮表示，不需要保留原始矢量。這通常是以不太精確的搜索為代價的，但這些方法可以在單個服務(wù)器的主存中擴(kuò)展到數(shù)十億個向量。其他方法，如HNSW和NSG，在原始向量的頂部添加索引結(jié)構(gòu)，以提高搜索效率。

GPU實現(xiàn)可以接受來自CPU或GPU存儲器的輸入。在具有GPU的服務(wù)器上，GPU索引可以用作CPU索引的插入式替換（例如，用GpuIndexFlatL2替換IndexFlatL2），并且自動處理到GPU存儲器的副本/從GPU存儲器的復(fù)制。然而，如果輸入和輸出都保持在GPU上，結(jié)果將更快。同時支持單GPU和多GPU使用。

八 ivox

基于LRU機(jī)制可DIY，鏈接：https://github.com/gaoxiang12/faster-lio

Faster LIO是一種用于激光雷達(dá)姿態(tài)跟蹤和點(diǎn)云測繪的輕型激光雷達(dá)慣性里程計。它是在FastLIO2的基礎(chǔ)上開發(fā)的，可提供約1.5-2倍的速度提升。對于固態(tài)激光雷達(dá)，它可以達(dá)到近1k-2k赫茲，對于典型的32線旋轉(zhuǎn)激光雷達(dá)，可以達(dá)到超過100赫茲。

論文：https://github.com/gaoxiang12/faster-lio/blob/main/doc/faster-lio.pdf

九 nmslib

高效的相似性搜索庫、用于評估通用非度量空間的 k-NN 方法的工具包。

鏈接：https://github.com/nmslib/nmslib

非度量空間庫（NMSLIB）是一個高效的跨平臺相似性搜索庫，也是評估相似性搜索方法的工具包。核心庫沒有任何第三方依賴項。它最近越來越受歡迎。該項目的目標(biāo)是創(chuàng)建一個有效和全面的工具包，用于在通用和非度量空間中進(jìn)行搜索。盡管該庫包含各種度量空間訪問方法，但我們的主要關(guān)注點(diǎn)是通用和近似搜索方法，特別是非度量空間的方法。NMSLIB可能是第一個原則上支持非度量空間搜索的庫。

NMSLIB是一個可擴(kuò)展的庫，這意味著可以添加新的搜索方法和距離函數(shù)。NMSLIB可以直接在C++和Python中使用（通過Python綁定）。此外，還可以構(gòu)建一個查詢服務(wù)器，該服務(wù)器可以從Java（或Apache Thrift（0.12版本）支持的其他語言）使用。Java有一個本機(jī)客戶端，即它可以在許多平臺上工作，而不需要安裝C++庫。