嵌入式设备室内地图的瓦片金字塔优化

张俪文，汪云甲，曹新运

(中国矿业大学 环境与测绘学院，江苏 徐州 221116)

1 引言

瓦片金字塔技术已经广泛应用在组织和储存海量遥感数据，并取得许多重要的成果[1-2]，而且该技术还适用于各种地图服务，如矢量地图，街景地图和三维地图。传统的金字塔模型采用2倍率[3]的分辨率变化函数，适用于上述跨度较大的地图数据，但对于地图数据的跨度较小时，如室内地图，区域专题地图，这类模型将不再适合：动态缩放显示时，画面会产生跳跃和断层[4]；图像在几何比例缩放时，会产生细节显示模糊的情况，从而影响地图表达。

地图的加载速度与瓦片模型[5-8]、缓存[9-10]以及检索方式[11-12]有关，其中瓦片模型，即瓦片规格，对地图加载速度和总体文件大小有重要影响。瓦片规格较小，会造成文件数目增加，加载次数过多，以致延迟显示速度；瓦片规格较大，则会加载过多屏幕之外的数据，造成数据冗余。因此需要选择适合的瓦片规格以保证较快的显示速度。

2 瓦片金字塔模型分层优化

瓦片金字塔模型是将同一地区不同分辨率的图像分层管理，从上到下分辨率由低到高，但所表示的地理范围不变[13]。设第0层的分辨率为res0，则第l层的分辨率resl为[14]

resl=res0×f(l)

(1)

根据划分的策略不同，选择不同的。遥感图像中最常使用的是指数变化，即指数变化较快，则可以很好的适应大范围图像到小范围图像的变化。但是在室内地图中由于地图的范围较小，而指数变化的速度过快，常用的分层方法并不能满足室内地图放大缩小的需求。如图1所示，在使用传统的指数变化的图像时，第1、2层的分辨率变化还不是很显著，但是随着指数的变大，由于分辨率变化的过快，在第3层已经不能反映原图中的线条，而第4层的部分线段已经由模糊点代替。

图1 指数变化示意

为克服指数变化过快不能满足室内地图放大和缩小的需求，考虑室内地图选择变化较为均匀的，可能会取得更好的效果。因此，本文在室内地图中使用线性变化代替指数变化，即为查看最终效果，在图1的第0层图幅的基础上，采用线性系数0.2，结果如下图2所示。可以明显看出：第1、2、3层中的线条比较清晰，第4层中较细的线条部分出现模糊打断的情况。对比图1(c)和图2(d)，第4层也远比图1中指数变化的第3层的线条清晰。

图2 线性变化示意

3 瓦片金字塔模型规格选择

由于嵌入式设备内存的限制，整幅图像放入内存中会导致内存溢出(out of memory，OOM)错误，对图像进行分块可以很好的解决这个问题。图像分块理论上没有具体的限制，但是在实际应用中需要考虑读取时间和数据大小，如果涉及到网络还要考虑数据传输的问题。

实验使用1040*609的204 kB的PNG图像，在1024*600的屏幕上进行显示，瓦片的规格有16*16、24*24、32*32、64*64、72*72、96*96、108*108、128*128、196*196、256*256、300*300、400*400、512*512。程序运行在安卓(Android)2.2的模拟器上，内存36 MB，SDCard 256 MB。

在现有的优化模型基础上，尝试选取合适的瓦片规格。这里讨论的瓦片规格选择主要针对两方面：分块文件大小和读取文件时间。

3.1 分块文件大小

在划分瓦片的过程中会出现空白瓦片，这类瓦片应当删除，表1是瓦片划分中分块文件大小和空白瓦片大小，以及文件的删除率。从表中可以看出，文件大小的变化主要是由两方面的原因造成：一方面，文件的空白区域有一部分变为空白瓦片被删除，另一个方面，新建文件的头文件也会占用一定的空间，在文件足够多的时候，这些头文件占用的空间，会抵消掉删除空白瓦片的减少量。

表1 分块文件大小、空值文件大小和文件删除率

当瓦片的规格较小时，文件的数量会很大，会使文件的总大小激增，如图3所示，瓦片的大小应该选择72*72以上规格，会使得去空值文件和原始图像大小基本相当。因此选择合适的瓦片规格能够在很大程度上减少文件删除率，让用户能够得到更好的体验，建议选取的瓦片规格不能太小。

图3 瓦片文件大小变化图

3.2 文件读取时间

从时间大小上来看，显示时间有两个部分组成，一部分是读取文件使用的时间，另一部分是显示使用的时间，对每个规格的瓦片都进行10次同范围的显示，以下是统计的时间信息，包括瓦片读取时间和瓦片显示时间，如表2、表3所示。

表2 瓦片读取时间

表3 瓦片显示时间

将读取时间和显示时间相加，即可得到显示总时间变化曲线图，如图4所示。从显示总时间上来看，更加肯定了使用大于72*72规格瓦片更有利于快速显示。从曲线走势上可以看出，选择合适的瓦片规格，能够在很大程度上降低文件读取时间。

