一种基于TMS的瓦片金字塔切分方法

刘让国，刘晓杰，刘顺喜，韦二龙

（1.中国电子科技集团公司第五十四研究所，河北 石家庄 050081；2.中国土地勘测规划院，北京 100035）

一种基于TMS的瓦片金字塔切分方法

刘让国1，刘晓杰1，刘顺喜2，韦二龙1

（1.中国电子科技集团公司第五十四研究所，河北 石家庄 050081；2.中国土地勘测规划院，北京 100035）

为了有效提高大数据量下的切片效率，从瓦片地图服务（Tile Map Service，TMS）元文件、瓦片划分规则和瓦片命名规则等方面对TMS技术进行了研究，对切片算法进行了设计实现，并结合多线程机制进行了优化改进，从而提出一种基于TMS的瓦片金字塔切分方法。试验结果表明，该方法能提高瓦片的切片效率。

金字塔；瓦片；四叉树；多线程；TMS

0 引言

目前地理信息系统处理显示的数据量已达GB级、TB级甚至PB级，一次性完全加载显示基本没有可能，也会造成显示效率低下。因此需要对空间数据进行预处理，形成统一的存储组织标准，进行分块存放。实时调度时可根据空间位置索引到瓦片，直接调用对应数据，实现海量信息的快速共享与高效应用［1，2］。

本文对TMS切片算法进行了设计实现，针对以前的TMS切片算法效率不高、单线程执行的特点，利用多线程的方法对TMS切片算法进行了改进，有效提高了TMS切片算法的效率。新的TMS切片算法特别在处理大数据上具有显著优势。

1 TMS瓦片金字塔技术

地图瓦片技术是一种地图预缓存技术，将配置好的一定坐标范围的地图，按照固定的若干个比例尺（瓦片级别）和指定图片尺寸，切成若干行及列的正方形图片，以指定的格式保存成图像文件，按一定的命名规则和组织方式存储到目录系统中或是数据库系统里，形成金字塔模型的静态地图缓存，地图切图所获得的地图切片也叫瓦片（Tile）。瓦片金字塔模型是一种多分辨率层次模型，从瓦片金字塔的底层到顶层，分辨率越来越低，但表示的地理范围不变［3，4］。瓦片金字塔的示意如图1所示。

图1 瓦片金字塔

瓦片地图由于采用了以“空间换取时间”的策略，预先缓存地图，读取静态的图片在客户端拼接浏览，从而可以快速地提供地图的服务，带来更好的用户体验［5］。

TMS是由开源地理空间基金会（Open Source Geospatial Foundation，OSGeo）定义和发布的一种地图瓦片规范。通过定义统一的切图标准和独立服务接口，以地图切片的行列位置为基础参数直接访问栅格地图，提高地图的访问速度。目前，TMS正逐步成为事实标准，TMS服务是栅格地图发布的发展方向［6］。TMS是一种倒金字塔模型，0层分辨率最低。

1.1 TMS元文件解析

一个TMS数据定义了一个访问地图数据的统一接口，客户端并不直接访问这些地图数据，而是根据TMS的描述信息间接获取，一般表现为一个XML配置文件［7］。一个典型的TMS配置文件如图2所示。

图2 TMS元文件描述

由于使用XML文件进行组织，TMS元文件表现为一个典型的树状结构。根节点＜TileMap＞资源表示一个完整的地图，子节点＜Title＞表示该地图名称，子节点＜Abstract＞表示该地图简要描述，子节点＜SRS＞（Spatial Reference System）表示该地图使用的空间参考，子节点＜BoundingBox＞表示数据覆盖的空间范围，子节点＜Origin＞表示数据的原点坐标，子节点＜tileformat＞表示瓦片格式，包括瓦片大小和扩展名，子节点＜TileSets＞表示一些与尺度相关的地图数据集，包含一个投影模式（Profile）属性，投影模式共有3种：global-geodetic、global-mercator和local。

子节点＜TileSets＞的子节点集合＜TileSet＞由规则采样的图像数据块构成，一个＜TileSet＞表示在某一尺度上一系列固定大小均匀采样的数据块。一个＜TileSet＞的存储路径由其href属性决定，若href没有指定，则可以由其order（尺度或级数）指定。units-per-pixel表示瓦片的分辨率，即每个像素代表的度数，

当前最大级数一般为22级（折合分辨率约为0.01 m／像素）。其中，width为一个瓦片的像素宽度，一般定义为512或256，n为order级数。

若ImgeWidth表示一幅影像的像素宽度，maxX表示该影像的最大经度坐标，minX表示该影像的最小经度坐标，则该影像分辨率为（maxX－minX）／ImgeWidth，则切片的级数应满足Rn＜＝影像分辨率，结合式（1）推导得：

即

其中，n＝ceil（dblvalue）表示n为大于等于dblvalue的最小整数。

1.2 TMS瓦片划分规则

