矢量金字塔与R树融合模型研究

马贤迪，常原飞，乔彦友

(中国科学院遥感与数字地球研究所，北京 100101)



矢量金字塔与R树融合模型研究

马贤迪，常原飞，乔彦友

(中国科学院遥感与数字地球研究所，北京 100101)

Research on a Vector Pyramid Model Fused R Tree Index

MA Xiandi，CHANG Yuanfei，QIAO Yanyou

摘要：主要围绕如何在移动设备上快速显示大数据量的面(线)状矢量数据，结合多级空间索引和矢量数据压缩提出了一种基于多尺度R树的矢量数据模型，该模型可用于资源有限的移动设备。首先按照比例尺对矢量数据进行不同级别的压缩，再将不同比例尺下的处理结果通过多尺度R树索引组织存储。通过这种方法可以达到在不同比例尺下显示不同详细程度的几何对象。试验采用湖南1∶10 000的林业资源小班数据来验证该模型的可行性和效率。

关键词：矢量数据模型；金字塔；R树；移动GIS；多级空间索引

近年来，移动智能设备得到了快速发展和普及[1-2]，移动GIS[3-5]也成了当前GIS领域的一个重要研究方向。这种移动终端比较适合于土地、森林等行业相关数据的采集[6-8]，在这些领域移动GIS也得到了广泛的研究。随着移动GIS在各领域的不断深入，现有GIS数据处理技术已经不能满足现代信息社会的需求，其中非常重要的原因就是移动GIS不能解决矢量数据随比例尺变化产生的信息量增减问题[9-10]。典型的例子就是一个大比例尺单精度矢量数据在一定空间范围内空间对象随比例尺缩小而急剧增多，并相互覆盖。而数据量增多会导致渲染速度过慢，影响用户的操作体验。

与影像金字塔类似，多尺度矢量数据组织和表达是减少参与显示数据量的直接解决办法。而传统格网索引[11]或层级索引对数据对象多级显示没有给予足够的支持；基于四叉树[12]的多级显示索引结构又因为其本身的限制，对于分布不均的空间对象检索效率低下；即使是支持多尺度表达的R树[13]各种变形[14]，又由于其设计时未考虑移动应用特点，造成显示失真或效率低下，不能满足移动设备需求。

移动GIS矢量数据快速可视化关键技术之一就是依据比例尺减少相应的数据量。针对目前移动GIS应用特点，本文将多级R树索引和矢量压缩算法相结合，提出一种适合当前移动应用的矢量数据金字塔结构，用于实现移动终端上无极比例尺大矢量数据的查询和快速显示。

一、数据与方法

1. 空间索引

空间对象多尺度表达已成为当前地理科学领域的前沿性问题，特别是在移动GIS领域这一研究还处于初级阶段。下面从空间索引及多级空间索引在移动GIS中的应用来阐述相关研究进展。

(1) 空间索引在移动GIS中的应用

传统空间索引主要有格网索引、树状索引及混合索引，树状索引主要有四叉树和R树及其变体：

1) 格网索引：将二维平面划分为m×n网格，并用空间曲线建立格网一维索引，这种索引在空间对象分布不均时效率难以保证。

2) 四叉树索引：该索引具有良好的节点插入和删除效率，适合于动态空间数据，但是在空间对象密度不均时查询效率低下。

3) R树索引：插入和删除节点效率较低，平均查找性能高，适合于矢量数据更新频率低的移动GIS应用。

(2) 多级空间索引

传统空间索引针对单尺度区域查询，为了多尺度表达空间数据，需要建立多级空间索引。Reactive Tree[15]在R树基础上引入了对象实体权重，并按照权重将对象实体在索引树不同层次上存储，随分辨率不同，低权重对象将被过滤，从而提供了多尺度表达空间实体的方法。在Multi-scale Hilbert R-tree[16]索引中，使用一种Douglas-Peuker[17]算法的变体对曲线和多边形的顶点进行重要度计算，从而在不同尺度上显示不同重要度的化简体。

其他基于多尺度R树及其变体的索引，大都采用上述选择和化简两种思路来建立索引，类似的有多级Hilbert-R-Tree索引(HHRT，Hierarchical Hilbert-R-Tree)[18]、GAP-tree(Generalized Area Partitioning Tree)[14]、SDMR树(Spatial Data Multi-representation R Tree)[19]等。

上述多级索引，都是将原始数据集A按某种规则划分为多尺度数据集，并未建立A的多级简体。这种方案虽然在空间上冗余不大，但每次访问都需要从A中抽取非簇聚存储的子集，由于抽取的也是原始精度的数据，在小比例尺显示时精度和效率都有损失。这种方案适合于网络上的渐进传输但不适合于移动GIS应用。本文中金字塔模型在第一层建立对象的简体，仅研究一级简体和多级简化信息的结合，以后会研究多级简体和多级简化信息的结合。

