一种新的散乱点云数据多级空间索引
作者简介:赵江洪(1976-),女,新疆阜康人,博士,副教授,研究方向为三维激光雷达数据处理。E-mail: zhaojiangh@bucea.edu.cn
收稿日期: 2015-10-09
要求修回日期: 2015-11-06
网络出版日期: 2015-12-20
基金资助
国家自然科学基金项目(41301429)
武汉大学精密工程与工业测量国家测绘地理信息局重点实验室开放基金 项目(PF2012-1)
现代城市测绘国家测绘地理信息局重点实验室开放课题(20111229N)
北京建筑大学博士科研启动基金项目(Z13084)
北京市自然科学基金项目(8142014)
A New Multi-level Spatial Index of Scattered Point Cloud Data
Received date: 2015-10-09
Request revised date: 2015-11-06
Online published: 2015-12-20
Copyright
散乱点云数据具有数据量大(海量性)、数据表达精细(高空间分辨率)、空间三维点之间无拓扑关系(散乱性)等特征,在对其进行应用前必须进行数据预处理(如去噪、配准、分割等)。而在这些数据处理过程中需频繁的进行邻域查找,如果没有高效的查询索引机制,很难实现数据自动处理。因此,如何进行数据的组织和索引,以提高后续邻域检索和查询等操作的速度,是目前点云数据处理中的一个研究热点。针对现有点云数据采用的空间索引方式的优缺点,本文提出了一种多级格网和KD树混合的空间索引,该索引提出变分辨率格网索引与KD树的混合索引模式,简称MultiGrid-KD树索引。该方法在保持网格索引算法实现简单查询效率高等优点的同时,解决了单一分辨率数据冗余的问题。以故宫太和殿的点云数据为例,对本文提出的MultiGrid-KD树索引算法和KD树、八叉树等经典算法做对比。结果表明,本文索引方法在最邻近点查询以及四邻域查询的效率上均优于KD树,以及八叉树索引。
赵江洪 , 王继伟 , 王晏民 , 郭明 . 一种新的散乱点云数据多级空间索引[J]. 地球信息科学学报, 2015 , 17(12) : 1450 -1455 . DOI: 10.3724/SP.J.1047.2015.01450
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
Fig. 1 K-D tree construction of 3D point cloud data图1 三维点云的KD树构建过程 |
Fig. 2 Octree space divisionand the structural representation of the octree图2 八叉树划分其对应结构示意图 |
Fig. 3 Relationship between grid, reign and KD-tree图3 格网、区域及KD树的关系 |
Fig. 4 A memorial archway of Taihe Palace图4 太和殿外南面牌坊 |
Fig. 5 The gate of Supreme Harmony图5 太和门内房屋 |
Tab. 1 Time cost of the index location (ms)表1 索引定位的耗时(ms) |
点数 | KD树 | MultiGrid-KD树 | |||||
---|---|---|---|---|---|---|---|
总耗时 | 平均单点耗时 | 一级索引耗时 | KD树索引耗时 | 总耗时 | 平均单点耗时 | ||
141 999 | 187 | 0.00131691 | 16 | 109 | 125 | 0.000880288 | |
642 984 | 873 | 0.00135773 | 47 | 452 | 499 | 0.000776069 | |
1 053 197 | 1544 | 0.00146601 | 93 | 734 | 827 | 0.000785228 |
Fig. 6 Analysis of index location time cost图6 索引定位的耗时分析 |
Fig. 7 Analysis of the nearest distance inquiry图7 最近距离点查询分析 |
Tab. 2 Time cost of the nearest distance inquiry (ms)表2 最近距离查询耗时(ms) |
点数 | KD树 | MultiGrid-KD树 | |||
---|---|---|---|---|---|
总耗时 | 平均单点耗时 | 总耗时 | 平均单点耗时 | ||
141 999 | 250 | 0.001760576 | 172 | 0.001211276 | |
642 984 | 1264 | 0.001965834 | 796 | 0.001237978 | |
1 053 197 | 2231 | 0.002118312 | 1341 | 0.001273266 |
Tab. 3 Time cost of the four nearest neighborhoods inquiry (ms)表3 四邻域查询耗时(ms) |
点数 | KD树 | MultiGrid-KD树 | |||
---|---|---|---|---|---|
总耗时 | 平均单点耗时 | 总耗时 | 平均单点耗时 | ||
141 999 | 445 | 0.003133825 | 313 | 0.002204241 | |
642 984 | 2398 | 0.003729486 | 1687 | 0.002623704 | |
1 053 197 | 4430 | 0.004206241 | 2883 | 0.002737380 |
Fig. 8 Analyze of Four Neighborhood Distance Inquiry图8 四邻域查询分析 |
The authors have declared that no competing interests exist.
[1] |
|
[2] |
|
[3] |
|
[4] |
|
[5] |
|
[6] |
|
[7] |
|
[8] |
|
[9] |
|
[10] |
|
[11] |
|
[12] |
|
[13] |
|
[14] |
|
[15] |
|
[16] |
|
[17] |
|
[18] |
|
[19] |
|
/
〈 | 〉 |