تنزيل nanoflann - تنزيل رمز المصدر nanoflann

nanoflann

ج/ج++

v1.6.2

تنزيل

1

Nanoflann هي مكتبة C ++ 11 رأس فقط لبناء أشجار KD من مجموعات البيانات مع طوبولوجيا مختلفة: R ² ، R ³ (النقاط السحب) ، لذلك (2) وهكذا (3) (مجموعات الدوران 2D و 3D). لا يتم توفير أي دعم لل NN التقريبي. لا يتطلب Nanoflann التجميع أو التثبيت. تحتاج فقط إلى #include <nanoflann.hpp> في الكود الخاص بك.

هذه المكتبة هي شوكة لمكتبة Flann من تأليف ماريوس موجة وديفيد ج. لوي ، ولدت كمشروع طفل ل 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 مع knnSearch() و radiusSearch() : pointcloud_kdd_radius.cpp
بحث KD Tree على مجموعة بيانات Cloud Point: pointcloud_example.cpp
البحث عن KD Tree على مجموعة بيانات Cloud Dynamic Point: Dynamic_PointCloud_Example.cpp
بحث KD Tree على مجموعة دوران (SO2): so2_example.cpp
البحث عن شجرة KD على مجموعة دوران (SO3): SO3_EXAMPLE.CPP
بحث KD Tree على مجموعة بيانات Cloud Point مع فئة محول خارجي: pointcloud_adaptor_example.cpp
kd-tree salept مباشرة على Eigen::Matrix<> : matrix_example.cpp
kd-tree appet مباشرة على std::vector<std::vector<T> > أو std::vector<Eigen::VectorXd> : vector_of_vectors_example.cpp
مثال مع Makefile للاستخدام من خلال pkg-config (على سبيل المثال ، بعد القيام "بإجراء تثبيت" أو بعد التثبيت من مستودعات Ubuntu): example_with_pkgconfig/
مثال على كيفية إنشاء فهرس وحفظه على القرص للاستخدام لاحقًا: saveload_example.cpp
أمثلة واجهة المستخدم الرسومية (تتطلب mrpt-gui ، eg sudo apt install libmrpt-gui-dev ):
- nanoflann_gui_example_r3

Nanoflann-Demo-1

1.4. لماذا شوكة؟

كفاءة وقت التنفيذ :
- تأتي قوة مكتبة flann الأصلية من إمكانية الاختيار بين خوارزميات ANN المختلفة. تكلفة هذه المرونة هي إعلان الأساليب الافتراضية الخالصة التي (في بعض الظروف) تفرض عقوبات في وقت التشغيل. في nanoflann تم استبدال جميع هذه الأساليب الافتراضية بمجموعة من نمط القالب المتكرر الغريب (CRTP) والطرق المضمّنة ، والتي تكون أسرع بكثير.
- بالنسبة إلى radiusSearch() ، ليست هناك حاجة لإجراء مكالمة لتحديد عدد النقاط داخل نصف القطر ثم اتصل بها مرة أخرى للحصول على البيانات. باستخدام حاويات STL لبيانات الإخراج ، يتم تغيير حجم الحاويات تلقائيًا.
- يمكن للمستخدمين (اختياريًا) تعيين أبعاد المشكلة في وقت الترجمة عبر وسيطة قالب ، وبالتالي السماح للمترجم بفصل الحلقات بالكامل.
- يسمح nanoflann للمستخدمين بتوفير مربع ملزم مسبقًا للبيانات ، إن وجدت ، لتجنب إعادة التثبيت.
- تم تحويل مؤشرات نقاط البيانات من int إلى size_t ، والتي تزيل الحد الأقصى عند التعامل مع مجموعات البيانات الكبيرة جدًا.
كفاءة الذاكرة : بدلاً من إنشاء نسخة من مجموعة البيانات بأكملها في مصفوفة مثل flann المخصصة قبل إنشاء فهرس KD Tree ، يسمح nanoflann بالوصول المباشر إلى بياناتك عبر واجهة محول يجب تنفيذها في فئتك.

ارجع إلى الأمثلة أدناه أو إلى C ++ API من Nanoflann :: KdtreeSingleIndexAdaptor <> لمزيد من المعلومات.

1.5. ماذا يمكن أن يفعل نانوفلان ؟

بناء أشجار KD مع فهرس واحد (لا توجد أشجار KD عشوائية ، لا عمليات تفتيش تقريبية).
سريع ، الاستعلام الآمن للخيط لأقرب الجيران على أشجار KD. نقاط الدخول هي:
- Nanoflann :: KdtreesingleIndexAdaptor <> ::knnSearch()
  - يجد أقرب جيران num_closest إلى query_point[0:dim-1] . يتم تخزين مؤشراتهم داخل كائن النتيجة. انظر مثال رمز الاستخدام.