图4 瓦片显示总时间关系图

为进一步分析上述数据，下面从文件读取消耗时间的大小和时间消耗的稳定性两方面综合分析。比较表2与表3可以发现，显示时间所占的份额较少，因此这里重点在读取时间上进行筛选。选取96*96、108*108和128*128的瓦片读取时间大小进行比较，如图5所示。三条曲线的时间变化较为稳定，从时间大小上来看选择128*128规格的瓦片较好，读取时间更短。

图5 瓦片的读取时间大小分析

从时间消耗稳定性方面分析，截选规格大于128*128的瓦片，如图6所示。128*128的瓦片稳定性更好。从均值上来看，这三个瓦片规格读取的时间现不多，512*512规格的占用的时间更少；但是从单个时间上来看，512*512与256*256规格的瓦片时间的变化较大，并不稳定，这是由Android的垃圾处理机制造成的，从稳定性能上来说，选择128*128规格的瓦片较好。

图6 瓦片读取时间稳定性分析

综上所述，在选择瓦片规格时，需要综合考虑分块文件大小以及文件读取时间和稳定性，反过来，选择合适的瓦片规格会使得室内地图在Android平台上加载时间更短更稳定，且不会引起图像的模糊打断现象。

4 结论

为了快速读取和显示室内地图，本文对瓦片金字塔模型进行改进，选用线性分辨率变化函数取代指数变化函数，并从文件大小、读取时间大小和稳定性方面综合分析瓦片的选取问题，通过实验得出不同瓦片规格文件对读取时间和时间稳定性的影响，得到如下结论：

(1)对于室内地图，使用指数变换分辨率函数会使得原始图像在放大、缩小过程中出现模糊断点的现象，改用线性变化的分辨率可以得到更好的用户体验；

(2)合适的瓦片规格能够在很大程度上降低文件删除率，使得用户能够得到更好的体验，瓦片规格不宜选取太小。

(3)选取合适的瓦片规格，能够在很大程度上降低文件的读取时间，提高读取时间的稳定性；

因此，在加载室内地图选取瓦片规格时，需要综合考虑瓦片规格对文件删除率的影响、图像显示时间以及显示时间的稳定性。在本文实验条件下，使用128*128规格的瓦片可以使得用户在加载室内地图时能够更加清晰快速。

[1] 戴晨光，邓雪清，张永生.海量地形数据实时可视化技术研究[J].测绘信息与工程，2004，29(6)：6-9.

[2] 杜莹，武玉国，王晓明，等.全球多分辨率虚拟地形环境的金字塔模型研究[J].系统仿真学报，2006，18(4)：955-958+967.

[3] 邓雪清.栅格型空间数据服务体系结构与算法研究[D].郑州：中国人民解放军信息工程大学，2003.

[4] TIMPF S，FRANK A U.A Multi-scale Data Structure for Cartographic Objects[M].Wien：Technical University of Vienna，Department for Geoinformation，1995.

[5] 李德仁，肖志峰，朱欣焰，等.空间信息多级网格的划分方法及编码研究[J].测绘学报，2006，35(1)：52-56+70.

[6] 张永生，贲进，竟晓冲.地球空间信息球面离散网格：理论，算法及应用[M].北京：科学出版社，2007.

[7] KANG Yong-Kyoon，KIM Ki-Chang，KIM Yoo-Sung .Probability-based Tile Pre-fetching and Cache Replacement Algorithms for Web Geographical Information Systems[EB/OL].(2001-09-05)[2014-08-08].http：//people.cs.aau.dk/～simas/teaching/map_download/MobilePrefetching2.pdf.

[8] YANG Chao-wei，WONG D，YANG Rui-xin，et al.Performance-improving Techniques in Web-based GIS[J].International Journal of Geographical Information Science，2005，19(3)：319-342.

[9] 王浩，喻占武，曾武，等.基于瓦片寿命和访问热度的海量空间数据缓存置换策略[J].武汉大学学报：信息科学版，2009，34(6)：667-670.

[10] 李云锦，钟耳顺，王尔琪，等.马尔可夫模型在空间数据预取中的应用[J].测绘通报，2010(7)：1-4.

[11] CHEN Hue-ling，CHANG Ye-in.Neighbor-finding Based on Space-filling Curves[J].Information systems，2005，30(3)：205-226.

[12] 龚健雅.一种基于自然数的线性四叉树编码[J].测绘学报，1992，21(2)：90-99.

[13] RABIEE H R，KASHYA PR，SAFAVIAN S R.Multiresolution Segmentation-based Image Coding with Hierarchical Data Structures[C]//Proceedings of 1996 IEEE International Conference on Acoustics，Speech，and Signal Processing(ICASSP-96).Atlanta，GA：IEEE，1996：1870-1873.

[14] 戚正伟，付国庆，蔡松露，等.嵌入式GIS开发及应用[M].北京：清华大学出版社.2009.