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

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

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

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

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

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

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

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

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

目前，以Google Maps、百度地圖為代表的移動端地圖應用，多以四叉樹瓦片金字塔模型進行遙感影像的可視化展示，每張瓦片像元大小為256×256[2]，雖然其具有數據量小、利于網絡傳輸等優點，但也存在尋址時間過長，讀寫次數頻繁等缺點。基于五層十五級組織架構的海量遙感數據在移動端加載展示尚存在技術空白，若直接套用四叉樹瓦片金字塔模型的方式來加載，存在內存溢出、地圖展示連續性差等問題[3]。鑒于此，本文詳細闡述了用于加載到移動端的遙感影像數據的五層十五級組織結構，并在此基礎上設計了大范圍遙感影像瓦片數據在移動端的快速瀏覽算法。

1 五層十五級遙感數據組織模型

由于遙感影像數據具有多源異構、多時空尺度、地理位置信息無統一標準以及數據量巨大等特性，直接使用會導致產品生產時計算量過大、展示效果差等不良后果[4]，故運用五層十五級遙感數據組織模型對遙感影像數據進行有效的組織管理[5]。

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

圖1 五層十五級遙感數據組織模型

2 五層十五級瓦片數據移動端傳統加載算法

五層十五級瓦片數據按四叉樹瓦片金字塔結構的數據加載算法[8]進行加載的主要步驟為：首先獲得屏幕的經緯度范圍；然后將經緯度轉化為瓦片行列號范圍；最后加載展示行列號范圍內的瓦片。

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

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

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

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

3 五層十五級瓦片數據移動端快速加載算法

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

3.1 按需動態計算待加載瓦片范圍

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

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

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

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

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

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

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

圖2 經緯度轉化為行列號的示意圖

3.2 循環加載展示

循環對待加載瓦片列表中的瓦片進行加載展示，具體步驟為：

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

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

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

3.3 緩存策略

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

1）判斷選中瓦片的Bitmap對象是否存在于內存緩存中：若存在，則結束本次緩存；若不存在，執行下一步。

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

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

3.4 延后刪除策略

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

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

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

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

4 測試結果及分析

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

實驗環境為三星GT-N8010，1.4GHz四核處理器，1 280×800分辨率，2 GB內存，16 GB存儲器，操作系統為Android 4.1.2。實驗影像為五層十五級組織結構的2015下半年和2016上半年北京地區4級（1 m分辨率）至15級（5 km分辨率）遙感數據瓦片。

4.1 加載時間的對比

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

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

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

4.2 內存使用量對比

本文還對兩種加載算法在加載過程中的內存消耗情況進行了測試統計，結果如圖3所示。

圖3 五層十五級瓦片加載內存消耗對比

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

5 結 語

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

[1] 段龍方. 面向遙感數據的云數據庫技術研究與應用[D]. 開封：河南大學,2014：1-11

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

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

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

[5] 中國科學院遙感應用研究所.一種基于經緯網格的數據分級組織方法：CN102346923A[P].2012-02-08

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

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

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

[9] 曹海濤,賈博,張波.移動GIS切片地圖展現技術[J].計算機系統應用,2013,22(12)：215-218

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

P208

B

1672-4623（2017）05-0029-03

10.3969/j.issn.1672-4623.2017.0050.9

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

2016-07-26。

項目來源：高分重大專項資助項目（Y4D00100GF、Y4D0100038）；中科院戰略先導專項資助項目（Y1Y02230XD）。