保持移動速度特征的軌跡線化簡方法

楊 敏，陳媛媛，金 澄，程 前

1. 武漢大學資源與環(huán)境科學學院，湖北 武漢 430072； 2. 北京大學遙感與地理信息系統(tǒng)研究所，北京 100871； 3. 國土資源部城市土地資源監(jiān)測與仿真重點實驗室，廣東 深圳 518034； 4. 地理國情監(jiān)測國家測繪地理信息局重點實驗室，湖北 武漢 430072； 5. 西安測繪研究所，陜西 西安 710054

保持移動速度特征的軌跡線化簡方法

楊 敏1，3，4，陳媛媛1，2，金 澄5，程 前1

1. 武漢大學資源與環(huán)境科學學院，湖北 武漢 430072； 2. 北京大學遙感與地理信息系統(tǒng)研究所，北京 100871； 3. 國土資源部城市土地資源監(jiān)測與仿真重點實驗室，廣東 深圳 518034； 4. 地理國情監(jiān)測國家測繪地理信息局重點實驗室，湖北 武漢 430072； 5. 西安測繪研究所，陜西 西安 710054

軌跡線數(shù)據(jù)實施化簡處理對于緩解數(shù)據(jù)存儲、傳輸壓力以及后期的分析可視化效率具有重要意義。常規(guī)方法(如Douglas-Peucker算法)主要考慮線目標的幾何形態(tài)結構，直接應用到軌跡線化簡中容易丟失移動物體的運動狀態(tài)特征。本研究從保持軌跡線隱含速度特征出發(fā)，提出了一種基于移動速度相似性原則的軌跡線層次化剖分與分區(qū)化簡處理方法。首先，以相鄰軌跡點構成的直線段為基本單元，在拓撲連接關系約束下基于速度指標對軌跡直線段進行層次化聚類，并將聚類結果組織為層次樹結構；然后，以建立的層次樹結構為約束條件對原始軌跡線實施分區(qū)處理，使得同一區(qū)域內(nèi)軌跡線片段的中間點距首尾基準線的最大時間同步偏移距離小于設定的閾值；最后，依次連接各分區(qū)軌跡線片段首尾點導出化簡結果。采用真實的車輛軌跡線作為試驗數(shù)據(jù)，通過與其他多種方法進行對比分析驗證了本文提出方法的有效性。

軌跡線數(shù)據(jù)；化簡；聚類分析；速度保持

軌跡線通常由一系列按時間序列組織的位置坐標點組成，用以描述物體或地理現(xiàn)象的時空移動軌跡。隨著位置感知設備的普及，各種類型的軌跡監(jiān)測數(shù)據(jù)成為當前眾源大數(shù)據(jù)的重要組成部分[1]，它們對于城市群體個體行為模式分析[1-2]、交通信息實時監(jiān)測表達[3]、地理數(shù)據(jù)庫更新[4]等具有重要意義。然而，具備空間/時間高分辨率特點的軌跡數(shù)據(jù)通常規(guī)模巨大。例如車載GPS設備若每10 s記錄一次，一個中等規(guī)模城市的出租車單個工作日產(chǎn)生的數(shù)據(jù)量將達到GB級別。一方面，這對存儲設備空間、網(wǎng)絡傳輸帶寬以及后期分析的計算資源造成巨大壓力[5]；另一方面，軌跡數(shù)據(jù)本身包含大量冗余信息，浪費存儲計算資源的同時也對分析處理及可視化表達造成負面干擾。解決上述問題的途徑之一是研究高效的軌跡數(shù)據(jù)化簡方法，即在滿足一定幾何精度條件下簡化數(shù)據(jù)構成，壓縮數(shù)據(jù)規(guī)模。