- Nanoflann :: KdtreesingleIndexAdaptor <> ::radiusSearch()
  - يجد جميع الجيران إلى query_point[0:dim-1] داخل نصف قطرها القصوى. يتم إعطاء الإخراج كمتجه للأزواج ، والذي يكون العنصر الأول هو فهرس النقطة والثاني المسافة المقابلة. انظر مثال رمز الاستخدام.
- Nanoflann :: KdtreesingleIndexAdaptor <> ::radiusSearchCustomCallback()
  - يمكن استخدامها لتلقي رد اتصال لكل نقطة موجودة في النطاق. قد يكون هذا أكثر كفاءة في بعض المواقف بدلاً من بناء متجه كبير من الأزواج مع النتائج.
العمل مع السحب 2D و 3D Point أو مجموعات بيانات N- الأبعاد.
العمل مباشرة مع Eigen::Matrix<> فئات (المصفوفات والمتجهات في المجالات).
العمل مع الغيوم النقطة الديناميكية دون الحاجة إلى إعادة بناء مؤشر KD Tree بالكامل.
العمل مع مقاييس المسافة:
- R^N : المساحات الإقليدية:
  - L1 (مانهاتن)
  - L2 (قاعدة إقليدية مربعة ، لصالح تحسين SSE2).
  - L2_Simple (قاعدة الإقليدية التربيعة ، لمجموعات بيانات الأبعاد المنخفضة مثل السحب النقطة).
- SO(2) : مجموعة الدوران 2D
  - metric_SO2 : الاختلاف الزاوي المطلق.
- SO(3) : مجموعة الدوران ثلاثية الأبعاد (من الأفضل أن يتم توفيرها في الإصدارات المستقبلية)
  - metric_SO3 : المنتج الداخلي بين الرباعي.
يحفظ وتحميل المؤشرات المبنية على القرص.
الدعم المستند إلى واجهة المستخدم الرسومية لقياس مكتبات KD Tree المتعددة وهي Nanoflann و Flann و Fastann و Libkdtree.

1.6. ما الذي لا يمكن أن يفعله نانوفلان ؟

استخدم مقاييس المسافة الأخرى بصرف النظر عن L1 و L2 و SO2 و SO3.
دعم مجموعات SE (3).
توجد واجهة C ++ فقط: لا يوجد دعم لـ C أو Matlab أو Python.
لا يوجد تكوين خوارزمية تلقائي (كما هو موضح في ورقة Muja & Lowe الأصلية).

1.7. استخدم في مشروعك عبر cmake

يمكنك إسقاط ملف nanoflann.hpp مباشرة في مشروعك. بدلاً من ذلك ، تتوفر طريقة Cmake Standard أيضًا:

بناء و "تثبيت" 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 Conan من قبل محفوظات Conan والمساهمين في المجتمع. إذا كان الإصدار قديمًا ، فيرجى إنشاء مشكلة أو سحب طلب على مستودع ConancenSerIndex.

باستخدام `vcpkg`

يمكنك تنزيل وتثبيت Nanoflann باستخدام مدير التبعية VCPKG:

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

يتم الحفاظ على ميناء Nanoflann في VCPKG من قبل أعضاء فريق Microsoft والمساهمين في المجتمع. إذا كان الإصدار قديمًا ، فيرجى إنشاء مشكلة أو سحب طلب على مستودع VCPKG.

1.9. تجميع تعريفات الوقت

NANOFLANN_FIRST_MATCH : إذا تم تحديدها ونقطتين لهما نفس المسافة ، فسيتم إرجاع النقطتين ذات المؤتمر الأدنى أولاً. وإلا لا يوجد ترتيب معين.
NANOFLANN_NO_THREADS : إذا تم تحديد إمكانات التعددية المعدلة ، بحيث يمكن استخدام المكتبة دون الارتباط باستخدام pthreads. إذا حاول المرء استخدام مؤشرات ترابط متعددة ، فسيتم طرح استثناء.

2. أي مساعدة في اختيار معلمات KD Tree؟

2.1. `KDTreeSingleIndexAdaptorParams::leaf_max_size`

شجرة KD هي ... حسنا ، شجرة :-). وعلى هذا النحو ، فإنه يحتوي على عقدة جذر ، ومجموعة من العقد الوسيطة وأخيراً ، العقد "الأوراق" التي هي تلك التي لا تحتوي على أطفال.

يتم تخزين النقاط (أو بشكل صحيح ، مؤشرات النقاط) فقط في العقد الأوراق. تحتوي كل ورقة على قائمة تندرج فيها النقاط ضمن نطاقها.

أثناء بناء الشجرة ، يتم تقسيم العقد بشكل متكرر حتى يكون عدد النقاط الموجودة في الداخل متساوية أو أقل من بعض العتبة. هذا هو leaf_max_size . أثناء إجراء الاستعلامات ، تنتهي "خوارزمية الأشجار" عن طريق اختيار العقد الورقية ، ثم إجراء بحث خطي (واحدًا تلو الآخر) لأقرب نقطة إلى الاستعلام داخل جميع تلك الموجودة في الورقة.

