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

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

保持移動(dòng)速度特征的軌跡線化簡(jiǎn)方法

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

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

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

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

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

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

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

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

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

1 方 法

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

1.1 軌跡直線段層次化聚類

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

(1)

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

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

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

(2)

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

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

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

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

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

(2) 以該軌跡線片段的首尾點(diǎn)構(gòu)成的直線段為基準(zhǔn)線，計(jì)算每一個(gè)中間軌跡點(diǎn)距基準(zhǔn)線的時(shí)間同步歐氏距離，并將其中的最大值記錄為dmax。

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

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

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

圖4 層次化聚類結(jié)果樹結(jié)構(gòu)組織Fig.4 Organization of hierarchical clusters using structure tree

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

2 試驗(yàn)分析與評(píng)價(jià)

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

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

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

(1) 時(shí)間同步距離誤差。時(shí)間同步距離誤差值定義如圖2所示，即原始軌跡線的每個(gè)軌跡點(diǎn)與化簡(jiǎn)后軌跡線上對(duì)應(yīng)的時(shí)間同步擬合點(diǎn)間的距離。試驗(yàn)中統(tǒng)計(jì)原始軌跡線所有軌跡點(diǎn)化簡(jiǎn)后的時(shí)間同步距離誤差，將其中的最大值(即最大時(shí)間同步距離誤差)和平均值(即平均時(shí)間同步距離誤差)作為評(píng)價(jià)指標(biāo)。

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

(3)

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

3 結(jié) 論

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

圖7 時(shí)間同步距離誤差比較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] 劉瑜，肖昱，高松，等.基于位置感知設(shè)備的人類移動(dòng)研究綜述[J].地理與地理信息科學(xué)，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].測(cè)繪學(xué)報(bào)，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] 唐爐亮，劉章，楊雪，等.符合認(rèn)知規(guī)律的時(shí)空軌跡融合與路網(wǎng)生成方法[J].測(cè)繪學(xué)報(bào)，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] 武芳，鄧紅艷.基于遺傳算法的線要素自動(dòng)化簡(jiǎn)模型[J].測(cè)繪學(xué)報(bào)，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] 錢海忠，武芳，陳波，等.采用斜拉式彎曲劃分的曲線化簡(jiǎn)方法[J].測(cè)繪學(xué)報(bào)，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] 艾廷華，郭仁忠，劉耀林.曲線彎曲深度層次結(jié)構(gòu)的二叉樹表達(dá)[J].測(cè)繪學(xué)報(bào)，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] 唐爐亮，楊雪，牛樂(lè)，等.一種眾源車載GPS軌跡大數(shù)據(jù)自適應(yīng)濾選方法[J].測(cè)繪學(xué)報(bào)，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

楊敏，陳媛媛，金澄，等.保持移動(dòng)速度特征的軌跡線化簡(jiǎn)方法[J].測(cè)繪學(xué)報(bào)，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

國(guó)家自然科學(xué)基金(41401447)；國(guó)土資源部城市土地資源監(jiān)測(cè)與仿真重點(diǎn)實(shí)驗(yàn)室開放基金(KF-2016-02-020)；地理國(guó)情監(jiān)測(cè)國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室開放基金(2015NGCM)

宋啟凡)

2017-01-13

2017-09-29

楊敏(1985—)，男，博士，副教授，研究方向?yàn)榈貓D綜合、多源數(shù)據(jù)集成與更新。

E-mail： yangmin2003@whu.edu.cn

陳媛媛