劉讓國(guó)，劉曉杰，劉順喜，韋二龍

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

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

劉讓國(guó)1，劉曉杰1，劉順喜2，韋二龍1

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

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

金字塔；瓦片；四叉樹(shù)；多線程；TMS

0 引言

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

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

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

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

圖1 瓦片金字塔

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

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

1.1 TMS元文件解析

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

圖2 TMS元文件描述

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

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

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

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

即

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

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

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

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

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

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

圖4 四叉樹(shù)的層編碼

表1 TMS分塊模式

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

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

情況1：已知某坐標(biāo)點(diǎn)X，Y（經(jīng)度，緯度），求其在某層level的文件號(hào)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：已知圖片編號(hào)column＼row，求這張圖片的左下角坐標(biāo)（X1，Y1）：

右上角坐標(biāo)（X2，Y2）為：

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

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

2.1 金字塔層級(jí)命中算法

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

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

式中，ScreenWidth代表請(qǐng)求范圍的屏幕像素寬度。

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

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

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

即

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

2.2 瓦片命中算法

對(duì)于某一級(jí)別Level，特定的請(qǐng)求范圍：BBox（minx，minY，maxX，maxY），命中的瓦片編號(hào)（column、row）計(jì)算如下：

最小瓦片編號(hào)：

最大瓦片編號(hào)：

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

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

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

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

即命中的瓦片編號(hào)列表為：

2.3 TMS切片算法

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

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

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

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

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

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

2.4 切片實(shí)驗(yàn)分析

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

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

●CPU：Intel E5620 2.4 GHz，4核；

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

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

●硬盤(pán)：500 GB。

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

表2 平均每個(gè)瓦片的切片速度

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

表3 多線程切分時(shí)間

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

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

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

3 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

［11］鄢靖豐，陶少華，夏方玉.基于單元樹(shù)結(jié)構(gòu)的廣度優(yōu)先P2P搜索算法［J］.計(jì)算機(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

劉讓國(guó)，劉曉杰，劉順喜，等.一種基于TMS的瓦片金字塔切分方法［J］.無(wú)線電工程，2015，45（11）：40－43，68.

劉讓國(guó)男，（1979—），高級(jí)工程師。主要研究方向：計(jì)算機(jī)圖形學(xué)與地理信息系統(tǒng)。

2015-08-05

國(guó)家部委基金資助項(xiàng)目。

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