二、kd树

言归正传，NANOFLANN库主要作用是构建kd树，方便查询数据。

2.1 树结构

把集合中的数据按分支关系排列就构成树结构。理解上应该是和聚类差不多的概念，比如在集合{1,25,30,35,60,65}里查找65，单个元素为一类，要是从大到小排列还好，从小到大的话查找时间就直接取决于元素个数N=5。而把元素排列为{1}-{30}-{25,35}和{1}-{60}-{65}两棵子树，查找时间取决于高度h=3。
结论：一个好的树结构能有效提高查找效率 。

一维空间使用平衡二叉树的搜索效率应该是最高的，平衡二叉树要求左右子树的高度差不大于1。

2.2 kd树构建

k维空间通过对每维数据切分来得到树结构，维度选择顺序也影响效率[1]，一般采用交替切分的方式，第一轮选切分维度需要计算方差[2]。分割的对象称为超平面，理想的超平面是对应维度的中位数。直到最大的叶子节点尺寸小于或等于阈值（leaf_max_size）。
对K维空间数据进行切分就构成kd树（k-dimensional tree）。图像参考[1]。

2.3 最近邻搜索

对二维空间而言，给定点p，查询集合中与其距离最近点的过程即为最近邻搜索（Nearest Neighbour，NN）。按照问题的复杂程度，可以分解为两个方面 1-NN与 k-NN，分别表示距离搜索点最近的一个点以及最近的k个点[1]。

1-NN大致流程

(1) 二叉法查找到最近叶子节点，保存最近点和最小距离；
(2) 回溯查找到父节点，在搜索点处以最小距离画圆，圆与其父节点所在超平面相交，则(3)，否则(4)；
(3) 进入对应子树查找到叶子节点，保存最近点和最小距离，执行(4)；
(4) 一直回溯到根节点，圆与根节点所在超平面不相交，则搜索结束，返回最近邻点和最小距离。

详细解释推荐查看[3]。

k-NN与1-NN的区别在于k-NN保存的是最近邻点集和点集的最大距离（FLANN中称为worest distance）。和聚类真的好像。

2.4 FLANN和NANOFLANN

FLANN（Fast Library for Approximate Nearest Neighbors），翻译成中文叫做快速近似最近邻搜索库。
ANN属于对最近邻搜索（NN）的改进，通过将最小距离除以大于1的系数，使过程(3)能更快地筛选节点。这种方式（ANN）能使 NN的查询速度提高10-100倍。

nanoflann是对原始flann库的改进，具体优点参考[4]。

三、makeNN

以下是函数注释。

void CoarseInitializer::makeNN()
	const float NNDistFactor=0.05;
	// 第一个参数为距离, 第二个是特征点集, 第三个是维数
	typedef nanoflann::KDTreeSingleIndexAdaptor<
			nanoflann::L2_Simple_Adaptor<float, FLANNPointcloud> ,
			FLANNPointcloud,2> KDTree;
	// build indices构建索引
	FLANNPointcloud pcs[PYR_LEVELS];
	KDTree* indexes[PYR_LEVELS];
	//遍历金字塔，为每层二维点集建立一个KDTree索引
	for(int i=0;i<pyrLevelsUsed;i++)
		pcs[i] = FLANNPointcloud(numPoints[i], points[i]);//初始化
		indexes[i] = new KDTree(2, pcs[i], nanoflann::KDTreeSingleIndexAdaptorParams(5) );//为每层开辟kd-tree空间
		indexes[i]->buildIndex();//创建最近邻搜索索引
	const int nn=10;//就是k-NN的k
	// find NN & parents遍历金字塔
	for(int lvl=0;lvl<pyrLevelsUsed;lvl++)
		Pnt* pts = points[lvl];//第lvl层特征点集
		int npts = numPoints[lvl];//点集尺寸
		int ret_index[nn];//搜索到的最近邻点集
		float ret_dist[nn];//点集的最大距离
		nanoflann::KNNResultSet<float, int, int> resultSet(nn);//当前层搜索结果
		nanoflann::KNNResultSet<float, int, int> resultSet1(1);//
		//遍历所有特征点
		for(int i=0;i<npts;i++)
			//resultSet.init(pts[i].neighbours, pts[i].neighboursDist );
			resultSet.init(ret_index, ret_dist);//初始化
			Vec2f pt = Vec2f(pts[i].u,pts[i].v);
			indexes[lvl]->findNeighbors(resultSet, (float*)&pt, nanoflann::SearchParams());//使用建立的KDtree, 来查询最近邻
			int myidx=0;
			float sumDF = 0;
			//计算距离和
			for(int k=0;k<nn;k++)
				pts[i].neighbours[myidx]=ret_index[k];
				float df = expf(-ret_dist[k]*NNDistFactor);//计算距离的指数
				sumDF += df;
				pts[i].neighboursDist[myidx]=df;
				assert(ret_index[k]>=0 && ret_index[k] < npts);
				myidx++;
			for(int k=0;k<nn;k++)
				pts[i].neighboursDist[k] *= 10/sumDF;//距离归10化
			if(lvl < pyrLevelsUsed-1 )
				resultSet1.init(ret_index, ret_dist);//初始化
				pt = pt*0.5f-Vec2f(0.25f,0.25f);//转换到高一层
				indexes[lvl+1]->findNeighbors(resultSet1, (float*)&pt, nanoflann::SearchParams());//在高层查询最近邻1-NN
				pts[i].parent = ret_index[0];//保存高层搜索到的最近邻索引
				pts[i].parentDist = expf(-ret_dist[0]*NNDistFactor);//保存距离
				assert(ret_index[0]>=0 && ret_index[0] < numPoints[lvl+1]);
				pts[i].parent = -1;//最高层
				pts[i].parentDist = -1;
	for(int i=0;i<pyrLevelsUsed;i++)
		delete indexes[i];
