MGIS中地图栅格数据组织模型研究*

林启惠 郭 晖

(1.秦皇岛职业技术学院思政部 秦皇岛 066100)(2.海军工程大学电子工程学院 武汉 430033)



MGIS中地图栅格数据组织模型研究*

林启惠1郭 晖2

(1.秦皇岛职业技术学院思政部 秦皇岛 066100)(2.海军工程大学电子工程学院 武汉 430033)

研究瓦片金字塔模型和四叉树技术基础上,提出了一种地理地图栅格数据模型,该模型将地图栅格数据的使用分为获取、组织和索引三个步骤,并分析研究各步骤主要技术和方法,并利用瓦片金字塔模型和四叉树技术完成栅格数据组织。该模型能够高效完成栅格数据的组织和其他操作,具有高效实用特点。

MGIS; 瓦片金字塔; 四叉树; 地图栅格数据

Class Number TP391

1 引言

军事地理信息系统(military geographic information system,MGIS)是利用计算机系统,运用系统工程和信息科学的理论和方法,分析利用军事地理环境信息的军事空间信息系统,是数字化战场建设的基本技术,是数字化战场建设的信息平台,是基于信息系统作战能力建设的重要方面[1]。在MGIS系统中,如何高效、准确地进行地理地图的组织和显示是一项重要基础性工作。

文章主要对MGIS系统中地理栅格数据的组织模型进行研究,构建了获取、组织和索引的三步完成地图组织,其中地理数据组织具体利用四叉树方法建立地图瓦片金字塔模型,实现系统中地图数据的高效和准确组织。

2 瓦片金字塔模型

在地理信息图形数据的组织和管理模式设计中,为了提高系统地形地图的直观显示能力,主要采用更加适用于模拟空间场的栅格数据[2]。

瓦片金字塔模型是进行栅格数据组织的重要模型,并得到广泛应用。瓦片地图金字塔模型是一种多分辨率层次模型,从瓦片金字塔的底层到顶层,分辨率越来越低,但表示的地理范围不变[3]。瓦片地图金字塔模型在GIS系统中地形地图构建中栅格数据组织中有广泛应用。瓦片地图是指将固定范围的某一比例尺下的地图按照指定的尺寸(通常为128*128像素或256*256像素)切成若干行和列的正方形栅格图片,切图获得的正方形栅格图片即为瓦片地图。按照金字塔的思想,采用倍率方法构建一个多分辨率的层次模型,金字塔每一层的栅格数据切割为一定大小的瓦片,每层都由大小相同瓦片矩阵构成。

假设一个倍率为r,总层数为m的瓦片金字塔,那么第N层瓦片与第N+1层瓦片像素相同,第N层的分辨率为第N+1层的r倍,第M层分辨率为g,那么第0层瓦片即最底层的分辨率为

g0=gm×rm

该公式可以推广到一般层次,一个倍率为2的,总层为2的瓦片图片金字塔如图1所示。

图1 一个典型的瓦片金字塔

地图瓦片拓扑关系是指地图瓦片与其他地图瓦片在满足拓扑几何学原理的空间数据间相互关系,具体来说就是图形元素间相互空间上的连接、邻接关系,而并不考虑元素的具体位置。

作为一个倍率为2的瓦片地图金字塔,其地图瓦片拓扑关系主要包括同一层间的邻接关系,上下册间的双亲和孩子关系。其中,邻接关系主要是东、南、西、北四个方向的邻接瓦片,而双亲和孩子的关系包括东南、西南、西北、东北四个派生瓦片。

可以发现,该拓扑关系与数据结构中四叉树描述非常相似,唯一不同是瓦片地图金字塔中邻接和派生关系都有方向性,而在普通的四叉树中派生或邻接结点(叶子)是等价的。对四叉树引入更多信息描述,通过对四叉树的分析实现对瓦片地图金字塔的分析和研究。

3 线性四叉树

3.1 线性四叉树的构建

四叉树结构是树形结构的一种,它的每个子节点最多只有四个分子[4],能够实现空间递归分解的层次数据结构,所以可以利用瓦片地图金字塔建立到线性四叉树的映射完成线性四叉树的构建,一个n层瓦片地图金字塔与四叉树的映射图如图2所示。

其具体的映射步骤为:

