基于空間密度約束的GPS數據LOD模型構建方法

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

關鍵詞：動態可視化；GPS軌跡；LOD

中圖分類號：TP274 文獻標識碼：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）

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

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

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

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

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

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

3.1 空間劃分與編碼

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

經過編碼之后，空間每塊區域都對應唯一的一個編碼，且同一區域內的點要素具有相同的編碼。編碼具有這樣一個特性：字符串越短，代表空間范圍越大，且具有包含關系，比如編碼為ab的區域包含編碼為abc的區域。基于此特性，字符串編碼就代表著空間的金字塔結構，即LOD。基于空間劃分的LOD模型如圖2所示。

3.2 空間劃分閾值

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

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

4 實驗過程與結果分析（Experiment process result analysis）

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

4.1 實驗方法

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

4.2 實驗結果與分析

實驗統計不同比例尺下服務器響應時間、數據傳輸時間、可視化時間這三個指標，并繪制條形圖，即圖4、圖5、圖6。從圖4中可以看出，本文算法效率明顯高于基于Voronoi圖點LOD算法。實驗表明，基于Voronoi圖的點LOD算法會導致可視化頁面易出現無響應情形。

如圖5和圖6所示，對于數據傳輸時間和可視化時間這兩個指標，本文提出的點LOD算法比基于Voronoi圖的點LOD算法均占優。數據傳輸時間和可視化時間與點數正相關，說明區域一定的條件下，本文算法可以抽稀更多的點。

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

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

5 結論（Conclusion）

針對GPS軌跡數據動態可視化效率低下問題，本文將LOD技術引入可視化系統中。根據比例尺自適應地數據抽稀，保留數據原有空間分布特征的同時，提高了可視化效率。鑒于現有針對點狀要素LOD算法時間復雜度高，本文結合四叉樹的特點，提出了基于空間密度約束的LOD模型構建

算法。該算法與適用性高的基于Voronoi圖LOD算法相比，時間復雜度低，減少數據量的同時，縮短了服務器響應時間，從而提高了GPS軌跡數據動態可視化效率。

參考文獻（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] 賈奮勵，宋國民.電子地圖顯示中點狀要素LOD模型的建立[J].測繪學院學報，2002（01）：62-64.

[5] 李佳田，康順，羅富麗.利用層次Voronoi圖進行點群綜合[J].測繪學報，2014（12）：1300-1306.

[6] 毋河海.凸殼原理在點群目標綜合中的應用[J].測繪工程，1997（01）：1-6.

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

[8] 閆浩文，王家耀.基于Voronoi圖的點群目標普適綜合算法[J].中國圖象圖形學報，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] 李雯靜，李少寧，龍毅，等.利用重力模型進行GIS點群選取[J].武漢大學學報（信息科學版），2013，38（8）：945-949.

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

作者簡介：

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