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

劉讓國，劉曉杰，劉順喜，韋二龍

（1.中國電子科技集團公司第五十四研究所，河北 石家莊 050081；2.中國土地勘測規(guī)劃院，北京 100035）

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

劉讓國1，劉曉杰1，劉順喜2，韋二龍1

（1.中國電子科技集團公司第五十四研究所，河北 石家莊 050081；2.中國土地勘測規(guī)劃院，北京 100035）

為了有效提高大數(shù)據(jù)量下的切片效率，從瓦片地圖服務(wù)（Tile Map Service，TMS）元文件、瓦片劃分規(guī)則和瓦片命名規(guī)則等方面對TMS技術(shù)進行了研究，對切片算法進行了設(shè)計實現(xiàn)，并結(jié)合多線程機制進行了優(yōu)化改進，從而提出一種基于TMS的瓦片金字塔切分方法。試驗結(jié)果表明，該方法能提高瓦片的切片效率。

金字塔；瓦片；四叉樹；多線程；TMS

0 引言

目前地理信息系統(tǒng)處理顯示的數(shù)據(jù)量已達GB級、TB級甚至PB級，一次性完全加載顯示基本沒有可能，也會造成顯示效率低下。因此需要對空間數(shù)據(jù)進行預(yù)處理，形成統(tǒng)一的存儲組織標準，進行分塊存放。實時調(diào)度時可根據(jù)空間位置索引到瓦片，直接調(diào)用對應(yīng)數(shù)據(jù)，實現(xiàn)海量信息的快速共享與高效應(yīng)用［1，2］。

本文對TMS切片算法進行了設(shè)計實現(xiàn)，針對以前的TMS切片算法效率不高、單線程執(zhí)行的特點，利用多線程的方法對TMS切片算法進行了改進，有效提高了TMS切片算法的效率。新的TMS切片算法特別在處理大數(shù)據(jù)上具有顯著優(yōu)勢。

1 TMS瓦片金字塔技術(shù)

地圖瓦片技術(shù)是一種地圖預(yù)緩存技術(shù)，將配置好的一定坐標范圍的地圖，按照固定的若干個比例尺（瓦片級別）和指定圖片尺寸，切成若干行及列的正方形圖片，以指定的格式保存成圖像文件，按一定的命名規(guī)則和組織方式存儲到目錄系統(tǒng)中或是數(shù)據(jù)庫系統(tǒng)里，形成金字塔模型的靜態(tài)地圖緩存，地圖切圖所獲得的地圖切片也叫瓦片（Tile）。瓦片金字塔模型是一種多分辨率層次模型，從瓦片金字塔的底層到頂層，分辨率越來越低，但表示的地理范圍不變［3，4］。瓦片金字塔的示意如圖1所示。

圖1 瓦片金字塔

瓦片地圖由于采用了以“空間換取時間”的策略，預(yù)先緩存地圖，讀取靜態(tài)的圖片在客戶端拼接瀏覽，從而可以快速地提供地圖的服務(wù)，帶來更好的用戶體驗［5］。

TMS是由開源地理空間基金會（Open Source Geospatial Foundation，OSGeo）定義和發(fā)布的一種地圖瓦片規(guī)范。通過定義統(tǒng)一的切圖標準和獨立服務(wù)接口，以地圖切片的行列位置為基礎(chǔ)參數(shù)直接訪問柵格地圖，提高地圖的訪問速度。目前，TMS正逐步成為事實標準，TMS服務(wù)是柵格地圖發(fā)布的發(fā)展方向［6］。TMS是一種倒金字塔模型，0層分辨率最低。

1.1 TMS元文件解析

一個TMS數(shù)據(jù)定義了一個訪問地圖數(shù)據(jù)的統(tǒng)一接口，客戶端并不直接訪問這些地圖數(shù)據(jù)，而是根據(jù)TMS的描述信息間接獲取，一般表現(xiàn)為一個XML配置文件［7］。一個典型的TMS配置文件如圖2所示。

圖2 TMS元文件描述