1) 对m层瓦片金字塔,建立一个层次D=m的线性四叉树,确保瓦片地图金字塔的第i层和线性四叉树的第n-i层瓦片和结点对应;

图2 金字塔与四叉树对应关系

2) 对顶层的瓦片地图金字塔不进行分割,直接与四叉树根结点对应;

3) 除顶层外每层瓦片地图进行分割,从第m-1层金字塔开始,将该曾瓦片地图按照派生拓扑关系分解为东南、西南、西北、东北四个瓦片地图,对应于根结点上的四个儿子结点;

4) 依照3)方法对各层进行分割,直到第0层。

3.2 线性四叉树的编码

对线性四叉树进行编码是为了提高线性四叉树的索引效率,从而提高瓦片地图金字塔的存在便利性,这里介绍一种最常见的编码方式。用00,01,10,11分别表示西南、西北、东南、东北四个方向,每一层次较上一层次在编码尾部增加两位编码表示该瓦片是上层结点哪个方位方向派生而来的,具体步骤如图3所示。

图3 四叉树编码步骤

采用这种编码方式可以携带充分信息量,同时具备以下特征:

1) 对应特征。线性四叉树深度为n的结点与[0,4n-1]内的二进制值间是互相映射的,且若一个结点A的编码比其父结点少尾部两位。

2) 位置特征。根据派生方向与编码的对应关系,提取该二进制编码奇数位编码和偶数位编码称为(Mo,Me),以及其对应的十进制数值(i,j),根据分析可以知道Mo、i代表结点瓦片地图在平面内由南向北的顺序位置,Me、j则表示结点瓦片地图在平面内由西向东的顺序位置,即Mo对应的是结点瓦片位置的南北向分解后的位置编码,Me对应的是结点瓦片位置的东西向分解后的位置编码,空间编码与位置编码的对应关系如图4所示。

图4 空间编码与位置编码对应关系

3) 存在特征。某瓦片地图结点的不同尺寸邻域存在,那与其相同尺寸的邻域必然存在。

4) 邻域特征。某瓦片地图结点的相同尺寸的邻域存在,则该瓦片地图结点与其相邻结点存在数学运算关系。

在完成瓦片地图空间编码的同时,根据不同的应用类型和方向,可以加入其他信息编码,例如深度信息编码,分辨率编码,尺寸编码和区域编码等。

3.3 线性四叉树的操作

在瓦片地图金字塔模型中可以将针对地形地图的操作转化为对应线性四叉树的操作,由于对地形地图操作一般不会涉及到删除、添加等,主要集中在查看、平移等,对于四叉树来说,主要就是实现对四叉树的索引,四叉树索引包括Skyline[5]等诸多算法,这里简要介绍地形地图操作和四叉树索引对应操作的关系。

1) 地图平移。地图在平移过程中,其分辨率不变,主要是地图的中心点发生改变,那么对于四叉树主要进行四叉树同层间结点的查找,以及邻接域的确定。

2) 地图缩放。地图在缩放过程中,其中心点不变,主要完成分辨率变化,根据缩放比例大小,确定四叉树层间切换,以及中心结点的确定。

3) 地图补边。当地图显示不能充分时,特别对于边缘不能充分填充,应当采用四叉树中邻域的求解方法。

4 地理栅格数据组织模型

地理栅格数据组织模型主要利用瓦片金字塔模型和四叉树技术,从地图数据组织,数据组织和数据操作三个方面着手,一是基础数据获取,主要包括基础地图栅格数据的获取和存储模式,二是数据组织方式,主要介绍瓦片地图数据的四叉树编码和相关信息的存储,三是地图操作设计,主要包括四叉树索引技术。

4.1 地理栅格数据的获取

地理数据是地理信息系统重要部分,其数据获取工作占有重要地位。为了提高工作效率,降低成本,有效利用已有空间数据,需要利用不同来源数据。目前,在地理信息图形数据的组织和管理模式设计中,空间数据模型主要分矢量数据和栅格数据两种[6]。矢量数据描述地理要素的空间特点是通过离散的位置坐标来表示的,利用欧几里德几何学中的点、线、面及其组合体表示地理实体的空间分布。栅格数据模型是指将空间分割成有规则的网格,在各个网格上给出相应的属性来表示空间实体的数据组织形式。为了提高系统地形地图的直观显示能力,主要采用更加适用于模拟空间场的栅格数据。

