基于层次菱形块的球面DEM数据组织

2011-04-18 10:28焦健
城市勘测 2011年2期
关键词:四叉树子块剖分

焦健

(芜湖市勘察测绘设计研究院,安徽芜湖 241000)

基于层次菱形块的球面DEM数据组织

焦健∗

(芜湖市勘察测绘设计研究院,安徽芜湖 241000)

如何对全球DEM进行有效的组织管理,是GIS乃至数字地球面临的首要问题之一。本文采用四叉树菱形分层分块的结构进行椭球面的三角格网DEM数据组织,垂直方向上依据四叉树划分为不同分辨率的数据层,水平方向上以菱形块为单位组织数据。各个菱形块根据其空间分布位置,依据线性四叉树进行Morton编码和空间索引,实现了海量DEM数据的高效管理。

菱形块;球面DEM;数据组织;空间索引

1 引 言

全球DEM高程数据的组织管理面对的是以GB甚至TB计算的海量数据。如何对这些数据进行有效的组织管理并在此基础上提高系统的效率,是GIS乃至数字地球面临的首要问题之一。数字高程模型数据组织的目的就是要将所有相关的DEM数据通过数据库或文件系统有效地管理起来,并根据其地理分布建立统一的空间索引,进而可以快速调度数据库中的任意范围的数据,实现对整个研究区域DEM数据的无缝漫游。

当前,许多实用系统都是基于文件系统的管理方式实现较大数据量的地形数据动态调度[1,2]。基于文件系统的存储方式也基本上可以满足地形可视化和空间分析的需要。尽管基于文件管理的方式受到网络环境下的多用户并发操作的局限,但考虑到在数据建立后,可视化和空间分析阶段几乎不存在多用户同时修改一块数据,因此基于文件系统的数据库管理方式仍为许多用户使用。但是也有人认为基于文件管理的方式在数据组织和空间索引、数据动态更新、网络环境下的多用户操作诸多方面存在局限性,他们提倡采用关系型数据库管理系统(RDBMS)实现对海量DEM数据的管理[3]。现阶段以较成熟的RDBMS技术作保障,能够实现存储容量与访问速度的平衡,部分提供基于标准的SQL语句的查询、输出,而且安全性能较好。但关系型数据库相对于文件存储方式来说,以BLOB字段存储地形数据的方式在数据的获取操作上,并没有实质的进步。相反,在数据的读取速度和块内数据的定位上还不如数据文件快速和灵活[4]。而且它不支持对非结构化数据的标准SQL,用二进制大对象管理DEM也不够灵活。对象关系数据库(ORDB)的出现将会较好地解决这些存在的问题,通过抽象数据类型(AbstractDataType)或行类型(RowType)扩充管理DEM文本或二进制对象,支持对自定义栅格数据的标准SQL查询[5]。但是现有的ORDB技术离成熟完善的产业化阶段还有距离,因此不能采用。

从以上的分析可以看出,对于DEM数据,是采用关系数据库还是文件系统还没有一个统一的认识,正所谓仁者见仁、智者见智。作者认为,对一个多部门采用的大型系统来说,应该采用数据库系统,但对于一些小型的系统尤其是实验系统来说,采用文件系统管理DEM数据则更为方便。本文对基于关系数据库的DEM数据管理进行研究,包括数据库结构、数据块内部数据的存储方式、数据块的编码和索引等。

地球是一个非常复杂的开放的巨系统,随着观察视野的变化,我们希望空间地理信息比例尺也自动增减。由于地图的自动综合受诸多因素的影响,目前比较可行的是采用多尺度空间数据库来达到此目的。所谓多尺度就是指系统内包含几种不同比例尺(或分辨率)的空间数据,其目的是为了适度地反映系统所关心区域的空间地理信息,以避免地物信息的过粗、失真或地物信息的负载量过大而无法使用。多尺度空间数据库现有多库多版本、一库多版本、一库一版本和LOD等四种方案[2,6,7]。对基于椭球面的格网DEM,本文采用一种混合的方式进行组织存储:即在对全球DEM进行菱形分层分块(四分体——菱形块——菱形子块)的基础上,建立LOD模型组织全球DEM数据。

2 基于菱形块的层次数据库结构

