Unduh nanoflann - Unduh Kode Sumber nanoflann

nanoflann

C/C++

v1.6.2

Unduh

1. Tentang

Nanoflann adalah perpustakaan c ++ 11 header khusus untuk membangun pohon kD kumpulan data dengan topologi yang berbeda: r ² , r ³ (awan titik), jadi (2) dan demikian (3) (kelompok rotasi 2D dan 3D). Tidak ada dukungan untuk perkiraan NN disediakan. Nanoflann tidak memerlukan kompilasi atau pemasangan. Anda hanya perlu #include <nanoflann.hpp> dalam kode Anda.

Perpustakaan ini adalah garpu dari Perpustakaan Flann oleh Marius Muja dan David G. Lowe, dan lahir sebagai proyek anak MRPT. Mengikuti persyaratan lisensi asli, Nanoflann didistribusikan di bawah lisensi BSD. Tolong, untuk bug menggunakan tombol masalah atau garpu dan buka permintaan tarik.

Mengutip sebagai:

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

Lihat rilis changelog untuk daftar perubahan proyek.

1.1. Memperoleh kode

Cara termudah: Kloning repositori git ini dan ambil file include/nanoflann.hpp untuk digunakan di mana Anda membutuhkannya.
Pengguna Debian atau Ubuntu (21.04 atau yang lebih baru) dapat menginstalnya dengan:
```
$ sudo apt install libnanoflann-dev
```

Pengguna MacOS dapat menginstal nanoflann dengan homebrew dengan:

$ brew install brewsci/science/nanoflann

atau

$ brew tap brewsci/science
$ brew install nanoflann

Pengguna MacPorts dapat menggunakan:

$ sudo port install nanoflann

Pengguna Linux juga dapat menginstalnya dengan LinuxBrew dengan: brew install homebrew/science/nanoflann
Daftar rilis stabil . Lihat Changelog

Meskipun Nanoflann sendiri tidak harus dikompilasi, Anda dapat membangun beberapa contoh dan tes dengan:

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

1.2. Referensi C ++ API

Jelajahi dokumentasi doxygen.
Catatan penting: Jika norma L2 digunakan, perhatikan bahwa jari -jari pencarian dan semua jarak yang diteruskan dan dikembalikan sebenarnya adalah jarak kuadrat .

1.3. Contoh Kode

KD-tree Look-up dengan knnSearch() dan radiusSearch() : pointcloud_kdd_radius.cpp
KD-tree Look-up pada dataset titik cloud: pointcloud_example.cpp
KD-tree Look-up pada dataset cloud titik dinamis: Dynamic_PointCloud_example.cpp
KD-tree Look-up pada grup rotasi (SO2): so2_example.cpp
KD-tree Look-up pada grup rotasi (SO3): so3_example.cpp
KD-Tree Look-up pada dataset titik cloud dengan kelas adaptor eksternal: pointcloud_adaptor_example.cpp
KD-tree Look-up langsung pada Eigen::Matrix<> : matrix_example.cpp
KD-tree Look-up langsung di std::vector<std::vector<T> > atau std::vector<Eigen::VectorXd> : vector_of_vectors_example.cpp
Contoh dengan Makefile untuk digunakan melalui pkg-config (misalnya, setelah melakukan "membuat instal" atau setelah menginstal dari repositori ubuntu): example_with_pkgconfig/
Contoh cara membangun indeks dan menyimpannya ke disk untuk penggunaan selanjutnya: saveload_example.cpp
Contoh GUI (membutuhkan mrpt-gui , misalnya sudo apt install libmrpt-gui-dev ):
- nanoflan_gui_example_r3

nanoflann-demo-1

1.4. Mengapa garpu?

Efisiensi Waktu Eksekusi :
- Kekuatan Perpustakaan flann asli berasal dari kemungkinan memilih antara berbagai algoritma Ann. Biaya fleksibilitas ini adalah deklarasi metode virtual murni yang (dalam beberapa keadaan) menjatuhkan hukuman run-time. Dalam nanoflann semua metode virtual tersebut telah digantikan dengan kombinasi dari pola template yang berulang (CRTP) dan metode inline, yang jauh lebih cepat.
- Untuk radiusSearch() , tidak perlu melakukan panggilan untuk menentukan jumlah poin dalam radius dan kemudian memanggilnya lagi untuk mendapatkan data. Dengan menggunakan wadah STL untuk data output, wadah secara otomatis diubah ukurannya.
- Pengguna dapat (secara opsional) mengatur dimensi masalah pada waktu kompilasi melalui argumen templat, sehingga memungkinkan kompiler untuk membuka loop sepenuhnya.
- nanoflann memungkinkan pengguna untuk menyediakan kotak pembatas data yang dihapuskan, jika tersedia, untuk menghindari komputasi.
- Indeks titik data telah dikonversi dari int ke size_t , yang menghilangkan batas saat menangani set data yang sangat besar.
Efisiensi Memori : Alih -alih membuat salinan seluruh dataset ke dalam matriks seperti flann khusus sebelum membangun indeks KD -Tree, nanoflann memungkinkan akses langsung ke data Anda melalui antarmuka adaptor yang harus diimplementasikan di kelas Anda.