又重新学了一下FLANN相关的kdtree和最近邻搜索。
 参考了DSO的makeNN函数，重新考虑了一下上面的例子，用程序作为学习成果分享一下。 
#include <iostream>
#include <vector>
#include <math.h>
#include "Eigen/Core"
#include "nanoflann.h"
using namespace std;
//参考DSO的CoarseInitializer.h里的struct FLANNPointcloud的写法
struct Pointcloud
    typedef std::vector<vector<int>> pts;
    inline Pointcloud(int n, pts p) :  num(n), points(p) {}
    int num;
    pts points;//点集
    // 返回数据点的数目
    inline size_t kdtree_get_point_count() const { return num; }
    // 返回欧式距离
    inline float kdtree_distance(const float *p1, const size_t idx_p2,size_t ) const
        const float d0=p1[0]-points[idx_p2][0];
        const float d1=p1[1]-points[idx_p2][1];
        return sqrt(d0*d0+d1*d1);
    inline float kdtree_get_pt(const size_t idx, int dim) const
        if (dim==0) return points[idx][0];
        else return points[idx][1];
    template <class BBOX>
        bool kdtree_get_bbox(BBOX& ) const { return false; }
int main()
    //准备数据
    vector<vector<int>> t_data = {{30,40},{5,25},{35,45},{10,12},{70,70},{50,30}};
    vector<int> test = {6,12};
    int k = t_data[0].size();//样本维度
    int num = t_data.size();//样本数量
    // 第一个参数为distance, 第二个是datasetadaptor, 第三个是维数
    typedef nanoflann::KDTreeSingleIndexAdaptor<
            nanoflann::L2_Simple_Adaptor<float, Pointcloud>,
            Pointcloud, 2> KDTree;
    int neighbours;//最近点
    float neighboursDist;   //最近点的距离
    KDTree* indexes; // 点云建立KDtree
    Pointcloud pcs = Pointcloud(num, t_data); 
    indexes = new KDTree(2, pcs, nanoflann::KDTreeSingleIndexAdaptorParams(3));
    indexes->buildIndex();
    const int nn=1;
    int ret_index[nn];  // 搜索到的临近点
    float ret_dist[nn]; // 搜索到点的距离
    nanoflann::KNNResultSet<float, int, int> resultSet1(1);
    Eigen::Matrix<float,2,1> pt = Eigen::Matrix<float,2,1>(test[0],test[1]); // 当前点
    for(int i=0;i<num;i++)
        resultSet1.init(ret_index, ret_dist);
        // 使用建立的KDtree, 来查询最近邻
        indexes->findNeighbors(resultSet1, (float*)&pt, nanoflann::SearchParams());
        neighbours=ret_index[0]; // 最近的索引
        float df = ret_dist[0]; 
        neighboursDist=df;
    return 0;
