徐 鵬，趙亞萌，蘇煥煥，王 棟

（1.河南大學(xué) 空間信息處理實驗室，河南 開封 475004；2.中國科學(xué)院遙感與數(shù)字地球研究所，北京 100101）

海量五層十五級瓦片移動端快速加載算法研究

徐 鵬1,2，趙亞萌2，蘇煥煥1,2，王 棟2

（1.河南大學(xué) 空間信息處理實驗室，河南 開封 475004；2.中國科學(xué)院遙感與數(shù)字地球研究所，北京 100101）

針對傳統(tǒng)四叉樹加載方法在海量五層十五級遙感瓦片數(shù)據(jù)移動端加載展示過程中出現(xiàn)的內(nèi)存溢出和卡頓問題，設(shè)計了新型五層十五級瓦片移動端快速加載算法，以實現(xiàn)按需動態(tài)計算待加載瓦片范圍，循環(huán)加載展示；并采用緩存策略和延后刪除策略保證了展示效果。實驗結(jié)果表明，該算法顯著提高了五層十五級瓦片在移動端的加載速度，增強(qiáng)了展示的流暢性，內(nèi)存消耗量明顯下降并保持穩(wěn)定。

五層十五級；遙感瓦片數(shù)據(jù)；移動端；緩存策略；延后刪除策略

近年來，隨著風(fēng)云系列、環(huán)境星系列、資源系列和高分系列等遙感衛(wèi)星的密集發(fā)射，我國的衛(wèi)星遙感技術(shù)蓬勃發(fā)展，每天產(chǎn)生的遙感影像數(shù)據(jù)量也以TB級持續(xù)增長；積累了長時間序列的對地觀測數(shù)據(jù)，在氣象、國土、交通、環(huán)境保護(hù)和減災(zāi)等領(lǐng)域得到了廣泛應(yīng)用[1]。與此同時，移動端互聯(lián)網(wǎng)技術(shù)發(fā)展迅速，已成為互聯(lián)網(wǎng)發(fā)展的一個主方向，手機(jī)/平板電腦中的移動地圖服務(wù)應(yīng)用已逐漸深入人們的日常生活，如用戶使用移動地圖查找出行路線、規(guī)劃旅游線路或搜索未知地點等，遙感影像數(shù)據(jù)作為移動地圖服務(wù)的基礎(chǔ)數(shù)據(jù)，可為用戶提供更加生動、真實的使用感受。

目前，以Google Maps、百度地圖為代表的移動端地圖應(yīng)用，多以四叉樹瓦片金字塔模型進(jìn)行遙感影像的可視化展示，每張瓦片像元大小為256×256[2]，雖然其具有數(shù)據(jù)量小、利于網(wǎng)絡(luò)傳輸?shù)葍?yōu)點，但也存在尋址時間過長，讀寫次數(shù)頻繁等缺點?；谖鍖邮寮壗M織架構(gòu)的海量遙感數(shù)據(jù)在移動端加載展示尚存在技術(shù)空白，若直接套用四叉樹瓦片金字塔模型的方式來加載，存在內(nèi)存溢出、地圖展示連續(xù)性差等問題[3]。鑒于此，本文詳細(xì)闡述了用于加載到移動端的遙感影像數(shù)據(jù)的五層十五級組織結(jié)構(gòu)，并在此基礎(chǔ)上設(shè)計了大范圍遙感影像瓦片數(shù)據(jù)在移動端的快速瀏覽算法。

1 五層十五級遙感數(shù)據(jù)組織模型

由于遙感影像數(shù)據(jù)具有多源異構(gòu)、多時空尺度、地理位置信息無統(tǒng)一標(biāo)準(zhǔn)以及數(shù)據(jù)量巨大等特性，直接使用會導(dǎo)致產(chǎn)品生產(chǎn)時計算量過大、展示效果差等不良后果[4]，故運用五層十五級遙感數(shù)據(jù)組織模型對遙感影像數(shù)據(jù)進(jìn)行有效的組織管理[5]。

五層十五級遙感數(shù)據(jù)組織模型摒棄了四叉樹切分標(biāo)準(zhǔn)，將180°×360°的地球表層空間以 50°、5°、0.5°、0.05°、0.005°為基準(zhǔn)建立十進(jìn)制空間分辨率標(biāo)準(zhǔn)化數(shù)據(jù)層級，每層內(nèi)再按5∶2.5∶1構(gòu)成了3級標(biāo)準(zhǔn)瓦片，每張瓦片像元大小為1 000×1 000[6]。各級別的切塊大小都是簡單的有限浮點數(shù)，能按照簡單化經(jīng)緯度坐標(biāo)進(jìn)行位置確定，方便了數(shù)據(jù)的組織和管理，保證了多塊圖像在球面上顯示時可無縫拼接，滿足了不同比例尺地圖的輸出要求[7]。五層十五級遙感影像數(shù)據(jù)組織模型如圖1所示。

