KD树在PCL中的运用
KD树在PCL中的运用
一、什么是KD树
本质上说,KD树就是一颗平衡二叉树,是将多维空间数据空间划分的一种结构,通常在二维空间和三维空间上使用,根据划分规则将多个点划分为节点空间,划分规则通常是根据距离的平方作为划分权重,即根据距离权重的二分法形成的树结构(表述可能不太适合),目的用于快速查找一个指定点的邻域的其他点的信息。
二、KD树的如何搭建
比如二维空间坐标系下有以下六个点:{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}
通过KD的划分,会划分为以下的树状结构:
三、如何理解这个KD树呢
它的实际意义是:距离(7,2)这个点的最近两个点为(5,4),(9,6)。最近的点是(5,4),由两点间距离评判。假设求最近的三个点,那就在第三层节点中再找一个最近的点。
然而,这个结构有什么作用呢?
在点的数量非常多时候,比如十几万个点,假如你现在想知道十几万个点中,距离(5,4)这个点距离最近的10个点,这时候就显得尤为重要了。一个一个比较,将是巨大的代价,但是有了这个KD树,就很快找到这十个点,只需要十几次的比较就可以找到这些目标点,这就是KD树的主要功能。
四、KD树在点云处理PCL中的使用
都知道在点云数据中存在大量的三维点,那么想要对某些点进行一些算法处理,比如检测特征点,匹配点云数据、及其他的描述算子,这时候就需要使用KD树快速定位到指定点的邻域点,再根据各自算法处理得到最后的结果,这样庞大的数据中处理,因为KD树,可以节省非常多的计算时间,KD树算法主要在搭建KD树过程消耗一些时间,求邻近点几乎不消耗计算时间,对于一个点云数据,应尽量少的初始化KD树。
KD树具有这么先进的优点,那么在PCL中具体是怎么使用的呢?
// kd 树在PCL中的使用例子
//创建点云对象
pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);
// 生成随机点1000个,无序点云
cloud->width=1000;
cloud->height=1;
cloud->points.resize(cloud->width*cloud->height);
for(int i=0;i<cloud->points.size();i++)
{
cloud->points[i].x=1024.0f*rand()/(RAND_MAX+1.0F);
cloud->points[i].y=1024.0f*rand()/(RAND_MAX+1.0F);
cloud->points[i].z=1024.0f*rand()/(RAND_MAX+1.0F);
}
// 创建KD树
pcl::KdTreeFLANN<pcl::PointXYZ>kdtree;
kdtree.setInputCloud(cloud);
// 指定查询的点
pcl::PointXYZ vp;
vp.x=1024.0f*rand()/(RAND_MAX+1.0F);
vp.y=1024.0f*rand()/(RAND_MAX+1.0F);
vp.z=1024.0f*rand()/(RAND_MAX+1.0F);
// 指定最邻近点个数,此时想查询最近的10个点
int k=10;
vector<int>v_id(k);// 用于保存这10个点的id
vector<float>v_dist(k)// 用于保存这10个点到指定点的距离平方
// 获取目标点
if(kdtree.nearestKSearch(vp,k,v_id,v_dist)>0)//>0表示找到,=0表示找不到
{
cout<<"result:"<<endl;
for(int i=0;i<v_id.size();;i++)
{
cout<<"i="<<i<<"---"<<"vid="<<v_id[i]<<"dist="<<v_dist[i]<<endl;
}
}
// 拿到最邻近的点,就可以做相应的算法处理
.....