八叉树与三维R*树集成的激光点云数据存储结构

doi:10.3724/SP.J.1047.2017.00587

地球信息科学学报 ›› 2017, Vol. 19 ›› Issue (5): 587-594.doi: 10.3724/SP.J.1047.2017.00587

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

八叉树与三维R^*树集成的激光点云数据存储结构

王永志^*(), 杨路生, 廖丽霞, 潘红伟

江西理工大学建筑与测绘工程学院,赣州 341000

收稿日期:2016-06-23 修回日期:2016-07-28 出版日期:2017-05-20 发布日期:2017-05-20
通讯作者: 王永志 E-mail:gisstarnnu@gmail.com
作者简介:
作者简介：王永志（1983-）,男,博士,副教授,主要从事地学三维建模与模拟、三维激光点云数据处理等研究工作。E-mail:gisstarnnu@gmail.com
基金资助:
国家自然科学基金项目（41361078）;江西省科技厅青年科学基金项目（20142BAB217027）

Integrated Laser Point Cloud Data Storage Structure Based on Octree and 3D R^*-tree

WANG Yongzhi^*(), YANG Lusheng, LIAO Lixia, PAN Hongwei

Faculty of Architectural and Surveying Engineering, Jiangxi University of Science and Technology, Ganzhou 341000, China

Received:2016-06-23 Revised:2016-07-28 Online:2017-05-20 Published:2017-05-20
Contact: WANG Yongzhi E-mail:gisstarnnu@gmail.com

摘要/Abstract

摘要：

针对海量激光点云数据组织与管理困难等问题,结合八叉树在三维空间上的快速收敛能力以及三维R^*树对不规则分布的多维点数据性能稳定的优势,提出了一种八叉树与三维R^*树集成的空间混合索引结构—3DOR^*树。首先,通过对激光点云数据进行八叉树划分;然后,对八叉树叶子节点构建三维R^*树,进而实现3DOR^*树索引结构的构建;最后,对激光点云数据进行特征分析,构建基于3DOR^*树的激光点云数据存储结构,实现基于3DOR^*树的激光点云存储与管理。本文以江西理工大学图书馆激光点云数据为例,进行实验对比分析,证明了基于3DOR^*树的激光点云数据存储结构比三维R^*树、八叉树与三维R树混合树等其他树形结构,具有高效的空间存储与查询等优势,可应用于海量激光点云数据存储、管理与分析应用。

关键词: 三维激光扫描, 激光点云, 八叉树, 三维R*树, 数据存储结构

Abstract:

Aiming at the difficulties of massive laser point cloud data organization and management, a new spatial index structure-3DOR^*-tree is proposed. This is constructed by fully integrating Octree with fast convergence capability of 3D space and 3D R^*-tree with the advantages of stable performance of irregularly distributed data. Firstly, laser point cloud data is divided using Octree, and then 3D R^*-trees are built on the octree leaves. The laser point cloud data is stored only on the leaves of 3D R^* tree and 3DOR^*-tree index structure is constructed. Then, we analyze feature of laser point cloud to achieve laser point cloud storage and management based on 3DOR^*-tree. At last, the point cloud data of the library of JiangXi University of Science and Technology are used for experiment and comparative analysis. The result shows that the improved storage structure of laser point cloud data based on 3DOR^*-tree has an advantage of efficient space storage and query compared to other tree structure, such as 3D R^* tree, integrated tree of Octree and R tree and so on. Thus, 3DOR^*-tree can be applied to management and analysis applications of massive laser point cloud data storage.

Key words: 3D laser-scanning, laser point cloud, octree, 3D R*-tree, data storage structure

王永志, 杨路生, 廖丽霞, 潘红伟. 八叉树与三维R^*树集成的激光点云数据存储结构[J]. 地球信息科学学报, 2017, 19(5): 587-594.DOI:10.3724/SP.J.1047.2017.00587

WANG Yongzhi,YANG Lusheng,LIAO Lixia,PAN Hongwei. Integrated Laser Point Cloud Data Storage Structure Based on Octree and 3D R^*-tree[J]. Journal of Geo-information Science, 2017, 19(5): 587-594.DOI:10.3724/SP.J.1047.2017.00587

图/表 8

图1

图2

图3

图4

表1

表2

图5

图6

参考文献 19

[1]	Kobayyashi K, Akiyama K, et al.Laser-scanning imaging system for real-timeof 3D object problem[J]. Object Communications, 1989,74(4):165-170.
[2]	徐源强,高井祥,王坚.三维激光扫描技术[J].测绘信息与工程,2010,35(4):5-6.
	[Xu Y Q, Gao J X, Wang J.3D Laser scanning technology[J]. Journal of Geomatics Aug, 2010,35(4):5-6. ]