圖1 五層十五級遙感數(shù)據(jù)組織模型

2 五層十五級瓦片數(shù)據(jù)移動端傳統(tǒng)加載算法

五層十五級瓦片數(shù)據(jù)按四叉樹瓦片金字塔結(jié)構(gòu)的數(shù)據(jù)加載算法[8]進(jìn)行加載的主要步驟為：首先獲得屏幕的經(jīng)緯度范圍；然后將經(jīng)緯度轉(zhuǎn)化為瓦片行列號范圍；最后加載展示行列號范圍內(nèi)的瓦片。

1）利用屏幕的屬性得到屏幕坐標(biāo)范圍((0,0),(width,height))以及屏幕坐標(biāo)對應(yīng)的經(jīng)緯度范圍((lon0,lat0),(lonwidth,latheight))；其中，(0,0)為屏幕左上角坐標(biāo)原點，(width,height)為屏幕右下角坐標(biāo)點，(lon0,lat0)為屏幕坐標(biāo)原點所對應(yīng)地理坐標(biāo)，(lonwidth,latheight)為屏幕右下角所對應(yīng)地理坐標(biāo)。

2）將((lon0,lat0),(lonwidth,latheight))利用式（1）轉(zhuǎn)化為((mincol,maxrow),(maxcol,minrow))。

式中，z為層級對應(yīng)的瓦片分割間隔度數(shù)；(lon,lat)為頂點的經(jīng)緯度；(col,row)為瓦片所在的行列號；Int()為向下取整函數(shù)。為了保證行列號都為正值，便于計算，在緯度轉(zhuǎn)換公式中加上90°的偏移量，在經(jīng)度轉(zhuǎn)換公式中加上180°的偏移量。

3）選取((mincol,maxrow),(maxcol,minrow))內(nèi)所包含的瓦片進(jìn)行加載展示。

3 五層十五級瓦片數(shù)據(jù)移動端快速加載算法

五層十五級瓦片數(shù)據(jù)快速加載算法的主要步驟為：首先按需動態(tài)計算待加載瓦片范圍；然后循環(huán)對待加載瓦片列表中的瓦片進(jìn)行展示，并執(zhí)行緩存和延后刪除策略；最后判定選中瓦片是否為待加載列表內(nèi)最后一張瓦片的五層十五級瓦片在移動端快速加載展示。

3.1 按需動態(tài)計算待加載瓦片范圍

利用用戶操作的局部性原理，提出了一種新的計算瓦片索引范圍的算法，主要特點在于增加了對用戶將要執(zhí)行的操作的預(yù)判，并對將要展示的范圍進(jìn)行了預(yù)先計算。按需動態(tài)計算待加載瓦片范圍的算法具體步驟為：

1）獲取屏幕坐標(biāo)((0,0),(width,height))及經(jīng)緯度((lon0,lat0),(lonwidth,latheight))，并生成屏幕坐標(biāo)向量=(0,0,width,height)。

2）判定預(yù)先加載的方向，并計算待展示屏幕坐標(biāo)范圍：①當(dāng)用戶操作為放大或縮小時，預(yù)先加載方向為空，設(shè)定預(yù)加載向量為方向向量為；②當(dāng)用戶操作為平移滑動時，設(shè)定預(yù)加載向量為而預(yù)先加載方向則為最后一次屏幕的主要滑動方向：向右，則方向向量為向左，則方向向量為向上，則方向向量為向下，則方向向量為=(0,0,0,1)T；③按式（2）計算得到待展示的屏幕坐標(biāo)范圍((minwidth,minheight), (maxwidth,maxheight))。

式中，tilewidth、tileheight為五層十五級組織結(jié)構(gòu)瓦片的像元寬度和高度，均為1 000 pixel。

3）將待展示的屏幕坐標(biāo)范圍轉(zhuǎn)化為待展示的經(jīng)緯度范圍：利用式（3）將屏幕坐標(biāo)范圍((minwidth,minheight), (maxwidth,maxheight))轉(zhuǎn)換為經(jīng)緯度范圍((minlon,maxlat), (maxlon,minlat))。

式中，h∈[minheight, maxheight] ；w∈[minwidth, maxwidth]；height為屏幕長度；width為屏幕寬度。

