摘 要： 為提高嵌入式GIS 環(huán)境下矢量地圖的顯示速度， 設(shè)計(jì)了一種適用于嵌入式環(huán)境基于LOD 的地圖數(shù)據(jù)組織模型。 針對(duì)嵌入式設(shè)備硬件條件限制， 從減少非顯示區(qū)域的冗余地圖數(shù)據(jù)的讀取和提高外存檢索矢量數(shù)據(jù)的效率兩方面入手， 對(duì)矢量地圖數(shù)據(jù)進(jìn)行了分層、分塊和建立索引等處理。 通過實(shí)驗(yàn)表明， 該方法能很好地提高矢量地圖的顯示速度， 可以滿足嵌入式環(huán)境下地圖快速顯示的要求。

　　1 引言

　　地理信息系統(tǒng)（Geographic InformaTION System, 簡稱GIS）產(chǎn)品被廣泛應(yīng)用于交通、測繪、環(huán)境、國防、航空航天等與國民經(jīng)濟(jì)乃至國家命脈相關(guān)的重要領(lǐng)域，帶來了顯著的經(jīng)濟(jì)和社會(huì)效益。近年來隨著嵌入式技術(shù)的迅猛發(fā)展， GIS 技術(shù)也逐步應(yīng)用于以手機(jī)、掌上電腦為代表的移動(dòng)終端， 使得嵌入式GIS 成為當(dāng)今GIS 研究領(lǐng)域的一個(gè)重要趨勢。 當(dāng)前地圖數(shù)據(jù)量巨大，要求地圖刷新頻率高、實(shí)時(shí)性強(qiáng)， 普通桌面系統(tǒng)的地圖顯示方法很難適用于存儲(chǔ)器容量小、處理器性能低的嵌入式系統(tǒng)， 提高地圖的顯示效率成為嵌入式GIS產(chǎn)品研發(fā)的首要問題。 矢量地圖擁有數(shù)據(jù)結(jié)構(gòu)緊湊，冗余度低； 圖形顯示質(zhì)量好， 精度高， 不失真等優(yōu)點(diǎn)，目前已被廣泛應(yīng)用與嵌入式移動(dòng)終端。 本文針對(duì)矢量電子地圖研究了地圖顯示數(shù)學(xué)模型， 設(shè)計(jì)了基于LOD的逐層分塊的地圖數(shù)據(jù)組織結(jié)構(gòu)， 并以此為基礎(chǔ)建立網(wǎng)格索引， 通過實(shí)驗(yàn)證明該方法可有效提高地圖顯示速度。

　　2 矢量地圖顯示數(shù)學(xué)模型

　　地圖的數(shù)據(jù)組織結(jié)構(gòu)是影響地圖顯示速度的核心因素。 因此， 要對(duì)矢量地圖顯示數(shù)學(xué)模型分析研究，合理組織地圖數(shù)據(jù)， 才能有效提高地圖顯示速度。

　　由于電子地圖的數(shù)據(jù)量較大， 嵌入式設(shè)備的地圖數(shù)據(jù)一般會(huì)存放在外存儲(chǔ)器中， 系統(tǒng)顯示地圖時(shí)需要先將地圖數(shù)據(jù)讀入內(nèi)存， 再由地圖繪制程序解析內(nèi)存中的數(shù)據(jù)， 將地圖顯示在屏幕上。 假設(shè)某矢量地圖數(shù)據(jù)占用物理存儲(chǔ)空間為D, 數(shù)據(jù)讀入內(nèi)存速度為V1,顯示速度為V2, 數(shù)據(jù)讀取準(zhǔn)備時(shí)間為f （n） , 用戶可等待時(shí)間為T, 嵌入式設(shè)備內(nèi)存容量為R, 則有以下公式成立：

　　嵌入式設(shè)備內(nèi)存容量一定， 若V1, V2, T 為常數(shù)，則必須減少D 和f （n）才能滿足數(shù)據(jù)顯示和處理的要求，提高地圖的顯示速度。

　　通過對(duì)地圖顯示數(shù)學(xué)模型的分析可以發(fā)現(xiàn)， 要使地圖的顯示速度達(dá)到最快， 需要解決兩個(gè)問題： 一是盡量減少地圖非屏幕顯示區(qū)域的數(shù)據(jù)量， 即根據(jù)顯示范圍限制讀入的數(shù)據(jù)量； 二是要能以最快的速度從龐大的地圖數(shù)據(jù)中找到當(dāng)前顯示范圍所涉及的相關(guān)數(shù)據(jù)。

