海量五层十五级瓦片移动端快速加载算法研究

徐 鹏，赵亚萌，苏焕焕，王 栋

（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）。