EN中文

Journal of Geo-information Science >

2015 , Vol. 17 >Issue 12: 1450 - 1455

DOI: https://doi.org/10.3724/SP.J.1047.2015.01450

Orginal Article

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

  • ZHAO Jianghong , 1, * ,
  • WANG Jiwei 2 ,
  • WANG Yanmin ,
  • GUO Ming
Expand
  • 1. Beijing University of Civil Engineering and Architecture, Beijing 100044, China
  • 2. Beijing Guodian Jingwei Engineering Technology Co., LTD, Beijing 100044, China
*Corresponding author: ZHAO Jianghong,

Received date: 2015-10-09

  Request revised date: 2015-11-06

  Online published: 2015-12-20

Copyright

《地球信息科学学报》编辑部 所有
Fold

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

Cite this article

ZHAO Jianghong , WANG Jiwei , WANG Yanmin , GUO Ming . A New Multi-level Spatial Index of Scattered Point Cloud Data[J]. Journal of Geo-information Science, 2015 , 17(12) : 1450 -1455 . DOI: 10.3724/SP.J.1047.2015.01450

1 引言

三维彩色扫描技术具有快速性,不接触性,穿透性,主动性,高精度,自动化等特性,随着其测量精度、扫描速度、空间解析度等方面的进步和价格的降低,在古建筑保护方面得到广泛应用[1-2]。
古建筑点云数据具有数据量大（海量性）、数据表达精细（高空间分辨率）、空间三维点之间无拓扑关系（散乱性）等特征[3],在进行后续的数据处理中需频繁地进行邻域查找,因此,必须进行数据的组织和索引,以提高后续邻域检索和查询等操作的速度。
20世纪70年代中期以来多维索引技术问世,1974年R. A. Finkel和J. L. Bentley合作提出了四叉树,主要存储空间多维点[4];1975年J. L. Bentley提出了K-D树,对于精确的点匹配查找具有和二叉树一样良好的性能[5];1978年Hunter首次提出八叉树结构的概念[6]。R树于1984年由Guttman提出,是最早支持扩展对象存取的方法之一,是目前应用最为广泛的一种空间索引结构[7]。
目前适合点云的三维空间索引方法主要有规则格网[8-9]、Octree、KD树[10]、R树及其变种[11]。规则格网法算法实现简单,查询效率很高,但存在单一分辨率、数据冗余等问题[12-13]。针对点云数据较多采用Kd树索引和八叉树。KD树是k维空间点数据的二叉树,它的常数因子很小,继承了二叉树检索效率较高的特点,经过粗略测试这种结构的效率和散列相比,在一百万数据量之下占有优势,但海量数据则存在深度较大引起效率降低的情况,其划分方法如图1所示（图中白色点为点云数据,红色是第1次分割,绿色为第2次,蓝色为第3次分割）。
Fig. 1 K-D tree construction of 3D point cloud data

图1 三维点云的KD树构建过程

八叉树是一种用于描述三维空间的树状数据结构,是四叉树在三维空间的应用,其结构如图2所示。八叉树算法实现简单,较适用于分布均匀的数据,虽然深度较KD树低,但子树判断较费时间,检索效率较低。也有学者提出将这2种方法集成[14-16],但八叉树和KD树在数据量很大的情况下都会存在深度过大问题,将这2种方法集成,同样存在深度过大问题。
Fig. 2 Octree space divisionand the structural representation of the octree

图2 八叉树划分其对应结构示意图

2 MultiGrid-KD树索引

2.1 MultiGrid-KD树索引的基本思想

根据上述索引的优缺点,本文提出了变分辨率格网索引与KD树的混合索引模式,简称MultiGrid-KD树索引。该方法在保持网格索引算法实现简单查询效率高等优点的同时,吸收了变分辨率的思想,形成变分辨率格网,解决了格网索引单一分辨率,数据冗余的问题。另外,二级索引机制使得每次查询的需要访问的数据量锐减,保证了KD树深度较小,从而大幅提高查询效率。
MultiGrid-KD树的基本思想是建立二级索引机制。第一级用格网索引到区域,第二级用KD树索引到每一个单点。具体过程如下：用不重叠的长方体或立方体分割空间,形成格网。由于点云分布不均匀,给定格网中点数最小值的阈值,将数据过少的网格合并成变分辨率格网称区域（region）。在区域中建立KD树索引到单点。在二维平面上格网、区域以及KD树的关系如图3所示。图中蓝色虚线为格网,而红色实线则为区域。一个区域包含一个或多个格网,每一区域内部建立一棵KD树。一个格网只属于一个区域。
Fig. 3 Relationship between grid, reign and KD-tree