Lihat contoh di bawah ini atau ke C ++ API dari Nanoflann :: Kdtreesingleindexadaptor <> untuk info lebih lanjut.

1.5. Apa yang bisa dilakukan nanoflann ?

Membangun pohon kD dengan indeks tunggal (tidak ada pohon kD acak, tidak ada pencarian perkiraan).
Permintaan yang cepat dan aman untuk tetangga terdekat di pohon KD. Titik masuknya adalah:
- nanoflann :: kdtreesingleindexadaptor <> ::knnSearch()
  - Menemukan tetangga terdekat num_closest ke query_point[0:dim-1] . Indeks mereka disimpan di dalam objek hasil. Lihat contoh kode penggunaan.
- nanoflann :: kdtreesingleindexadaptor <> ::radiusSearch()
  - Menemukan semua tetangga untuk query_point[0:dim-1] dalam radius maksimum. Output diberikan sebagai vektor pasangan, di mana elemen pertama adalah indeks titik dan yang kedua jarak yang sesuai. Lihat contoh kode penggunaan.
- nanoflann :: kdtreesingleindexadaptor <> ::radiusSearchCustomCallback()
  - Dapat digunakan untuk menerima panggilan balik untuk setiap titik yang ditemukan dalam jangkauan. Ini mungkin lebih efisien dalam beberapa situasi daripada membangun vektor pasangan yang sangat besar dengan hasilnya.
Bekerja dengan awan 2D dan 3D atau set data N-dimensi.
Bekerja secara langsung dengan Eigen::Matrix<> (matriks dan vektor vektor).
Bekerja dengan awan titik dinamis tanpa perlu membangun kembali seluruh indeks pohon-kd.
Bekerja dengan metrik jarak:
- R^N : Ruang Euclidean:
  - L1 (Manhattan)
  - L2 (norma Euclidean kuadrat , mendukung optimasi SSE2).
  - L2_Simple (norma Euclidean kuadrat , untuk set data berdimensionalitas rendah seperti awan titik).
- SO(2) : kelompok rotasi 2D
  - metric_SO2 : Perbedaan sudut absolut.
- SO(3) : Grup Rotasi 3D (support yang lebih baik disediakan dalam rilis mendatang)
  - metric_SO3 : Produk Dalam antara Kuarter.
Menyimpan dan memuat indeks yang dibangun ke disk.
Dukungan Berbasis GUI untuk membandingkan beberapa perpustakaan KD-Tree yaitu Nanoflann, Flann, Fastann dan Libkdtree.

1.6. Apa yang tidak bisa dilakukan Nanoflann ?

Gunakan metrik jarak lain selain dari L1, L2, SO2 dan SO3.
Dukungan untuk grup SE (3).
Hanya antarmuka C ++ yang ada: tidak ada dukungan untuk C, Matlab atau Python.
Tidak ada konfigurasi algoritma otomatis (seperti yang dijelaskan dalam kertas Muja & Lowe asli).

1.7. Gunakan dalam proyek Anda melalui CMake

Anda dapat langsung menjatuhkan file nanoflann.hpp di proyek Anda. Atau, metode standar CMake juga tersedia:

Bangun dan "Instal" Nanoflann. Atur CMAKE_INSTALL_PREFIX ke jalur yang tepat dan kemudian jalankan make install (Linux, OSX) atau bangun target INSTALL (Visual Studio).
Kemudian, tambahkan sesuatu seperti ini ke skrip cmake proyek Anda:

 # 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. Manajer Paket

Menggunakan `conan`

Anda dapat memasang binari pra-built untuk nanoflann atau membangunnya dari sumber menggunakan Conan. Gunakan perintah berikut untuk menginstal versi terbaru:

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

Untuk instruksi terperinci tentang cara menggunakan Conan, silakan merujuk ke dokumentasi Conan.

Resep nanoflann Conan selalu diperbarui oleh Conan Loaders dan kontributor masyarakat. Jika versi sudah ketinggalan zaman, silakan buat permintaan atau tarik permintaan di Repositori ConancenterIndex.

Menggunakan `vcpkg`

Anda dapat mengunduh dan menginstal nanoflann menggunakan VCPKG Dependency Manager:

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

Pelabuhan Nanoflann di VCPKG terus diperbarui oleh anggota tim Microsoft dan kontributor komunitas. Jika versi sudah ketinggalan zaman, silakan buat masalah atau tarik permintaan pada repositori VCPKG.

1.9. Kompilasi definisi waktu

NANOFLANN_FIRST_MATCH : Jika didefinisikan dan dua titik memiliki jarak yang sama, yang dengan indeks terendah akan dikembalikan terlebih dahulu. Kalau tidak, tidak ada urutan tertentu.
NANOFLANN_NO_THREADS : Jika didefinisikan, kemampuan multithreading akan dinonaktifkan, sehingga perpustakaan dapat digunakan tanpa menghubungkan dengan pthreads. Jika seseorang mencoba menggunakan beberapa utas, pengecualian akan dilemparkan.