　　針對(duì)問題一， 本文采用逐層分塊策略組織地圖數(shù)據(jù)， 減少非屏幕區(qū)域的數(shù)據(jù)讀入； 對(duì)于問題二， 則對(duì)圖塊建立索引， 以降低外存調(diào)度當(dāng)前顯示數(shù)據(jù)的時(shí)間。

　　3 矢量地圖快速顯示策略

　　3.1 數(shù)據(jù)組織模型設(shè)計(jì)

　　作者引入多細(xì)節(jié)層次LOD（Levels of Detail）技術(shù)思想，該技術(shù)最初是一種運(yùn)用于控制三維場景復(fù)雜程度的技術(shù)， 其基本思想是： 在建立地表模型時(shí)， 應(yīng)充分考慮人的視覺特點(diǎn)， 對(duì)處于視覺不同區(qū)域的模型采用不同的分辨率表示， 這樣整個(gè)地表模型就表現(xiàn)為以"塊"為單位的具有多分辨率的細(xì)節(jié)層次模型， 當(dāng)從近處觀察物體時(shí)， 采用精細(xì)模型， 當(dāng)從遠(yuǎn)處觀察物體時(shí)采用較為粗糙的模型[5]. 這一思想不僅限用于三維場景， 對(duì)于矢量地圖的快速顯示同樣適用。

　　系統(tǒng)對(duì)每個(gè)地圖分別制作多個(gè)比例尺的地圖數(shù)據(jù)，同時(shí)參考地圖地理要素的規(guī)范， 根據(jù)要素的重要程度將不同比例尺地圖中的圖層劃分為不同的顯示層次，這樣電子地圖在縮放顯示過程中， 可根據(jù)當(dāng)前顯示比例尺， 確定需要顯示的地理要素。 同時(shí)考慮到嵌入式設(shè)備顯示屏幕較小， 顯示覆蓋范圍相對(duì)有限， 需根據(jù)顯示屏幕尺寸對(duì)矢量地圖數(shù)據(jù)進(jìn)行分塊處理， 以減少地圖顯示時(shí)讀入內(nèi)存的冗余數(shù)據(jù)。 通過上述對(duì)矢量地圖的分層分塊組織， 便形成了基于LOD 的逐層分塊地圖數(shù)據(jù)組織模型， 如圖1所示。

　　地圖顯示時(shí)， 在不同顯示層次上需要讀入相應(yīng)的數(shù)據(jù)集合， 并實(shí)現(xiàn)根據(jù)設(shè)備顯示范圍讀入相應(yīng)圖塊數(shù)據(jù)， 從而大大減少地圖數(shù)據(jù)讀取和顯示數(shù)據(jù)量， 提高了地圖顯示的效率。

圖1 基于LOD 的逐層分塊地圖數(shù)據(jù)組織模型

　　3.2 矢量地圖數(shù)據(jù)分層處理

　　在地圖的顯示過程中， 地圖縮小時(shí)屏幕覆蓋地圖的范圍增大， 只需顯示主要地理要素對(duì)象， 相對(duì)次要的地理要素可隱藏而不顯示； 地圖放大顯示時(shí)屏幕覆蓋范圍減小， 在當(dāng)前已顯示的地理要素基礎(chǔ)上， 相對(duì)次要的地理要素也需顯示出來。 基于這一特性， 可將地圖數(shù)據(jù)所描述的地理要素依據(jù)其重要性特征分為多個(gè)數(shù)據(jù)層次， 即對(duì)所需顯示的地圖按照?qǐng)D層的重要程度設(shè)置一個(gè)顯示參數(shù)， 該參數(shù)代表地圖放大到什么程度時(shí)， 才顯示該圖層。 劃分的地圖數(shù)據(jù)層次依次記為L1, L2, L3, …， 其中L1 記錄地圖中最主要的地理要素，L2記錄次重要的地理要素， L3記錄一般性地理要素， 依此類推。

　　實(shí)際操作時(shí)， 對(duì)地圖數(shù)據(jù)分層處理顯示參數(shù)的確定非常重要， 其選擇的優(yōu)劣直接影響地圖顯示效率。

　　本文依據(jù)地理要素的屬性， 按照以下原則確定顯示參數(shù)將：

