基于空間密度約束的GPS數(shù)據(jù)LOD模型構(gòu)建方法

摘 要：為解決GPS軌跡數(shù)據(jù)動態(tài)可視化效率低下問題，本文通過引入LOD（Level Of Detail，LOD）技術(shù)從海量軌跡中提取能夠代表原始數(shù)據(jù)的空間特征點(diǎn)，保留原有空間分布特征，壓縮數(shù)據(jù)量。現(xiàn)有LOD模型構(gòu)建算法雖壓縮了數(shù)據(jù)量，但時間復(fù)雜度高，不能顯著提高可視化效率。本文提出了一種基于四叉樹的點(diǎn)LOD構(gòu)建算法。實(shí)驗(yàn)表明：本文提出的點(diǎn)LOD算法與基于Voronoi圖的點(diǎn)LOD算法相比，具有時間復(fù)雜度低，LOD構(gòu)建速度快，無符號壓蓋等優(yōu)點(diǎn)。

關(guān)鍵詞：動態(tài)可視化；GPS軌跡；LOD

中圖分類號：TP274 文獻(xiàn)標(biāo)識碼：A

Abstract：To address the challenge to visualization of GPS trajectory data，this paper integrates Level Of Detail（LOD）technology into GPS data visualization in order to improve visualization efficiency while maintaining visualization quality.Although the existing LOD algorithms compress the quantity of GPS Data，it cannot significantly improve the visualization efficiency because of high time complexity.This paper proposes a quadtree-based point LOD algorithm.Experiments shows that the quadtree-based point LOD algorithm has lower time complexity，higher performance and better visualization quality than the widely used Voronoi-based LOD algorithm.

Keywords：online visualization；GPS trajectory；LOD

1 引言（Introduction）

隨著空間定位技術(shù)的成熟發(fā)展，可用于記錄位置信息的設(shè)備越來越普及，手機(jī)、平板等移動終端及汽車大都內(nèi)嵌了GPS芯片或安裝了GPS接收機(jī)，這些設(shè)備每天產(chǎn)生大量的GPS軌跡數(shù)據(jù)[1]。GPS軌跡數(shù)據(jù)富含運(yùn)動主體的群體分布特征，其動態(tài)可視化有助于用戶快速直觀地理解分析這些特征[2，3]。以出租車為例，出租車GPS數(shù)據(jù)動態(tài)可視化，可直觀反映出租車群體的空間分布變化情況。GPS軌跡數(shù)據(jù)作為一種高動態(tài)性的時空序列數(shù)據(jù)，與傳統(tǒng)靜態(tài)空間數(shù)據(jù)相比，具有海量、更新速度快、時空密集度高等特點(diǎn)。因此，如何高效、準(zhǔn)確地可視化GPS軌跡數(shù)據(jù)，使用戶能夠快速直觀地獲取GPS軌跡蘊(yùn)含的信息，是GPS數(shù)據(jù)可視化研究中亟待解決的問題。

2 常見LOD算法綜述（Summary of common LOD algorithm）

為解決GPS軌跡數(shù)據(jù)動態(tài)可視化效率低下問題，本文通過引入LOD技術(shù)從海量軌跡中提取能夠代表原始數(shù)據(jù)的空間特征點(diǎn)，縮短數(shù)據(jù)傳輸時間，以提高可視化效率。目前，國內(nèi)外針對LOD技術(shù)在電子地圖顯示中的研究取得了一些顯著成果。對于點(diǎn)狀要素LOD可視化研究，文獻(xiàn)[4]重點(diǎn)研究了電子地圖顯示中點(diǎn)狀要素LOD模型的建立，提出了一種基于Voronoi圖和Delaunay三角網(wǎng)綜合相關(guān)因素影響建立點(diǎn)狀要素LOD模型的算法，實(shí)現(xiàn)了不同比例尺下都能得到盡量合理的地圖外觀。文獻(xiàn)[5]結(jié)合聚類方法，在Voronoi圖的基礎(chǔ)上提取聚類中心點(diǎn)，同時利用層次Voronoi圖結(jié)構(gòu)逐步細(xì)化地表達(dá)聚類中心點(diǎn)，進(jìn)而實(shí)現(xiàn)點(diǎn)群由繁到簡的綜合。文獻(xiàn)[6]針對聚集分布的點(diǎn)群，借助凸殼算法形成多層嵌套，以反映點(diǎn)群的逐層分布特征。

無論是Voronoi圖法還是凸殼法，都存在這樣一個問題：算法時間復(fù)雜度高。這對于大數(shù)據(jù)可視化來說，雖進(jìn)行了數(shù)據(jù)抽稀，縮短了前端可視化時間，但由于服務(wù)器端計(jì)算量大、耗時久，導(dǎo)致操作延時長、用戶體驗(yàn)差等問題。因此，針對大數(shù)據(jù)量的點(diǎn)群可視化需要一種更為快速的LOD模型構(gòu)建算法。