4）將待展示的經(jīng)緯度范圍轉(zhuǎn)化為待加載瓦片的行列號范圍：如圖2所示，根據(jù)待展示的經(jīng)緯度范圍((minlon,maxlat),(maxlon,minlat))，按照式（1）將經(jīng)緯度范圍轉(zhuǎn)化為待加載瓦片的行列號范圍((mincol,maxrow), (maxcol,minrow))，并添加到待加載瓦片列表中。

圖2 經(jīng)緯度轉(zhuǎn)化為行列號的示意圖

3.2 循環(huán)加載展示

循環(huán)對待加載瓦片列表中的瓦片進(jìn)行加載展示，具體步驟為：

1）判斷展示列表中是否包含選中瓦片：若已包含，則結(jié)束本次加載；若未包含，執(zhí)行下一步。

2）判斷內(nèi)存緩存中是否包含選中瓦片的Bitmap對象：若已包含，則渲染繪制選中瓦片的Bitmap對象到用戶界面（UI），并將選中瓦片添加到加載列表中；若未包含，執(zhí)行下一步。

3）判斷本地存儲中是否存在選中瓦片：若存在，則將選中瓦片讀入內(nèi)存生成Bitmap對象并繪制到UI上，再將選中瓦片添加到加載列表中；若不存在，則向瓦片數(shù)據(jù)服務(wù)器發(fā)起瓦片數(shù)據(jù)下載請求，下載選中瓦片數(shù)據(jù)，并保存到本地數(shù)據(jù)存儲中。

3.3 緩存策略

根據(jù)瓦片加載的局部性原理，選中瓦片可能在臨近一段時間內(nèi)被連續(xù)選中，因此將選中瓦片的Bitmap對象以合理的策略安置到內(nèi)存中，以便再次加載顯示時避免重復(fù)的I/O操作。五層十五級瓦片在加載展示后設(shè)計了一、二級兩級緩存機(jī)制，用于緩解有限的設(shè)備內(nèi)存與大量遙感影像數(shù)據(jù)快速展示之間的矛盾。

1）判斷選中瓦片的Bitmap對象是否存在于內(nèi)存緩存中：若存在，則結(jié)束本次緩存；若不存在，執(zhí)行下一步。

2）將選中瓦片的Bitmap對象添加到一級緩存中，并判定一級緩存容量是否超過閾值：若超過，則移除一級緩存中最久未使用瓦片的Bitmap對象，并將其添加到二級緩存后執(zhí)行下一步；若未超過，則結(jié)束本次緩存。

3）判斷二級緩存容量是否超過閾值：若未超過，則結(jié)束本次緩存；若超過，則移除二級緩存中最久未使用瓦片的Bitmap對象。

3.4 延后刪除策略

由于手機(jī)的內(nèi)存容量是有限的，若添加瓦片過多會導(dǎo)致主線程UI出現(xiàn)卡頓現(xiàn)象，更嚴(yán)重的會造成內(nèi)存溢出、程序崩潰的情況，因此本文運用延后刪除策略來解決該問題。五層十五級瓦片快速加載算法的刪除策略為：

1）判斷加載列表中瓦片數(shù)量是否超過閾值：若超過，執(zhí)行下一步；若未超過，則結(jié)束本次刪除。

2）判定用戶操作的類型：若是放大，則保留加載列表中的高層級瓦片，并從中選取距當(dāng)前屏幕中心最遠(yuǎn)的瓦片；若是平移，則直接選取加載列表中距當(dāng)前屏幕中心最遠(yuǎn)的瓦片；若是縮小，則直接刪除加載列表中的低層級瓦片，并結(jié)束本次刪除。

3）判斷所選取瓦片是否包含于待加載瓦片列表中：若不包含，則從加載列表中刪除該瓦片；若包含，則結(jié)束本次刪除。

4 測試結(jié)果及分析

為了驗證五層十五級瓦片移動端快速加載算法的性能，本文使用多張五層十五級瓦片對兩種算法進(jìn)行加載展示，以便對比分析。

實驗環(huán)境為三星GT-N8010，1.4GHz四核處理器，1 280×800分辨率，2 GB內(nèi)存，16 GB存儲器，操作系統(tǒng)為Android 4.1.2。實驗影像為五層十五級組織結(jié)構(gòu)的2015下半年和2016上半年北京地區(qū)4級（1 m分辨率）至15級（5 km分辨率）遙感數(shù)據(jù)瓦片。

4.1 加載時間的對比

首先，對五層十五級瓦片的加載時間進(jìn)行統(tǒng)計測試，分別利用傳統(tǒng)數(shù)據(jù)加載算法和五層十五級瓦片移動端快速加載算法對五層十五級瓦片進(jìn)行展示，其中傳統(tǒng)加載時間包括獲取屏幕行列號范圍和渲染繪制瓦片的總體耗時，而快速加載時間包括按需動態(tài)計算待加載范圍、Bitmap對象緩存、渲染繪制瓦片和延后刪除瓦片的總體耗時。測試結(jié)果如表1所示。