2. 矢量金字塔模型创建

在创建矢量金字塔时，首先对原始矢量数据建立其某种R树变体索引，其次将原始数据通过化简压缩成与R树索引层数相同、分辨率依次降低的矢量数据集，最后将这些同一矢量数据在不同分辨率的集合体通过R树索引组织成矢量金字塔。假设矢量数据集(面、线)V的维度为n(本文中取2)，矢量金字塔具体的建立步骤如下：

1) 对V建立R树空间索引，R树节点可包含孩子数有限([m，M]，m=M/2)，高度为Level(默认设置为8，可以通过调整m和M来实现)，叶子节点为第0层。

2) 确定矢量数据的最大显示比例尺(默认设置为1∶4000)和最小显示比例尺(默认是1∶512 000)，比例尺依金字塔逐级缩小Ratio(默认为2)倍，默认建立8级金字塔。

3) 计算金字塔每层的压缩算法参数。具体是：一个像素实际地理长度设置为该层压缩算法参数。如在比例尺为1∶512 000、DPI(每英寸(2.54 cm)内的像素个数)为96时，压缩算法参数θMaxLevel计算方法为

θMaxLevel=512 000÷((96÷2.54)×100)≈135.47(m)

4) 建立金字塔的第1层数据简体V0：以θ0作为压缩算法参数对原始数据进行压缩处理。

5) 建立金字塔其余各层的简体(V1-VMaxLevel-1)。与第1层不同的是：其余各层建立的是V0中对象映射集合，并且记录的是对象保留的坐标点在V0中的位置，其目的是减少金字塔数据大小，由此可以得到整个金字塔数据集VVPRD。

6) 对数据进行过滤，并建立其映射关系。首先将VL以θL为边长进行格网划分，依次统计Gij内完全包含的对象个数，如果大于1，则保留一个并删除剩余的对象，同时建立保留对象和删除对象之间的映射关系并保存到磁盘文件中(文件名.map)。

7) 将VL按照R树进行存储。V0按照R树中第0层中的叶子顺序存储，保证每个叶子节点中包含的对象是连续存储的；L﹥0时，VL按照R树中第L层中的非叶子节点顺序存储，保证每个节点中包含对象的化简信息是连续存储的。

8) 将R树存储。R树第L层某个节点中除记录标准信息外，还存储该节点在VL中的数据地址、包含对象(注：非节点)个数。

3. 矢量数据压缩

矢量数据的压缩方法目前有两种途径：一种是降低坐标存储精度，另一种是过滤冗余点。国内有学者提出将双精度浮点型坐标转换为单精度或整形的坐标，这种方法可以减少一半左右的存储空间[20-21]。后者是目前的主流数据化简算法，有垂距法、Douglas-Peucker等算法[22-25]。文中讨论的矢量金字塔模型采用的压缩算法是Douglas-Peucker算法。

Douglas-Peucker是对线状数据的化简算法。而面状数据是由线状数据组成的，因此运用Douglas-Peucker算法简化面状几何对象方法如图1所示：分别处理面状几何对象的每一个环，将环的起点和终点连接作为一条线段(PsPe)，找出多边形上距离线段最远的点Pi将多边形分成两条线段，递归处理(PsPi)和(PiPe)线段直到满足精度需求(最远的点到PmPn的距离小于压缩算法参数)，化简过程如图1所示：原始多边形由6个点组成，根据Douglas-Peucker算法计算出其在给定精度下应该保留的4个关键点，V0记录实体坐标，VL(0

图1　数据化简过程

4. 几何对象过滤

VL中每个格网大小为θL×θL，假设其中一个格网Gij如图2所示，Gij内包含5个对象，删除10、13、15、20这几个对象，并且按照图2右边表格格式存储到文件中。这一步的目的是去除屏幕上相互覆盖的对象，以达到屏幕上一个像素空间(或给定精度的像素空间)仅显示一个几何对象的目的。对于跨格网的对象不作处理。

图2　对象过滤图

5. 模型的文件存储结构

金字塔模型的文件存储结构设计要保证目标信息能够准确和快速地读取。整个金字塔模型存储到3个文件中：文件名.vprd、文件名.vpx、文件名.map。其中vprd文件存储了压缩后的整个矢量金字塔数据集(V0-MaxLevel)；vpx文件存储了空间对象的索引和每个空间对象在vprd文件中的相对偏移量等相关信息；map文件存储几何对象的映射关系。在vprd文件中矢量对象VObject(叶子节点存储矢量对象)或矢量对象的简化信息VSimplifyInfo(非叶子节点)按照R树索引顺序排列使得属于每个节点的VObject(VSimplifyInfo)得以连续存储，其目的是为了一次IO便可以读取一个节点内的所有矢量对象和其对应的简化信息。原始对象唯一标识(ID)在每层对象中都相同。叶子节点中单个VObject格式见表1。

李凌扎实的法律功底以及谦虚好学的精神，得到了检察院同事们的一致肯定，也坚定了李凌做好公诉工作的信心。自此之后，李凌跟着龚科长一起办理了一系列大案要案，对检察院的业务也逐渐变得熟稔起来。仅仅半年时间，李凌便开始像其他资深检察员一样，开始独立办理重大、疑难案件，从而被破格提拔为助理检察员，三年之后便被任命为检察员。

表1　面(线)状目标的记录内容

非叶子节点中单个VSimplifyInfo格式见表2。如图1中的几何对象其nVertices记录为4，pPnt记录为1、3、4、6。

map文件记录了每层对象的过滤信息，分为文件信息头和文件内容两部分。信息头的目的是区分每层过滤信息在map文件中的偏移。具体格式见表3和表4。

表2　几何对象格式

表3　映射文件信息头格式

表4　映射文件内容格式

在vpx文件中，多级R树节点Node连续存储。单个Node对象格式见表5。

表5　节点Node格式

在vpx文件中还存储每层R树在vprd文件中的起始偏移量、每个VObject(VSimplifyInfo)在vprd文件中的偏移量及金字塔第1层比例尺等辅助信息。

6. 模型的使用方法

1) 初始化R树：读取vpx文件，在内存中恢复R树，建立节点数据在vprd文件中的偏移量和长度数组，并与R树关联。

