嵌入式設備室內地圖的瓦片金字塔優化

張儷文，汪云甲，曹新運

(中國礦業大學 環境與測繪學院，江蘇 徐州 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.