空間數(shù)據(jù)的綜合化簡在地圖制圖以及計算機視覺領域受到廣泛關注。具體到線狀目標的化簡問題，國內(nèi)外相關學者提出了一系列的算法模型[6-11]。這些方法主要面向快照式靜態(tài)地理數(shù)據(jù)(如描述某一時刻道路、河流、境界等地理實體的線狀目標)，依據(jù)幾何特征上的距離、角度、面積以及這些參量背后的地理意義來分析并保留重要的特征點，包括端點、極值點(局部極大極小點)、拐點等。它們雖然能夠較好地保持原始線狀目標的空間形態(tài)結構，但是缺乏對時間維信息的考慮，直接應用到時空軌跡線化簡中容易丟失速度、加速度等移動變化特征。以應用最為廣泛的Douglas-Peucker算法為例[9](如圖1所示)，通過中間點相對當前基準線(首尾點連線)的偏移距離對原始軌跡線進行遞歸分段。某一軌跡點距基準線的偏移距離定義為該點到基準線的最短歐氏距離。當某一段軌跡線片段對應的最大偏移距離小于設定的幾何誤差ε，則該軌跡線片段化簡擬合為對應的基準線。該過程中部分偏移距離較小但是對物體運動模式變化描述具有重要意義的軌跡點(如p3，p7，p8)將被舍棄。

圖1 Douglas-Peucker算法Fig.1 The principle Douglas-Peucker algorithm

圖2 時間同步歐氏偏移距離定義Fig.2 The definition of synchronized euclidean distance

在上述研究成果的基礎上，本研究提出一種保持移動速度特征的軌跡線化簡方法。速度特征是反映移動物體運動狀態(tài)的重要指標，化簡過程盡量保持原有軌跡線隱含的速度變化信息對于后期移動模式的分析、挖掘和預測有積極的作用。例如車輛交通事故領域，車輛軌跡線速度變化上的關鍵軌跡點是事故分析及理賠的重要依據(jù)。本文方法采用的基本思想是基于移動速度相似性原則對原始軌跡線進行層次化剖分，然后將剖分關系作為約束條件結合化簡精度要求對原始軌跡線實施分區(qū)化簡，使得距離誤差控制下的軌跡點取舍行為盡量發(fā)生在移動速度均一的軌跡線片段內(nèi)，而速度變化上的重要軌跡點由于處于分區(qū)臨界位置而被保留，從而緩解化簡操作對原始軌跡線隱含速度特征的破壞。下文首先介紹本文提出的方法，然后利用真實的車輛軌跡數(shù)據(jù)進行試驗，并與其他已有方法的化簡結果進行對比式分析，最后給出相關結論。

1 方 法

給定一條原始軌跡線T={p1，p2，…，pn}，每個軌跡點pi表示為三元組信息〈xi，yi，ti〉，n是軌跡線包含的軌跡點數(shù)量。其中，xi和yi為軌跡點pi的空間位置坐標，ti表示pi產(chǎn)生的時間信息，由時間相鄰軌跡點構成的直線段分別表示為e1、e2、…、en-1。高精度測量設備產(chǎn)生的軌跡點還包括定位點的高程信息以及移動物體的瞬時速度和方向信息，本研究暫不考慮這一情況。本文提出的化簡方法主要包括軌跡直線段層次化聚類與軌跡線分區(qū)化簡兩個基本步驟。具體如下：

1.1 軌跡直線段層次化聚類

軌跡線直線段層次化聚類是指在拓撲連接關系的約束下，依據(jù)移動速度相似性原則對所有軌跡直線段單元進行層次化組織。首先，分別計算每條軌跡直線段對應的物體移動速度值?？紤]到軌跡線是對物體運動位置狀態(tài)的離散化描述模型，本文方法的一個前置條件是假設同一軌跡直線段區(qū)域內(nèi)物體的移動速度保持均勻。因此，對于由相鄰軌跡點pi、pi+1組成直線段ei，對應的物體移動速度vi可由式(1)計算得到

(1)

式中，d(pi，pi+1)表示軌跡點pi和pi+1間的歐氏距離，ti和ti+1則分別是軌跡點pi和pi+1的定位時間。

