nanoflann库
点云处理过程中可能会遇到寻找最临近点的问题，常用的解决方案就是用空间换效率。例如建立kd-tree等树状结构来代替遍历。
这里向大家介绍一个nanoflann工程，nanoflann 算法对fastann进行了改进，效率以及内存使用等方面都进行了优化，而且代码十分轻量级且开源，是一个不错的选择。工程代码下载地址 https://github.com/jlblancoc/nanoflann
1.介绍
nanoflann是一个c++11标准库，用于构建具有不同拓扑（R2，R3（点云），SO(2)和SO(3)（2D和3D旋转组））的KD树。nanoflann不需要编译或安装。你只需要#include
1.1 如何使用库
最简单的方法：将其include/nanoflann.hpp用于需要的地方。
1.2 代码示例
KD-trees使用kdd_search()和查找radius_search() ： pointcloud_kdd_radius.cpp
点云数据集上的KD树查找：pointcloud_example.cpp
在动态点云数据集上进行KD树查找：dynamic_pointcloud_example.cpp
旋转组（SO2）上的KD树查找：SO2_example.cpp
旋转组（SO3）上的KD树查找：SO3_example.cpp
使用外部适配器类在点云数据集上查找KD树：pointcloud_adaptor_example.cpp
KD-tree使用在Eigen::Matrix<>：matrix_example.cpp上查找
KD-tree查找std::vector
如何构建索引并将其保存到磁盘供以后使用的示例：saveload_example.cpp
3. nanoflann可以做什么？
A.建立具有单一索引的KD树（没有随机化的KD树，没有大致的搜索）。快速，线程安全地查询KD树上最近的邻居。接口是：
1. nanoflann :: KDTreeSingleIndexAdaptor <>::knnSearch()
找到num_closest最近的邻居query_point[0:dim-1]。它们的索引存储在结果对象中。查看示例使用代码：
2. nanoflann :: KDTreeSingleIndexAdaptor <>::radiusSearch()
query_point[0:dim-1]在最大半径范围内查找所有邻居。输出作为对的向量给出，其中第一个元素是点索引，第二个元素是相应的距离。查看示例使用代码。
3. nanoflann :: KDTreeSingleIndexAdaptor<>::radiusSearchCustomCallback()
可以用于接收范围内找到的每个点的回叫。这在某些情况下可能更有效，而不是用结果构建一个巨大的向量对。
B. 使用2D和3D点云或N维数据集。
C. 直接使用Eigen::Matrix<>类（矩阵和向量向量）
D. 使用动态点云而无需重建整个kd-tree索引。
E. 使用距离度量标准：
o L1 （曼哈顿）
o L2 （欧几里得，赞成SSE2优化）。
o L2_Simple （欧几里得，用于像点云这样的低维数据集）。
o SO2 （用于旋转组SO2）。
o SO3 （欧几里得，对于旋转组SO3）。
F. 将构建的索引保存并加载到磁盘。
1.4 Nanoflann不能做什么？
使用除L1，L2，SO2和SO3以外的其他距离度量。
支持SE（3）组。
只有C ++接口存在：不支持C，MATLAB或Python。
2.如何选择KD树参数？
2.1 KDTreeSingleIndexAdaptorParams::leaf_max_size
KD树它有一个根节点，一组中间节点，最后是没有孩子的“叶”节点。点只存储在叶节点中。每个叶子都包含一个列表，其中包含哪些点落入其范围内。在构建树的同时，递归地分割节点，直到内部的点数等于或低于某个阈值。那是leaf_max_size。在进行查 时，“树算法”通过选择叶节点结束，然后在叶中的所有元素内对查询的最近点执行线性搜索（一个接一个）。所以，leaf_max_size必须将其设定为合适的值：
· 较大的值意味着树会更快地构建（因为树会更小），但是每个查询会更慢（因为叶子中的线性搜索要完成更多的点）。
· 较小的值将构建树慢得多（将会有许多树节点），但查询会更快......因为搜索的“树部分”（对数复杂度）仍然有很高的成本。
选择哪个数字确实取决于应用程序，甚至取决于处理器高速缓存的大小，因此理想情况下应该执行一些基准测试以最大限度地提高效率。
但为了帮助选择一个比较合适的参数作为一个基准，我提供了以下两个基准。每个图表代表leaf_max_size1到10K之间不同值的树构建（水平）和查询（垂直）时间（95％不确定性椭圆，由于对数标度而变形）。
· 一个100K点云，均匀分布（每个点有（x，y，z）float坐标）：
· 一个来自真实数据集（scan_071_points.dat来自弗莱堡校区360数据集，每个点具有（x，y，z）float坐标）的大约150K点云：
因此，对于查询成本占主导地位的应用（例如ICP），似乎leaf_max_size10到50之间是最佳的。目前，其默认值为10。
3.性能
3.1 nanoflann：更快，更少的内存使用
3.2 原始flann对比nanoflann
许多点云算法（如ICP）中最耗时的部分是查询最近邻居的KD树。因此这个操作是最重要的。nanoflann相对于原始flann实现可节省大约50％的时间（此图表中的时间以微秒为单位）：
由于模板化代码的原因，在构建KD树索引时还节省了一些时间，避免在辅助矩阵中复制数据（下图中的时间以毫秒为单位）：
4.其他KD树项目
FLANN - Marius Muja和David G. Lowe（不列颠哥伦比亚大学）。
FASTANN - James Philbin（VGG，牛津大学）。
ANN - David M. Mount和Sunil Arya（马里兰大学）。
libkdtree ++ - Martin F. Krafft等人。
资源
三维点云论文及相关应用分享
【点云论文速读】基于激光雷达的里程计及3D点云地图中的定位方法
3D目标检测：MV3D-Net
三维点云分割综述（上）
3D-MiniNet: 从点云中学习2D表示以实现快速有效的3D LIDAR语义分割（2020）
win下使用QT添加VTK插件实现点云可视化GUI
JSNet：3D点云的联合实例和语义分割
大场景三维点云的语义分割综述
PCL中outofcore模块---基于核外八叉树的大规模点云的显示
基于局部凹凸性进行目标分割
基于三维卷积神经网络的点云标记
点云的超体素(SuperVoxel)
基于超点图的大规模点云分割
更多文章可查看：点云学习历史文章大汇总
SLAM及AR相关分享
【开源方案共享】ORB-SLAM3开源啦！
【论文速读】AVP-SLAM：自动泊车系统中的语义SLAM
【点云论文速读】StructSLAM:结构化线特征SLAM
SLAM和AR综述
常用的3D深度相机
AR设备单目视觉惯导SLAM算法综述与评价
SLAM综述(4)激光与视觉融合SLAM
Kimera实时重建的语义SLAM系统
SLAM综述(3)-视觉与惯导，视觉与深度学习SLAM
易扩展的SLAM框架-OpenVSLAM
高翔：非结构化道路激光SLAM中的挑战
SLAM综述之Lidar SLAM
基于鱼眼相机的SLAM方法介绍
往期线上分享录播汇总
第一期B站录播之三维模型检索技术
第二期B站录播之深度学习在3D场景中的应用
第三期B站录播之CMake进阶学习
第四期B站录播之点云物体及六自由度姿态估计
第五期B站录播之点云深度学习语义分割拓展
第六期B站录播之Pointnetlk解读
[线上分享录播]点云配准概述及其在激光SLAM中的应用
[线上分享录播]cloudcompare插件开发
[线上分享录播]基于点云数据的 Mesh重建与处理
[线上分享录播]机器人力反馈遥操作技术及机器人视觉分享
[线上分享录播]地面点云配准与机载点云航带平差
点云PCL更多活动请查看：点云PCL活动之应届生校招群
扫描下方微信视频号二维码可查看最新研究成果及相关开源方案的演示：
如果你对本文感兴趣，点击“原文阅读”获取知识星球二维码，务必按照“姓名+学校/公司+研究方向”备注加入免费知识星球，星球可自由发言交流和分享。也可免费下载公众号分享的论文pdf文档，和更多热爱分享的小伙伴一起交流吧！
欢迎各位转发分享朋友圈，将公众号设置为星标，或点击“在看”以示鼓励和支持，让我们继续分享！
以上内容如有错误请留言评论，欢迎指正交流。如有侵权，请联系删除
扫描二维码
关注我们
让我们一起分享一起学习吧！期待有想法，乐于分享的小伙伴加入免费星球注入爱分享的新鲜活力。分享的主题包含但不限于三维视觉，点云，高精地图，自动驾驶，以及机器人等相关的领域。
分享及合作方式：联系微信“920177957”（需要按要求备注）联系邮箱：[email protected]，欢迎企业来联系公众号展开合作。
点一下“在看”你会更好看耶
更多相关：
-
点云PCL免费知识星球，点云论文速读。标题：三维点云分割综述（上）排版：particle欢迎各位加入免费知识星球，获取PDF文档，欢迎转发朋友圈，分享快乐。这是一篇综述性论文，以下只做概述性介绍，介绍文章已共享在微信群和免费知识星球中，文章在公众号将分成三个部分:第一部分介绍点云的获取以及各种传感器获取点云的特性，以及分割概念的区别...
-
点云PCL免费知识星球，点云论文速读。文章：DLL: Direct LIDAR Localization. A map-based localization approach for aerial robots作者：Fernando Caballero1 and Luis Merino编译：点云PCL代码：https://githu...
-
CloudCompare是一个三维点云（网格）编辑和处理软件。最初，它被设计用来对稠密的三维点云进行直接比较。它依赖于一种特定的八叉树结构，在进行点云对比这类任务时具有出色的性能【1】。此外，由于大多数点云都是由地面激光扫描仪采集的，CloudCompare的目的是在一台标准笔记本电脑上处理大规模的点云——通常超过1000万个点云。...
-
点云PCL免费知识星球，点云论文速读。文章：Open3DGen: Open-Source Software for Reconstructing Textured 3D Models from RGB-D Images作者：Teo T. Niemirepo, Marko Viitanen, and Jarno Vanne编译：点云P...
-
点云PCL免费知识星球，点云论文速读。标题：Real-Time Spatio-Temporal LiDAR Point Cloud Compression作者：Yu Feng , Shaoshan Liu , and Yuhao Zhu来源：2020IROS本文仅做学术分享，如有侵权，请联系删除。欢迎各位加入免费知识星球，获取PDF...
-
标题：Voxelized GICP for Fast and Accurate 3D Point Cloud Registration作者：Kenji Koide, Masashi Yokozuka, Shuji Oishi, and Atsuhiko Banno来源：分享者代码：https://github.com/SMRT-AI...
-
点云PCL免费知识星球，点云论文速读。标题：LIC-Fusion 2.0: LiDAR-Inertial-Camera Odometry with Sliding-Window Plane-Feature Tracking作者：Xingxing Zuo1;2, Yulin Yang3, Patrick Geneva3, Jiajun...
-
点云PCL免费知识星球，点云论文速读。标题：CMRNet++: Map and Camera Agnostic Monocular Visual Localization in LiDAR Maps作者：Daniele Cattaneo, Domenico Giorgio Sorrenti, Abhinav Valada来源：分享者...
-
点云PCL免费知识星球，点云论文速读。标题：LIO-SAM: Tightly-coupled Lidar Inertial Odometry via Smoothing and Mapping作者：Tixiao Shan, Brendan Englot, Drew Meyers, Wei Wang, Carlo Ratti, and...
-
前言CloudCompare是另一款开源且完善的点云处理软件，我们可以在这款软件的基础上，任意的设计成我们想要的界面，可以说是点云处理软件的最佳选择，所以我认为如果你是研究点云算法的可以使用PCL，GDAL,等其他库，如果你是做工程的需要点云的界面显示，那么cloudCompare就是不二选择，当然如果是简单的界面使用PCL和QT也...