栅格数据从来源可以分为各种遥感数据、航测数据、航空雷达数据等,从类型分为索引图,分类图,双字节图等,这里系统使用来自Google Earth的地理栅格数据,它是Google公司于2005年6月向全球退出的免费卫星影像软件[7],以各种分辨率的卫星影像为最基础数据,数据格式采用JPEG的透明真彩色叠加图。系统通过使用专业软件获取Google Earth的地理栅格数据包括JPEG格式的瓦片图片和包含高程、经度和维度的信息数据。

4.2 地理栅格数据的组织

图像数据分块和分层技术是提高地图数据读取的有效办法,栅格数据处理是典型的分块技术,分层技术是对图形进行抽象形成多分辨率的图像层数据。金字塔模型是一种典型的栅格数据组织模型,而栅格数据存储主要分为数据库和文件两种存储方式[8]。

栅格数据组织的金字塔模型主要包括瓦片金字塔模型,小波金字塔模型,多金字塔模型,非一致分层分块金字塔模型和三重金字塔模型等[9]。瓦片金字塔模型在上节已经作了详细介绍,这里简要介绍另外四种金字塔模型。小波金字塔模型的基本思想是将小波变换与金字塔相结合,一张高分辨率的图像经过一次小波变换后分为近似的子图和三种高分辨率的子图,而近似子图继续进行小波变换,继续迭代到结束构建小波金字塔。多金字塔模型是对原主体金字塔模型进行分割为多个子模型,每个子模型代表的地理数据逻辑范围是主体金字塔某曾中一个瓦片所占的逻辑范围,从而实现子模型各层瓦片与主体金字塔瓦片的无缝连接。非一致分层分块金字塔模型各层之间不采用固定分辨率,根据原始数据的分辨率构建金字塔,各层瓦片大小非一致,采用缓存交替工作、多线程预读图像块方法。三重金字塔模型是由根据命名规则建立的栅格文件构建的一重金字塔,索引图层根据命名规则建立关联字段构建的一重金字塔和文件内部借助ArcGIS自动生成的一重金字塔共同构建。

作为MGIS系统由于军事保密需要,大多在单机运行或在小型局域网,且地形地图相对固定,主要集中于中国沿海海区或某些战区,地理信息量相对较少,所以基于上述应用要求,采用瓦片金字塔模型进行地形地理栅格数据组织。

地形地理栅格数据的管理和存储主要基于文件和基于数据库两种类型,基于文件的方式主要针对小数据量设计,数据存储在本地文件中,不涉及数据库操作,具有结构简单、维护费用少、技术相对承受、在小数据量应用效率较高等优势,采用顺序文件、索引文件、直接文件等多种方式,适用于存储更新周期快而对数据本身操作少的情况。基于数据库栅格存储方式采用多个独立栅格目录、若干栅格数据集和若干金字塔数据层的三层存储组织结构,具有良好的安全措施和数据恢复机制,还提供对连续的栅格数据的快速访问、支持事务处理和并发控制,安全机制。系统采用基于数据库的栅格数据存储模式。

4.3 地理栅格数据的索引

地理空间索引是依据地理要素(或对象)的空间位置、形状或地理对象之间的某种空间关系,按一定的顺序排列的一种数据结构,包括地理对象的标识、外接矩形和指向地理对象的指针等三个部分。地理信息对象采用栅格数据格式,基于数据库存储方式,需要完成对存储数据检索查询。

对于地理信息对象栅格数据的常见空间索引方法包括R树和四叉树。其中,R树最早由GutTman在1984年提出[10],后逐步形成由R树,R+树、R3树、Hibert R树、SR树组成的R树系列空间索引,它直接对地理空间中占据一定范围的地理要素进行索引,又具备一般满二叉树B树特点,具有很强的灵活性、可调节性、无需预知整个空间对象所处空间范围,同时具备B树相似结构和特征,从而能很好支持数据库的事务、滚回和并发功能。四叉树属于基于空间划分组织索引结构的一类索引机制,将已知范围的空间化成四个相等的子空间,并类似继续逐层划分,四叉树特点是可以用顺序存储的线性表表示索引,较小内存需求量,插入和删除更加简单。在基于通过ODBC或ADO外挂在现有关系数据库上的,一般采用查询速度快、结构相对简单的四叉树索引。