2. Adakah bantuan untuk memilih parameter KD-tree?

2.1. `KDTreeSingleIndexAdaptorParams::leaf_max_size`

Sebuah pohon KD adalah ... yah, pohon :-). Dan karena itu memiliki simpul akar, satu set node perantara dan akhirnya, "daun" yang merupakan mereka yang tidak memiliki anak.

Poin (atau, dengan benar, indeks titik) hanya disimpan dalam node daun. Setiap daun berisi daftar poin mana yang termasuk dalam jangkauannya.

Saat membangun pohon, node dibagi secara rekursif sampai jumlah titik di dalamnya sama atau di bawah beberapa ambang batas. Itu adalah leaf_max_size . Saat melakukan kueri, "algoritma pohon" berakhir dengan memilih node daun, kemudian melakukan pencarian linier (satu per satu) untuk titik terdekat dengan kueri di dalam semua yang ada di daun.

Jadi, leaf_max_size harus ditetapkan sebagai tradeoff :

Nilai -nilai besar berarti bahwa pohon akan dibangun lebih cepat (karena pohon akan lebih kecil), tetapi setiap kueri akan lebih lambat (karena pencarian linier dalam daun harus dilakukan pada lebih banyak titik).
Nilai-nilai kecil akan membangun pohon jauh lebih lambat (akan ada banyak node pohon), tetapi pertanyaan akan lebih cepat ... hingga beberapa titik, karena "bagian pohon" pencarian (kompleksitas logaritmik) masih memiliki biaya yang signifikan.

Angka apa yang harus dipilih benar -benar tergantung pada aplikasi dan bahkan pada ukuran memori cache prosesor, jadi idealnya Anda harus melakukan beberapa pembandingan untuk memaksimalkan efisiensi.

Tetapi untuk membantu memilih nilai yang baik sebagai aturan praktis, saya memberikan dua tolok ukur berikut. Setiap grafik mewakili waktu pembuatan pohon (horisontal) dan kueri (vertikal) untuk nilai leaf_max_size yang berbeda antara 1 dan 10k (sebagai elips ketidakpastian 95%, dideformasi karena skala logaritmik).

Awan titik 100K, terdistribusi secara seragam (setiap titik memiliki (x, y, z) float koordinat):

A ~ 150K Point Cloud dari Dataset Nyata ( scan_071_points.dat dari Dataset Freiburg Campus 360, setiap titik memiliki (x, y, z) koordinat float ):

Jadi, tampaknya leaf_max_size antara 10 dan 50 akan optimal dalam aplikasi di mana biaya kueri mendominasi (misalnya ICP). Saat ini, nilai defaultnya adalah 10.

2.2. `KDTreeSingleIndexAdaptorParams::checks`

Parameter ini benar -benar diabaikan dalam nanoflann , tetapi disimpan untuk kompatibilitas ke belakang dengan antarmuka Flann asli. Abaikan saja.

2.3. `KDTreeSingleIndexAdaptorParams::n_thread_build`

Parameter ini menentukan jumlah maksimum utas yang dapat disebut secara bersamaan selama pembangunan pohon KD. Nilai default adalah 1. Ketika parameter diatur ke 0, nanoflann secara otomatis menentukan jumlah utas yang akan digunakan.

Lihat permintaan tarik ini untuk beberapa pembandingan yang menunjukkan bahwa menggunakan jumlah maksimum utas tidak selalu merupakan pendekatan yang paling efisien. Lakukan pembandingan pada data Anda!

3. Kinerja

3.1. `nanoflann` : Penggunaan memori yang lebih cepat dan lebih sedikit

Lihat "Mengapa garpu?" Bagian di atas untuk ide -ide optimisasi utama di balik nanoflann .

Perhatikan bahwa tidak ada optimasi SSE2/SSE3 yang eksplisit di nanoflann , tetapi penggunaan intensif inline dan templat dalam praktik berubah menjadi kode yang dioptimalkan secara otomatis SSE yang dihasilkan oleh kompiler.

3.2. Benchmark: asli `flann` vs `nanoflann`

Bagian yang paling memakan waktu dari banyak algoritma cloud titik (seperti ICP) adalah menanyakan pohon-KD untuk tetangga terdekat. Oleh karena itu, operasi ini adalah yang paling penting.

nanoflann menyediakan penghematan waktu ~ 50% sehubungan dengan implementasi flann asli (waktu dalam bagan ini berada dalam mikrodetik untuk setiap kueri):

Meskipun sebagian besar keuntungan berasal dari kueri (karena sejumlah besar dari mereka dalam operasi tipikal dengan awan titik), ada juga beberapa waktu yang dihemat saat membangun indeks pohon-kd, karena kode templatisasi tetapi juga untuk menghindari duplikasi data dalam matriks pembantu (waktu dalam bagan berikutnya adalah di milagondasi):

Tes kinerja ini hanya mewakili pengujian kami. Jika Anda ingin mengulanginya, baca instruksi dalam tes perf