由于使用XML文件進行組織，TMS元文件表現(xiàn)為一個典型的樹狀結(jié)構(gòu)。根節(jié)點＜TileMap＞資源表示一個完整的地圖，子節(jié)點＜Title＞表示該地圖名稱，子節(jié)點＜Abstract＞表示該地圖簡要描述，子節(jié)點＜SRS＞（Spatial Reference System）表示該地圖使用的空間參考，子節(jié)點＜BoundingBox＞表示數(shù)據(jù)覆蓋的空間范圍，子節(jié)點＜Origin＞表示數(shù)據(jù)的原點坐標，子節(jié)點＜tileformat＞表示瓦片格式，包括瓦片大小和擴展名，子節(jié)點＜TileSets＞表示一些與尺度相關(guān)的地圖數(shù)據(jù)集，包含一個投影模式（Profile）屬性，投影模式共有3種：global-geodetic、global-mercator和local。

子節(jié)點＜TileSets＞的子節(jié)點集合＜TileSet＞由規(guī)則采樣的圖像數(shù)據(jù)塊構(gòu)成，一個＜TileSet＞表示在某一尺度上一系列固定大小均勻采樣的數(shù)據(jù)塊。一個＜TileSet＞的存儲路徑由其href屬性決定，若href沒有指定，則可以由其order（尺度或級數(shù)）指定。units-per-pixel表示瓦片的分辨率，即每個像素代表的度數(shù)，

當前最大級數(shù)一般為22級（折合分辨率約為0.01 m／像素）。其中，width為一個瓦片的像素寬度，一般定義為512或256，n為order級數(shù)。

若ImgeWidth表示一幅影像的像素寬度，maxX表示該影像的最大經(jīng)度坐標，minX表示該影像的最小經(jīng)度坐標，則該影像分辨率為（maxX－minX）／ImgeWidth，則切片的級數(shù)應(yīng)滿足Rn＜＝影像分辨率，結(jié)合式（1）推導(dǎo)得：

即

其中，n＝ceil（dblvalue）表示n為大于等于dblvalue的最小整數(shù)。

1.2 TMS瓦片劃分規(guī)則

TMS采用四叉樹結(jié)構(gòu)進行瓦片劃分，四叉樹是一種每個非葉子節(jié)點最多只有4個分支的樹型結(jié)構(gòu)，也是一種層次數(shù)據(jù)結(jié)構(gòu)，其特性是能夠?qū)崿F(xiàn)空間遞歸分解。瓦片金字塔模型的四叉樹結(jié)構(gòu)示意圖如圖3所示，其中矩形符號代表葉子節(jié)點，圓形符號代表非葉子節(jié)點。

圖3 瓦片金字塔模型的四叉樹結(jié)構(gòu)

在瓦片金字塔基礎(chǔ)上構(gòu)建線性四叉樹瓦片索引，與構(gòu)建瓦片金字塔對應(yīng)，規(guī)定塊劃分從地形數(shù)據(jù)左下角開始，從左至右，從下到上依次進行。同時規(guī)定四叉樹的層編碼與金字塔的層編碼保持一致，如圖4所示。

以一幅使用WGS84投影的地球全球地圖為例，在0圖層，TMS將這幅影像分成2塊瓦片，每一塊影像跨度為180°×180°。圖層1在圖層0影像的基礎(chǔ)之上提高2倍的分辨率，也就是說對于同一影像，被分成90°×90°的片段，因此產(chǎn)生8塊信息的瓦片。在圖層2，分辨率提高到含有32塊45°×45°的瓦片，圖層3也就是22.5°×22.5°，含有128塊瓦片，以此類推，如表1所示。

圖4 四叉樹的層編碼

表1 TMS分塊模式

1.3 TMS瓦片命名規(guī)則

TMS根據(jù)不同的細節(jié)層次，將瓦片存儲在不同的文件夾中，瓦片的位置索引信息存儲在文件路徑中，如文件路徑為“…＼圖層名＼level＼column＼row. ext”，其中l(wèi)evel表示層級，column表示列號，row表示行號，ext為后綴名：可為png、jpg、tiff等。坐標與圖片命名的對應(yīng)公式如下：

情況1：已知某坐標點X，Y（經(jīng)度，緯度），求其在某層level的文件號column＼row：

其中，n＝floor（dblvalue）表示n為小于等于dblvalue的最大整數(shù)。

