《点云库PCL学习教程》第5章 kd-tree.ppt

《《点云库PCL学习教程》第5章 kd-tree.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、点的点它将分在左边的子树中，如果大于根节点的点它将分在右边的子树中）。树的每一级都在下一个维度上分开，所有其他的维度用完之后就回到第一个维度。建立kd-tree最高效的方法是，像快速分类一样使用分割法，把指定维度的值放在根上，在该维度上包含较小数值的在左子树，较大的在右子树。然后分别在左边和右边的子树上重复这个过程，直到用户准备分类的最后一个树仅仅由一个元素组成。5.2PCL中kd-tree模块及类介绍PCL中kd-tree库提供了kd-tree数据结构，基于FLANN进行快速最近邻检索。最近邻检索在匹配、特征

4、描述子计算、邻域特征提取中是非常基础的核心操作。kd-tree模块利用三个类与两个函数实现了利用kd-tree数据结构对点云的高效管理和检索，其依赖于pcl_common模块。5.1.1kd-tree模块中类说明以及全局函数说明kd-tree模块中目前共有3个类，以后有可能增加以下两个类。1.classpcl::KdTree类KdTree是kd-tree数据结构的实现，并且是具有近邻搜索实现的类KdTreeFLANN的基类，其继承关系如图5-2所示。图5-2kd-tree模块中类的继承关系类Kd

5、Tree关键成员函数KdTree(boolsorted=true)空的构造函数virtualvoidsetInputCloud(constPointCloudConstPtr&cloud,constIndicesConstPtr&indices=IndicesConstPtr())设置输入点云，参数cloud为输入点云的共享指针引用，indices为在kd-tree中使用的点对应的索引，如果不设置，则默认使用整个点云填充kd-tree。virtual~KdTree()析构函数。virtualintnearest

6、KSearch(constPointT&p_q,intk,std::vector&k_indices,std::vector&k_sqr_distances)const=0纯虚函数，具体实现在其子类KdTreeFLANN中，其用来进行K邻域搜索，参数p_q为需要查询的点，k为K邻域个数，k_indices为搜索完的邻域点对应的索引，k_sqr_distances为搜索完的每个领域点与查询点之间的欧式距离。virtualintnearestKSearch(constPointCloud&c

7、loud,intindex,intk,std::vector&k_indices,std::vector&k_sqr_distances)const纯虚函数，具体实现在其子类KdTreeFLANN中，参数cloud为需要查询的点集合，index为点集合中需要查询点的索引，其他参数同上。virtualintnearestKSearch(intindex,intk,std::vector&k_indices,std::vector&k_sqr_distances)co

8、nst纯虚函数，具体实现在其子类KdTreeFLANN中，其用来进行k邻域搜索，参数index为点云中需要查询点的索引，其他参数同上。virtualintradiusSearch(constPointT&p_q,doubleradius,std::vector&k_indices,std::vector&k_sqr_distances,unsignedintma