لذلك ، يجب تعيين leaf_max_size كمدافع :

تعني القيم الكبيرة أن الشجرة سيتم بناؤها بشكل أسرع (نظرًا لأن الشجرة ستكون أصغر) ، لكن كل استعلام سيكون أبطأ (نظرًا لأن البحث الخطي في الورقة يجب أن يتم على المزيد من النقاط).
ستقوم القيم الصغيرة ببناء الشجرة أبطأ بكثير (سيكون هناك العديد من عقد الأشجار) ، لكن الاستعلامات ستكون أسرع ... حتى مرحلة ما ، لأن "جزء الأشجار" للبحث (التعقيد اللوغاريتمي) لا يزال له تكلفة كبيرة.

يعتمد الرقم الذي يجب تحديده حقًا على التطبيق وحتى على حجم ذاكرة ذاكرة التخزين المؤقت للمعالج ، لذلك من الناحية المثالية ، يجب عليك القيام ببعض المعايير لزيادة الكفاءة.

ولكن للمساعدة في اختيار قيمة جيدة كقاعدة عامة ، أقدم المعايير التالية. يمثل كل رسم بياني بناء الأشجار (الأفقي) والاستعلام (العمودي) لقيم leaf_max_size مختلفة بين 1 و 10 كيلو (مثل 95 ٪ من حالات عدم اليقين ، مشوهة بسبب المقياس اللوغاريتمي).

سحابة نقطة 100k ، موزعة بشكل موحد (كل نقطة لديها (x ، y ، z) إحداثيات float ):

A ~ 150k Point Cloud من مجموعة بيانات حقيقية ( scan_071_points.dat من مجموعة بيانات Freiburg Campus 360 ، تحتوي كل نقطة على float (x ، y ، z)

لذلك ، يبدو أن leaf_max_size بين 10 و 50 سيكون الأمثل في التطبيقات التي تهيمن فيها تكلفة الاستعلامات (مثل ICP). في الوقت الحاضر ، قيمتها الافتراضية هي 10.

2.2. `KDTreeSingleIndexAdaptorParams::checks`

يتم تجاهل هذه المعلمة حقًا في nanoflann ، ولكن تم الاحتفاظ بها للتوافق المتخلف مع واجهة Flann الأصلية. فقط تجاهلها.

2.3. `KDTreeSingleIndexAdaptorParams::n_thread_build`

تحدد هذه المعلمة الحد الأقصى لعدد الخيوط التي يمكن استدعاؤها بشكل متزامن أثناء بناء شجرة KD. القيمة الافتراضية هي 1. عند ضبط المعلمة على 0 ، تحدد nanoflann تلقائيًا عدد مؤشرات الترابط المراد استخدامها.

راجع طلب السحب هذا لبعض المقاييس التي توضح أن استخدام الحد الأقصى لعدد المواضيع ليس دائمًا هو النهج الأكثر كفاءة. هل القياس على بياناتك!

3. الأداء

3.1. `nanoflann` : استخدام ذاكرة أسرع وأقل

الرجوع إلى "لماذا شوكة؟" القسم أعلاه لأفكار التحسين الرئيسية وراء nanoflann .

لاحظ أنه لا توجد تحسينات صريحة SSE2/SSE3 في nanoflann ، ولكن الاستخدام المكثف inline والقوالب في الممارسة العملية يتحول إلى رمز محسّن SSE تلقائيًا الذي تم إنشاؤه بواسطة برنامج التحويل البرمجي.

3.2. المعيار: `flann` الأصلي مقابل `nanoflann`

الجزء الأكثر استهلاكًا للوقت من العديد من خوارزميات Cloud Cloud (مثل ICP) هو الاستعلام عن شجرة KD لأقرب الجيران. وبالتالي فإن هذه العملية هي الأكثر أهمية.

يوفر nanoflann توفير الوقت بنسبة 50 ٪ فيما يتعلق بتنفيذ flann الأصلي (الأوقات في هذا المخطط في Microseconds لكل استعلام):

على الرغم من أن معظم المكاسب تأتي من الاستعلامات (بسبب العدد الكبير منها في أي عملية نموذجية مع غيوم النقطة) ، هناك أيضًا بعض الوقت المحفوظ أثناء بناء مؤشر الشجرة KD ، بسبب الكود المعبد ، وأيضًا لتجنب تكرار البيانات في مصفوفة الإفراطية (الأوقات في الرسم القادم في Milliseconds):

اختبارات الأداء هذه تمثل فقط اختبارنا. إذا كنت ترغب في تكرارها ، فاقرأ التعليمات في اختبارات perf