地球信息科学学报 ›› 2015, Vol. 17 ›› Issue (12): 1450-1455.doi: 10.3724/SP.J.1047.2015.01450
收稿日期:
2015-10-09
修回日期:
2015-11-06
出版日期:
2015-12-20
发布日期:
2015-12-20
作者简介:
作者简介:赵江洪(1976-),女,新疆阜康人,博士,副教授,研究方向为三维激光雷达数据处理。E-mail:
基金资助:
ZHAO Jianghong1,*(), WANG Jiwei2, WANG Yanmin, GUO Ming
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:
摘要:
散乱点云数据具有数据量大(海量性)、数据表达精细(高空间分辨率)、空间三维点之间无拓扑关系(散乱性)等特征,在对其进行应用前必须进行数据预处理(如去噪、配准、分割等)。而在这些数据处理过程中需频繁的进行邻域查找,如果没有高效的查询索引机制,很难实现数据自动处理。因此,如何进行数据的组织和索引,以提高后续邻域检索和查询等操作的速度,是目前点云数据处理中的一个研究热点。针对现有点云数据采用的空间索引方式的优缺点,本文提出了一种多级格网和KD树混合的空间索引,该索引提出变分辨率格网索引与KD树的混合索引模式,简称MultiGrid-KD树索引。该方法在保持网格索引算法实现简单查询效率高等优点的同时,解决了单一分辨率数据冗余的问题。以故宫太和殿的点云数据为例,对本文提出的MultiGrid-KD树索引算法和KD树、八叉树等经典算法做对比。结果表明,本文索引方法在最邻近点查询以及四邻域查询的效率上均优于KD树,以及八叉树索引。
赵江洪, 王继伟, 王晏民, 郭明. 一种新的散乱点云数据多级空间索引[J]. 地球信息科学学报, 2015, 17(12): 1450-1455.DOI:10.3724/SP.J.1047.2015.01450
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] |
杜志强,李德仁,朱宜萱,等.基于3DGIS的木构建筑群三维重建与可视化[J].系统仿真学报,2006,18(7):1884-1889.
doi: 10.3969/j.issn.1004-731X.2006.07.036 |
[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.
doi: 10.1007/BF00288933 |
[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.
doi: 10.3969/j.issn.1672-4623.2006.06.002 |
[10] | 史文中,吴立新,李清泉,等.三维空间信息系统模型与算法[M].北京:电子工业出版社,2007. |
[11] | 龚俊,谢潇.基于R树索引的三维可视化查询方法[J].武汉大学学报(信息科学版),2011,36(10):1140-1143,1153. |
[12] | 王晏民,郭明.大规模点云数据的二三维混合索引方法[J].测绘学报,2012,41(4):605-612. |
[13] | 龚健雅,夏宗国.矢量与栅格集成的三维数据模型[J].武汉测绘科技大学学报,1997,22(1):7-15. |
[14] | 伏玉琛,郭薇,周洞汝.空间索引的混合树结构研究[J].计算机工程与应用,2003,39(17):41-42. |
[15] | 廖丽琼,白俊松,罗德安.基于八叉树及KD 树的混合型点云数据存储结构[J].计算机系统应用,2012,21(3):87-90. |
[16] |
路明月,何永健.三维海量点云数据的组织与索引方法[J].地球信息科学,2008,10(20):190-194.
doi: 10.3969/j.issn.1560-8999.2008.02.012 |
[17] | 赵江洪,王晏民,张瑞菊,等.一种古建筑散乱点云空间索引的方法.中国,201310473979.X.[P].2013-11-27. |
[18] | 朱凌. 基于地面三维激光扫描的古建大木结构三维建模研究[D].北京:中国科学院,2007. |
[19] | 赵江洪. 古建筑散乱点云基准面的提取与拟合[D].武汉:武汉大学,2012. |
[1] | 张永军, 黄星北, 刘欣怡. 一种地形自适应的机载LiDAR点云正则化TPS滤波方法[J]. 地球信息科学学报, 2020, 22(4): 898-908. |
[2] | 李鹏鹏, 李永强, 蔡来良, 董亚涵, 范辉龙. 车载LiDAR点云中道路绿化带提取与动态分析[J]. 地球信息科学学报, 2020, 22(2): 268-278. |
[3] | 王金鑫,赵光成,禄丰年,张古彬,曾涛,乔天荣. 真三维地质模型构建的球体测地线八叉树网格方法[J]. 地球信息科学学报, 2019, 21(8): 1161-1169. |
[4] | 方莉娜, 黄志文, 罗海峰, 陈崇成. 结合SVM与图匹配的车载激光点云道路标线识别[J]. 地球信息科学学报, 2019, 21(7): 994-1008. |
[5] | 陈博伟, 庞勇, 李增元, 卢昊, 梁晓军. 基于随机森林的光子计数激光雷达点云滤波[J]. 地球信息科学学报, 2019, 21(6): 898-906. |
[6] | 王森援, 蔡国榕, 王宗跃, 吴云东. 基于加权约束的单体建筑物点云表面重建算法[J]. 地球信息科学学报, 2019, 21(5): 654-662. |
[7] | 陶鹏杰, 宋孟肖, 段延松. 利用高精度DLG进行机载LiDAR点云精度评定研究[J]. 地球信息科学学报, 2019, 21(4): 608-614. |
[8] | 张刚, 刘文彬, 张男. 基于区域特征分割的密集匹配点云渐进形态学滤波[J]. 地球信息科学学报, 2019, 21(4): 615-622. |
[9] | 李鹏, 邢帅, 李瑾, 何华, 王丹菂, 李鹏程. 基于虚拟特征点的三维激光点云粗配准算法[J]. 地球信息科学学报, 2018, 20(4): 430-439. |
[10] | 袁鹏飞, 黄荣刚, 胡平波, 杨必胜. 基于多光谱LiDAR数据的道路中心线提取[J]. 地球信息科学学报, 2018, 20(4): 452-461. |
[11] | 李沛婷, 赵庆展, 陈洪. 回波强度约束下的无人机LiDAR点云K-means聚类滤波[J]. 地球信息科学学报, 2018, 20(4): 471-479. |
[12] | 耿雨馨, 钟若飞, 彭宝江. 基于车载激光点云的街景立面自动提取[J]. 地球信息科学学报, 2018, 20(4): 480-488. |
[13] | 刘强, 傅学庆, 黄华芳, 党海燕, 于国超, 李仁杰, 张军海. 基于LiDAR数据特征的湖相层三维地理信息提取[J]. 地球信息科学学报, 2018, 20(4): 489-495. |
[14] | 罗海峰, 方莉娜, 陈崇成. 车载激光扫描数据路坎点云提取方法[J]. 地球信息科学学报, 2017, 19(7): 861-871. |
[15] | 王永志, 杨路生, 廖丽霞, 潘红伟. 八叉树与三维R*树集成的激光点云数据存储结构[J]. 地球信息科学学报, 2017, 19(5): 587-594. |
|