假設(shè)：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）為：

假設(shè)：column＝6，row＝2，Level＝2，則X1＝90，Y1＝0；X2＝135，Y2＝45。

2 TMS切片算法設(shè)計

2.1 金字塔層級命中算法

對瓦片進行調(diào)度顯示時，首先需要定位到瓦片所在層級，對于特定的請求范圍，如一個屏幕大小表示的地理空間范圍：BBox（minX，minY，maxX，maxY），命中的金字塔級別計算如下：

首先計算屏幕像素分辨率，即1個屏幕像素的地理空間長度（度數(shù)／像素）：

式中，ScreenWidth代表請求范圍的屏幕像素寬度。

然后與金字塔層級對應(yīng)的分辨率進行比較：

式中，width為一個瓦片的像素寬度；n為金字塔級數(shù)，n＞＝0。

若Rs＜＝1.5Rn，則命中的金字塔層級為n，推導(dǎo)可得：

即

n＝floor（dblvalue）表示n為小于等于dblvalue的最大整數(shù)。

2.2 瓦片命中算法

對于某一級別Level，特定的請求范圍：BBox（minx，minY，maxX，maxY），命中的瓦片編號（column、row）計算如下：

最小瓦片編號：

最大瓦片編號：

則命中的瓦片列數(shù)為：

命中的瓦片行數(shù)為：

命中的瓦片數(shù)目為：

定義命中的瓦片編號為：（CX，RY），則CMin＜＝CX＜＝CMax；RMin＜＝RY＜＝RMax。

即命中的瓦片編號列表為：

2.3 TMS切片算法

TMS瓦片金字塔為四叉樹的層次數(shù)據(jù)結(jié)構(gòu)，可采用深度優(yōu)先算法或廣度優(yōu)先算法進行切片。

深度優(yōu)先算法［8，9］：從0層開始進行切片，左下角為起始點，先切片0／0／0.ext，再進行0／0／0.ext的4個子樹的第一個子樹1／0／0.ext進行切片，再進行1／0／0.ext的第一個子樹進行切片，如此遞歸。算法具有編程實現(xiàn)簡單、遞歸嵌套較多、切片效率不高、尤其是大數(shù)據(jù)量的特點。

廣度優(yōu)先算法［10，11］：先進行0層切片，再進行1層切片，如此類推至n層或先進行n層切片，再進行n－1層，如此類推至0層。算法具有編程邏輯清晰、切片效率較高、單線程執(zhí)行的特點。

算法優(yōu)化：對于大數(shù)據(jù)量的影像，每次數(shù)據(jù)讀取和瓦片切割會耗費較長時間，事先將圖像分別縮放至n層分辨率，n－1層分辨率，直至0層。然后再逐層進行切片，每層可由一個獨立的線程進行切片處理。每層切片完畢后，同時刪除縮放的預(yù)處理影像，釋放臨時占用的存儲空間。

但是，對于n層或接近n層的預(yù)處理影像數(shù)據(jù)量仍然較大，改進為每層先按行進行切片，生成長條圖像，長條圖像高度等于瓦片高度，再每行一個線程獨立進行逐列切片。每行切片完畢，則刪除該行長條圖像。

算法特點：采用臨時的“空間換取時間”的策略，有效降低每個瓦片的切割時間，采用多線程并行執(zhí)行，充分發(fā)揮多核處理器的性能，可有效提高切片效率，尤其是大數(shù)據(jù)量［12］。

2.4 切片實驗分析

實驗采用GDAL庫函數(shù)進行影像數(shù)據(jù)的讀寫，瓦片大小設(shè)定為512512像素，在惠普Z600圖形工作站上進行，工作站系統(tǒng)配置如下：

●操作系統(tǒng)：Windows XP SP3，32位；

●CPU：Intel E5620 2.4 GHz，4核；

●內(nèi)存：4 GB；

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

●硬盤：500 GB。

多次實驗取平均值，影像圖像數(shù)據(jù)量和切片時間記錄如表2所示。

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

由表2可知，切割一個固定大小的瓦片，影像大小對切片效率影響較大，小于300 Mbytes的圖像一個切片時間約在100 ms以下，對于大于2 GB的文件約1～3 s或更長時間。因此，減少影像大小能夠有效提高切片效率。

