この記事はWeChat公式アカウント「自動運転ハート」の許可を得て転載しています。転載の許可については、元の情報源にお問い合わせください。

I. ANNベンチマーク

リンク: https://github.com/erikbern/ann-benchmarks

高次元空間での最近傍の高速検索はますます重要な問題となっており、最適化を推進するためには明らかに必要であるにもかかわらず、手法を客観的に比較した経験的な試みはほとんど行われていません。

このプロジェクトには、選択されたメトリクスについて近似最近傍探索（ANN）の様々な実装をベンチマークするためのツールが含まれています。データセット（HDF5形式）が事前に生成され、各アルゴリズム用のDockerコンテナが用意されており、機能の整合性を検証するためのテストスイートが提供されています。

II. PCL

よく知られているポイント クラウド ライブラリについては説明の必要はありません。豊富な機能を備え、さまざまなポイント クラウド処理アルゴリズムをサポートしています。

III. ikdtree

リンク: https://github.com/hku-mars/ikd-Tree

香港大学は、ロボット応用向けに設計された増分KD木であるikd-treeをオープンソース化しました。ikd-treeは、新たに到着したポイントのみを使用してKD木を増分的に更新するため、既存の静的KD木と比較して計算時間が大幅に短縮されます。ポイントごとの演算に加えて、ikd-treeはボックスごとの演算やダウンサンプリングなどの機能もサポートしており、これらはロボット応用において非常に有用です。

関連参考文献:

• ikd-Tree: ロボットアプリケーション向けの増分KDツリー
• FAST-LIO2: 高速直接LiDAR慣性オドメトリ

IV. ナノフラン

nanoflannはヘッダーファイルのみで簡単に統合できます。C++11専用のライブラリで、R2、R3（点群）、SO(2)、SO(3)（2次元および3次元回転群）といった異なるトポロジを持つデータセットのKDツリーを構築できます。近似ニューラルネットワークはサポートされていません。nanoflannはコンパイルやインストールは不要です。コードに`<nanoflan.hpp>`をインクルードするだけです。

V. libpointmatcher:

ETHポイントクラウドICPライブラリであるlibpointmatcherは、ポイントクラウドの位置合わせのための反復最近傍点（ICP）アルゴリズムを実装しています。点対点と点対平面の両方のICPをサポートしています。点対点を用いることで、剛体変換だけでなく、クラウド間のスケーリング変化（相似変換）も処理できます。

リンク: https://libpointmatcher.readthedocs.io/en/latest/#developer

VI. オープン3D

Intel Labs ポイントクラウド処理ライブラリ: https://www.open3d.org/

Open3Dは、3Dデータ処理ソフトウェアの迅速な開発を支援するオープンソースライブラリです。Open3Dのフロントエンドは、厳選されたC++およびPythonのデータ構造とアルゴリズムを公開しています。バックエンドは高度に最適化され、並列化向けに構成されています。様々なプラットフォームにインストールでき、ソースコードから最小限の労力でコンパイルできます。コードは簡潔で、スタイルに一貫性があり、明確なコードレビューメカニズムによって維持されています。Open3Dは、多くの公開された研究プロジェクトで使用されており、クラウドでも積極的に導入されています。また、様々な近傍マッチングアルゴリズムやICPレジストレーションアルゴリズムなども統合されています。

VII. ファイス

Metaは、効率的な類似性検索と高密度ベクトルクラスタリングに使用されます。リンク: https://github.com/facebookresearch/faiss。

Faiss には複数の類似検索手法が含まれています。インスタンスはベクトルとして表現され、整数で識別され、ベクトルはL2（ユークリッド）距離またはドット積を用いて比較できると仮定しています。クエリベクトルに類似するベクトルとは、クエリベクトルとのL2距離が最も小さい、またはドット積が最も大きいベクトルです。また、正規化されたベクトルのドット積であるコサイン類似度もサポートしています。

バイナリベクトルやコンパクト量子化コードに基づく手法など、一部の手法では、元のベクトルを保存せずに、ベクトルの圧縮表現のみを使用します。これは通常、検索精度が低下するという代償を伴いますが、これらの手法は単一サーバーのメインメモリに数十億のベクトルを格納するスケールで使用できます。HNSWやNSGなどの他の手法では、元のベクトルにインデックス構造を追加することで検索効率を向上させます。

GPU実装は、CPUまたはGPUメモリからの入力を受け付けます。GPU搭載サーバーでは、GPUインデックスをCPUインデックスの挿入置換として使用できます（例：IndexFlatL2をGpuInde​​xFlatL2に置き換える）。また、GPUメモリとの間のコピーは自動的に処理されます。ただし、入力と出力の両方がGPU上に保持されている場合は、結果が高速になります。シングルGPUとマルチGPUの両方の使用がサポートされています。

8ivox

LRUメカニズムに基づいてカスタマイズできます。リンク: https://github.com/gaoxiang12/faster-lio

Faster LIOは、ライダー姿勢追跡と点群マッピングに使用される軽量なライダー慣性オドメトリシステムです。FastLIO2をベースに開発され、約1.5～2倍の速度向上を実現します。ソリッドステートライダーでは1～2kHz程度、一般的な32ライン回転ライダーでは100Hz以上まで到達可能です。

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

ニネンムスリブ

一般的な非メトリック空間における k-NN 法を評価するための効率的な類似性検索ライブラリとツールキット。

リンク: https://github.com/nmslib/nmslib

非計量空間ライブラリ（NMSLIB）は、高性能でクロスプラットフォームな類似検索ライブラリであり、類似検索手法を評価するためのツールキットです。コアライブラリはサードパーティに依存しておらず、最近人気が高まっています。このプロジェクトの目標は、一般空間および非計量空間における検索のための効率的かつ包括的なツールキットを作成することです。ライブラリには様々な計量空間アクセス手法が含まれていますが、主な焦点は一般検索手法と近似検索手法、特に非計量空間を対象としたものにあります。NMSLIBは、非計量空間検索を原理的にサポートする最初のライブラリとなる可能性があります。

NMSLIBは拡張可能なライブラリであり、新しい検索手法や距離関数を追加できます。NMSLIBはC++およびPython（Pythonバインディング経由）で直接使用できます。さらに、Java（またはApache Thrift（バージョン0.12）でサポートされている他の言語）から使用できるクエリサーバーを構築できます。Javaにはネイティブクライアントがあるため、C++ライブラリをインストールしなくても多くのプラットフォームで動作します。