nanoflann
v1.6.2
Nanoflann เป็น ไลบรารีส่วนหัวของ C ++ 11 สำหรับการสร้างชุดข้อมูล KD KD ของชุดข้อมูลที่มีทอพอโลยีที่แตกต่างกัน: R 2 , R 3 (จุดคลาวด์) ดังนั้น (2) และดังนั้น (3) (กลุ่มการหมุน 2D และ 3D) ไม่มีการสนับสนุนสำหรับ NN โดยประมาณ Nanoflann ไม่จำเป็นต้องรวบรวมหรือติดตั้ง คุณเพียงแค่ต้อง #include <nanoflann.hpp> ในรหัสของคุณ
ห้องสมุดนี้เป็น ส้อม ของห้องสมุด Flann โดย Marius Muja และ David G. Lowe และเกิดเป็นโครงการเด็กของ 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}
}
ดูการเปลี่ยนแปลงการเปิดตัวสำหรับรายการการเปลี่ยนแปลงโครงการ
include/nanoflann.hpp เพื่อใช้งานที่คุณต้องการ$ sudo apt install libnanoflann-devnanoflann ด้วย homebrew ด้วย: $ brew install brewsci/science/nanoflann$ brew tap brewsci/science
$ brew install nanoflann$ sudo port install nanoflannbrew install homebrew/science/nanoflannแม้ว่า Nanoflann นั้นไม่จำเป็นต้องรวบรวม แต่คุณสามารถสร้างตัวอย่างและการทดสอบด้วย:
$ sudo apt-get install build-essential cmake libgtest-dev libeigen3-dev
$ mkdir build && cd build && cmake ..
$ make && make testเรียกดูเอกสาร Doxygen
หมายเหตุสำคัญ: หากมีการใช้บรรทัดฐาน L2 ให้สังเกตว่ารัศมีการค้นหาและระยะทางที่ส่งคืนและส่งคืนทั้งหมดนั้นเป็น ระยะทางกำลังสอง
knnSearch() และ radiusSearch() : pointcloud_kdd_radius.cppEigen::Matrix<> : matrix_example.cppstd::vector<std::vector<T> > หรือ std::vector<Eigen::VectorXd> : vector_of_vectors_example.cppMakefile สำหรับการใช้งานผ่าน pkg-config (ตัวอย่างเช่นหลังจากทำการ "ติดตั้ง" หรือหลังจากติดตั้งจากที่เก็บ Ubuntu): example_with_pkgconfig/mrpt-gui เช่น sudo apt install libmrpt-gui-dev ):
ประสิทธิภาพเวลาดำเนินการ :
flann ดั้งเดิมมาจากความเป็นไปได้ในการเลือกระหว่างอัลกอริทึม Ann ที่แตกต่างกัน ค่าใช้จ่ายของความยืดหยุ่นนี้คือการประกาศวิธีการเสมือนจริงที่บริสุทธิ์ซึ่ง (ในบางสถานการณ์) กำหนดบทลงโทษเวลา ใน nanoflann วิธีการเสมือนทั้งหมดเหล่านั้นถูกแทนที่ด้วยการรวมกันของรูปแบบเทมเพลตที่เกิดขึ้นซ้ำ ๆ (CRTP) และวิธีการ Inlined ซึ่งเร็วกว่ามากradiusSearch() ไม่จำเป็นต้องโทรหาเพื่อกำหนดจำนวนคะแนนภายในรัศมีแล้วเรียกมันอีกครั้งเพื่อรับข้อมูล โดยใช้คอนเทนเนอร์ STL สำหรับข้อมูลเอาต์พุตคอนเทนเนอร์จะถูกปรับขนาดโดยอัตโนมัติnanoflann ช่วยให้ผู้ใช้สามารถจัดเตรียมกล่องขอบเขตที่คาดการณ์ล่วงหน้าของข้อมูลได้หากมีเพื่อหลีกเลี่ยงการคำนวณใหม่int เป็น size_t ซึ่งจะลบขีด จำกัด เมื่อจัดการชุดข้อมูลขนาดใหญ่มาก ประสิทธิภาพของหน่วยความจำ : แทนที่จะทำสำเนาชุดข้อมูลทั้งหมดลงในเมทริกซ์เหมือน flann ที่กำหนดเองก่อนที่จะสร้างดัชนี KD -Tree nanoflann อนุญาตให้เข้าถึงข้อมูลของคุณโดยตรงผ่าน ส่วนต่อประสานอะแดปเตอร์ ซึ่งจะต้องใช้ในชั้นเรียนของคุณ
อ้างถึงตัวอย่างด้านล่างหรือไปยัง C ++ API ของ Nanoflann :: KdtreesingleIndexadaptor <> สำหรับข้อมูลเพิ่มเติม
::knnSearch()num_closest เพื่อนบ้านที่ใกล้ที่สุดเพื่อ query_point[0:dim-1] ดัชนีของพวกเขาจะถูกเก็บไว้ภายในวัตถุผลลัพธ์ ดูตัวอย่างรหัสการใช้งาน::radiusSearch()query_point[0:dim-1] ภายในรัศมีสูงสุด เอาต์พุตจะได้รับเป็นเวกเตอร์ของคู่ซึ่งองค์ประกอบแรกคือดัชนีจุดและระยะที่สองคือระยะทางที่สอดคล้องกัน ดูตัวอย่างรหัสการใช้งาน::radiusSearchCustomCallback()Eigen::Matrix<> คลาส (เมทริกซ์และเวกเตอร์ของเวทเตอร์)R^N : พื้นที่ Euclidean:L1 (แมนฮัตตัน)L2 (Norm Euclidean ยกกำลังสอง ซึ่งเป็นที่นิยมการเพิ่มประสิทธิภาพ SSE2)L2_Simple (บรรทัดฐานแบบยุคลิด- ยกกำลังสอง สำหรับชุดข้อมูลมิติต่ำเช่นจุดคลาวด์จุด)SO(2) : กลุ่มการหมุน 2Dmetric_SO2 : ความแตกต่างเชิงมุมสัมบูรณ์SO(3) : กลุ่มการหมุน 3D (ดีกว่าที่จะให้ในการเผยแพร่ในอนาคต)metric_SO3 : ผลิตภัณฑ์ภายในระหว่าง Quaternions คุณสามารถวางไฟล์ nanoflann.hpp โดยตรงในโครงการของคุณ หรือวิธีการมาตรฐาน CMAKE ก็มีอยู่เช่นกัน:
CMAKE_INSTALL_PREFIX เป็นเส้นทางที่เหมาะสมจากนั้นเรียกใช้งาน make install (Linux, OSX) หรือสร้างเป้าหมาย INSTALL (Visual Studio) # 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)conan คุณสามารถติดตั้งไบนารีที่สร้างไว้ล่วงหน้าสำหรับ nanoflann หรือสร้างจากแหล่งที่มาโดยใช้โคนัน ใช้คำสั่งต่อไปนี้เพื่อติดตั้งเวอร์ชันล่าสุด:
$ conan install --requires= " nanoflann/[*] " --build=missingสำหรับคำแนะนำโดยละเอียดเกี่ยวกับวิธีการใช้โคนันโปรดดูเอกสารของโคนัน
สูตร nanoflann Conan ได้รับการปรับปรุงให้ทันสมัยโดย Conan ผู้ดูแลและผู้มีส่วนร่วมในชุมชน หากเวอร์ชันล้าสมัยโปรดสร้างปัญหาหรือดึงคำขอบนที่เก็บ ConancenterIndex
vcpkgคุณสามารถดาวน์โหลดและติดตั้ง Nanoflann โดยใช้ VCPKG Perdency Manager:
$ git clone https://github.com/Microsoft/vcpkg.git
$ cd vcpkg
$ ./bootstrap-vcpkg.sh
$ ./vcpkg integrate install
$ ./vcpkg install nanoflannพอร์ต Nanoflann ใน VCPKG ได้รับการปรับปรุงโดยสมาชิกในทีม Microsoft และผู้มีส่วนร่วมในชุมชน หากเวอร์ชันล้าสมัยโปรดสร้างปัญหาหรือดึงคำขอบนที่เก็บ VCPKG
NANOFLANN_FIRST_MATCH : หากกำหนดและสองจุดมีระยะทางเท่ากันหนึ่งที่มีดัชนีต่ำสุดจะถูกส่งคืนก่อน มิฉะนั้นจะไม่มีคำสั่งเฉพาะNANOFLANN_NO_THREADS : หากกำหนดความสามารถแบบมัลติเธรดจะถูกปิดใช้งานเพื่อให้สามารถใช้ไลบรารีได้โดยไม่ต้องเชื่อมโยงกับ pthreads หากมีใครพยายามใช้หลายเธรดข้อยกเว้นจะถูกโยนลงไป KDTreeSingleIndexAdaptorParams::leaf_max_sizeต้นไม้ KD คือ ... ดีต้นไม้ :-) และเช่นนี้มีโหนดรูทชุดของโหนดตัวกลางและในที่สุดโหนด "ใบไม้" ซึ่งเป็นโหนดที่ไม่มีลูก
คะแนน (หรืออย่างถูกต้องดัชนีจุด) จะถูกเก็บไว้ในโหนดใบไม้เท่านั้น ใบแต่ละใบมีรายการที่จุดอยู่ในช่วงของมัน
ในขณะที่สร้างต้นไม้โหนดจะถูกแบ่งซ้ำจนกว่าจำนวนจุดภายในจะเท่ากันหรือต่ำกว่าเกณฑ์บางอย่าง นั่นคือ leaf_max_size ในขณะที่ทำแบบสอบถาม "อัลกอริทึมต้นไม้" จบลงด้วยการเลือกโหนดใบไม้จากนั้นทำการค้นหาเชิงเส้น (หนึ่งต่อหนึ่ง) สำหรับจุดที่ใกล้เคียงที่สุดกับการสืบค้นภายในทุกคนในใบไม้
ดังนั้น leaf_max_size จะต้องตั้งค่าเป็น tradeoff :
หมายเลขใดที่จะเลือกขึ้นอยู่กับแอปพลิเคชันและแม้กระทั่งขนาดของหน่วยความจำแคชโปรเซสเซอร์ดังนั้นคุณควรทำการเปรียบเทียบเพื่อเพิ่มประสิทธิภาพสูงสุด
แต่เพื่อช่วยในการเลือกคุณค่าที่ดีเป็นกฎง่ายๆฉันได้จัดทำมาตรฐานสองประการต่อไปนี้ แต่ละกราฟแสดงถึงการสร้างต้นไม้ (แนวนอน) และแบบสอบถาม (แนวตั้ง) สำหรับค่า leaf_max_size ที่แตกต่างกันระหว่าง 1 ถึง 10k (เป็นจุดไข่ปลาความไม่แน่นอน 95%, ผิดรูปเนื่องจากมาตราส่วนลอการิทึม)
float (x, y, z)):scan_071_points.dat จากชุดข้อมูล Freiburg Campus 360, แต่ละจุดมีพิกัด (x, y, z) พิกัด float ): ดังนั้นดูเหมือนว่า leaf_max_size ระหว่าง 10 ถึง 50 จะเหมาะสมที่สุดในแอปพลิเคชันที่ค่าใช้จ่ายของการสืบค้นมีอำนาจ (เช่น ICP) ในปัจจุบันค่าเริ่มต้นคือ 10
KDTreeSingleIndexAdaptorParams::checks พารามิเตอร์นี้ถูกละเว้นใน nanoflann แต่ถูกเก็บไว้เพื่อความเข้ากันได้ย้อนหลังกับอินเทอร์เฟซ Flann ดั้งเดิม เพียงแค่เพิกเฉย
KDTreeSingleIndexAdaptorParams::n_thread_build พารามิเตอร์นี้กำหนดจำนวนเกลียวสูงสุดที่สามารถเรียกได้พร้อมกันระหว่างการสร้างต้นไม้ KD ค่าเริ่มต้นคือ 1 เมื่อพารามิเตอร์ถูกตั้งค่าเป็น 0, nanoflann จะกำหนดจำนวนเธรดที่จะใช้โดยอัตโนมัติ
ดูคำขอดึงนี้สำหรับการเปรียบเทียบบางอย่างแสดงให้เห็นว่าการใช้จำนวนเธรดสูงสุดนั้นไม่ได้เป็นวิธีที่มีประสิทธิภาพมากที่สุดเสมอไป ทำการเปรียบเทียบข้อมูลของคุณ!
nanoflann : การใช้ความทรงจำที่เร็วขึ้นและน้อยลง อ้างถึง "ทำไมส้อม" ส่วนด้านบนสำหรับแนวคิดการเพิ่มประสิทธิภาพหลักที่อยู่เบื้องหลัง nanoflann
ขอให้สังเกตว่าไม่มีการเพิ่มประสิทธิภาพ SSE2/SSE3 ที่ชัดเจนใน nanoflann แต่การใช้ inline และเทมเพลตอย่างเข้มข้นในทางปฏิบัติจะเปลี่ยนเป็นรหัส SSE ที่เพิ่มประสิทธิภาพโดยอัตโนมัติที่สร้างโดยคอมไพเลอร์
flann Original vs nanoflannส่วนที่ใช้เวลานานที่สุดของอัลกอริทึมเมฆหลายจุด (เช่น ICP) กำลังสอบถามต้นไม้ KD สำหรับเพื่อนบ้านที่ใกล้ที่สุด การดำเนินการนี้จึงเป็นเวลาที่สำคัญที่สุด
nanoflann ให้การประหยัดเวลา ~ 50% เกี่ยวกับการใช้งาน flann ดั้งเดิม (เวลาในแผนภูมินี้อยู่ในไมโครวินาทีสำหรับแต่ละแบบสอบถาม):
แม้ว่าอัตราขยายส่วนใหญ่มาจากการสืบค้น (เนื่องจากจำนวนมากในการดำเนินการทั่วไปใด ๆ กับเมฆจุด) แต่ก็มีเวลาบันทึกในขณะที่สร้างดัชนี KD-Tree เนื่องจากรหัส templatized แต่ยังหลีกเลี่ยงการทำซ้ำข้อมูลในเมทริกซ์เสริม
การทดสอบประสิทธิภาพเหล่านี้เป็นเพียงตัวแทนของการทดสอบของเรา หากคุณต้องการทำซ้ำให้อ่านคำแนะนำในการทดสอบอย่างสมบูรณ์แบบ
หมายเหตุ: โลโก้โครงการเกิดจาก Cedarseed
ผู้มีส่วนร่วม