3 基于空間密度約束的LOD模型構(gòu)建方法（A LOD construction method for GPS trajectory data with constraints in spatial density）

基于空間密度約束的點(diǎn)狀要素LOD模型構(gòu)建算法借鑒了四叉樹的思想，邏輯上分為兩步，即空間劃分與編碼。空間劃分是將空間區(qū)域分別沿經(jīng)度方向和緯度方向遞歸中分，終止條件與比例尺有關(guān)。編碼是把劃分后的格網(wǎng)都賦予一個唯一的編碼。

3.1 空間劃分與編碼

空間劃分是對可視化區(qū)域的范圍沿經(jīng)緯度方向不斷地交替進(jìn)行二分，每四次二分作為一個層次，即兩次四叉劃分作為一個層次。用0和1表示每次二分產(chǎn)生的區(qū)域，即當(dāng)沿緯度方向進(jìn)行二分時，上面區(qū)域的編碼為1，下面區(qū)域的編碼為0；當(dāng)沿經(jīng)度方向進(jìn)行二分時，右側(cè)區(qū)域的編碼為1，左側(cè)區(qū)域的編碼為0；進(jìn)而，每四次二分的二進(jìn)制編碼轉(zhuǎn)換為16進(jìn)制編碼，即為某一層網(wǎng)格的編碼，如圖1所示。16進(jìn)制編碼由數(shù)字0—9和英文小寫字母a—f組成。

經(jīng)過編碼之后，空間每塊區(qū)域都對應(yīng)唯一的一個編碼，且同一區(qū)域內(nèi)的點(diǎn)要素具有相同的編碼。編碼具有這樣一個特性：字符串越短，代表空間范圍越大，且具有包含關(guān)系，比如編碼為ab的區(qū)域包含編碼為abc的區(qū)域。基于此特性，字符串編碼就代表著空間的金字塔結(jié)構(gòu)，即LOD。基于空間劃分的LOD模型如圖2所示。

3.2 空間劃分閾值

本文提出的點(diǎn)LOD模型構(gòu)建算法是一個遞歸劃分的過程，遞歸劃分并不是無限進(jìn)行，當(dāng)格網(wǎng)被劃分到一定大小就應(yīng)該終止劃分。本文提出的點(diǎn)狀要素LOD的構(gòu)建基本思想是在當(dāng)前比例尺下，一個可視化符號所覆蓋的區(qū)域內(nèi)的點(diǎn)群要素只顯示一個，因此空間劃分的終止條件與可視化符號大小和比例尺有關(guān)。設(shè)可視化符號寬度為d，當(dāng)前比例尺為1：x，則屏幕長度對應(yīng)地圖上的實(shí)際距離是z，且1：x=d：z。z即為格網(wǎng)劃分的閾值。因此，空間劃分的終止條件為格網(wǎng)寬度小于等于z。閾值z與比例尺的關(guān)系公式如下：

紙質(zhì)地圖上人眼能夠分辨兩點(diǎn)之間的距離最小為0.1mm[7]，因此可視化符號最小不應(yīng)該小于0.1mm，即d>=0.1mm，且根據(jù)點(diǎn)形狀的不同，此值還應(yīng)適當(dāng)增大。當(dāng)已知可視化符號d，則空間劃分的終止閾值就可由公式（1）得出。

4 實(shí)驗(yàn)過程與結(jié)果分析（Experiment process result analysis）

目前點(diǎn)要素化簡的算法有凸殼化簡法、相關(guān)系數(shù)控制法、重力模型法和Voronoi圖法，且大都只適用于居民地綜合[8-12]。僅基于Voronoi圖的簡化算法應(yīng)用范圍較為廣泛，除了針對居民地，還可以針對其他呈點(diǎn)狀分布的地物要素[8]。因此，本文以適用性最高的Voronoi圖法作為對比對象，比較兩種算法的抽稀效率和可視化效果。

4.1 實(shí)驗(yàn)方法

本文設(shè)計(jì)了一個基于B/S架構(gòu)GPS數(shù)據(jù)可視化系統(tǒng)，系統(tǒng)架構(gòu)如圖3所示。實(shí)驗(yàn)以武漢市出租車GPS數(shù)據(jù)為可視化對象，數(shù)據(jù)量大小約200MB。從服務(wù)器響應(yīng)時間、數(shù)據(jù)傳輸時間、可視化時間和可視化效果這四個指標(biāo)進(jìn)行評價，其中可視化效果指數(shù)據(jù)抽稀之后仍能反映點(diǎn)狀要素空間分布特征，且可視化符號無壓蓋。實(shí)驗(yàn)環(huán)境見表1。基于空間密度約束的點(diǎn)LOD算法空間劃分閾值等于可視化符號的寬度，為4mm。