3) 全图显示：计算比例尺ScaleF，若ScaleL1< ScaleF< ScaleL2则显示VL2简体，否则直接显示VMaxLevel-1，具体细节在第4条。

4) 缩放：分为两种情况。

固定比例尺，比例尺相对于1∶512 000放大RatioL倍(L为0～Level-1之间的整数，Ratio取2)：使用当前视口范围矩形框变换后的地理坐标对R树进行自顶向下的搜索，分别记录搜索到的第L层和第0层节点集合SL和S0，根据对象映射表过滤S0，然后从vprd文件中读取S0和SL的信息，用SL的信息对S0进行化简并显示到屏幕上。需要说明的是：SL中的ID集合是S0中ID集合的超集，因为VL存储的只是V0中对象的化简信息，相对来说数据量很小，此时减少IO次数可以提高IO效率，因此原始对象逐个读取，而化简信息R树L层中一个节点一次性读取(只有边界部分会有冗余信息，但这些冗余信息会随着漫游过程变成有用信息)，因此这种策略是可行并且有效的。

5) 漫游：与缩放过程类似，搜索得结果集后，与内存中当前显示对象进行比较，只读取差集。

6) 属性查询和其他分析功能：使用查询点的地理坐标可查询得到当前显示对象FID值，这个值与原始对象中的是一致的，可通过该值访问属性或读取原始坐标来作空间分析。

二、试验与结果

为了测试模型效率，本文在QtCreator(Linux)下，采用C++语言，开发了相应的原型系统，系统测试机为三星N5100(Galaxy Note 8.0)，CPU为4核1.6 GHz主频，系统内存2 GB，屏幕分辨率为1280×800像素，dpi为189，操作系统为Android 4.1；系统测试数据为SHP格式的多边形矢量数据，原始数据大小为246 MB，包含47 566个几何对象和15 577 152个顶点，横坐标范围：395 735.18～451 291.33，纵坐标范围：3 089 567.36～3 172 370.04。按照M值取10、固定缩放倍率为2建立矢量金字塔后，VPRD文件大小为75.4 MB，VPX文件大小为5.1 MB，MAP文件大小为0.14 MB，金字塔高度为8层。表6为读取全图区域的不同层金字塔数据时的点数、时间等一些信息。

全图显示时比例尺为1∶516 736，因此显示第8层金字塔数据。可以看出重叠的区域相比原始地图明显减少并且视觉上看不出明显的缝隙，而IO速度提高了19倍左右，渲染速度提高了17倍左右。图3为原始数据和金字塔模型在同一区域的显示图。

表6　矢量金字塔模型效果

图3　渲染结果

三、结束语

本文基于矢量数据压缩原理，使用多级R树索引，将运行时需要的矢量数据预先处理成金字塔模型，有效提高了矢量数据显示和查询的性能。移动终端屏幕一般不大，因此显示所需数据量有一定上限，通过数据压缩，模型的实时读取和显示效率是可以得到保证的。在移动应用中，底图往往是静态或更新频率低的准静态，由于R树是一棵高度平衡树，其查询效率相比同类索引高出很多，而索引可以在PC上生成移动端使用，因此R树插入删除的低效并不影响移动端的使用，故金字塔的性能是满足要求的。