表3 多線程切分時間

由表3可知，多線程切片效率是單線程的4～6倍。但隨著線程數(shù)的增加，效率改進并不明顯，線程過多將會耗費更多的線程同步時間，也可能與操作系統(tǒng)、CPU的多線程處理能力、磁盤IO等有關(guān)。但多線程并發(fā)處理同一幅影像，生成的瓦片會出現(xiàn)影像條帶空缺的情況，嚴重影響使用，且線程數(shù)越多，出現(xiàn)的概率越大。

為避免多個線程并發(fā)處理同一幅影像而出現(xiàn)條帶空缺的情況，使用一個單線程（主線程）處理原始影像按行生成長條圖像，在長條圖像生成后同時啟動一個新線程（子線程）對該長條圖像進行切片，主線程繼續(xù)處理生成下一個長條圖像。

對于上述5.1 GB的同一幅影像，生成一個長條圖像的時間約16 s，大小約96 MB，含96個瓦片，結(jié)合表2，每個瓦片切割的時間按100 ms計算，則切片時間為：96100／1 000＝9.6 s。對于該幅影像，理論上，在主線程生成下一個長條圖像后，子線程即可完成上一個長條圖像的切片。該影像共需生成75個長條圖像，則理論上計算總時間為：7516／60＝20 min。經(jīng)多次試驗取平均值，實際耗費時間約為26.8 min。

3 結(jié)束語

通過對TMS技術(shù)進行深入研究和切片算法設(shè)計，實現(xiàn)了TMS瓦片金字塔的快速切分，可為項目工程應(yīng)用提供數(shù)據(jù)處理支持。對切片效率改進仍有較大的提升空間，今后可在多線程切片機制或多機并行處理等方面繼續(xù)進行研究試驗。

［1］張學(xué)亮，陳金勇，陳 勇.基于Hadoop云計算平臺的海量文本處理研究［J］.無線電通信技術(shù)，2014，40（1）：54－57.

［2］唐偉廣，馬 健.基于瓦片技術(shù)的遙感影像庫設(shè)計與實現(xiàn)［J］.無線電工程，2013，43（6）：44－46，57.

［3］黃夢龍.瓦片地圖技術(shù)在桌面端GIS中的應(yīng)用［J］.地理空間信息，2011，9（4）：149－151.

［4］李 釗，李建軍，李 冰，等.海量數(shù)據(jù)紋理映射技術(shù)研究［J］.無線電通信技術(shù)，2011，37（4）：34－36.

［5］王文濤.地理柵格數(shù)據(jù)壓縮與場景組織管理技術(shù)研究與實現(xiàn)［D］.長沙：國防科學(xué)技術(shù)大學(xué)，2011.

［6］聶云峰，周文生，舒 堅，等.基于Z曲線的瓦片地圖服務(wù)空間索引［J］.中國圖像圖形學(xué)報，2012，17（2）：286－292.

［7］吳小東，許捍衛(wèi).基于OSGEarth的城市三維場景構(gòu)建

［8］唐青松.深度優(yōu)先算法在創(chuàng)建樹形結(jié)構(gòu)中的應(yīng)用研究［J］.計算機技術(shù)與發(fā)展，2014，24（9）：226－229.

［9］龔建華.深度優(yōu)先搜索算法及其改進［J］.現(xiàn)代電子技術(shù)，2007，30（22）：90－92.

［10］楊愛民.并行廣度優(yōu)先搜索算法研究［D］.西安：西安電子科技大學(xué)，2012.

［11］鄢靖豐，陶少華，夏方玉.基于單元樹結(jié)構(gòu)的廣度優(yōu)先P2P搜索算法［J］.計算機工程，2011，37（9）：135－137.

［12］李秀芳.基于多核的多線程算法并行優(yōu)化［D］.鄭州：鄭州大學(xué)，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—），高級工程師。主要研究方向：計算機圖形學(xué)與地理信息系統(tǒng)。

2015-08-05

國家部委基金資助項目。

劉曉杰女，（1980—），高級工程師。主要研究方向：大數(shù)據(jù)管理與架構(gòu)設(shè)計。