三维海量点云数据的组织与索引方法
来源:    发布时间: 2012-11-21 15:25   3151 次浏览   大小:  16px  14px  12px
三维点云是三维GIS重要的数据来源, 也是三维GIS对地学空间对象、现象进行表达、描述以及建模的重要手段。点云数据的高效组织是对其进行各种分析处理的基础, 为此本文在对三维坐标点按照一定的规则进行排序的基础上, 采用规则空间八叉树与平衡二叉树相结合的嵌套复合结构进行组织, 大大加速了三维点数据基于坐标的查询检索, 为海量点云数据的进一步分析操作奠定了基础。


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

关键词: 三维海量点云  三维GIS  空间数据组织  复合组织结构

 

三维GIS是传统二维GISz空间上的扩展,能够更真实地表达地学对象及现象的存在特征,并完成在真三维空间的分析操作, GIS发展的重要方向。近年来, 随着雷达、激光扫描等三维遥测技术的日益成熟, 三维点云数据成为三维领域重要的数据来源, 也是三维GIS对地学空间对象、现象进行表达、描述以及建模的重要手段。通过对三维点云数据的处理操作, 能够提取出其中隐含的属性以及空间特征信息, 也可以衍生出构建三维空间模型的其他矢量数据(TIN数据等) 。然而三维点云数据的海量性及其离散性在很大程度上制约着这些操作分析的快速进行。因此需要对其进行高效的组织, 并以此建立强大的索引机制进一步支持相关的操作分析。

 

1.三维坐标的点云数据组织

对于三维点云而言, 三维坐标是其基本数据,也是蕴含空间信息的直接载体, 所以对点云进行的各种涉及空间关系特征的操作处理(如三维点云的数据压缩、空间插值、表面重构等[ 6 ] )往往都需要三维点坐标的匹配查询, 在海量数据下, 这种匹配查询的效率成为制约其快速进行的重要因素; 并且三维坐标点作为三维矢量数据的主要表现形式, 是构建空间几何对象的基本元素, 也是进行各种矢量空间判断及操作分析的直接对象, 所以基于坐标对三维点数据进行高效的组织, 对于三维GIS的矢量数据操作有着非常重要的意义。

 

2.数据组织结构的设计实现与应用

1数据组织结构设计与实现

通过分析, 三维点数据以坐标为关键字直接存储在二叉树中, 而二叉树作为二级组织结构关联存储于空间八叉树的叶子节点中。这种结构的内存实现比较容易 ,八叉树与二叉树的嵌套关系可以用指针或者ID作为关联手段进行实现。

由于点云数据的海量性, 文中在设计时将该结构映射到外存的数据库文件组织中, 使内外存结构相一致, 以便在数据量超大, 以至于内存无法一次性读入时, 可以以外存替代内存进行无缝结合的统一数据检索。这种点云数据的嵌套复合组织, 在数据库中可以通过对八叉树表单以及点数据表单的设定来实现。其中八叉树用于点云数据的预处理, 关键是能够快速获取点坐标所归属的叶子节点。

2)应用实例

文中在基于VC ++ 1NET 2005OpenGL自主开发的三维可视化分析平台中, 结合SQL Server数据库系统实现了对某地区三维雷达点云数据(共有1 178 799个坐标点)的复合结构组织及其可视化表达(如图4所示) , 并对其进行相关检索操作分析, 获得显著效果, 有效地验证了这种复合结构的正确性以及有效性。

3.结论

本文在对三维空间坐标进行顶点排序的基础上, 采用空间规则八叉树与二叉树相结合的嵌套复合结构对空间点云数据进行了高效的组织,根本上解决了海量点云数据基于顶点坐标的快速查询检索的瓶颈问题, 同时也为三维GIS领域基于顶点的三维矢量数据分析操作奠定了基础。然而在数据读入时, 需要进行多次比较, 以确认存放的位置,所以初始化的速度会相对较慢。在超大数据量时,可以将初始化后的各种数据存放于结构一致的数据库中, 以后的检索查询可以直接在数据库中进行,从而避免复合结构的频繁初始化。