为了便于存储管理,并充分利用QTM网格自身的特点,我们将“南北”相邻的两个QTM三角形合并成一个菱形块,以固定大小的菱形块为单元组织数据,并作为数据库的一个基本存储单元。其在数据库中对应一条记录(在文件系统下对应一个数据文件),采用四叉树空间索引结构进行索引查询。

如图1所示,我们将用于地球表面剖分的正八面体的8个三角形面按南北向相邻两两合并,形成4个菱形,我们称为四分体[8]。这样,一个八面体(相当于一个地球表面)对应4个四分体。对八面体的每个面进行递归QTM细分,细分后的QTM格网经过“南北”合并,也可以看成是每个四分体四叉树细分后的菱形块格网,如图2所示。

图1 八面体对应的四个四分体

一个菱形块剖分成四个菱形子块,如图2所示,完全类似于规则格网四叉树剖分,唯一的不同是,这些格网实际上并不规则,是通过QTM剖分得来的,其顶点位于球面上,显然不共面。但这对于数据的组织并没什么影响。通过如此剖分,整个地球表面可以用一个四叉树来表达,全球表面对应4个四分体,每个四分体分割成下一级的4个较小的菱形块,如此递归,直到满足一定的分辨率为止。

图2 三层QTM递归剖分(左)与相应的菱形块格网层次剖分

在数据组织时,我们以QTM三角形为基础,采用菱形分块的层次结构组织数据,如图3所示。整个地球表面可以通过对应的4个初始菱形块(四分体),其进一步划分成若干个菱形块,而每个菱形块又包括若干个菱形子块,每个菱形子块作为全球DEM组织管理的最基本的单元,相当于传统管理上的一幅图。每一子块由经过若干层剖分的QTM格网组成,在数据库中作为一条记录存储(在文件系统下对应一个数据文件),其数据的存储格式见后节介绍。每个菱形子块地址用其所属的四分体编码和Morton编码的组合来标识,可以方便地用四叉树进行索引,而存储于每个菱形块内部的数据,可以通过行列结构索引。这样,通过“四分体——菱形子块——行列”结构的索引,就可以唯一确定全球范围内任意位置的DEM值。

图3 基于四叉树菱形块的DEM数据分层分块组织

为了提高系统的交互效率,满足大范围大数据量的地形漫游及分析的要求,有必要建立多细节LOD模型,相应地,用多分辨率DEM数据库进行存储管理。本文采用对全球DEM进行菱形块分层分块(四分体——菱形块——菱形子块)的基础上,建立LOD模型组织全球DEM数据。不同的LOD在数据库中位于不同的层,其中,最底层的DEM为基本数据库层,属于原始数据,其分辨率最高,其余各层的DEM数据则可以视具体情况组织。本文首先通过原始数据构建较少的LOD层,再用这些基本的LOD层派生一些LOD分层,依此组建由远到近、由小到大一系列不同详细程度的LOD分层数据。这样,不仅可以通过建立不同分辨率的数据库层获取数据库级的LOD,还可以借助于快速处理算法实时地从高分辨率数据自动地抽取相邻层次中间分辨率的数据。其数据库的体系结构如图4所示。

图4 层次结构的数据库体系

3 椭球面三角格网DEM的数据结构

对于规则格网DEM数据来说,目前多以行列矩阵的格式存储,该格式在每个格网顶点只需存储该点的高程值。对于基于椭球面三角格网DEM来说,由于其格网的规则性,任意一个格网顶点的坐标可以根据该顶点高程值的存储位置计算出来,而且其与相邻顶点之间的拓扑关系也隐含在它们的存储位置中,因此完全可以采用类似于规则格网的存储方式。具体到全球三角格网DEM,存储时以菱形子块作为数据存储的基本单位,每个菱形子块在数据库中对应一条记录,在文件系统下对应一个数据文件,菱形子块的大小决定了数据文件的大小。对于每个菱形子块(类似于一幅图),只需存储元数据(包括格网角点的坐标、菱形格网的剖分层数、行列数、空间参考坐标系等)和高程值串即可。其中高程值串采用blob(Binary Large Object)字段存储,一个菱形子块对应一个大二进制blob文件。由于大多数关系数据库都支持blob字段,因此,全球DEM数据可以使用大多数的关系数据库和对象关系数据库方便地进行存储[9]。

在每一个菱形块内,格网点的个数均为(2n+1)× (2n+1),在高程值串中,格网点高程值的存储顺序采用如图5所示的次序。