这个函数想通过看程序来理解真的有难度，我只能把理论先看一遍，至于nanoflann库的实现只能以后再说了。 
[1] http://www.whudj.cn/?p=920
 [2] https://zhuanlan.zhihu.com/p/53826008
 [3] https://blog.csdn.net/app_12062011/article/details/51986805
 [4] https://www.5axxw.com/wiki/content/g4pz76
				版权声明：可以任意转载，转载时请务必以超链接形式标明文章原始出处和作者信息及本声明http://www.chedong.com/tech/apache_install.html关键词： apache install php resin mod_gzip mod_expire webalizer cronolog内容摘要：Apache是一个历史悠久并且功能十分强大的WEB服务器，但其丰富的功能对于一个新手来说往往不知道从何下手。我个人感觉Apache的设计充分体现了模块化设计的优势，通过在动态模块加载（DSO）模式下的安装，任何子应用模块都可以通过配置文件的简单修改进行积木式的灵活配置。安装的过




    

及其轻量化： ，只用将极少代码问价copy到现有项目中即可实现KNN搜索；
简单易学： github上贴心的提供了实例代码，轻松上手；
**功能强大：**实现多个空间的近邻搜索，对L1，L2，SO2和SO3空间进行距离度量 ；
实例代码容易引起歧义： 没有对输入和输出参数的具体描述，很容
				KDtree相关库nanoflann的应用
在ICP求解运动估计问题中，首先要解决的就是特征关联问题，一般都是利用KD树进行最近邻（NN）搜索，即在点云集A中找出其中每个点在点云集B中的距离最近的点，以实现数据关联。
与PCL中的KD树最近邻搜索相比，更推荐nanoflann方法，后者运行速度更快，且只需要包含少量头文件即可（nanoflann.hpp和nanoflann_utils.h）。
nanoflann实例应用
在source点云中，找出每一个特征点pisrcp^{src}_ipisrc在targ
				FLANN介绍FLANN库全称是Fast Library for Approximate Nearest Neighbors，它是目前最完整的（近似）最近邻开源库。不但实现了一系列查找算法，还包含了一种自动选取最快算法的机制。flann::Index_类该类模板是最近邻索引类，该类用于抽象不同类型的最近邻搜索的索引。 
以下是flann::Index_类的声明：template <typename
				install flann and lz4 from github , uninstall the default ones.sudo apt-get remove liblz4-dev 
sudo apt-get remove libflann-devCMakeList.txtcmake_minimum_required(VERSION 2.8)project(testFlann)file(GLO
具体实现：利用ScanRegistration中提取到的特征点，建立相邻时间点云数据之间的关联，由此推断lidar的运动。
备注：绿色的函数指在下面解释，红色的函数指本文单独的函数解释
代码流程：
1、主函数： main
/** Main node entry point. */
int main(int argc, char ...
我的问题出在了包含目录设置上。具体解决方案是在 属性-&gt;C++目录-&gt;包含目录 中。
之前添加的包含目录是：D:\Program Files (x86)\PCLroot\WIN64\3rdParty\FLANN\include\flann
实际应该去掉\flann，把包含目录改为：D:\Program Files (x86)\PCLroot\WIN64\3r...
				这个错误通常是由于缺少动态共享对象（DSO）引起的。DSO是一种在运行时加载的库，它包含可重定位的代码和数据。如果程序需要使用某个符号，但是该符号在DSO中找不到，就会出现这个错误。
解决这个问题的方法是确保所有需要的DSO都已正确安装，并且程序能够正确地找到它们。您可以尝试使用ldd命令来查看程序所依赖的DSO，或者使用strace命令来跟踪程序在运行时加载DSO的过程。如果您仍然无法解决问题，请尝试在相关的论坛或社区寻求帮助。
                    CSDN-Ada助手: 
                    非常棒的主题！感谢您分享DSO数据读取的经验。我们期待您能继续分享更多关于测试测量方面的经验和技巧。或者，您可以考虑分享一些关于使用DSO测试测量的实际案例，这将非常有帮助。祝写作愉快！
为了方便博主创作，提高生产力，CSDN上线了AI写作助手功能，就在创作编辑器右侧哦～（https://mp.csdn.net/edit?utm_source=blog_comment_recall ）诚邀您来加入测评，到此（https://activity.csdn.net/creatActivity?id=10450&utm_source=blog_comment_recall）发布测评文章即可获得「话题勋章」，同时还有机会拿定制奖牌。
                DSO学习笔记三 makePixelStatus函数
                    我的笔帽呢: 
                    抱歉，是哪里出错了了吗
                DSO学习笔记三 makePixelStatus函数
                    weixin_37247719: 
                    你好,请问有相关的图片和标定数据,可以本地跑一下吗?
                ZED2相机标定
                    qq_41789464: 
                    你好 博主无法注册谷歌账户，不能下载棋盘格文件，能否发我一份
                DSO论文学习有感
                    Ning_Yin: 
                    图像RMSE的计算是不是所有像素的光度误差求均方根？
应该差不多，代码里光度误差再带个huber权重