然后，以軌跡直線段為基本單元實施圖3所示的層次化聚類過程(注：圖3中軌跡線相鄰軌跡點間時間間隔相同)。層次化聚類是指在空間鄰近關系約束條件下，依據(jù)單個或多個屬性特征對空間目標進行不同空間粒度的分組分區(qū)[18]。該過程的核心問題包括：①如何定義相鄰聚類單元之間基于屬性特征的差異性；②聚類過程中采用何種鄰近約束策略。針對上述兩個問題，文獻[19]提出了single linkage、complete linkage、average linkage 3種屬性特征差異性計算模型以及first-order和full-order兩種聚類約束策略(限于論文篇幅，本文不再對上述模型和策略的具體細節(jié)展開描述)?；谖墨I[19]提供的建議以及軌跡直線段依據(jù)速度特征實施層次化聚類的具體特點，筆者采用average linkage和full-order構建針對軌跡直線段基于速度屬性特征的層次化分類模型。

圖3 軌跡線直線段的層次化聚類過程示意圖Fig.3 Hierarchical clustering procedure for line segments in a trajectory

(2)

式中，將相鄰的兩個聚類單元間的連接邊長度定義為各自包含軌跡直線段間的速度差異平方的均值。L(Gi，Gj)值越小，表明則兩個聚類單元對應的軌跡線片段區(qū)域間物體移動速度越接近，組成更高級別聚類單元的優(yōu)先級越高。每次相鄰聚類單元發(fā)生合并操作后，新組成的聚類單元需要重新計算并更新與周圍相鄰聚類單元間的連接邊長度，并調(diào)整連接邊排序。如圖3(b)中，當G(e4)和G(e5)合并為G(e4，e5)后，L(G(e3)，G(e4))需要更新為L(G(e3)，G(e4，e5))，L(G(e5)，G(e6))需要更新為L(G(e4，e5)，G(e6))。

1.2 軌跡線分區(qū)化簡

按1.1節(jié)方法對原始軌跡線包含的直線段實施層次化聚類后，聚類結果可進一步組織為樹結構模型。如圖4所示，樹結構的根節(jié)點(編號為①)則對應于由所有軌跡直線段組成的最大聚類單元G(e1，e2，…，e10)，而葉子節(jié)點(如編號為⑩)對應于由單條軌跡直線段構成的聚類單元(如G(e10))。從根節(jié)點到葉子節(jié)點，對應的軌跡線片段區(qū)域物體移動速度差異越來越小，形成一種層次化的剖分關系。

進一步，將建立的原始軌跡線剖分結構作為約束條件，結合設置的化簡幾何誤差ε對原始軌跡線進行分區(qū)處理。該過程表現(xiàn)為從根節(jié)點開始，由上而下依次遍歷如圖4所示的樹結構。每遍歷一個樹節(jié)點：

(1) 提取該樹節(jié)點對應聚類單元包含的所有軌跡線直線段，并連接組織為軌跡線片段。

(2) 以該軌跡線片段的首尾點構成的直線段為基準線，計算每一個中間軌跡點距基準線的時間同步歐氏距離，并將其中的最大值記錄為dmax。

(3) 比較dmax與ε間的大小關系，如果dmax≤ε，將該部分軌跡線片段劃分為同一個區(qū)域，同時跳過該樹節(jié)點的孩子節(jié)點；如果dmax>ε，則后續(xù)進一步考察該節(jié)點包含的孩子節(jié)點。

按上述步驟完成對樹結構的遍歷后，原始軌跡線被分為不同的區(qū)域，同一區(qū)域內(nèi)的軌跡線片段化簡為由首尾軌跡點連接的直線段，依次連接每一區(qū)域內(nèi)軌跡線片段的化簡結果即可得到完整的化簡結果。

圖5(a)是在圖4層次化樹結構基礎上結合化簡距離誤差閾值ε獲得的原始軌跡線分區(qū)結果，圖5(b)是依據(jù)分區(qū)信息導出的最終化簡結果。對比圖5(b)和圖1(d)可以發(fā)現(xiàn)，DP算法依據(jù)幾何偏移量對軌跡線進行分段化簡，在移動速度上對所有軌跡點一視同仁，導致部分在移動速度變化上具有重要意義但是幾何偏移特征不夠明顯的軌跡點被舍棄。而本文方法通過層次化聚類手段建立原始軌跡線在速度變化上的層次化剖分結構，并以此作為距離誤差控制下軌跡線分區(qū)化簡的約束條件，從而使得移動速度變化上具有重要意義的軌跡點如p3、p7、p8由于處在分區(qū)臨界點而得以保留，最終緩解化簡過程對原始軌跡線速度變化特征的破壞。

