一种新的散乱点云数据多级空间索引

散乱点云数据具有数据量大（海量性）、数据表达精细（高空间分辨率）、空间三维点之间无拓扑关系（散乱性）等特征,在对其进行应用前必须进行数据预处理（如去噪、配准、分割等）。而在这些数据处理过程中需频繁的进行邻域查找,如果没有高效的查询索引机制,很难实现数据自动处理。因此,如何进行数据的组织和索引,以提高后续邻域检索和查询等操作的速度,是目前点云数据处理中的一个研究热点。针对现有点云数据采用的空间索引方式的优缺点,本文提出了一种多级格网和KD树混合的空间索引,该索引提出变分辨率格网索引与KD树的混合索引模式,简称MultiGrid-KD树索引。该方法在保持网格索引算法实现简单查询效率高等优点的同时,解决了单一分辨率数据冗余的问题。以故宫太和殿的点云数据为例,对本文提出的MultiGrid-KD树索引算法和KD树、八叉树等经典算法做对比。结果表明,本文索引方法在最邻近点查询以及四邻域查询的效率上均优于KD树,以及八叉树索引。

A New Multi-level Spatial Index of Scattered Point Cloud Data

Laser scanning technology has been widely used in cultural relic protection because of its speed, accuracy, non-touch, real-time and automatism. As the product of laser scanning, point cloud data has the following characteristics: a large amount of data (mass), high spatial resolution and no topological relations between the three dimensional points (scattering). Point cloud data must be processed before using. Point cloud data processing includes de-noising, registration, merge, segmentation and so on. Neighborhood searching will be frequently needed during the procedure of point cloud data processing. Therefore, the data must be organized and the spatial index should be constructed to improve the speed of neighborhood searching and query. Currently, the main algorithms of three dimensional spatial indexing for point cloud data are regular grid, quadtree, octree, KD-tree, R-tree and so on. Among these algorithms, the octree and KD-tree are used most frequently. The octree algorithm is easy to be applied and is adaptive to the data with an evenly distributing tendency. But considering the irregular distributing point cloud data in ancient architectures, it is proved to be inefficient. KD-tree is the extension of the binary tree. It divides the space based on the data distribution rather than divides the space into two parts rigidly such as the quad-tree and octree. It is more efficient in neighborhood searching. But taking into a large amount of data, the depth of KD-tree will be too big to conduct neighborhood searching efficiently. Since the single spatial index cannot adapt to all types of data, the multi-level spatial index is a hot spot of current studies. According to the merits and demerits of existing spatial index algorithms, a new composed index of multi-grid and KD-tree was proposed. The algorithm integrates the developing regular grid index and KD-tree index. It is easily applied and very efficient for neighborhood searching. Through an experiment using the Forbidden City data, compared with the KD-tree index and octree index, the newly proposed index was proved to perform better than the KD-Tree index and octree index with respect to neighborhood searching efficiency.