4.1 k-d tree和八叉树的概念及相关算法

4.1.1 k-d tree概念及相关算法

k-d tree简介

k-d tree，或称k维树，是计算机科学中使用的一种数据结构，用来组织表示k维空间中的点集合，如图4-1所示。它是一种带有其他约束条件的二分查找树。k-d tree对于区间和近邻搜索十分有用。我们为了达到目的，通常只在三个维度中进行处理，因此所有的k-d tree都将是三维k-d tree。k-d tree的每一级在指定维度上分开所有的子节点。在树的根部，所有子节点在第一个指定的维度上被分开（也就是说，第一维坐标小于根节点的点将分在左边的子树中，大于根节点的点将分在右边的子树中）。树的每一级都在下一个维度上分开，所有其他的维度用完之后就回到第一个维度。建立k-d tree最高效的方法是，像快速分类一样使用分割法，把指定维度的值放在根上，在该维度上包含较小数值的在左子树，较大的在右子树。然后分别在左边和右边的子树上重复这个过程，直到你准备分类的最后一个树仅仅由一个元素组成。

图4-1 k-d tree示例（来自wiki）

4.1.2 PCL中k-d tree模块及类

PCL中k-d tree库提供了k-d tree数据结构，基于FLANN进行快速最近邻检索。最近邻检索在匹配、特征描述子计算、邻域特征提取中是非常基础的核心操作。k-d tree模块利用两个类与两个函数实现了利用k-d tree 数据结构对点云的高效管理和检索，其依赖于pcl＿common 模块。具体说明受篇幅所限，请感兴趣的读者自行查询相关资料以及 http：//docs.pointclouds.org/trunk/group＿k-d tree.html。

4.1.3 八叉树概念及相关算法

八叉树简介

八叉树结构是Hunter博士于1978年首次提出的一种数据模型，如图4-2所示。八叉树结构通过循环递归的划分方法对大小为2n×2n×2n的三维空间的几何对象进行剖分，从而构成一个具有根节点的方向图。在八叉树结构中如果被划分的体元具有相同的属性，则该体元构成一个叶节点；否则继续将该体元剖分成8个子立方体，依次递归剖分。对于2n×2n×2n大小的空间对象，最多剖分n次。

图4-2 八叉树示例（来自wiki）

4.1.4 PCL中八叉树模块及类

PCL中八叉树库提供了八叉树数据结构，利用FLANN进行快速邻域检索。邻域检索在匹配、特征描述子计算、邻域特征提取中是非常基础的核心操作。八叉树模块利用15个类实现了利用八叉树数据结构对点云的高效管理和检索，以及相应的一些空间处理算法，例如压缩、空间变化检测，其依赖于pcl＿common模块。具体说明受篇幅所限，请感兴趣的读者自行查阅相关资料http：//docs.pointclouds.org/trunk/group＿octree.html。