nanoflannダウンロードnanoflannソースコードのダウンロード

nanoflann

C/C++

v1.6.2

ダウンロード

1。概要

Nanoflannは、さまざまなトポロジーを持つデータセットのKDツリーを構築するためのC ++ 11ヘッダーのみのライブラリです：R ² 、R ³ （ポイントクラウド）、SO（2）およびSO（3）（2Dおよび3D回転グループ）。おおよそのNNのサポートは提供されていません。 Nanoflannは、コンパイルまたはインストールを必要としません。コードに#include <nanoflann.hpp>が必要です。

このライブラリは、Marius MujaとDavid G. LoweによるFlann Libraryのフォークであり、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ユーザーは、以下でnanoflann HomeBrewにインストールできます。
```
$ 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 look-up with 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 look-up on a Eigen::Matrix<> ：matrix_example.cpp
kd-treeルックアップはstd::vector<std::vector<T> >またはstd::vector<Eigen::VectorXd> ：vector_of_vectors_example.cppで直接ルックアップ
pkg-configを介した使用のためのMakefileを使用します（たとえば、「インストール」を行った後、またはubuntuリポジトリからインストールした後）：example_with_pkgconfig/
インデックスを構築し、後で使用するためにディスクに保存する方法の例：saveload_example.cpp
GUIの例（ mrpt-gui sudo apt install libmrpt-gui-dev必要です。
- nanoflann_gui_example_r3

Nanoflann-Demo-1

1.4。なぜフォークなのか？

実行時間効率：
- 元のflann Libraryの力は、異なるANNアルゴリズムを選択する可能性に由来しています。この柔軟性のコストは、（状況によっては）ランタイムペナルティを課す純粋な仮想方法の宣言です。 nanoflannでは、これらの仮想方法はすべて、不思議な繰り返しテンプレートパターン（CRTP）とインラインドメソッドの組み合わせに置き換えられました。これらははるかに高速です。
- radiusSearch()の場合、半径内のポイント数を決定し、データを取得するために再度電話をかけるために呼び出しを行う必要はありません。出力データにSTLコンテナを使用することにより、コンテナは自動的にサイズ変更されます。
- ユーザーは（オプションで）テンプレート引数を介してコンパイル時に問題の次元を設定することができ、コンパイラがループを完全に展開できるようにすることができます。
- nanoflann使用すると、ユーザーは、利用可能な場合は、再構成を避けるために、データの事前に計算された境界ボックスを提供できます。
- データポイントのインデックスはintからsize_tに変換されており、非常に大きなデータセットを処理するときに制限を削除します。
メモリ効率：KD -Treeインデックスを構築する前に、データセット全体のカスタムflannのようなマトリックスにコピーする代わりに、 nanoflannクラスで実装する必要があるアダプターインターフェイスを介してデータに直接アクセスできます。

詳細については、以下の例またはnanoflann :: kdtreesingleindexadaptor <>のC ++ APIを参照してください。

1.5。ナノフランは何ができますか？

単一のインデックスを備えたKD-Treeを構築します（ランダム化されたKDツリーはなく、おおよその検索なし）。
KD-Treeの最も近い隣人のための高速のスレッドセーフクエリ。エントリポイントは次のとおりです。
- Nanoflann :: KdtreeSingleindexadaptor <> ::knnSearch()
  - query_point[0:dim-1]にnum_closestの最近隣人を見つけます。それらのインデックスは、結果オブジェクト内に保存されます。使用法コードの例を参照してください。
- nanoflann :: Kdtreesingleindexadaptor <> ::radiusSearch()
  - 最大半径内ですべての隣人をquery_point[0:dim-1]に見つけます。出力はペアのベクトルとして与えられ、その最初の要素はポイントインデックス、2番目は対応する距離です。使用法コードの例を参照してください。
- 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 ：Quaternions間の内製品。
構築されたインデックスをディスクに保存してロードします。
複数のKDツリーライブラリのベンチマークに関するGUIベースのサポート、つまりNanoflann、Flann、Fastann、Libkdtree。

1.6。ナノフランは何ができませんか？

L1、L2、SO2、およびSO3を除いて、他の距離メトリックを使用します。
SE（3）グループのサポート。
C ++インターフェイスのみが存在します。C、MATLAB、またはPythonのサポートはありません。
自動アルゴリズムの構成はありません（元のMuja＆Loweの論文で説明されています）。

1.7。 Cmakeを介してプロジェクトで使用します

プロジェクトにnanoflann.hppファイルを直接ドロップできます。または、Cmake標準メソッドも利用できます。

Nanoflannを構築および「インストール」します。 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を使用してソースから構築したりできます。次のコマンドを使用して、最新バージョンをインストールします。

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

コナンの使用方法に関する詳細な手順については、コナンのドキュメントを参照してください。

nanoflann・コナンのレシピは、コナンのメンテナーとコミュニティの貢献者によって最新の状態に保たれています。バージョンが古くなっている場合は、ConancenterIndexリポジトリで問題を作成するか、リクエストをプルしてください。

`vcpkg`を使用します

VCPKG依存関係マネージャーを使用してNanoflannをダウンロードしてインストールできます。

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

VCPKGのNanoflannポートは、Microsoftチームのメンバーとコミュニティの貢献者によって最新の状態に保たれています。バージョンが古くなっている場合は、VCPKGリポジトリに問題を作成するか、リクエストをプルしてください。

1.9。時間定義をコンパイルします

NANOFLANN_FIRST_MATCH ：定義され、2つのポイントが同じ距離を持っている場合、最も低いインデックスのあるポイントが最初に返されます。それ以外の場合、特定の順序はありません。
NANOFLANN_NO_THREADS ：定義されている場合、マルチスレッド機能は無効になるため、pthreadsとリンクせずにライブラリを使用できます。複数のスレッドを使用しようとすると、例外がスローされます。

2。KD-Treeパラメーターの選択に役立ちますか？

2.1。 `KDTreeSingleIndexAdaptorParams::leaf_max_size`

KD-Treeは...まあ、木:-)です。そのため、ルートノード、中間ノードのセット、最後に、子供のない「リーフ」ノードがあります。

ポイント（または、適切に、ポイントインデックス）は、リーフノードにのみ保存されます。各葉には、そのポイントがその範囲内に収まるリストが含まれています。

ツリーを構築する間、ノードは、内部のポイントの数が等か何らかのしきい値を下回るまで再帰的に分割されます。それはleaf_max_sizeです。クエリを実行している間、「ツリーアルゴリズム」は葉のノードを選択し、葉のすべてのクエリに最も近いポイントに線形検索（1つ）を実行することで終了します。

したがって、 leaf_max_sizeトレードオフとして設定する必要があります。

大きな値は、ツリーがより速く構築されることを意味します（ツリーが小さくなるため）が、各クエリは遅くなります（葉の線形検索はより多くのポイントで実行されるため）。
小さな値はツリーをはるかに遅く構築します（多くのツリーノードがあります）が、検索（対数複雑さ）の「ツリーパート」にはまだかなりのコストがかかるため、クエリはより速くなります。

選択する番号は、実際にアプリケーションとプロセッサキャッシュメモリのサイズに依存しているため、効率を最大化するためにベンチマークを行う必要があります。

しかし、経験則として良い価値を選択するのを助けるために、次の2つのベンチマークを提供します。各グラフは、1〜10Kの異なるleaf_max_size値のツリービルド（水平）およびクエリ（垂直）時間を表します（95％の不確実性楕円形は、対数スケールのために変形しました）。

均一に分布した100kポイントクラウド（各ポイントには（x、y、z） float座標があります）：

実際のデータセットからの〜150kポイントクラウド（ scan_071_points.dat freiburgキャンパス360データセットから、各ポイントには（x、y、z） float座標があります）：

したがって、 10〜50のleaf_max_size 、クエリのコストが支配するアプリケーションで最適になるようです（例：ICP）。現在、そのデフォルト値は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トリーをクエリすることです。したがって、この操作は最も重要な時間です。

nanoflann 、元のflann実装に関して約50％の時間節約を提供します（このチャートの時間は、クエリごとにマイクロ秒単位です）：

ゲインのほとんどはクエリから来ていますが（ポイントクラウドを使用した典型的な操作の多くのため）、テンプレート化されたコードのためにKD-Treeインデックスを構築する際には、補助マトリックスのデータの複製を回避するための時間も保存されています（次のチャートの時間は、ミルシェントです）。

これらのパフォーマンステストは、私たちのテストのみを表しています。それらを繰り返したい場合は、パフォーマンスの指示を読んでください

4。その他のKD-Treeプロジェクト

Flann -Marius MujaとDavid G. Lowe（ブリティッシュコロンビア大学）。
ファーストン - ジェームズ・フィルビン（VGG、オックスフォード大学）。
アン - デビッド・M・マウントとスニル・アリア（メリーランド大学）。
libkdtree ++ -Martin F. Krafft＆others。

注：プロジェクトのロゴは杉によるものです

貢献者

拡大する

追加情報

バージョン v1.6.2
タイプ C/C++
更新時間 2025-03-14
サイズ 594.45KB
から Github

nanoflann

1。概要

1.1。コードを取得します

1.2。 C ++ APIリファレンス

1.3。コードの例

1.4。なぜフォークなのか？

1.5。ナノフランは何ができますか？

1.6。ナノフランは何ができませんか？

1.7。 Cmakeを介してプロジェクトで使用します

1.8。パッケージマネージャー

`conan`の使用

`vcpkg`を使用します

1.9。時間定義をコンパイルします

2。KD-Treeパラメーターの選択に役立ちますか？

2.1。 `KDTreeSingleIndexAdaptorParams::leaf_max_size`

2.2。 `KDTreeSingleIndexAdaptorParams::checks`

2.3。 `KDTreeSingleIndexAdaptorParams::n_thread_build`

3。パフォーマンス

3.1。 `nanoflann` ：メモリの使用量が速く、より少ない

3.2。ベンチマーク：オリジナルの`flann` vs `nanoflann`

4。その他のKD-Treeプロジェクト

DragonBonesCPP

Beeftext

networkit

TensorflowASR

libjson rpc cpp

PEGTL

chat.petals.dev

GPT Prompt Templates

GPTyped

DragonBonesCPP

Beeftext

networkit

Google Dorks

shepherd

mongo express

nanoflann

1。概要

1.1。コードを取得します

1.2。 C ++ APIリファレンス

1.3。コードの例

1.4。なぜフォークなのか？

1.5。ナノフランは何ができますか？

1.6。ナノフランは何ができませんか？

1.7。 Cmakeを介してプロジェクトで使用します

1.8。パッケージマネージャー

conanの使用

vcpkgを使用します

1.9。時間定義をコンパイルします

2。KD-Treeパラメーターの選択に役立ちますか？

2.1。 KDTreeSingleIndexAdaptorParams::leaf_max_size

2.2。 KDTreeSingleIndexAdaptorParams::checks

2.3。 KDTreeSingleIndexAdaptorParams::n_thread_build

3。パフォーマンス

3.1。 nanoflann ：メモリの使用量が速く、より少ない

3.2。ベンチマーク：オリジナルのflann vs nanoflann

4。その他のKD-Treeプロジェクト

`conan`の使用

`vcpkg`を使用します

2.1。 `KDTreeSingleIndexAdaptorParams::leaf_max_size`

2.2。 `KDTreeSingleIndexAdaptorParams::checks`

2.3。 `KDTreeSingleIndexAdaptorParams::n_thread_build`

3.1。 `nanoflann` ：メモリの使用量が速く、より少ない

3.2。ベンチマーク：オリジナルの`flann` vs `nanoflann`