TMS采用四叉树结构进行瓦片划分，四叉树是一种每个非叶子节点最多只有4个分支的树型结构，也是一种层次数据结构，其特性是能够实现空间递归分解。瓦片金字塔模型的四叉树结构示意图如图3所示，其中矩形符号代表叶子节点，圆形符号代表非叶子节点。

图3 瓦片金字塔模型的四叉树结构

在瓦片金字塔基础上构建线性四叉树瓦片索引，与构建瓦片金字塔对应，规定块划分从地形数据左下角开始，从左至右，从下到上依次进行。同时规定四叉树的层编码与金字塔的层编码保持一致，如图4所示。

以一幅使用WGS84投影的地球全球地图为例，在0图层，TMS将这幅影像分成2块瓦片，每一块影像跨度为180°×180°。图层1在图层0影像的基础之上提高2倍的分辨率，也就是说对于同一影像，被分成90°×90°的片段，因此产生8块信息的瓦片。在图层2，分辨率提高到含有32块45°×45°的瓦片，图层3也就是22.5°×22.5°，含有128块瓦片，以此类推，如表1所示。

图4 四叉树的层编码

表1 TMS分块模式

1.3 TMS瓦片命名规则

TMS根据不同的细节层次，将瓦片存储在不同的文件夹中，瓦片的位置索引信息存储在文件路径中，如文件路径为“…＼图层名＼level＼column＼row. ext”，其中level表示层级，column表示列号，row表示行号，ext为后缀名：可为png、jpg、tiff等。坐标与图片命名的对应公式如下：

情况1：已知某坐标点X，Y（经度，纬度），求其在某层level的文件号column＼row：

其中，n＝floor（dblvalue）表示n为小于等于dblvalue的最大整数。

假设：X＝120，Y＝30，Level＝2，则column＝floor（6.667）＝6，row＝floor（2.667）＝2。即2＼6＼2.png。

情况2：已知图片编号column＼row，求这张图片的左下角坐标（X1，Y1）：

右上角坐标（X2，Y2）为：

假设：column＝6，row＝2，Level＝2，则X1＝90，Y1＝0；X2＝135，Y2＝45。

2 TMS切片算法设计

2.1 金字塔层级命中算法

对瓦片进行调度显示时，首先需要定位到瓦片所在层级，对于特定的请求范围，如一个屏幕大小表示的地理空间范围：BBox（minX，minY，maxX，maxY），命中的金字塔级别计算如下：

首先计算屏幕像素分辨率，即1个屏幕像素的地理空间长度（度数／像素）：

式中，ScreenWidth代表请求范围的屏幕像素宽度。

然后与金字塔层级对应的分辨率进行比较：

式中，width为一个瓦片的像素宽度；n为金字塔级数，n＞＝0。

若Rs＜＝1.5Rn，则命中的金字塔层级为n，推导可得：

即

n＝floor（dblvalue）表示n为小于等于dblvalue的最大整数。

2.2 瓦片命中算法

对于某一级别Level，特定的请求范围：BBox（minx，minY，maxX，maxY），命中的瓦片编号（column、row）计算如下：

最小瓦片编号：

最大瓦片编号：

则命中的瓦片列数为：

命中的瓦片行数为：

命中的瓦片数目为：

定义命中的瓦片编号为：（CX，RY），则CMin＜＝CX＜＝CMax；RMin＜＝RY＜＝RMax。

即命中的瓦片编号列表为：

2.3 TMS切片算法

TMS瓦片金字塔为四叉树的层次数据结构，可采用深度优先算法或广度优先算法进行切片。

深度优先算法［8，9］：从0层开始进行切片，左下角为起始点，先切片0／0／0.ext，再进行0／0／0.ext的4个子树的第一个子树1／0／0.ext进行切片，再进行1／0／0.ext的第一个子树进行切片，如此递归。算法具有编程实现简单、递归嵌套较多、切片效率不高、尤其是大数据量的特点。

广度优先算法［10，11］：先进行0层切片，再进行1层切片，如此类推至n层或先进行n层切片，再进行n－1层，如此类推至0层。算法具有编程逻辑清晰、切片效率较高、单线程执行的特点。

算法优化：对于大数据量的影像，每次数据读取和瓦片切割会耗费较长时间，事先将图像分别缩放至n层分辨率，n－1层分辨率，直至0层。然后再逐层进行切片，每层可由一个独立的线程进行切片处理。每层切片完毕后，同时删除缩放的预处理影像，释放临时占用的存储空间。

但是，对于n层或接近n层的预处理影像数据量仍然较大，改进为每层先按行进行切片，生成长条图像，长条图像高度等于瓦片高度，再每行一个线程独立进行逐列切片。每行切片完毕，则删除该行长条图像。

算法特点：采用临时的“空间换取时间”的策略，有效降低每个瓦片的切割时间，采用多线程并行执行，充分发挥多核处理器的性能，可有效提高切片效率，尤其是大数据量［12］。

2.4 切片实验分析

实验采用GDAL库函数进行影像数据的读写，瓦片大小设定为512512像素，在惠普Z600图形工作站上进行，工作站系统配置如下：