　?、?對(duì)于基礎(chǔ)地理要素， 如道路、橋梁、河流、行政區(qū)邊界等， 在國家標(biāo)準(zhǔn)《基礎(chǔ)地理信息要素分類與代碼》中采用要素編碼區(qū)分了其重要性特征， 可以參考其要素編碼設(shè)定顯示參數(shù)；② 對(duì)于非基礎(chǔ)地理要素， 如學(xué)校、酒店、商業(yè)街區(qū)、街區(qū)居民地等， 其重要性特征沒有統(tǒng)一的標(biāo)準(zhǔn)， 則根據(jù)這類地理要素自身包含的等級(jí)屬性， 如酒店星級(jí)、街區(qū)面積等來確定顯示參數(shù)。

　　以某城市公路網(wǎng)為例， 采用道路要素編碼為顯示參數(shù)進(jìn)行分層處理， 可分為4 個(gè)層次： L1 記錄城市一級(jí)、二級(jí)道路： 高速公路及環(huán)線； L2 記錄城市三級(jí)道路： 市內(nèi)主干道， L3 記錄四級(jí)道路： 市內(nèi)次干道， L4 記錄城市五級(jí)道路： 市區(qū)分支街道。 地圖顯示時(shí)， 不同層次細(xì)節(jié)顯示需要在上一層次顯示的基礎(chǔ)上讀入相應(yīng)Li 的數(shù)據(jù)集合來支持， 如圖2 給出某城市公路網(wǎng)L1~L4 的顯示效果。

圖2 某城市公路網(wǎng)不同層次顯示效果圖

3.3 矢量地圖數(shù)據(jù)分塊方法

　　要提高地圖的顯示速度， 應(yīng)盡量減少地圖非屏幕顯示區(qū)域的數(shù)據(jù)量， 因此需對(duì)矢量地圖進(jìn)行分割形成地理范圍更小的圖塊， 并將圖塊作為嵌入式GIS 系統(tǒng)地圖數(shù)據(jù)處理的基本單元。[!--empirenews.page--]

　　對(duì)于矢量數(shù)據(jù)的分塊方法分別是對(duì)點(diǎn)、線、面的矩形分割， 即將地圖數(shù)據(jù)根據(jù)屏幕顯示范圍大小橫向分為N 份， 縱向分為M 份， 形成由N×M 個(gè)同等大小的基本地理單元組成的圖塊集合。 地圖顯示時(shí)， 系統(tǒng)只需根據(jù)顯示層次讀入與顯示覆蓋區(qū)域相交的部分圖塊， 快速將地圖繪制在屏幕上。

　　在對(duì)地圖數(shù)據(jù)進(jìn)行分塊處理時(shí)， 需要重點(diǎn)考慮分割圖塊的大小。 因?yàn)橐欢ㄊ噶繑?shù)據(jù)劃分的圖塊較大， 則讀入內(nèi)存的非屏幕顯示區(qū)域的數(shù)據(jù)就會(huì)越多， 增加了不必要的冗余數(shù)據(jù)； 而數(shù)據(jù)劃分的圖塊越小， 讀取數(shù)據(jù)的準(zhǔn)備時(shí)間就越長， 且對(duì)矢量數(shù)據(jù)的分割還會(huì)增加顯示的數(shù)據(jù)量， 也會(huì)影響顯示速度。 因此在數(shù)據(jù)分塊時(shí)要根據(jù)實(shí)際屏幕顯示尺寸和地圖比例尺綜合考慮分塊大小。

　　若已知屏幕分辨率為L×W 像素， 地圖的比例尺為1:S, 地圖經(jīng)度覆蓋范圍X, 緯度覆蓋范圍Y, 地圖表示精度記為A, 地球圓周單位秒代表距離為m （m 為常量， m ≈31 米）， 記地圖橫向劃分圖塊數(shù)量為N, 縱向劃分圖塊數(shù)量為M, 則有以下公式：

　　其中， X, Y 單位為秒， A=0.1×10^-3×S.

　　以比例尺為1:50 000, 經(jīng)度范圍25‘, 緯度范圍15‘

　　的矢量地圖和800×480 的屏幕為例， 可由式（2）推導(dǎo)得該地圖應(yīng)劃分為12×12 塊圖塊。

　　3.4 矢量地圖網(wǎng)格索引

　　如前文所述， 提高地圖顯示速度還必須使地圖顯示時(shí)能快速的從外存檢索和調(diào)度當(dāng)前顯示范圍所涉及的矢量數(shù)據(jù)， 因此還需建立空間索引。針對(duì)逐層分塊的地圖組織策略， 建立了基于文件存儲(chǔ)的網(wǎng)格索引。