4.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)統(tǒng)計(jì)不同比例尺下服務(wù)器響應(yīng)時間、數(shù)據(jù)傳輸時間、可視化時間這三個指標(biāo)，并繪制條形圖，即圖4、圖5、圖6。從圖4中可以看出，本文算法效率明顯高于基于Voronoi圖點(diǎn)LOD算法。實(shí)驗(yàn)表明，基于Voronoi圖的點(diǎn)LOD算法會導(dǎo)致可視化頁面易出現(xiàn)無響應(yīng)情形。

如圖5和圖6所示，對于數(shù)據(jù)傳輸時間和可視化時間這兩個指標(biāo)，本文提出的點(diǎn)LOD算法比基于Voronoi圖的點(diǎn)LOD算法均占優(yōu)。數(shù)據(jù)傳輸時間和可視化時間與點(diǎn)數(shù)正相關(guān)，說明區(qū)域一定的條件下，本文算法可以抽稀更多的點(diǎn)。

對于可視化效果這一指標(biāo)并無量化數(shù)據(jù)，對比分析圖7、圖8、圖9可以發(fā)現(xiàn)兩種構(gòu)建LOD的算法均可以減緩符號壓蓋現(xiàn)象，同時保持點(diǎn)群空間分布特征。但基于Voronoi圖的點(diǎn)LOD算法本身的原因，在點(diǎn)群稀疏的地方也會進(jìn)行抽稀，這不滿足GPS數(shù)據(jù)動態(tài)可視化需求。

綜上所述，本文提出的基于空間密度約束的點(diǎn)LOD模型構(gòu)建算法顧及點(diǎn)狀要素空間分布特征的同時，大大減小了算法時間復(fù)雜度，進(jìn)而提高了可視化效率，比基于Voronoi圖的點(diǎn)LOD算法更優(yōu)。

5 結(jié)論（Conclusion）

針對GPS軌跡數(shù)據(jù)動態(tài)可視化效率低下問題，本文將LOD技術(shù)引入可視化系統(tǒng)中。根據(jù)比例尺自適應(yīng)地?cái)?shù)據(jù)抽稀，保留數(shù)據(jù)原有空間分布特征的同時，提高了可視化效率。鑒于現(xiàn)有針對點(diǎn)狀要素LOD算法時間復(fù)雜度高，本文結(jié)合四叉樹的特點(diǎn)，提出了基于空間密度約束的LOD模型構(gòu)建

算法。該算法與適用性高的基于Voronoi圖LOD算法相比，時間復(fù)雜度低，減少數(shù)據(jù)量的同時，縮短了服務(wù)器響應(yīng)時間，從而提高了GPS軌跡數(shù)據(jù)動態(tài)可視化效率。

參考文獻(xiàn)（References）

[1] Mao Y，Zhong H，Qi H，et al.An Adaptive Trajectory Clustering Method Based on Grid and Density in Mobile Pattern Analysis[J].Sensors，2017，17（9）：2013.

[2] Cai L，Zhou Y，Liang Y，et al.Research and Application of GPS Trajectory Data Visualization[J].Annals of Data Science，2017（4）：1-15.

[3] Liu Y，Kang C，Gao S，et al.Understanding intra-urban trip patterns from taxi trajectory data[J].Journal of Geographical Systems，2012，14（4）：463-483.

[4] 賈奮勵，宋國民.電子地圖顯示中點(diǎn)狀要素LOD模型的建立[J].測繪學(xué)院學(xué)報(bào)，2002（01）：62-64.

[5] 李佳田，康順，羅富麗.利用層次Voronoi圖進(jìn)行點(diǎn)群綜合[J].測繪學(xué)報(bào)，2014（12）：1300-1306.

[6] 毋河海.凸殼原理在點(diǎn)群目標(biāo)綜合中的應(yīng)用[J].測繪工程，1997（01）：1-6.

[7] Hans-Uli Feldmann.Cartographic Generalisation-Topographic Maps[M].Swiss：Swiss Society of Cartography，2005.

[8] 閆浩文，王家耀.基于Voronoi圖的點(diǎn)群目標(biāo)普適綜合算法[J].中國圖象圖形學(xué)報(bào)，2005（05）：633-636.

[9] Kreveld M J V，Oostrum R W V，Snoeyink J.Efficient Settlement Selection for Interactive Display[J].In Proc.Auto-Carto 13：ACSM/ASPRS Annual Convention Technical Papers， 1997：287-296.

[10] Sadahiro Y.Cluster Perception in the Distribution of Point Objects[J].Cartographica the International Journal for Geographic Information & Geovisualization，1997（03）：49-62.

[11] 李雯靜，李少寧，龍毅，等.利用重力模型進(jìn)行GIS點(diǎn)群選取[J].武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2013，38（8）：945-949.

[12] 艾廷華，劉耀林.保持空間分布特征的群點(diǎn)化簡方法[J].測繪學(xué)報(bào)，2002，31（2）：175-181.

作者簡介：

孫澤昌（1990-），男，碩士，助理工程師.研究領(lǐng)域：GIS與鐵路選線.