[3]	Nebiker S, Bleisch S, Christen M.Rich point clouds in virtual globes: A new paradigm in city modeling[J]. Computer, Environment & Urban System, 2010,34(6):508-517. doi: 10.1016/j.compenvurbsys.2010.05.002
[4]	王晏民,郭明.大规模点云数据的二维与三维混合索引方法[J].测绘学报,2012,41(4):605-612.
	[Wang Y M, Guo M.A combined 2D and 3D spatial indexing of very large point-cloud data stes[J]. Acta Geodaetica et Cartographica Sinica, 2012,41(4):605-612. ]
[5]	杨建思. 一种四叉树与KD树结合的海量机载LiDAR数据组织管理方法[J].武汉大学学报·信息科学版,2014,39(8):918-922. doi: 10.13203/j.whugis20130676
	[Yang J S.A method of combing the model of the global quadtree index with local KD-tree for massive airborne LiDAR point cloud data organization[J]. Geomatics and Information Science of Wuhan University, 2014,39(8):918-922. ] doi: 10.13203/j.whugis20130676
[6]	路明月,何永健.三维海量点云数据的组织与索引方法[J].地球信息科学,2008,10(2):190-194.
	[Lu M Y, He Y J.Organization and indexing method for 3D points cloud data[J]. Journal of Geo-information Science, 2008,10(2):190-194. ]