　　基于文件的網(wǎng)格索引以索引文件存儲(chǔ)索引數(shù)據(jù)， 通過名為POSITION 的位置指針可以對(duì)每個(gè)空間目標(biāo)的首地址進(jìn)行快速定位， 具有操作簡潔、直接訪問、適應(yīng)廣泛的優(yōu)點(diǎn)， 其索引結(jié)構(gòu)如圖3 所示。

圖3 基于文件的網(wǎng)格索引結(jié)構(gòu)圖

　　索引數(shù)據(jù)按地圖層次存儲(chǔ)， 每層索引數(shù)據(jù)與相應(yīng)的地圖分層數(shù)據(jù)對(duì)應(yīng)。 索引數(shù)據(jù)結(jié)構(gòu)包括索引頭、層次描述信息和每層劃分圖塊索引： 索引頭主要包括該地圖數(shù)據(jù)的名稱、編號(hào)和劃分層數(shù)； 層次描述信息包括各層次的編號(hào)、左下角點(diǎn)坐標(biāo)、分塊的寬度和高度、分塊的行數(shù)和列數(shù)以及該層圖塊索引在索引文件中的位置； 圖塊索引內(nèi)容主要包括圖塊數(shù)據(jù)在地圖數(shù)據(jù)文件中的位置指針及其地理要素概要信息， 包括標(biāo)識(shí)、要素類型編碼、外接矩形、占用存儲(chǔ)空間大小等。

　　建立網(wǎng)格索引后， 地圖顯示時(shí)系統(tǒng)首先計(jì)算出當(dāng)前層次覆蓋顯示區(qū)域的圖塊； 然后根據(jù)每個(gè)圖塊的地理要素信息進(jìn)行重復(fù)顯示判斷， 過濾掉已經(jīng)顯示的地理要素； 再根據(jù)位置指針， 從地圖文件中讀取該圖塊的矢量數(shù)據(jù)， 進(jìn)行顯示處理。 因此網(wǎng)格索引能直接過濾掉非屏幕顯示區(qū)域圖塊及地理要素， 極大地減少地圖數(shù)據(jù)的讀取量， 并通過索引文件中的POSITION 指針直接從地圖文件中查找到矢量數(shù)據(jù)， 有效縮短了檢索時(shí)間。

　　4 性能測試與分析

　　為驗(yàn)證本文設(shè)計(jì)的嵌入式GIS 地圖快速顯示方法的有效性， 本文選擇UT6410 開發(fā)板搭建嵌入式試驗(yàn)平臺(tái)進(jìn)行了測試。 實(shí)驗(yàn)平臺(tái)擁有主頻667MHz 的ARM處理器、128MB 內(nèi)存、8GB SD 卡存儲(chǔ)器和分辨率800×480 的顯示屏幕， 并搭載嵌入式Linux 系統(tǒng)； 測試地圖是比例尺分別為1:50 000 和1:250 000 同一地區(qū)的全要素矢量地圖。 實(shí)驗(yàn)將采用本文方法及未采用本文方法時(shí)直接全圖讀入內(nèi)存顯示方法的地圖顯示性能進(jìn)行了對(duì)比測試， 實(shí)驗(yàn)結(jié)果參見表1.

表1 采用逐層分塊法與全圖讀入法地圖顯示性能對(duì)比

　　由實(shí)驗(yàn)結(jié)果可以看出， 在矢量地圖數(shù)據(jù)相同的條件下， 采用逐層分塊并建立網(wǎng)格索引方法比未采用此方法時(shí)的地圖顯示速度提高了6~8 倍， 并達(dá)到了平滑漫游和縮放的顯示要求。

　　5 結(jié)語

　　為使矢量地圖能夠在嵌入式GIS 平臺(tái)上實(shí)現(xiàn)快速顯示， 本文基于對(duì)矢量地圖顯示數(shù)學(xué)模型的分析， 從減少地圖非屏幕顯示區(qū)域的數(shù)據(jù)量和快速檢索并調(diào)度當(dāng)前顯示數(shù)據(jù)兩方面入手， 引入LOD 思想構(gòu)建了逐層分塊地圖數(shù)據(jù)組織模型， 結(jié)合嵌入式矢量地圖數(shù)據(jù)訪問特點(diǎn)重點(diǎn)研究了地圖分層、分塊的策略及實(shí)施， 并在此基礎(chǔ)上建立了文件存儲(chǔ)的網(wǎng)格索引。 定性分析和實(shí)驗(yàn)結(jié)果表明， 本文提供的方法能夠很好地滿足嵌入式環(huán)境下地圖快速顯示的要求， 有效提高地圖操作效率。