圖4 層次化聚類結果樹結構組織Fig.4 Organization of hierarchical clusters using structure tree

圖5 軌跡線分區(qū)及化簡結果輸出Fig.5 Original trajectory regionalization and simplified result output

2 試驗分析與評價

為了驗證方法的有效性，本研究采用了真實數(shù)據(jù)進行試驗測試。試驗數(shù)據(jù)如圖6所示，包括由超過3000個軌跡點組成的25條獨立軌跡線。這些軌跡數(shù)據(jù)來自車載GPS設備記錄的某城區(qū)車輛運行軌跡，車輛類型包括公交車和出租車兩種，相鄰軌跡點采集的時間間隔為1 s。由于車輛運行過程中存在臨時停車現(xiàn)象，表現(xiàn)為一定時間間隔內(nèi)軌跡點坐標重合，通過預處理的方式探測得到并打斷，直接將該部分軌跡線片段首尾點連接作為化簡結果。

圖6 試驗數(shù)據(jù)示例Fig.6 Experimental data

采用對比式策略進行化簡結果分析與評價，參考算法包括DP方法、TD-TR方法和OW-TR方法。考慮到試驗數(shù)據(jù)各軌跡點處未記錄車輛的瞬時速度和方向，因此沒有將DR方法作為比較對象。由于不同方法采用不同的化簡控制參數(shù)，如DP方法采用最短歐氏偏移距離，而TD-TR、OW-TR以及本文方法采用同步時間歐氏偏移距離，無法直接將化簡結果進行比較。因此，采用調(diào)整控制參數(shù)進行多次化簡的策略，使得不同方法獲得的化簡結果處于相同(非常接近)的壓縮比率，然后實施分析評價。壓縮比率ρ定義為化簡后減少的軌跡點數(shù)量與原始軌跡點數(shù)量的比值，ρ越大則表明化簡程度越大。試驗中ρ取值由最小10%至最高80%。為了使結果評價更為準確，定義如下定量化指標：

(1) 時間同步距離誤差。時間同步距離誤差值定義如圖2所示，即原始軌跡線的每個軌跡點與化簡后軌跡線上對應的時間同步擬合點間的距離。試驗中統(tǒng)計原始軌跡線所有軌跡點化簡后的時間同步距離誤差，將其中的最大值(即最大時間同步距離誤差)和平均值(即平均時間同步距離誤差)作為評價指標。

(2) 速度誤差。對于相鄰軌跡點pi、pi+1組成的一條原始軌跡線直線段ei，化簡前后的速度誤差speed_error(ei)定義為

(3)

圖7對比了4種方法在不同壓縮比率條件下產(chǎn)生的時間同步距離誤差?？梢园l(fā)現(xiàn)，不管是最大時間同步距離誤差，還是平均時間同步距離誤差，TD-TR方法、OW-TR方法以及本文提出的方法表現(xiàn)較為接近，且明顯優(yōu)于DP方法。原因是前面3種方法均采用了時間同步距離作為軌跡點取舍的控制指標。其中，TD-TR方法采用全局性由上而下的比較策略，時間同步距離誤差控制上好于采用局部啟發(fā)式策略的OW-TR方法。而本文方法雖然也是一種全局性方法，由于增加了原始軌跡線在速度變化上的層次化剖分關系作為約束條件，使得部分速度變化大但是在時間同步距離指標上不是最優(yōu)的軌跡點優(yōu)先保留，導致同一壓縮率水平下時間同步距離誤差高于TD-TR方法，部分壓縮比率區(qū)間甚至略高于OW-TR方法。也正是由于上述原因，使得本文方法在速度保持上優(yōu)于其他幾種方法。圖8(a)和圖8(b)分別是4種方法在不同壓縮比率水平下的最大速度誤差對比圖和平均速度誤差對比圖。由于時間同步距離考慮了時間維信息，使得TD-TR和OW-TR兩種方法在速度保持上優(yōu)于采用最短歐氏距離作為控制參數(shù)的DP算法；而本文方法在TD-TR方法基礎上，通過約束條件的形式加強速度變化在軌跡點取舍決策上的影響，使得化簡結果在速度保持上更優(yōu)。圖9展示了軌跡線局部片段利用4種不同方法化簡后的結果實例。通過視覺分析可以看到，DP方法化簡后丟失大量在速度變化上的重要軌跡點如pi、pj、pk、pl、pm、pn、po，這一情況在TD-TR方法化簡結果(丟失pk、pl、pm、pn)以及OW-TR方法化簡結果(丟失pk、pl、pm、pn)中有所緩解，而本文方法則能夠比較好地保持上述重要軌跡點。

