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