表1 五層十五級瓦片平均加載時間對比

由表1可知，當(dāng)加載展示的瓦片較少時，本文通過緩存加載瓦片Bitmap對象的方式將平均加載時間縮短為傳統(tǒng)加載方式的53%；兩種加載方式的平均加載時間均隨加載張數(shù)的遞增而遞減，與此同時，快速加載方式通過按需動態(tài)計算待加載瓦片范圍增加了內(nèi)存中的瓦片，進(jìn)一步縮短了加載平均時間，增大了加速比，實現(xiàn)了瓦片的快速展示。

4.2 內(nèi)存使用量對比

本文還對兩種加載算法在加載過程中的內(nèi)存消耗情況進(jìn)行了測試統(tǒng)計，結(jié)果如圖3所示。

圖3 五層十五級瓦片加載內(nèi)存消耗對比

由圖3可知，五層十五級瓦片按照傳統(tǒng)加載方式加載時，移動設(shè)備內(nèi)存使用量隨加載次數(shù)呈線性增長，由于移動端設(shè)備內(nèi)存有限，當(dāng)內(nèi)存消耗量達(dá)到或超過250 M時會導(dǎo)致程序卡頓甚至崩潰；而按照快速加載方式加載時，通過對內(nèi)存中的瓦片Bitmap對象執(zhí)行緩存和延后刪除策略，將內(nèi)存的最大使用量控制為150 M，保證了海量遙感數(shù)據(jù)在移動端的流暢展示和加載的穩(wěn)定性。

5 結(jié) 語

實驗表明，本文提出的快速加載算法與傳統(tǒng)加載算法相比，在海量五層十五級瓦片數(shù)據(jù)展示時的速度是原來的2.5倍，且避免了內(nèi)存的過度消耗，提升了海量五層十五級瓦片數(shù)據(jù)在移動端展示的效率。下一步的工作，將會重點研究五層十五級瓦片在移動端展示的并行加載算法，進(jìn)一步提高海量瓦片在移動端的加載效率。

[1] 段龍方. 面向遙感數(shù)據(jù)的云數(shù)據(jù)庫技術(shù)研究與應(yīng)用[D]. 開封：河南大學(xué),2014：1-11

[2] 周強(qiáng),宋志峰,劉易鑫,等.一種適用于多移動終端的地圖瓦片格式的研究與應(yīng)用[J].測繪與空間地理信息, 2013,36(增刊)：70-76

[3] 高勇,陳文康,李浩松,等.基于多層架構(gòu)的WebGIS瓦片加載模式[J].計算機(jī)與數(shù)字工程,2015,43(6)：1 078-1 083

[4] 羅曉麗.基于云計算的遙感影像存儲組織模型研究[D].開封：河南大學(xué),2013：9-10

[5] 中國科學(xué)院遙感應(yīng)用研究所.一種基于經(jīng)緯網(wǎng)格的數(shù)據(jù)分級組織方法：CN102346923A[P].2012-02-08

[6] 鄭逢斌,張哲,余濤,等.一種支持多任務(wù)高效處理的遙感產(chǎn)品生產(chǎn)線架構(gòu)研究[J].計算機(jī)科學(xué),2012,39(增刊)：181-184

[7] 王棟,鄭逢斌,賴積保,等.基于五層十五級遙感數(shù)據(jù)結(jié)構(gòu)的并行算法研究[J].微計算機(jī)信息,2012,28(1)：166-167

[8] 黃夢龍.瓦片地圖技術(shù)在桌面端GIS中的應(yīng)用[J].地理空間信息,2011,9(4)：149-151

[9] 曹海濤,賈博,張波.移動GIS切片地圖展現(xiàn)技術(shù)[J].計算機(jī)系統(tǒng)應(yīng)用,2013,22(12)：215-218

[10] 李榮寬,高勇,楊璞.一種地圖顯示優(yōu)化的方法[J].科技創(chuàng)新導(dǎo)報,2014(14)：216-217

P208

B

1672-4623（2017）05-0029-03

10.3969/j.issn.1672-4623.2017.0050.9

徐鵬，碩士研究生，主要研究方向為空間數(shù)據(jù)處理。

2016-07-26。

項目來源：高分重大專項資助項目（Y4D00100GF、Y4D0100038）；中科院戰(zhàn)略先導(dǎo)專項資助項目（Y1Y02230XD）。