《点云库PCL学习教程》kdtreePPT课件

1、第5章 kd-tree,1,.,通过雷达、激光扫描、立体摄像机等三维测量设备获取的点云数据，具有数据量大、分布不均匀等特点。作为三维领域中一个重要的数据来源，点云数据主要是表征目标表面的海量点集合，并不具备传统实体网格数据的几何拓扑信息。所以点云数据处理中最为核心的问题就是建立离散点间的拓扑关系，实现基于邻域关系的快速查找。 本章首先对常用的点云空间索引方法kd-tree概念进行介绍，然后对PCL的kd-tree相关模块及类进行简单说明，最后通过应用实例来展示如何灵活应用PCL中kd-tree模块。,2,.,本章各小节目录,5.1 kd-tree概念简介 5.2 PCL中kd-tree模块及类

2、介绍 5.3 应用实例解析,3,.,5.1 kd-tree概念简介,Kd-tree或者k维树是计算机科学中使用的一种数据结构，用来组织表示k维空间中点集合。它是一种带有其他约束条件的二分查找树。kd-tree对于区间和近邻搜索十分有用。我们为了达到目的，通常只在三个维度中进行处理，因此所有的kd-tree都将是三维kd-tree。如图5-1所示，kd-tree的每一级在指定维度上分开所有的子节点。在树的根部所有子节点是以第一个指定的维度上被分开（也就是说，如果第一维坐标小于根节点的点它将分在左边的子树中，如果大于根节点的点它将分在右边的子树中）。,4,.,树的每一级都在下一个维度上分开，所有其

3、他的维度用完之后就回到第一个维度。建立kd-tree最高效的方法是，像快速分类一样使用分割法，把指定维度的值放在根上，在该维度上包含较小数值的在左子树，较大的在右子树。然后分别在左边和右边的子树上重复这个过程，直到用户准备分类的最后一个树仅仅由一个元素组成。,5,.,5.2 PCL中kd-tree模块及类介绍,PCL中kd-tree库提供了kd-tree数据结构，基于FLANN进行快速最近邻检索。最近邻检索在匹配、特征描述子计算、邻域特征提取中是非常基础的核心操作。kd-tree模块利用三个类与两个函数实现了利用kd-tree数据结构对点云的高效管理和检索，其依赖于pcl_common模块。,

4、6,.,5.1.1 kd-tree模块中类说明以及全局函数说明 kd-tree模块中目前共有3个类，以后有可能增加以下两个类。 1. class pcl:KdTree 类KdTree是kd-tree数据结构的实现，并且是具有近邻搜索实现的类KdTreeFLANN的基类，其继承关系如图5-2所示。,图5-2 kd-tree模块中类的继承关系,7,.,类KdTree关键成员函数 KdTree(bool sorted=true) 空的构造函数 virtual void setInputCloud(const PointCloudConstPtr /用系统时间初始化随机种子 pcl:PointClou

5、d:Ptr cloud(new pcl:PointCloud); /随机点云生成 cloud-width=1000; /此处为点云数量 cloud-height=1; /此处表示点云为无序点云 cloud-points.resize(cloud-width*cloud-height); for(size_t i=0; ipoints.size(); +i) /循环填充点云数据 cloud-pointsi.x=1024.0f*rand()/(RAND_MAX+1.0f); cloud-pointsi.y=1024.0f*rand()/(RAND_MAX+1.0f); cloud-pointsi.

6、z=1024.0f*rand()/(RAND_MAX+1.0f); ,17,.,下面的代码块创建了KdTreeFLANN对象，并把创建的点云设置成输入，然后创建一个searchPoint变量作为查询点，并且分配随机坐标值给它。 pcl:KdTreeFLANN kdtree; /创建kd-tree对象 kdtree.setInputCloud(cloud); /设置搜索空间 pcl:PointXYZ searchPoint; /定义查询点并赋随机值 searchPoint.x=1024.0f*rand()/(RAND_MAX+1.0f); searchPoint.y=1024.0f*rand()

7、/(RAND_MAX+1.0f); searchPoint.z=1024.0f*rand()/(RAND_MAX+1.0f); 现在创建一个整数（设置成10）和两个向量来存储搜索到的K近邻，两个向量中一个存储搜索到查询点近邻的索引，另一个存储对应近邻的距离平方。 /k近邻搜索 int K=10; std:vector pointIdxNKNSearch(K); /存储查询点近邻索引,18,.,std:vector pointNKNSquaredDistance(K); /存储近邻点对应距离平方 std:cout0) /执行k近邻搜索 for(size_t i=0; ipointspointId

8、xNKNSearchi.xpointspointIdxNKNSearchi.ypointspointIdxNKNSearchi.z“(squared distance:”pointNKNSquaredDistancei“)”std:endl; ,19,.,下面代码展示查找到给定searchPoint的某一半径（随机产生）内的所有近邻，重新定义两个向量pointIdxRadiusSearch、pointRadiusSquaredDistance来存储关于近邻的信息。 /半径r内近邻搜索方式 std:vector pointIdxRadiusSearch; /存储近邻索引 std:vector p

9、ointRadiusSquaredDistance; /存储近邻对应的距离平方 float radius=256.0f*rand()/(RAND_MAX+1.0f); 像之前一样，如果kd-tree对象在指定半径内返回多于0个近邻，它将打印输出向量中存储的点的坐标与距离。 if(kdtree.radiusSearch(searchPoint, radius, pointIdxRadiusSearch, pointRadiusSquaredDistance)0) for(size_t i=0; ipointIdxRadiusSearch.size(); +i),20,.,Std:coutpointspointIdxRa