对于瓦片金字塔模型的四叉树构建的步骤为:

1) 对于n层瓦片金字塔,建立一个D=n的线性四叉树,使得瓦片金字塔的第i层Li与线性四叉树的第n-i层像元对应;

2) 对瓦片金字塔的顶层图像不进行分割,使其直接与线性四叉树的根节点对应;

3) 对顶层之外各层图像进行瓦片分割,按照第2节要求从西南SW、西北NW、东南SE、东北NE四个方向进行划分切割;

4) 按照上述方法分割到第0层。

假设四叉树中任一层i的节点编码H为H1H2…Hi-1Hi,其中Hi∈{SiWiSiEiNiWiNiEi},SW,SE,NW,NE分别用00,01,10,11表示,每层划分的子层节点编码应当附上上层父亲节点编码。这种编码方式能够较好显示该节点的深度信息、分辨率信息、区域信息和位置信息。具体来说,应有:

1) 深度信息:假设顶层节点编码为00,那么四叉树的任一节点编码H的层次深度D=length(H)/2-1;

2) 分辨率信息:假设根节点像元的分辨率为R0,那么四叉树第i层对应像元分辨率为Ri=2Di×R0;

3) 区域信息:节点编码H为H1H2…Hi-1Hi,那么其父节点编码为H1H2…Hi-1,依次类推得到任一级父亲节点编码;

3) 位置信息:按照上节四叉树节点编码的规定进行编码奇数偶数分解,得到相应西东和南北方向相对位置。

5 结语

本文提出了一种MGIS系统中的地理地图栅格数据模型,该模型将地图栅格数据的使用分为获取、组织和索引三个步骤,并分析研究各步骤主要技术和方法,重点研究了地图栅格数据组织中的瓦片金字塔模型和四叉树技术。该模型能够高效完成栅格数据的组织和其他地图操作,具有高效实用特点。

[1] 王家耀.军事地理信息系统(MGIS)在现代化战争中的作用及其发展[J].信息工程大学学报,2000,1(4):102-105.

[2] 李玉阳,晋朝勃,笪良龙,等.MGIS技术在海军信息战中的应用[J].指挥控制与仿真,2007,29(3):117-120.

[3] 王家耀.地理信息系统的发展及其在信息战中的应用[J].信息工程大学学报,2004,5(2):103-107.

[4] 李启清,等.一种可扩展四叉树结构及其先序遍历算法[J].计算机工程与应用,2003(28):22-41.

[5] Scott T. Shipley, Ira A. Graffman, Joseph K. Ingram. GIS Applications in Climate and Meteorology[J]. 2000(1):56-59.

[6] Paul A. Longley. The academic success of GIS in geography: Problems and prospects[J]. Journal of Geographical System,2000:231-238.

[7] 严寒冰,郑加成,等.GIS的空间数据模型[J].浙江工程学院学报,1999,2(8):113-115.

[8] 张宏.地理信息系统算法基础[M].北京:科学出版社,2001:50-55.

[9] 徐开明.地理信息公共服务平台建设与现代测绘服务模式[J].地理信息世界,20114(3):23-27.

[10] 汪璟玢.一种结合空间聚类算法的R树优化算法[J].计算机工程与应用,2014(5):112-115.

Research on the Model of Map Raster Data Organization in MGIS

LIN Qihui1GUO Hui2

(1. Department of Ideological and Political, Qinhuangdao Vocational and Technical College, Qinhuangdao 066100) (2. College of Electronics Engineering, Naval University of Engineening, Wuhan 430033)

On the base of the research of tile pyramid model and the quad-tree technology, a geographic map raster data model is proposed, which uses the map of raster data with three steps that capture, organize and index, and each step of major techniques and methods is analyzed, and tile pyramid model and quadtree technology are used to complete raster data organization. The model can efficiently complete raster data organization and other operations, is efficient and practical.

MGIS, tile pyramid, quadtree, map raster data

2014年10月14日,

2014年11月21日

林启惠,女,助教,研究方向:网络及数据库技术。郭晖,女,讲师,研究方向:计算机应用技术。

TP391

10.3969/j.issn1672-9730.2015.04.027