基于点云空间分布特征的多级索引结构

Multi-level index structure based on spatial distribution characteristics of point cloud

为解决点云数据分布不规则、非均匀产生的查询效率低下的问题,提出了一种基于三维点云数据空间分布特征的多级索引结构。将点云空间信息引入传统八叉树,形成一种新的数据结构——方向八叉树,用于点云空间的全局划分。在每次划分空间之前,先对点云数据进行主成分分析,形成节点的方向包围盒,再进一步将空间划分为八个子空间。为了实现数据的快速调度与查询,在局部,使用KD树对方向八叉树的叶子节点进行二次组织构建。实验结果表明,方向八叉树能有效减少节点总数和冗余节点数量;方向八叉树和KD树的组合嵌套结构可以有效划分海量点云数据,实现点云数据的高效检索,对点云数据进行有效管理。

In order to solve the problem of inefficient querying arising from irregular and uneven distribution of point cloud data, a multi-level index structure based on the spatial distribution characteristics of 3D point cloud data is proposed. The point cloud spatial information is introduced into the traditional octree to form a new data structure-the oriented octree, which is used for the global division of point cloud space. Before each division of the space, a principal component analysis is performed on the point cloud data to form an oriented bounding box of the nodes, and then the space is further divided into eight subspaces. To achieve fast scheduling and querying of data, KD tree is used for the secondary organization and construction of the data in the leaf nodes locally. The experimental results show that the oriented octree can effectively reduce the total number of nodes and the number of redundant nodes, the combined nested structure of oriented octree and KD tree can effectively divide the huge amount of point cloud data, realize efficient retrieval of point cloud data, and effectively manage point cloud data.