图3 格网、区域及KD树的关系

通过该方式索引,在进行空间检索时,可直接根据点坐标计算出格网索引数组的下标,从而定 位到所在区域,然后在区域范围内通过KD树进行检索。
该索引方式较八叉树与KD树的集成索引方式减少了八叉树的深度检索,同时,每棵KD树的数据量大大减少,避免了KD树深度过大的问题,保证了KD树的查询效率。在保持网格索引算法实现简单查询效率高等优点的同时,解决了单一分辨率、数据冗余的问题。因此,整体检索效率比单一的八叉树,KD树及这2种方法的集成方式要高。

2.2 变分辨率格网索引的构造及最近邻搜索

基于MultiGrid-KD树索引的最近邻检索算法的基本思路：根据查询点的坐标计算其所在的格网,然后在格网索引数组中找出格网所在区域号。在区域数组中找到对应区域,利用区域内的KD树进行最近邻查询。比较该点与其所属区域的6个面的距离,如果大于到一个或多个面的距离,则根据区域结构体中存储的邻接关系找到相应的区域,再利用这些区域内的KD树搜索最近邻。最后,将每个KD树搜到的最近邻进行比较,得出最终结果。具体步骤如下：
（1）采集古建筑的原始数据,并根据点坐标构建点集,标记为{X}。
（2）对所述点集{X}进行格网划分,并构建格网索引数组,根据格网中的点坐标计算出格网索引数组每个单元的值。
（3）设置格网包含点数的最小阈值,将点数小于最小阈值的格网合并为区域,或利用八叉树划分出区域。
设置八叉树划分时节点包含点数的阈值a,由于古建筑散乱点云分布的不均匀性,八叉树每个节点包含的点数不同,节点包含的点数大于a的则继续进行八叉树划分,直至节点包含的点数小于a,节点包含的点数小于a的即为叶子节点,利用八叉树的所有叶子节点构建区域及区域数组Region[k],每个区域的ID和所有相邻6个面的区域的ID存储到相应的区域数组中,在每个区域中构建KD树,遍历格网索引数组,计算各个格网对应的区域在区域数组中的ID并存储到格网索引数组中。
（4）根据查询点的坐标x, y, z计算出格网索引数组每个单元的值m, n, l。
m = ( x - x 0 ) / dx , n = ( y - y 0 ) / dy , l = ( z - z 0 ) / dz , （1）
式中,x0, y0, z0是格网划分的起点坐标,即点集最小包围盒的minx, miny, minz。
通过格网索引数组中格网对应的区域在区域数组中的ID,从而定位到所在区域Region[Index[m][n][l]],在相应的区域中利用KD树进行最近邻搜索,得到该区域中与查询点距离最近的点,并将该点与查询点的距离与查询点到其所在的区域的6个面的距离进行比较,若该点与查询点的距离小于查询点到其所在的区域的6个面的距离,则该点即为最终的与查询点距离最近的点;若该点与查询点的距离大于该点到所在的区域的一个或多个面的距离,则在所述一个或多个面的相邻区域中继续利用KD树进行最近邻搜索,得到最终与查询点距离最近的点[17]。

3 实验对比及分析

有学者试验证明KD树明显优于八叉树[18]。因此,本文将MultiGrid-KD树索引与KD树的效率进行了比较。
本文以故宫建筑物点云数据为实验数据,在主频为1.2 G赫兹的双核CPU,内存1G,操作系统为win7的笔记本上对MultiGrid-KD树进行实验验证。图4是太和殿南外柱子一级索引的构建效果图,图5是太和门内的一间房屋扫描点云的构造效果图。这2幅点云数据的一级格网创建的点数阈值为5000,对于小于5000的格网,再对其构建KD树索引,其中KD树的点数阈值设为30。
Fig. 4 A memorial archway of Taihe Palace

图4 太和殿外南面牌坊

Fig. 5 The gate of Supreme Harmony

图5 太和门内房屋