在随后的工作中，将进一步对海量数据(如全省乃至全国林业资源数据)的金字塔构建进行研究，从而提高模型的适用性，另外也会探讨模型在空间分析方面的处理方法，扩大模型的使用范围。

参考文献：

[1]陈静,吴信才,张发勇,等. 基于WebGIS的iPhone应用系统设计与实现[J].微计算机信息, 2009,25(11):140-142.

[2]王刚,韩振镖. 面向Android智能移动终端的GIS设计与实现[J]. 测绘通报, 2013(8):77-80.

[3]王继周,李成名. 嵌入式移动GIS研究[J]. 测绘科学,2005,30(4):48-50.

[4]郭峰林,胡鹏,徐小双,等. 移动GIS中可视化技术研究[J]. 测绘科学,2007,32(6):74-76.

[5]康铭东,彭玉群. 移动GIS的关键技术与应用[J]. 测绘通报, 2008(9):50-53.

[6]孙贵博,宋伟东,张烁. Smart Client架构下的移动GIS数据采集研究[J]. 测绘科学,2011,36(4):188-190.

[7]余丰华,夏跃珍,杨克红,等.移动GIS技术在地质灾害数据采集领域的应用研究[J]. 中国地质灾害与防治学报, 2006(2):102-106.

[8]李欣. 基于位置服务的移动GIS应用模式研究[J]. 测绘科学,2008,33(6):182-184.

[9]杨必胜,李清泉.World Wide Web(WWW)上矢量地图数据的多分辨率传输算法[J].测绘学报,2005,34(4):355-360.

[10]杨必胜,李必军.空间数据网络渐进传输的概念,关键技术与研究进展[J].中国图象图形学报,2009(6):1018-1023.

[11]张小虎,钟耳顺,王少华,等. 多尺度空间格网数据的索引编码研究[J]. 测绘通报,2014(7):35-38.

[12]阎超德,赵学胜. GIS空间索引方法述评[J]. 地理与地理信息科学,2004(4):23-26.

[13]GUTTMAN A. R-trees: A Dynamic Index Structure for Spatial Searching[C]∥Proceedings of the ACM SIGMOD International Conference on Management of Data. Boston:[s.n.]，1984: 47-54.

[14]程昌秀. 矢量数据多尺度空间索引方法的研究[J]. 武汉大学学报(信息科学版),2009(5):597-601.

[15]OOSTEROM P. The Reactive-Tree: a Storage Structure for a Seamless, Scaleless Geographic Database[C]∥Auto-Carto 10th Annual Convention. Baltimore:[s.n.]，1991.

[16]CHAN E P F, CHOW K K W. On Multi-scale Display of Geometric Objects[J]. Data&Knowledge Engineering,2002(40):91-119.

[17]DOUGLAS D H, PEUCKER T K. Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature[J].The Canadian Cartographer,1973,10(2):112-122.

[18]叶常春,周兴铭. 一种支持多比例尺表示的地图数据组织方法[J]. 计算机学报,2004(7):964-970.

[19]邓红艳,武芳,翟仁健,等. 一种用于空间数据多尺度表达的R树索引结构[J]. 计算机学报,2009(1):177-184.

[20]李青元,刘晓东.WebGIS矢量空间数据压缩方法探讨[J].中国图象图形学报:A辑,2001,6(12):1225-1229.

[21]冯亮.面向大场景三维可视化的高精度地形数据组织[J].测绘科学,2012,37(5):119-120.

[22]彭认灿,董箭,郑义东,等.垂距法与道格拉斯-普克法删除冗余顶点效率的比较[J].测绘通报,2010(3):66-67.

[23]KOLESNIKOV A, FRANTI P. Data Reduction of Large Vector Graphics [J].Pattern Recognition, 2005, 38(3):381-394.

[24]RICHARDS N, WARE M. Ant Colony Optimization Applied to Map Generalization[C]∥13th Workshop of the ICA Commission on Generalisation and Multiple Representation.[S.l.]：ICA，2010.

[25]LI L, LI C, LIN Z. Data Structure of Sliced Saving Vector Data for PDA[J]. Acta Geodaetica et Cartographica Sinica，2002，31(2)：170-174.

中图分类号：P208

文献标识码：B

文章编号：0494-0911(2016)02-0059-05

作者简介：马贤迪(1990—)，男，硕士生，研究方向为地理信息系统研究与应用。E-mail：madilong@163.com

基金项目：国家重大科技专项(21-Y30B05-9001-13/15)；国家863计划(2008AA12Z203)

收稿日期：2014-12-08； 修回日期： 2015-04-08

引文格式： 马贤迪，常原飞，乔彦友. 矢量金字塔与R树融合模型研究[J].测绘通报，2016(2)：59-63.DOI:10.13474/j.cnki.11-2246.2016.0049.