《点云库PCL学习教程》第章 kdtree.pptx

第5章 kd-tree 通过雷达、激光扫描、立体摄像机等三维测量设备获取的点云数据，具有数据量大、分布不均匀等特点。作为三维领域中一个重要的数据来源，点云数据主要是表征目标表面的海量点集合，并不具备传统实体网格数据的几何拓扑信息。所以点云数据处理中最为核心的问题就是建立离散点间的拓扑关系，实现基于邻域关系的快速查找。 本章首先对常用的点云空间索引方法kd-tree概念进行介绍，然后对PCL的kd-tree相关模块及类进行简单说明，最后通过应用实例来展示如何灵活应用PCL中kd-tree模块。 本章各小节目录 5.1 kd-tree概念简介 5.2 PCL中kd-tree模块及类介绍 5.3 应用实例解析 5.1 kd-tree概念简介 Kd-tree或者k维树是计算机科学中使用的一种数据结构，用来组织表示k维空间中点集合。它是一种带有其他约束条件的二分查找树。kd-tree对于区间和近邻有哪些信誉好的足球投注网站十分有用。我们为了达到目的，通常只在三个维度中进行处理，因此所有的kd-tree都将是三维kd-tree。如图5-1所示，kd-tree的每一级在指定维度上分开所有的子节点。在树的根部所有子节点是以第一个指定的维度上被分开（也就是说，如果第一维坐标小于根节点的点它将分在左边的子树中，如果大于根节点的点它将分在右边的子树中）。 树的每一级都在下一个维度上分开，所有其他的维度用完之后就回到第一个维度。建立kd-tree最高效的方法是，像快速分类一样使用分割法，把指定维度的值放在根上，在该维度上包含较小数值的在左子树，较大的在右子树。然后分别在左边和右边的子树上重复这个过程，直到用户准备分类的最后一个树仅仅由一个元素组成。 5.2 PCL中kd-tree模块及类介绍 PCL中kd-tree库提供了kd-tree数据结构，基于FLANN进行快速最近邻检索。最近邻检索在匹配、特征描述子计算、邻域特征提取中是非常基础的核心操作。kd-tree模块利用三个类与两个函数实现了利用kd-tree数据结构对点云的高效管理和检索，其依赖于pcl_common模块。 5.1.1 kd-tree模块中类说明以及全局函数说明 kd-tree模块中目前共有3个类，以后有可能增加以下两个类。 1. class pcl::KdTreePointT 类KdTree是kd-tree数据结构的实现，并且是具有近邻有哪些信誉好的足球投注网站实现的类KdTreeFLANN的基类，其继承关系如图5-2所示。 图5-2 kd-tree模块中类的继承关系 类KdTree关键成员函数 KdTree(bool sorted=true) 空的构造函数 virtual void setInputCloud(const PointCloudConstPtr cloud, const IndicesConstPtr indices=IndicesConstPtr()) 设置输入点云，参数cloud为输入点云的共享指针引用，indices为在kd-tree中使用的点对应的索引，如果不设置，则默认使用整个点云填充kd-tree。 virtual~KdTree() 析构函数。 virtual int nearestKSearch(const PointT p_q, int k, std::vectorint k_indices, std::vectorfloat k_sqr_distances) const = 0 纯虚函数，具体实现在其子类KdTreeFLANN中，其用来 进行K邻域有哪些信誉好的足球投注网站，参数p_q为需要查询的点，k为K邻域个数，k_indices为有哪些信誉好的足球投注网站完的邻域点对应的索引，k_sqr_distances为有哪些信誉好的足球投注网站完的每个领域点与查询点之间的欧式距离。 virtual int nearestKSearch(const PointCloud cloud, int index, int k, std::vectorint k_indices, std::vectorfloat k_sqr_distances) const 纯虚函数，具体实现在其子类KdTreeFLANN中，参数cloud为需要查询的点集合，index为点集合中需要查询点的索引，其他参数同上。 virtual int nearestKSearch(int index, int k, std::vectorint k_indices, std::vectorfloat k_sqr_distances) const 纯虚函数，具体实现在其子类KdTreeFLANN中，其用来进行k邻域有哪些信誉好的足球投注网站，参数index为点云中需要查询点的索引，其他参数同上。 virtual int radiusSearch(const PointT p_q, double radius, std::vec