嵌入式設(shè)備室內(nèi)地圖的瓦片金字塔優(yōu)化

張儷文，汪云甲，曹新運

(中國礦業(yè)大學(xué) 環(huán)境與測繪學(xué)院，江蘇 徐州 221116)

1 引言

瓦片金字塔技術(shù)已經(jīng)廣泛應(yīng)用在組織和儲存海量遙感數(shù)據(jù)，并取得許多重要的成果[1-2]，而且該技術(shù)還適用于各種地圖服務(wù)，如矢量地圖，街景地圖和三維地圖。傳統(tǒng)的金字塔模型采用2倍率[3]的分辨率變化函數(shù)，適用于上述跨度較大的地圖數(shù)據(jù)，但對于地圖數(shù)據(jù)的跨度較小時，如室內(nèi)地圖，區(qū)域?qū)ｎ}地圖，這類模型將不再適合：動態(tài)縮放顯示時，畫面會產(chǎn)生跳躍和斷層[4]；圖像在幾何比例縮放時，會產(chǎn)生細(xì)節(jié)顯示模糊的情況，從而影響地圖表達。

地圖的加載速度與瓦片模型[5-8]、緩存[9-10]以及檢索方式[11-12]有關(guān)，其中瓦片模型，即瓦片規(guī)格，對地圖加載速度和總體文件大小有重要影響。瓦片規(guī)格較小，會造成文件數(shù)目增加，加載次數(shù)過多，以致延遲顯示速度；瓦片規(guī)格較大，則會加載過多屏幕之外的數(shù)據(jù)，造成數(shù)據(jù)冗余。因此需要選擇適合的瓦片規(guī)格以保證較快的顯示速度。

2 瓦片金字塔模型分層優(yōu)化

瓦片金字塔模型是將同一地區(qū)不同分辨率的圖像分層管理，從上到下分辨率由低到高，但所表示的地理范圍不變[13]。設(shè)第0層的分辨率為res0，則第l層的分辨率resl為[14]

resl=res0×f(l)

(1)

根據(jù)劃分的策略不同，選擇不同的。遙感圖像中最常使用的是指數(shù)變化，即指數(shù)變化較快，則可以很好的適應(yīng)大范圍圖像到小范圍圖像的變化。但是在室內(nèi)地圖中由于地圖的范圍較小，而指數(shù)變化的速度過快，常用的分層方法并不能滿足室內(nèi)地圖放大縮小的需求。如圖1所示，在使用傳統(tǒng)的指數(shù)變化的圖像時，第1、2層的分辨率變化還不是很顯著，但是隨著指數(shù)的變大，由于分辨率變化的過快，在第3層已經(jīng)不能反映原圖中的線條，而第4層的部分線段已經(jīng)由模糊點代替。

圖1 指數(shù)變化示意

為克服指數(shù)變化過快不能滿足室內(nèi)地圖放大和縮小的需求，考慮室內(nèi)地圖選擇變化較為均勻的，可能會取得更好的效果。因此，本文在室內(nèi)地圖中使用線性變化代替指數(shù)變化，即為查看最終效果，在圖1的第0層圖幅的基礎(chǔ)上，采用線性系數(shù)0.2，結(jié)果如下圖2所示?？梢悦黠@看出：第1、2、3層中的線條比較清晰，第4層中較細(xì)的線條部分出現(xiàn)模糊打斷的情況。對比圖1(c)和圖2(d)，第4層也遠比圖1中指數(shù)變化的第3層的線條清晰。

圖2 線性變化示意

3 瓦片金字塔模型規(guī)格選擇

由于嵌入式設(shè)備內(nèi)存的限制，整幅圖像放入內(nèi)存中會導(dǎo)致內(nèi)存溢出(out of memory，OOM)錯誤，對圖像進行分塊可以很好的解決這個問題。圖像分塊理論上沒有具體的限制，但是在實際應(yīng)用中需要考慮讀取時間和數(shù)據(jù)大小，如果涉及到網(wǎng)絡(luò)還要考慮數(shù)據(jù)傳輸?shù)膯栴}。

實驗使用1040*609的204 kB的PNG圖像，在1024*600的屏幕上進行顯示，瓦片的規(guī)格有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的模擬器上，內(nèi)存36 MB，SDCard 256 MB。

在現(xiàn)有的優(yōu)化模型基礎(chǔ)上，嘗試選取合適的瓦片規(guī)格。這里討論的瓦片規(guī)格選擇主要針對兩方面：分塊文件大小和讀取文件時間。

3.1 分塊文件大小

在劃分瓦片的過程中會出現(xiàn)空白瓦片，這類瓦片應(yīng)當(dāng)刪除，表1是瓦片劃分中分塊文件大小和空白瓦片大小，以及文件的刪除率。從表中可以看出，文件大小的變化主要是由兩方面的原因造成：一方面，文件的空白區(qū)域有一部分變?yōu)榭瞻淄咂粍h除，另一個方面，新建文件的頭文件也會占用一定的空間，在文件足夠多的時候，這些頭文件占用的空間，會抵消掉刪除空白瓦片的減少量。

表1 分塊文件大小、空值文件大小和文件刪除率

當(dāng)瓦片的規(guī)格較小時，文件的數(shù)量會很大，會使文件的總大小激增，如圖3所示，瓦片的大小應(yīng)該選擇72*72以上規(guī)格，會使得去空值文件和原始圖像大小基本相當(dāng)。因此選擇合適的瓦片規(guī)格能夠在很大程度上減少文件刪除率，讓用戶能夠得到更好的體驗，建議選取的瓦片規(guī)格不能太小。