基于指定位置的邻域检索的算法过程一般包括3个步骤：（1）定位到该位置所在的索引叶结点;（2）在该结点内进行最近点的N个点查询;（3）如果该位置到结点边界面的距离小于最近N个节点最大距离,则需到邻域结点进行继续检索。表1是KD树索引和MultiGrid-KD树索引结点定位耗时的比较,图6是2个索引算法的耗时(ms)分析。
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 最近距离点查询分析

从图6和表1的对比分析可看出,随着点数的增加,MultiGrid-KD树的结点定位耗时提高明显低于KD树索引。从单点平均耗来看,KD树索引随点数提高,而MultiGrid-KD树基本保持不变,甚至略有降低。主要原因在于：随着点数增加,KD树索引的深度也随之增加,从而造成结点定位耗时增加。而对于MultiGrid-KD树,一级索引采用格网直接定位,算法耗时对于每个点是固定的,后续的子KD树索引的点数控制在5000点附近,也基本固定不变。因此整个结点定位的耗时不会随点数增加而提高。由于算法在实际运行中涉及到相关的数据和代码调度开销,而随着点数增加,这些开销被稀释,因此在点数增加到一定程度时,平均单点耗时反而出现了降低[19]。从表1也可看出,一级索引由于采用了格网定位索引,定位耗时大幅降低。
表2是KD树索引和MultiGrid-KD树的最近距离点查询的比较,图6是2个索引的耗时分析。在算法过程中,叶节点区域内的最近点遍历检索占用了一定耗时。从单点平均耗来看,MultiGrid-KD树随着点数略微增长。
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
表3是KD树索引和MultiGrid-KD树的最近4个点的邻域查询比较,图8是2个索引的耗时分析。从对比分析可看出,对于四邻域查询,MultiGrid-KD树的算法效率也有较大幅提高。
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 四邻域查询分析

4 结论

本文阐述了一种新的针对点云数据的基于多级格网和KD树构建的空间索引——MultiGrid-KD树索引,以及该索引的构建方法和最近点查询算法。以故宫建筑物点云为实验数据,对MultiGrid-KD树索引进行实验,与经典算法KD树索引的索引定位耗时、最近距离点查询耗时及四邻域查询耗时进行对比。实验证明,本索引方式在邻域查询的效率上明显优于KD树索引。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
杜志强,李德仁,朱宜萱,等.基于3DGIS的木构建筑群三维重建与可视化[J].系统仿真学报,2006,18(7):1884-1889.迄今为止中国木构建筑及其建筑 艺术与工艺的文献均已非常罕见,利用计算机技术保护和研究古建筑已经成为关键问题。介绍了一个基于三维地理信息系统木构古建筑群的动态可视化系统以及该系 统的框架与工作流程,详细阐述了多细节层次技术(LOD)与CAD数据相结合进行精确建模的方法。为了达到逼真效果的实时浏览,提出了一个新的数据库管理 引擎,并介绍了遮挡剔除和可编程实时渲染等加速技术。最后,实验分析表明基于3DGIS的动态交互式可视化系统是文化遗产研究与保护的有效工具。

DOI

[2]
龚健雅等. 当代地理信息技术[M].北京:科学出版社,2004.

[3]
郭明. 海量精细空间数据管理技术研究[D].武汉:武汉大学,2011.

[4]
Finkel R A, Bentley J L.Quad-Trees, a data structure for retrieval on composite keys[J]. Acta Informatica, 1974,4:1-9.The quad tree is a data structure appropriate for storing information to be retrieved on composite keys. We discuss the specific case of two-dimensional retrieval, although the structure is easily generalised to arbitrary dimensions. Algorithms are given both for staightforward insertion and for a type of balanced insertion into quad trees. Empirical analyses show that the average time for insertion is logarithmic with the tree size. An algorithm for retrieval within regions is presented along with data from empirical studies which imply that searching is reasonably efficient. We define an optimized tree and present an algorithm to accomplish optimization in n log n time. Searching is guaranteed to be fast in optimized trees. Remaining problems include those of deletion from quad trees and merging of quad trees, which seem to be inherently difficult operations.

DOI

[5]
Bentley J L.Multidimensional binary search trees used for associative searching[J]. Communications of the ACM, 1975,18(9):509.

[6]
Hunter G M.Efficient computation and data structure for graphics[D]. Princeton, NJ: Department of Electrical and Computer Science, Princeton University,1978.