3 結 論

以軌跡數(shù)據(jù)為代表的時空大數(shù)據(jù)給數(shù)據(jù)存儲、傳輸以及計算分析等技術環(huán)節(jié)帶來了挑戰(zhàn)。解決上述問題的重要途徑之一是使“大數(shù)據(jù)”變小，通過數(shù)據(jù)綜合及壓縮方法剔除冗余以及細節(jié)信息，保留軌跡數(shù)據(jù)隱含的主體特征。傳統(tǒng)的地圖綜合方法主要面向靜態(tài)的地理現(xiàn)象描述數(shù)據(jù)，關注地理數(shù)據(jù)的空間幾何分布特征，對于帶時間維信息蘊含移動特征的時空軌跡數(shù)據(jù)缺乏有效措施。本研究以軌跡線數(shù)據(jù)化簡這一具體問題為例， 在傳統(tǒng)DP方法采用的迭代分區(qū)的思想的基礎上，增加基于移動速度相似性原則的軌跡線層次化剖分措施，并以此作為約束條件使得距離誤差控制下的軌跡點取舍行為盡量發(fā)生在移動速度均一的軌跡線片段內(nèi)，從而達到更好地保持原始軌跡線移動模式特征這一目的。試驗表明，在相同的壓縮比率水平下，本文方法相對于其他已有方法在移動速度變化特征保持上具有優(yōu)勢。下一步工作包括：①進一步完善并驗證提出的軌跡線層次化聚類分區(qū)方法。本文主要參考文獻[18—19]構建式(2)所示的速度差異統(tǒng)計參量，是否最佳還需要更加全面的試驗分析與評價工作。②提高算法執(zhí)行效率，包括降低算法的復雜度以及構建并行化的計算構架，以應對海量位置感知器持續(xù)不斷產(chǎn)生的軌跡數(shù)據(jù)對化簡操作的需求。③提高軌跡線隱含模式特征的識別與分區(qū)能力。運動物體在不同時刻以及不同地理環(huán)境下存在不同的移動模式，如何分析挖掘這些特征差異并實施合理的分區(qū)分段處理具有重要意義。④進一步考慮軌跡點包含的高程信息，建立空間三維軌跡線化簡模型。

圖7 時間同步距離誤差比較Fig.7 Comparison of synchronized Euclidean distance

圖8 速度誤差比較Fig.8 Comparison of speed error

[1] ZHENG Yu，XIE Xing，MA Weiying.GeoLife：A Collaborative Social Networking Service among User，Location and Trajectory[J].IEEE Data(Base)Engineering Bulletin，2010，33(2)：32-39.

[2] 劉瑜，肖昱，高松，等.基于位置感知設備的人類移動研究綜述[J].地理與地理信息科學，2011，27(4)：8-13.

LIU Yu，XIAO Yu，GAO Song，et al.A Review of Human Mobility Research Based on Location Aware Devices[J].Geography and Geo-Information Science，2011，27(4)：8-13.

[3] 李清泉，黃練.基于GPS軌跡數(shù)據(jù)的地圖匹配算法[J].測繪學報，2010，39(2)：207-212.

LI Qingquan，HUANG Lian.A Map Matching Algorithm for GPS Tracking Data[J].Acta Geodaetica et Cartographica Sinica，2010，39(2)：207-212.