采用这种格式不仅结构简单,占用存储空间少,而且还可以借助其他简单的栅格数据处理方法进行进一步的数据压缩处理,如自适应行程编码、四叉树方法、多级格网法等。

图5 三角格网点在存储单元中的存储次序

4 基于线性四叉树的菱形块索引及编码

整个地球表面可以用一个线性四叉树来表达,存储时只需纪录其叶结点的位置即可。其叶结点的位置用菱形块编码来标识,通过空间Z型填充曲线来索引,如图6所示。

图6 菱形块的四进制Morton码与其Z型空间索引曲线

每个基菱形块递归细分成较小的菱形块,由其所属的一个四分码和Morton码来标识。菱形块L的编码表示为:L=DM。其中D为该菱形块所在基菱形块的四分码,M为该菱形块的Morton码。每个基菱形块根据其所在位置由一个四分码(0、1、2、3)来标识,其标识规则为:

对基菱形块进行递归剖分,会产生4个新的较小的菱形块,用Morton码标识。对于每个基菱形块来说,进行一次四叉树分割,会产生4个新的小菱形块,如图6右所示分别用标号0、1、2、3来表示左、下、上、右4个小菱形块(对应四个子象限),每个小的菱形块继续递归细分,产生新的更小的菱形块,通过增加标号位数来标识,这种标号即为四进制的Morton码(用MQ表示)。Morton码的每一位字数都是不大于3的四进制数,并且每经过一次分割,增加一位数字,分割的次数越多,所得到的子区域(菱形块)越小,相应的Morton码位数越大。最后小菱形块的Morton码是所有各位上相应象限值相加,即:

[1] 陈刚,万刚,游雄.全球地形可视化方案的设计和实践[J].系统仿真学报,2001,13增刊,P 282~285

[2] 郭建中,欧阳,魏海平等.基于文件与基于数据库的格网索引[J].测绘学院学报,2002,19(3):P220~223

[3] 钟正,朱庆.一种基于海量数据库的DEM动态可视化方法[J].海洋测绘,2003,23(2):P9~19

[4] 郭建忠,安敏.GIS中多比例尺地理数据的管理和应用[J].解放军测绘学院学报,1999,16(1):P47~49

[5] 李峻,边馥苓,谈晓军.DEM及纹理图像的集成数据库研究[J].测绘科学,2000,25(3):P25~28

[6] 齐清,张安定.关于多比例尺GIS中数据库多重表达的几个问题的研究[J].地理研究,1999,18(2):P16~170

[7] 王晏民,李德仁,龚健雅.一种多比例尺GIS方案及其数据模型[J].武汉大学学报(信息科学版),2003,28(4): P458~462

[8] White.D.,Global Grids From Recursive Diamond Subdivisions of The Surface of an Octahedron or Icosahedron.Environmental Monitoring and Assessment,2000,4(1):P93~103

[9] 王永君,龚健雅.一种基于COM的数字高程模型可视化管理模式[J].系统仿真学报,2001,13增刊:P32~35

Data Organization of Spherical DEM based on hierarchical Diamonds

Jiao Jian
(Wuhu Geotechnical and Survey Design Institute,Wuhu 241000,China)

One of the primary problems that GIS and even the Digital Earth were faced to is how to organize and manage global DEM effectively.In this paper,The Ellipsoidal Triangular Network blocks data are organized on the Diamonds quad-tree.Data in vertical direction are divided into different resolution levels according to quad-tree,and in horizontal direction,Diamonds are regarded as basic units.Each Diamonds is libelled and indexed using linear quadtree Morton code according to its location.Thus we achieve efficient management of massive DEM data.

Diamonds;Spherical DEM;Data Organization;spatial index

1672-8262(2011)02-40-03

P208

A

2010—07—30

焦健(1968—),男,工程师,主要从事测绘与GIS数据处理工作。

猜你喜欢
四叉树子块剖分
基于八叉树的地震数据分布式存储与计算
基于特征值算法的图像Copy-Move篡改的被动取证方案
基于重心剖分的间断有限体积元方法
基于波浪式矩阵置换的稀疏度均衡分块压缩感知算法
二元样条函数空间的维数研究进展
基于WebGL的三维点云可视化研究
基于四叉树的高效梯度域图像融合
基于四叉树的高效梯度域图像融合
一种实时的三角剖分算法
复杂地电模型的非结构多重网格剖分算法