●操作系统：Windows XP SP3，32位；

●CPU：Intel E5620 2.4 GHz，4核；

●内存：4 GB；

●显卡：NVIDIA Quadro FX1800，显存768 MB；

●硬盘：500 GB。

多次实验取平均值，影像图像数据量和切片时间记录如表2所示。

表2 平均每个瓦片的切片速度

由表2可知，切割一个固定大小的瓦片，影像大小对切片效率影响较大，小于300 Mbytes的图像一个切片时间约在100 ms以下，对于大于2 GB的文件约1～3 s或更长时间。因此，减少影像大小能够有效提高切片效率。

表3 多线程切分时间

由表3可知，多线程切片效率是单线程的4～6倍。但随着线程数的增加，效率改进并不明显，线程过多将会耗费更多的线程同步时间，也可能与操作系统、CPU的多线程处理能力、磁盘IO等有关。但多线程并发处理同一幅影像，生成的瓦片会出现影像条带空缺的情况，严重影响使用，且线程数越多，出现的概率越大。

为避免多个线程并发处理同一幅影像而出现条带空缺的情况，使用一个单线程（主线程）处理原始影像按行生成长条图像，在长条图像生成后同时启动一个新线程（子线程）对该长条图像进行切片，主线程继续处理生成下一个长条图像。

对于上述5.1 GB的同一幅影像，生成一个长条图像的时间约16 s，大小约96 MB，含96个瓦片，结合表2，每个瓦片切割的时间按100 ms计算，则切片时间为：96100／1 000＝9.6 s。对于该幅影像，理论上，在主线程生成下一个长条图像后，子线程即可完成上一个长条图像的切片。该影像共需生成75个长条图像，则理论上计算总时间为：7516／60＝20 min。经多次试验取平均值，实际耗费时间约为26.8 min。

3 结束语

通过对TMS技术进行深入研究和切片算法设计，实现了TMS瓦片金字塔的快速切分，可为项目工程应用提供数据处理支持。对切片效率改进仍有较大的提升空间，今后可在多线程切片机制或多机并行处理等方面继续进行研究试验。

［1］张学亮，陈金勇，陈 勇.基于Hadoop云计算平台的海量文本处理研究［J］.无线电通信技术，2014，40（1）：54－57.

［2］唐伟广，马 健.基于瓦片技术的遥感影像库设计与实现［J］.无线电工程，2013，43（6）：44－46，57.

［3］黄梦龙.瓦片地图技术在桌面端GIS中的应用［J］.地理空间信息，2011，9（4）：149－151.

［4］李 钊，李建军，李 冰，等.海量数据纹理映射技术研究［J］.无线电通信技术，2011，37（4）：34－36.

［5］王文涛.地理栅格数据压缩与场景组织管理技术研究与实现［D］.长沙：国防科学技术大学，2011.

［6］聂云峰，周文生，舒 坚，等.基于Z曲线的瓦片地图服务空间索引［J］.中国图像图形学报，2012，17（2）：286－292.

［7］吴小东，许捍卫.基于OSGEarth的城市三维场景构建

［8］唐青松.深度优先算法在创建树形结构中的应用研究［J］.计算机技术与发展，2014，24（9）：226－229.

［9］龚建华.深度优先搜索算法及其改进［J］.现代电子技术，2007，30（22）：90－92.

［10］杨爱民.并行广度优先搜索算法研究［D］.西安：西安电子科技大学，2012.

［11］鄢靖丰，陶少华，夏方玉.基于单元树结构的广度优先P2P搜索算法［J］.计算机工程，2011，37（9）：135－137.

［12］李秀芳.基于多核的多线程算法并行优化［D］.郑州：郑州大学，2010.

A Tile Pyramid Slicing Based on TMS

LIU Rang-guo1，LIU Xiao-jie1，LIU Shun-xi2，WEI Er-long1
（1．The 54th Research Institute of CETC，Shijiazhuang Hebei 050081，China；2．China Land Surveying and Planning Institute，Beijing 100035，China）

For raising slice efficiency effectively under of big data quantity，research is performed on TMS technology，its metafile，the rule of tile slicing，tile naming and so on.A realization of TMS slice algorithm is designed.And a kind of method is put forward that tile pyramid slicing based on TMS，which improves slice algorithm combined with multithreading.Experiment results show that this meth-od can raise the slice efficiency of tile.

pyramid；tile；quad-tree；multithreading；TMS

TP361

A

1003－3106（2015）11－0040－04

10.3969／j.issn.1003－3106.2015.11.11

刘让国，刘晓杰，刘顺喜，等.一种基于TMS的瓦片金字塔切分方法［J］.无线电工程，2015，45（11）：40－43，68.

刘让国男，（1979—），高级工程师。主要研究方向：计算机图形学与地理信息系统。

2015-08-05

国家部委基金资助项目。

刘晓杰女，（1980—），高级工程师。主要研究方向：大数据管理与架构设计。