圖3 瓦片文件大小變化圖

3.2 文件讀取時間

從時間大小上來看，顯示時間有兩個部分組成，一部分是讀取文件使用的時間，另一部分是顯示使用的時間，對每個規(guī)格的瓦片都進行10次同范圍的顯示，以下是統(tǒng)計的時間信息，包括瓦片讀取時間和瓦片顯示時間，如表2、表3所示。

表2 瓦片讀取時間

表3 瓦片顯示時間

將讀取時間和顯示時間相加，即可得到顯示總時間變化曲線圖，如圖4所示。從顯示總時間上來看，更加肯定了使用大于72*72規(guī)格瓦片更有利于快速顯示。從曲線走勢上可以看出，選擇合適的瓦片規(guī)格，能夠在很大程度上降低文件讀取時間。

圖4 瓦片顯示總時間關(guān)系圖

為進一步分析上述數(shù)據(jù)，下面從文件讀取消耗時間的大小和時間消耗的穩(wěn)定性兩方面綜合分析。比較表2與表3可以發(fā)現(xiàn)，顯示時間所占的份額較少，因此這里重點在讀取時間上進行篩選。選取96*96、108*108和128*128的瓦片讀取時間大小進行比較，如圖5所示。三條曲線的時間變化較為穩(wěn)定，從時間大小上來看選擇128*128規(guī)格的瓦片較好，讀取時間更短。

圖5 瓦片的讀取時間大小分析

從時間消耗穩(wěn)定性方面分析，截選規(guī)格大于128*128的瓦片，如圖6所示。128*128的瓦片穩(wěn)定性更好。從均值上來看，這三個瓦片規(guī)格讀取的時間現(xiàn)不多，512*512規(guī)格的占用的時間更少；但是從單個時間上來看，512*512與256*256規(guī)格的瓦片時間的變化較大，并不穩(wěn)定，這是由Android的垃圾處理機制造成的，從穩(wěn)定性能上來說，選擇128*128規(guī)格的瓦片較好。

圖6 瓦片讀取時間穩(wěn)定性分析

綜上所述，在選擇瓦片規(guī)格時，需要綜合考慮分塊文件大小以及文件讀取時間和穩(wěn)定性，反過來，選擇合適的瓦片規(guī)格會使得室內(nèi)地圖在Android平臺上加載時間更短更穩(wěn)定，且不會引起圖像的模糊打斷現(xiàn)象。

4 結(jié)論

為了快速讀取和顯示室內(nèi)地圖，本文對瓦片金字塔模型進行改進，選用線性分辨率變化函數(shù)取代指數(shù)變化函數(shù)，并從文件大小、讀取時間大小和穩(wěn)定性方面綜合分析瓦片的選取問題，通過實驗得出不同瓦片規(guī)格文件對讀取時間和時間穩(wěn)定性的影響，得到如下結(jié)論：

(1)對于室內(nèi)地圖，使用指數(shù)變換分辨率函數(shù)會使得原始圖像在放大、縮小過程中出現(xiàn)模糊斷點的現(xiàn)象，改用線性變化的分辨率可以得到更好的用戶體驗；

(2)合適的瓦片規(guī)格能夠在很大程度上降低文件刪除率，使得用戶能夠得到更好的體驗，瓦片規(guī)格不宜選取太小。

(3)選取合適的瓦片規(guī)格，能夠在很大程度上降低文件的讀取時間，提高讀取時間的穩(wěn)定性；

因此，在加載室內(nèi)地圖選取瓦片規(guī)格時，需要綜合考慮瓦片規(guī)格對文件刪除率的影響、圖像顯示時間以及顯示時間的穩(wěn)定性。在本文實驗條件下，使用128*128規(guī)格的瓦片可以使得用戶在加載室內(nèi)地圖時能夠更加清晰快速。

[1] 戴晨光，鄧雪清，張永生.海量地形數(shù)據(jù)實時可視化技術(shù)研究[J].測繪信息與工程，2004，29(6)：6-9.

[2] 杜瑩，武玉國，王曉明，等.全球多分辨率虛擬地形環(huán)境的金字塔模型研究[J].系統(tǒng)仿真學(xué)報，2006，18(4)：955-958+967.

[3] 鄧雪清.柵格型空間數(shù)據(jù)服務(wù)體系結(jié)構(gòu)與算法研究[D].鄭州：中國人民解放軍信息工程大學(xué)，2003.

[4] TIMPF S，F(xiàn)RANK A U.A Multi-scale Data Structure for Cartographic Objects[M].Wien：Technical University of Vienna，Department for Geoinformation，1995.

[5] 李德仁，肖志峰，朱欣焰，等.空間信息多級網(wǎng)格的劃分方法及編碼研究[J].測繪學(xué)報，2006，35(1)：52-56+70.

[6] 張永生，賁進，竟曉沖.地球空間信息球面離散網(wǎng)格：理論，算法及應(yīng)用[M].北京：科學(xué)出版社，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] 王浩，喻占武，曾武，等.基于瓦片壽命和訪問熱度的海量空間數(shù)據(jù)緩存置換策略[J].武漢大學(xué)學(xué)報：信息科學(xué)版，2009，34(6)：667-670.

[10] 李云錦，鐘耳順，王爾琪，等.馬爾可夫模型在空間數(shù)據(jù)預(yù)取中的應(yīng)用[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] 龔健雅.一種基于自然數(shù)的線性四叉樹編碼[J].測繪學(xué)報，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開發(fā)及應(yīng)用[M].北京：清華大學(xué)出版社.2009.