[4] 唐爐亮，劉章，楊雪，等.符合認知規(guī)律的時空軌跡融合與路網(wǎng)生成方法[J].測繪學報，2015，44(11)：1271-1276，1284.DOI：10.11947/j.AGCS.2015.20140591.

TANG Luliang，LIU Zhang，YANG Xue，et al.A Method of Spatio-temporal Trajectory Fusion and Road Network Generation Based on Cognitive Law[J].Acta Geodaetica et Cartographica Sinica，2015，44(11)：1271-1276，1284.DOI：10.11947/j.AGCS.2015.20140591.

[5] MUCKELL J，OLSEN Jr P W，HWANG J H，et al.Compression of Trajectory Data：A Comprehensive Evaluation and New Approach[J].GeoInformatica，2014，18(3)：435-460.

[6] 武芳，鄧紅艷.基于遺傳算法的線要素自動化簡模型[J].測繪學報，2003，32(4)：349-355.DOI：10.3321/j.issn:1001-1595.2003.04.013.

WU Fang，DENG Hongyan.Using Genetic Algorithms for Solving Problems in Automated Line Simplification[J].Acta Geodaetica et Cartographica Sinica，2003，32(4)：349-355.DOI：10.3321/j.issn:1001-1595.2003.04.013.

[7] 錢海忠，武芳，陳波，等.采用斜拉式彎曲劃分的曲線化簡方法[J].測繪學報，2007，36(4)：443-449，456.DOI：10.3321/j.issn:1001-1595.2007.04.014.

QIAN Haizhong，WU Fang，CHEN Bo，et al.Simplifying Line with Oblique Dividing Curve Method[J].Acta Geodaetica et Cartographica Sinica，2007，36(4)：443-449，456.DOI：10.3321/j.issn:1001-1595.2007.04.014.

[8] 艾廷華，郭仁忠，劉耀林.曲線彎曲深度層次結構的二叉樹表達[J].測繪學報，2001，30(4)：343-348.DOI：10.3321/j.issn:1001-1595.2001.04.013.

AI Tinghua，GUO Renzhong，LIU Yaolin.A Binary Tree Representation of Curve Hierarchical Structure in Depth[J].Acta Geodaetica et Cartographica Sinica，2001，30(4)：343-348.DOI：10.3321/j.issn:1001-1595.2001.04.013.

[9] DOUGLAS D H，PEUCKER T K.Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J].Cartographica：The International Journal for Geographic Information and Geovisualization，1973，10(2)：112-122.

[10] LI Zhilin，OPENSHAW S.Algorithms for Automated Line Generalization1Based on a Natural Principle of Objective Generalization[J].International Journal of Geographical Information Systems，1992，6(5)：373-389.

[11] VISVALINGAM M，WHYATT J D.Line generalisation by repeated elimination of points[J].The Cartographic Journal，1993，30(1)：46-51.

[12] KEOGH E，CHU S，HART D，et al.An online algorithm for segmenting time series[C]∥Proceedings of 2001 IEEE International Conference on Data Mining (ICDM).San Jose，CA：IEEE，2001：289-296.

[13] POTAMIAS M，PATROUMPAS K，SELLIS T.Sampling Trajectory Streams with Spatiotemporal Criteria[C]∥Proceedings of the 18th International Conference on Scientific and Statistical Database Management (SSDBM).Vienna，Austria：IEEE，2006：275-284.

[14] TRAJCEVSKI G，CAO Hu，SCHEUERMANN P，et al.On-line Data Reduction and The Quality of History in Moving Objects Databases[C]∥Proceedings of the 5th ACM International Workshop on Data Engineering for Wireless and Mobile Access(MobiDE).Chicago，Illinois：ACM，2006：19-26.

[15] CHEN Yukun，JIANG Kai，ZHENG Yu，et al.Trajectory Simplification Method for Location-Based Social Networking Services[C]∥Proceedings of the 2009 International Workshop on Location Based Social Networks.Seattle，Washington：ACM，2009：33-40.

