地球信息科学学报

地球信息科学学报 ›› 2015, Vol. 17 ›› Issue (12): 1450-1455.doi: 10.3724/SP.J.1047.2015.01450

• 地球信息科学理论与方法 • 上一篇    下一篇

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

赵江洪1(), 王继伟2, 王晏民1, 郭明1   

  1. 1. 北京建筑大学测绘与城市空间信息学院,北京 100044
    2. 北京国电经纬工程技术有限公司,北京 100044
  • 收稿日期:2015-10-09 修回日期:2015-11-06 出版日期:2015-12-20 发布日期:2015-12-20
  • 作者简介:

    作者简介：赵江洪（1976-）,女,新疆阜康人,博士,副教授,研究方向为三维激光雷达数据处理。E-mail: zhaojiangh@bucea.edu.cn

  • 基金资助:
    国家自然科学基金项目（41301429）;武汉大学精密工程与工业测量国家测绘地理信息局重点实验室开放基金 项目（PF2012-1）;现代城市测绘国家测绘地理信息局重点实验室开放课题（20111229N）;北京建筑大学博士科研启动基金项目（Z13084）;北京市自然科学基金项目(8142014)

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

ZHAO Jianghong1,*(), WANG Jiwei2, WANG Yanmin, GUO Ming   

  1. 1. Beijing University of Civil Engineering and Architecture, Beijing 100044, China
    2. Beijing Guodian Jingwei Engineering Technology Co., LTD, Beijing 100044, China
  • Received:2015-10-09 Revised:2015-11-06 Online:2015-12-20 Published:2015-12-20
  • Contact: ZHAO Jianghong E-mail:zhaojiangh@bucea.edu.cn
  • About author:

    *The author: CHEN Nan, E-mail:fjcn99@163.com

RichHTML

PDF (PC)

赞

被引次数

3 | 3

摘要：

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

关键词: 点云, 空间索引, 邻域查询, KD树, 八叉树

Abstract:

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.

Key words: point cloud data, spatial index, neighborhood search, KD-tree, octree