[7]
Guttman A.R-Trees:A dynamic index structure for spatial searching[A]. In: Proc of ACM Int’l Conf on Management of Data[C]. New York,NY: USA, 1984:47-57.

[8]
王晏民.多比例尺GIS 数量空间数据组织研究[D].武汉:武汉大学,2002.

[9]
夏宇,朱欣焰,李德仁.空间信息多级网格索引技术研究[J]. 地理空间信息,2006,4(6):4-7.空间信息多极网格(SIMG)是一种适合网格计算环境下空间信息表示的新方法,介绍了SIMG的核心思想及其空间数据组织原理,基于现有空间索引技术和SIMG相对量表达特点,提出了一种SIMG-R树空间索引技术,可实现SIMG细部地物的快速查询。

DOI

[10]
史文中,吴立新,李清泉,等.三维空间信息系统模型与算法[M].北京:电子工业出版社,2007.

[11]
龚俊,谢潇.基于R树索引的三维可视化查询方法[J].武汉大学学报(信息科学版),2011,36(10):1140-1143,1153.针对应用日益广泛的最近邻查询,提出了一种基于R树广度遍历和优化排序原理的最近邻查询算法,能适应不同空间分布的目标数据集。同时,提出了多细节层次(LOD)目标查询方法。实验证明,此方法支持多尺度场景逼真描述,查询结果准确,满足当前三维GIS的功能需求。

[12]
王晏民,郭明.大规模点云数据的二三维混合索引方法[J].测绘学报,2012,41(4):605-612.为了统一管理海量点云模型数据，按需提取点云模型数据和提高点云查询效率，提出了一种二维与三维混合索引的点云模型的数据管理方法。采用四叉树和最小外包盒结构管理原始点云，以3D-R树管理多站点云，利用对象关系数据库管理全部点云模型和相关属性数据。利用古建筑大规模点云数据在微机上实现了点云模型的数据库存储与可视化。结果表明本方法能够管理超过10G级的点云模型数据和十亿级有效点，数据查询与效率较高。

[13]
龚健雅,夏宗国.矢量与栅格集成的三维数据模型[J].武汉测绘科技大学学报,1997,22(1):7-15.以矿山地质为背景，深入分析三维空间信息系统所涉及到的空间对象以及它们之间的联系，提出了几种新的空间对象类型。探讨用矢量与栅格混合的数据结构，以及面向对象的数据模型来表达各类三维空间对象，以此作为设计和建立三维地理信息系统的基础

[14]
伏玉琛,郭薇,周洞汝.空间索引的混合树结构研究[J].计算机工程与应用,2003,39(17):41-42.

[15]
廖丽琼,白俊松,罗德安.基于八叉树及KD 树的混合型点云数据存储结构[J].计算机系统应用,2012,21(3):87-90.通过对现有点云数据存储结构进行综合分析及比较,提出了一种基于八叉树及KD 树的混合型点云数据存储结构模型,文中对该模型的基本原理、实现步骤及快速索引的建立等进行了全面的论述,最后以一组实测数据为例,比较了KD 树、八叉树和本文提出的混合结构三种不同数据组织方式的检索效率,证明了所提出存储结构的有效性及实用性。

[16]
路明月,何永健.三维海量点云数据的组织与索引方法[J].地球信息科学,2008,10(20):190-194.三维点云是三维GIS重要的数据来源,也是三维GIS对地学空间 对象、现象进行表达、描述以及建模的重要手段.点云数据的高效组织是对其进行各种分析处理的基础,为此本文在对三维坐标点按照一定的规则进行排序的基础 上,采用规则空间八叉树与平衡二叉树相结合的嵌套复合结构进行组织,大大加速了三维点数据基于坐标的查询检索,为海量点云数据的进一步分析操作奠定了基 础.最后,文中对该复合组织结构进行了内外存相统一的设计与实现,并验证了该方法的正确性及有效性.

DOI

[17]
赵江洪,王晏民,张瑞菊,等.一种古建筑散乱点云空间索引的方法.中国,201310473979.X.[P].2013-11-27.

[18]
朱凌. 基于地面三维激光扫描的古建大木结构三维建模研究[D].北京:中国科学院,2007.

[19]
赵江洪. 古建筑散乱点云基准面的提取与拟合[D].武汉:武汉大学,2012.

Options
Outlines

/

〈 〉