【原】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 <nanoflann.hpp>在你的代码中。 

1.1 如何使用库

    最简单的方法：将其include/nanoflann.hpp用于需要的地方。

1.2 代码示例

1. KD-trees使用kdd_search()和查找radius_search() ： pointcloud_kdd_radius.cpp

2. 点云数据集上的KD树查找：pointcloud_example.cpp

3. 在动态点云数据集上进行KD树查找：dynamic_pointcloud_example.cpp

4. 旋转组（SO2）上的KD树查找：SO2_example.cpp

5. 旋转组（SO3）上的KD树查找：SO3_example.cpp

6. 使用外部适配器类在点云数据集上查找KD树：pointcloud_adaptor_example.cpp

7. KD-tree使用在Eigen::Matrix<>：matrix_example.cpp上查找

8. KD-tree查找std::vector<std::vector<T> >或std::vector<Eigen::VectorXd>：vector_of_vectors_example.cpp

9. 如何构建索引并将其保存到磁盘供以后使用的示例：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等人。