[7]	Elseberg J, Borrmann D, Nuchter A.One billion points in the cloud-an octree for efficient processing of 3D laser scans[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2013,76(1):76-88. doi: 10.1016/j.isprsjprs.2012.10.004
[8]	朱庆,龚俊.一种改进的真三维R树空间索引方法[J].武汉大学学报·信息科学版,2006,31(4):340-343. doi: 10.3321/j.issn:1671-8860.2006.04.015
	[Zhu Q, Gong J.An improved full 3D R-Tree spatial index mathod[J]. Geomatics and Information Science of Wuhan University, 2006,31(4):340-343. ] doi: 10.3321/j.issn:1671-8860.2006.04.015
[9]	龚俊,朱庆,章汉武,等.基于R树索引的三维场景细节层次自适应控制方法[J].测绘学报,2011,40(4):531-534.
	[Gong J, Zhu Q, Zhang H W, et al. An adaptive control method of LODs for 3D scene based on R-tree index[J]. Acta Geodaetica et Cartographica Sinica, 2011,40(4):531-534. ]
[10]	杨建思. 一种利用面元拟合的地面点云数据三维R树索引方法[J].武汉大学学报·信息科学版,2013,38(11):1313-1316.
	[Yang J S.3D R-Tree point clouds data indexing method based on plane fitting[J]. Geomatics and Information Science of Wuhan University, 2013,38(11):1313-1316. ]
[11]	陈茂霖,万幼川,田思忆,等. 一种基于线性KD树的点云数据组织方法[J].测绘通报,2016(1):23-27.
	[Chen M L, Wang Y C,Tian S Y, et al.A method of organizing point clouds based on Linear KD tree[J]. Bulletin of Surveying and Maping, 2016,1:23-27. ]
[12]	Yang J, Huang X.A hybrid spatial index for massive point cloud data management and visualization[J]. Transactions in GIS, 2014,18(S1):97-108. doi: 10.1111/tgis.12094
[13]	龚俊,柯胜男,朱庆,等.一种八叉树和三维R树集成的激光点云数据管理方法[J].测绘学报,2012,41(4):597-604.
	[Gong J, Ke S N, Zhu Q, et al.An efficient management method for point cloud data based on octree and 3D R-tree[J]. Acta Geodaetica et Cartographica Sinica, 2012,41(4):597-604. ]
[14]	赵江洪,王继伟,王晏民,等.一种新的散乱点云数据多级空间索引[J].地球信息科学学报,2015,17(12):1450-1455. doi: 10.3724/SP.J.1047.2015.01450
	[Zhao J H, Wang J W, Wang Y M, et al.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
[15]	熊伟成,杨必胜,董震.面向车载激光扫描数据的道路目标精细化鲁棒提取[J].地球信息科学学报,2016,18(3):376-385. doi: 10.3724/SP.J.1047.2016.00376
	[Xiong W C, Yang B S, Dong Z.Refining and robust extraction of roads from mobile laser scanning point clouds[J]. Journal of Geo-information Science, 2016,18(3):376-385. ] doi: 10.3724/SP.J.1047.2016.00376
[16]	何美章,朱庆,杜志强,等. 从灾后机载激光点云自动检测损毁房屋的等高线簇分析方法[J]. 测绘学报,2015(4): 407-413.
	[He M Z, Zhu Q, Du Z Q, et al. Contour cluster shape analysis for building damage detection from post-earthquake airborne LiDAR[J]. Acta Geodaetica et Cartographica Sinica, 2015(4):407-413. ]
[17]	Guttman A.R trees: A dynamic index structure for spatial searching[C]. ACM SIGMOD Conference,Boston,USA,1984.
[18]	Beckmann N, Kriegel H P, Schneidr R, et al.The R*-tree:An Efficient and Robust Access Method for Points and Rentangles[C]. ACM SIGMOD Conference.Atlantic City,USA,1990.
[19]	杨军,林岩龙,张瑞峰,等.一种大规模点云k邻域快速搜索算法[J].武汉大学学报·信息科学版, 2016,41(5): 656-664. doi: 10.13203/j.whugis20140191
	[Yang J, Lin Y L, Zhang R F, et al.A Fast Algorithm for Finding k-nearest Neighbors of Lage-Scale Scattered Point Cloud[J]. Geomatics and Information Science of Wuhan University, 2016,41(5):656-664. ] doi: 10.13203/j.whugis20140191

时间/ms	总点数/10⁴
时间/ms	60	80	100	200	300	500
三维R^*索引	54 273	73 438	92 412	195 730	315 736	569 307
3DOR树索引	14 763	18 635	24 294	57 920	102 060	210 451
3DOR^*树索引	14 819	18 946	24 765	58 067	88 936	223 438

时间/ms	总点数/10⁴
时间/ms	60	80	100	200	300	500
三维R^*索引	17	25	28	102	140	388
3DOR树索引	16	23	35	71	125	328
3DOR^*索引	16	23	35	68	109	296

八叉树与三维R^*树集成的激光点云数据存储结构

Integrated Laser Point Cloud Data Storage Structure Based on Octree and 3D R^*-tree

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 19

相关文章 14

Metrics

本文评价

推荐阅读 0

[1]	李鹏鹏, 李永强, 蔡来良, 董亚涵, 范辉龙. 车载LiDAR点云中道路绿化带提取与动态分析[J]. 地球信息科学学报, 2020, 22(2): 268-278.
[2]	陈锦, 谭凯, 张卫国. 基于地面三维激光扫描强度数据的潮滩表层含水量估算[J]. 地球信息科学学报, 2020, 22(2): 290-297.
[3]	王金鑫,赵光成,禄丰年,张古彬,曾涛,乔天荣. 真三维地质模型构建的球体测地线八叉树网格方法[J]. 地球信息科学学报, 2019, 21(8): 1161-1169.
[4]	方莉娜, 黄志文, 罗海峰, 陈崇成. 结合SVM与图匹配的车载激光点云道路标线识别[J]. 地球信息科学学报, 2019, 21(7): 994-1008.
[5]	李鹏, 邢帅, 李瑾, 何华, 王丹菂, 李鹏程. 基于虚拟特征点的三维激光点云粗配准算法[J]. 地球信息科学学报, 2018, 20(4): 430-439.
[6]	袁鹏飞, 黄荣刚, 胡平波, 杨必胜. 基于多光谱LiDAR数据的道路中心线提取[J]. 地球信息科学学报, 2018, 20(4): 452-461.
[7]	刘强, 傅学庆, 黄华芳, 党海燕, 于国超, 李仁杰, 张军海. 基于LiDAR数据特征的湖相层三维地理信息提取[J]. 地球信息科学学报, 2018, 20(4): 489-495.
[8]	罗海峰, 方莉娜, 陈崇成. 车载激光扫描数据路坎点云提取方法[J]. 地球信息科学学报, 2017, 19(7): 861-871.
[9]	李敏, 杨昕, 陈盼盼, 熊礼阳. 面向点云数据的黄土丘陵沟壑区沟沿线自动提取方法[J]. 地球信息科学学报, 2016, 18(7): 869-877.
[10]	熊伟成, 杨必胜, 董震. 面向车载激光扫描数据的道路目标精细化鲁棒提取[J]. 地球信息科学学报, 2016, 18(3): 376-385.
[11]	李志强, 程承旗, 李爽. 基于GeoSOT-3D的空间对象快速可视化与实验分析[J]. 地球信息科学学报, 2015, 17(7): 810-815.
[12]	王金鑫, 李耀辉, 郑亚圣, 邹煚, 杨晶. 基于SGOG瓦块的数字地球真三维可视化技术与应用[J]. 地球信息科学学报, 2015, 17(4): 438-444.
[13]	赵江洪, 王继伟, 王晏民, 郭明. 一种新的散乱点云数据多级空间索引[J]. 地球信息科学学报, 2015, 17(12): 1450-1455.
[14]	胡斌, 江南, 邹志强, 邵华, 王鹏. 大规模室外动态场景调度机制研究[J]. 地球信息科学学报, 2007, 9(5): 8-13.

八叉树与三维R*树集成的激光点云数据存储结构

Integrated Laser Point Cloud Data Storage Structure Based on Octree and 3D R*-tree

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 19

相关文章 14

Metrics

本文评价

推荐阅读 0

八叉树与三维R^*树集成的激光点云数据存储结构

Integrated Laser Point Cloud Data Storage Structure Based on Octree and 3D R^*-tree