资源描述：
《基于Hilbert排列码与R树的海量LIDAR点云索引》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第34卷第6期测绘科学Vol134No162009年11月ScienceofSurveyingandMappingNov1基于Hilbert排列码与R树的海量LIDAR点云索引①②①①①赖祖龙,万幼川,申邵洪,徐景中(①武汉大学遥感信息工程学院,武汉430079;②中国地质大学信息工程学院,武汉430074)【摘要】本文分析当前索引方法存在问题,针对高效海量点云数据的要求,提出一种基于Hilbert码与R树的二级索引方法。论文阐述了二级索引的建立原理与方法,可通过聚类方法与R树度M值来的优化第一级索引;使用HilbertR树作为第二索引,可以有效控制
2、两级R树的高度,同时点云的增加与更新可只在局部进行。最后本文通过两组实验来验证该数据组织方法的可行性和跟其他索引(KD树与四叉树)进行比较,得出它是一种高效管理海量点云的方法。【关键词】Hilbert排列码;R树;二级索引;LIDAR;空间聚类【中图分类号】TP391;TP75【文献标识码】A【文章编号】100922307(2009)0620128203[1]备上亿个或者更多的数据点,存储量巨大。综合考虑点1引言云的上述特征,本文使用一种二级索引有效管理海量点云,机载激光雷达(LIDAR)是一种集激光测距、计算机、其基本原理是首先把点云按空间格网划分
3、,以每个网格单全球定位系统和惯性导航系统等技术于一身的技术,用于元为基础,计算单元内LIDAR点的N维Hilbert排列码,按[1]获取高精度、高密度的三维坐标数据。目前,在GIS与Hilbert值把单元内的LIDAR点分为若干组,每个组作为整空间数据库中高效管理众多LIDAR点是一个重大挑战,然体以空间对象方式批量构建静态R树索引,从而建立第一而LIDAR数据的后处理(如滤波、分类与可视化等)依赖于索引或详细索引;然后将各网格单元按照中心点的Hilbert点云检索,即快速索引是实现海量点云操作与管理的支撑值进行分组,以网格内的第一级索引作为数据对象
4、,批量技术之一。构建HilbertR树索引,即第二级索引或全局索引,这种索当前,业界应用广泛的点云组织方法有KD树、四叉引特点是:树、八叉树、BSP树等,它们在小点云管理中是非常有效1)将LIDAR点按其Hilbert码排序分组,使得具有相的。但是,随着数据量的膨胀,索引树的深度急剧增大,同或相似属性的点聚集在一起,即可将目标在一定程度上容易产生索引树结构失衡、节点利用率低、节点key值度进行空间聚类,这种聚集性减少了空间数据处理所要求的[2]量顺序混乱等问题,最终导致整体的查询效率非常低;磁盘操作数,加快了数据处理的速度,同时按组建立R树,同时它们
5、属于内存索引,利用数据库协同管理海量点云时空间利用率高,没有冗余存储,查询效率高;也存在一定困难。在GIS与空间数据库中,R树及其变种2)以Hilbert码进行点聚类,建立步骤简单且容易编[3]是当前主流索引方法,但它不宜直接管理点云,存在一程实现;另外这样聚类分组具有灵活多变,根据操作点云些问题:①直接把LIDAR点以点状地物的方式存放索引的需要,N维Hilbert码既可反映平面坐标(X、Y)的空间属中,整个R树的深度会非常大,导致空间查询效率极低;性又可引入LIDAR点其他重要信息(如高程、强度值、图像②在操作点云过程中,由于LIDAR点的高程、
6、强度及其他灰度值),使得属性检索效率高;信息(如影像灰度值)是一个重要参数,在管理LIDAR点云3)一级索引R树的叶节点中存放的不是每个LIDAR时需要把它们作为除坐标(X、Y)外的高维元素进行检索,点ID,而是一组按HILBERT码排列的LIDAR点集合的ID,维数增加会使其查询效率急剧降低,而且GIS索引一般是同时二级索引R树的叶节点存放的是一级索引R树的ID,二维R树索引并不适用于此处检索。因此,为高效管理海这样有效地降低了索引树的高度;量LIDAR点云,本文提出一种基于Hilbert排列码与R树二4)二级索引建立过程符合数据网格划分要求,允许
7、建级索引的LIDAR数据组织方法。立者根据需要划分;以网格单元为基础建立的R树的子节点间的重叠矩形极少,即R树的查询效率接近100%;2点云组织原理5)该索引是一种高效的二级索引结构,既符合栅格空211基本思想间管理要求,又能够对局部的点云的有效管理,不会造成点云是一个空间数据的集合,数据点之间是离散的、存储冗余和牺牲查询效率,由此该索引适合海量点云的数散乱分布的;另外点云又是一个海量数据的集合,通常具据组织与管理;6)LIDAR点整个索引的维护代价少,支持局部点云索作者简介:赖祖龙(19762),男,籍贯:引的构建与更新。江西于都,讲师,博士研究生
8、,主要从212Hilbert排列码划分点云事3S集成、LIDAR技术、测量数据处空间填充曲线是一种把N维空间