[16] LONG Cheng，WONG R C W，JAGADISH H V.Trajectory Simplification：on Minimizing the Direction-Based Error[J].Proceedings of the VLDB Endowment，2014，8(1)：49-60.

[17] 唐爐亮，楊雪，牛樂，等.一種眾源車載GPS軌跡大數(shù)據(jù)自適應濾選方法[J].測繪學報，2016，45(12)：1455-1463.DOI：10.11947/j.AGCS.2016.20160117.

TANG Luliang，YANG Xue，NIU Le，et al.An Adaptive Filtering Method Based on Crowdsourced Big Trace Data[J].Acta Geodaetica et Cartographica Sinica，2016，45(12)：1455-1463.DOI：10.11947/j.AGCS.2016.20160117.

[19] GUO D.Regionalization with Dynamically Constrained Agglomerative Clustering and Partitioning (REDCAP)[J].International Journal of Geographical Information Science，2008，22(7)：801-823.

A Method of Speed-preserving Trajectory Simplification

YANG Min1，3，4，CHEN Yuanyuan1，2，JIN Cheng5，CHENG Qian1

1. School of Resource and Environmental Sciences，Wuhan University，Wuhan 430072,China； 2. Institute of Remote Sensing & Geographical Information System，Peking University，Beijing 100871,China； 3. Key Laboratory of Urban Land Resources Monitoring and Simulation，Ministry of Land and Resources，Shenzhen 518034,China； 4. Key Laboratory for National Geographic Census and Monitoring，National Administration of Surveying，Mapping and Geoinformation，Wuhan 430072,China； 5. Xi’an Research Institute of Surveying and Mapping，Xi’an 710054,China

Trajectory simplification plays an important role in trajectory data storage，transmission，temporal-spatial analysis and visualization.Traditional simplification methods，such as Douglas-Peucker algorithm，concern the geometric information while ignore the temporal information，which may result in loss of implied mobility features in the original trajectory.Aiming at minimize speed error in the trajectory simplification transformation，this paper presents a new method based on hierarchical clustering and regionalization operations.First，the line segments of the original trajectory are clustered at different levels based on the similarity of speed measure.With the support of the hierarchical clusters，the original trajectory is then divided into a series of segments.For each segment，the maximum synchronized Euclidean distance from the points to the segment line connecting two end points is no larger than the predefined threshold value.Finally，the simplified results is outputted by organizing the end points of each trajectory segments.Real life data was used to verity the effectiveness of the proposed method，and results of comparing with other existing methods showed that our method performs better in speed preserving.

trajectory data；simplification；clustering analysis；speed preservation

The National Natural Science Foundation of China (No. 41401447)；The Open Fund of Key Laboratory of Urban Land Resources Monitoring and Simulation，Ministry of Land and Resources (No. KF-2016-02-020)；The Open Fund of Key Laboratory for National Geographic Census and Monitoring，National Administration of Surveying，Mapping and Geoinformation (No. 2015NGCM)

YANG Min (1985—)，male，PhD，associate professor，majors in map generalization and multi-source data integration.

CHEN Yuanyuan

E-mail： ygrittechen@pku.edu.cn

楊敏，陳媛媛，金澄，等.保持移動速度特征的軌跡線化簡方法[J].測繪學報，2017,46(12)：2016-2023.

10.11947/j.AGCS.2017.20170023.

YANG Min，CHEN Yuanyuan，JIN Cheng，et al.A Method of Speed-preserving Trajectory Simplification[J]. Acta Geodaetica et Cartographica Sinica,2017,46(12):2016-2023. DOI:10.11947/j.AGCS.2017.20170023.

P208

A

1001-1595(2017)12-2016-08

國家自然科學基金(41401447)；國土資源部城市土地資源監(jiān)測與仿真重點實驗室開放基金(KF-2016-02-020)；地理國情監(jiān)測國家測繪地理信息局重點實驗室開放基金(2015NGCM)

宋啟凡)

2017-01-13

2017-09-29

楊敏(1985—)，男，博士，副教授，研究方向為地圖綜合、多源數(shù)據(jù)集成與更新。

E-mail： yangmin2003@whu.edu.cn

陳媛媛