王清， 丁赤飚， 付琨， 任文娟

(1.中國科學(xué)院 電子學(xué)研究所， 北京 100190； 2.中國科學(xué)院 空間信息處理與應(yīng)用系統(tǒng)技術(shù)重點實驗室， 北京 100190; 3.中國科學(xué)院大學(xué) 電子電氣與通信工程學(xué)院， 北京 100049)

基于膨脹運算的移動對象興趣點檢測方法

王清1,2,3， 丁赤飚1,3， 付琨1,2,3， 任文娟1,2,3

(1.中國科學(xué)院 電子學(xué)研究所， 北京 100190； 2.中國科學(xué)院 空間信息處理與應(yīng)用系統(tǒng)技術(shù)重點實驗室， 北京 100190; 3.中國科學(xué)院大學(xué) 電子電氣與通信工程學(xué)院， 北京 100049)

針對傳統(tǒng)興趣點檢測算法在準確性和效率方面的不足，提出基于膨脹運算的移動對象興趣點檢測方法(DMDO)。通過矩陣二值化操作濾除停留點噪聲，提高預(yù)測準確率，并用膨脹運算替代傳統(tǒng)方法中的聚類算法提高算法效率。將DMDO在開放空間數(shù)據(jù)集AMSA和IMIS3Days上進行仿真實驗，結(jié)果表明：DMDO相比基于密度的空間聚類算法，在數(shù)據(jù)集AMSA上準確率平均提高17.94%，算法效率提高6.63倍；在數(shù)據(jù)集IMIS3Days上準確率平均提高19.98%，算法效率提高9.13倍；相比以聚類點排序結(jié)果確定聚類結(jié)構(gòu)算法，DMDO在數(shù)據(jù)集AMSA上準確率平均提高20.04%，算法效率提高14.61倍；在數(shù)據(jù)集IMIS3Days上準確率平均提高16.60%，算法效率提高42.19倍；DMDO相比傳統(tǒng)方法均表現(xiàn)出較高的預(yù)測準確性、較低的時間開銷，適用于解決大數(shù)據(jù)背景下的移動對象興趣點檢測問題。

信息處理技術(shù)； 軌跡數(shù)據(jù)挖掘； 興趣點檢測； 膨脹運算； 開放空間

0 引言

隨著通信技術(shù)、全球定位導(dǎo)航系統(tǒng)的迅猛發(fā)展，可以通過多種途徑獲得不同類型的軌跡數(shù)據(jù)。例如通過智能手機、車載導(dǎo)航系統(tǒng)獲取行人、汽車等城市軌跡數(shù)據(jù)[1-3]，通過衛(wèi)星、雷達、船舶自動識別系統(tǒng)(AIS)等定位技術(shù)獲得船舶、飛機的軌跡數(shù)據(jù)[4]。軌跡表達了移動對象一段時間內(nèi)的位置信息，蘊含著移動對象的行為習(xí)慣。挖掘海量軌跡數(shù)據(jù)有助于深入了解移動對象行為習(xí)慣、感知社會需求[5]。為解決軌跡數(shù)據(jù)挖掘問題，實現(xiàn)位置大數(shù)據(jù)的應(yīng)用價值，基于位置的服務(wù)(LBS)應(yīng)運而生。研究區(qū)域中的興趣點是指具有特殊含義的停留區(qū)域，例如城市中的教學(xué)樓、宿舍、商城，海域沿岸的港口、補給站等。一部分LBS依賴興趣點的挖掘與檢測，例如，根據(jù)用戶常訪興趣點計算用戶間相似度，從而進行用戶社交網(wǎng)絡(luò)的挖掘與研究；預(yù)測用戶即將前往的興趣點，從而推送相關(guān)廣告信息等[6-8]。本文主要圍繞如何快速、準確地挖掘興趣點展開研究。

興趣點檢測技術(shù)主要分為兩類，即靜態(tài)提取和動態(tài)挖掘方法[9]。靜態(tài)提取方法需要人工標注類似教學(xué)樓、商城、港口、補給站等有特殊含義的停留位置[10-11]。動態(tài)挖掘方法不需要研究區(qū)域的先驗知識作為輸入條件，僅根據(jù)原始軌跡數(shù)據(jù)的時空特征發(fā)現(xiàn)潛在興趣點，這些時空特征包括經(jīng)緯度、速度、加速度和軌跡前進方向等。

動態(tài)挖掘算法一直是國內(nèi)外學(xué)者的研究重點。主要思路是首先檢測大量歷史軌跡的停留點，然后對停留點進行聚類，每類對應(yīng)一個興趣點。興趣點檢測主要分為兩部分內(nèi)容：停留點檢測和停留點聚類。

在停留點檢測方面，Agamennoni等[11]根據(jù)靜態(tài)速度閾值檢測停留點，小于速度閾值的軌跡點被認為是停留點。鄭宇等[12]提出根據(jù)時間閾值和距離閾值從歷史軌跡中提取停留點。羅庭等[13]根據(jù)移動對象軌跡曲折程度判斷其是否低速行駛，移動對象軌跡短時間內(nèi)曲折程度較高時，認為其行駛速度較低，處于“停留”狀態(tài)。

在停留點聚類方面，由于不同移動對象到達同一興趣點可能產(chǎn)生不同停留點，這些停留點距離很近，可利用聚類方法將停留點聚集為各個點簇，每個興趣點用點簇表示。大量研究工作圍繞采用不同的聚類方法及其改進方法展開。Ashbrook等[14]采用K均值(K-Means)聚類算法對歷史軌跡數(shù)據(jù)中提取的停留點進行聚類。K-Means算法是一種劃分聚類算法，需要用戶預(yù)先設(shè)定興趣點的數(shù)目K，但是從雜亂無章的軌跡中預(yù)先準確指定興趣點個數(shù)并非易事；并且，K-Means算法抗噪能力較差，易受離群點影響。由于K-Means算法存在參數(shù)設(shè)定、抗噪性差的問題，Palma 等[15]采用一種抗噪聲的基于密度的空間聚類(DBSCAN)算法對停留點進行聚類。DBSCAN算法可以避免預(yù)先設(shè)定興趣點數(shù)目并剔除噪聲點，但是需要設(shè)定數(shù)量閾值和距離閾值，并且算法時間復(fù)雜度隨著數(shù)據(jù)量的增加而大幅增加，不適宜大數(shù)據(jù)量環(huán)境下的興趣點檢測問題。Zimmermann等[16]采用一種以聚類點排序結(jié)果確定聚類結(jié)構(gòu)(OPTICS)的算法挖掘興趣點。OPTICS算法屬于基于密度的聚類算法，相比DBSCAN算法的改進之處在于，無需預(yù)先設(shè)定閾值，能獲得任何閾值的DBSCAN聚類結(jié)果。

目前國內(nèi)外挖掘興趣點所采用的主流方法可總結(jié)為首先檢測停留點，然后采用DBSCAN算法等基于密度的聚類算法對停留點進行聚類，以停留點簇表示各興趣點。主流算法存在問題主要為興趣點檢測準確率較低、算法時間復(fù)雜度較高：首先，算法易將移動對象偶然的停留誤判為停留點，在停留點檢測中存在大量誤判現(xiàn)象，影響了聚類結(jié)果，從而降低興趣點檢測的準確性；其次，以DBSCAN算法為代表的基于密度的聚類算法時間復(fù)雜度較高，數(shù)據(jù)規(guī)模較大時耗費時間長，不適用于大數(shù)據(jù)背景下的聚類問題。

針對傳統(tǒng)方法的不足，本文提出了基于膨脹運算的移動對象興趣點檢測算法(DMDO)，旨在通過矩陣二值化操作濾除誤判的停留點噪聲，并用膨脹運算替代聚類算法提高算法效率。

1 DMDO流程

在介紹具體算法之前，首先描述方法涉及的基本概念。

定義1停留點。移動對象的速度小于速度閾值speedThreshold時所在的具體經(jīng)緯度。若對于軌跡點p，滿足vp

定義2網(wǎng)格。將研究區(qū)域等距離劃分所形成的二維規(guī)則區(qū)域。

定義3停留網(wǎng)格。包含停留點的數(shù)目大于一定閾值的網(wǎng)格。

定義4興趣點。具有特殊含義的區(qū)域，例如教學(xué)樓、商城、港口、補給站等。本文根據(jù)停留點及停留網(wǎng)格挖掘興趣點。

算法流程如圖1所示。

圖1 DMDO流程圖Fig.1 Algorithm flow of DMDO

將研究區(qū)域離散化，均等劃分為等距網(wǎng)格。

計算合理的速度閾值，用于歷史軌跡中的檢測停留點。

遍歷歷史軌跡集合中的軌跡點，計算其速度值，并與速度閾值speedThreshold進行比較，若軌跡點速度值小于speedThreshold，則將其判定為停留點，映射至研究區(qū)域網(wǎng)格中，并將相應(yīng)網(wǎng)格的停留點計數(shù)增一。完成遍歷后，形成停留點計數(shù)矩陣Matrix.

根據(jù)閾值θ二值化停留點計數(shù)矩陣Matrix，獲得矩陣Matrix′. 二值化保留停留點數(shù)目較多的停留網(wǎng)格，濾除移動對象偶然停留所產(chǎn)生的誤判噪聲。

對矩陣Matrix′進行膨脹運算，連通空間位置較近的停留網(wǎng)格，形成各個連通區(qū)域。將覆蓋網(wǎng)格數(shù)量大于w×w(w表示膨脹運算模板寬度)的連通區(qū)域作為興趣點預(yù)測結(jié)果，將連通區(qū)域中包含停留點數(shù)目最多的網(wǎng)格設(shè)定為興趣點的中心。輸出興趣點預(yù)測結(jié)果，至此，DMDO流程結(jié)束。

DMDO用膨脹運算替代DBSCAN聚類，一方面膨脹運算能夠替代DBSCAN聚類實現(xiàn)連通、聚集的目的，另一方面，膨脹運算降低時間開銷。假設(shè)停留點數(shù)目為n，停留網(wǎng)格數(shù)目為m(m?n)，DBSCAN聚類的時間復(fù)雜度為O(n2)，膨脹運算的時間復(fù)雜度為O(m)，算法效率大幅提高。

計算合理速度閾值的算法流程如圖2所示。遍歷歷史軌跡集合中的軌跡點，根據(jù)當前點和相鄰點經(jīng)緯度計算其速度，然后采用K-Means算法將速度值聚為“高速”、“低速”兩類，并取兩類臨界值作為速度閾值speedThreshold.

圖2 速度閾值計算流程圖Fig.2 Calculation flow of speed threshold

2 DMDO實驗結(jié)果與分析

2.1 實驗環(huán)境及數(shù)據(jù)集

實驗的軟硬件條件如下：CPU為酷睿i3(2核，2.50 GHz)，內(nèi)存4.00 GB；操作系統(tǒng)為32位Windows10，仿真軟件為PyCharm 5.0.1.

為驗證DMDO挖掘興趣點的準確性及算法效率，本文將采用兩組開放空間數(shù)據(jù)集進行實驗。兩組數(shù)據(jù)集均為船舶軌跡數(shù)據(jù)，特征如表1所示。

數(shù)據(jù)集1 AMSA是由澳洲海事安全局提供的2015年8月至2015年11月的澳大利亞附近海域民用船舶軌跡數(shù)據(jù)，包含3 327條軌跡，458 716個軌跡點，平均采樣間隔為34.25 min. 數(shù)據(jù)集2 IMIS3Days是由IMIS Hellas S.A.公司提供的愛琴海海域民用船舶軌跡數(shù)據(jù)，包含933條軌跡，3 095 254個軌跡點，采樣間隔為10 s.

表1 實驗數(shù)據(jù)集特征

本文通過World Port Source網(wǎng)站獲取兩組數(shù)據(jù)集所在區(qū)域的真實興趣點作為評估標準，用于評估算法挖掘興趣點的準確性。兩組數(shù)據(jù)集真實興趣點的提取結(jié)果如表2所示。

表2 真實興趣點提取結(jié)果

2.2 實驗結(jié)果

本文從興趣點檢測的準確性和效率兩個方面對DMDO與兩種傳統(tǒng)算法DBSCAN及OPTICS進行對比，分別采用F1值、算法運行時間T量化算法準確性和效率。傳統(tǒng)方法DBSCAN的思路是首先通過速度閾值檢測歷史軌跡中的停留點，然后采用DBSCAN聚類算法對停留點進行聚類；OPTICS算法的思路是首先檢測停留點，然后采用OPTICS算法根據(jù)停留點之間的距離對其進行排序，再采用自動聚類方法根據(jù)排序結(jié)果對停留點進行聚類。

2.2.1 評估指標

本文用F1值評估興趣點檢測的準確性，其計算方法為

(1)

式中：P為準確率，表征興趣點檢測的查準率，即預(yù)測出的真實興趣點占算法預(yù)測結(jié)果總量的比率；R為召回率，表征興趣點檢測的查全率，即預(yù)測出的真實興趣點占真實興趣點總量的比率。若集合TD={TD1,TD2,…,TDn}表示研究區(qū)域中提前標注的真實興趣點，集合PD={PD1,PD2,…}表示算法的興趣點預(yù)測結(jié)果，則P和R的具體計算分別為

(2)

(3)

式中：函數(shù)H(PD,TDi)表示算法預(yù)測結(jié)果是否命中真實興趣點TDi. 若在預(yù)測結(jié)果集合PD中存在一個預(yù)測結(jié)果PDj，覆蓋真實興趣點TDi，則H(PD,TDi)=1，否則為0，即

(4)

2.2.2 實驗結(jié)果及分析

DMDO涉及的兩個重要參數(shù)為二值化閾值θ和膨脹運算模板寬度w. 閾值θ反映過濾停留點噪聲的力度，值越大表明過濾的力度越強；模板寬度w反映相鄰兩個停留點連通的難易程度，值越大表明越易連通。傳統(tǒng)DBSCAN算法中包含兩個參數(shù)eps和minPts；OPTICS算法中包含一個參數(shù)minPts. 其中，minPts與閾值θ具有類似含義，eps與模板寬度w具有類似含義。d表示網(wǎng)格劃分寬度，轉(zhuǎn)換關(guān)系可近似表示為

(5)

minPts=2θ.

(6)

在檢測出相同停留點的前提下，比較DMDO與兩傳統(tǒng)算法DBSCAN及OPTICS對于兩個數(shù)據(jù)集AMSA及IMIS3Days在不同參數(shù)組合(θ，w)下的準確性F1值和運行效率T. 實驗結(jié)果如圖3所示，圖3(a)表示采取不同參數(shù)組合時，3種算法在數(shù)據(jù)集AMSA上的F1值，圖3(b)表示3種算法在數(shù)據(jù)集AMSA上的運行時間T，圖3(c)和圖3(d)表示3種算法在數(shù)據(jù)集IMIS3Days上的F1值及運行時間T.

對于數(shù)據(jù)集AMSA，設(shè)置二值化閾值θ取值范圍為1～29，膨脹運算模板寬度w取值為1、3、5. 分析圖3(a)，當w為1、3、5時，DMDOF1值的變動范圍分別為[0.37, 0.45]、[0.58, 0.74]、[0.78, 0.83]，傳統(tǒng)算法DBSCAN變動范圍為[0.04, 0.15]、[0.42, 0.57]、[0.59, 0.77]，傳統(tǒng)算法OPTICS變動范圍為[0.34, 0.51]。當參數(shù)一致時，DMDO的F1值均顯著優(yōu)于DBSCAN算法。原因是兩種算法預(yù)測準確的興趣點數(shù)目相近，而DBSCAN算法預(yù)測的興趣點總數(shù)遠大于DMDO，因此DMDO的準確率遠高于DBSCAN算法，DMDO的F1值優(yōu)勢顯著。當w>1時，DMDO的F1值顯著優(yōu)于傳統(tǒng)算法OPTICS. 原因是OPTICS算法未對停留點連通的難易程度設(shè)置明確的閾值，僅根據(jù)停留點之間的距離自動聚類，導(dǎo)致挖掘結(jié)果包含較多的噪聲點，預(yù)測的興趣點數(shù)量過多，致使OPTICS算法的準確性下降。DMDO準確率的顯著優(yōu)勢表明將停留點噪聲誤判為興趣點的錯誤率較低，從而說明本文通過網(wǎng)格二值化過濾停留點噪聲的處理方法更為有效，剔除噪聲的力度更強。

分析圖3(b)，當w為1、3、5時，DMDO運行時間基本分布在1 s以內(nèi)，DBSCAN算法運行時間均大于2 s，效率平均提高7.63倍，而OPTICS算法由于涉及停留點排序及停留點聚類，運行時間基本分布于10 s以上。表明DMDO效率大幅提高。

對于數(shù)據(jù)集IMIS3Days，能夠獲得相似的結(jié)論。設(shè)置二值化閾值θ取值范圍為50～1 000，膨脹運算模板寬度w取值為1、3、5. 如圖3(c)所示，DMDO的F1值優(yōu)勢顯著，F(xiàn)1均值為0.67，DBSCAN算法的F1均值為0.47，OPTICS算法的F1均值為0.50，準確性大幅提高；如圖3(d)所示，DMDO的運行時間平均為0.26 s，DBSCAN算法的運行時間平均為2.57 s，算法效率平均提高9.13倍，OPTICS算法的運行時間平均為10.78 s.

上述比較分析了DMDO相比兩種傳統(tǒng)算法DBSCAN及OPTICS在準確性和效率上的優(yōu)勢，下文將通過圖3(a)和圖3(c)分析參數(shù)二值化閾值θ及膨脹運算模板寬度w對DMDOF1值的影響。

當w保持不變時，隨著二值化閾值θ增大，DMDO的F1值均存在先增后減的變化趨勢。原因是當二值化閾值θ增大時，算法能夠有效濾除移動對象偶然停留所產(chǎn)生的噪聲，使得算法準確率增大，F(xiàn)1值增大；當θ持續(xù)增大，可能將真實的興趣點當作噪聲濾除，使得算法準確率、召回率均下降，F(xiàn)1值降低。

當二值化閾值θ不變時，隨著膨脹運算模板寬度w的增大，DMDO的F1值顯著增大(表現(xiàn)為w=5曲線在w=3曲線之上，w=3曲線在w=1曲線之上)。原因是膨脹運算模板寬度反映膨脹程度，模板越寬，表明距離較近的停留網(wǎng)格越易連通。當模板寬度w增大時，相鄰的興趣點連通，使得預(yù)測的興趣點總數(shù)減少，提高預(yù)測準確率；另一方面，連通相鄰興趣點時覆蓋了興趣點之間的間隙，預(yù)測的興趣點區(qū)域涵蓋真實興趣點的可能性更高，從而提高了召回率。準確率、召回率的提高使得F1值增大。

圖3 實驗結(jié)果Fig.3 Experimental results

另外，F(xiàn)1對參數(shù)θ的敏感程度較低，對w的敏感程度較高，也即參數(shù)w對F1的影響更為顯著。

最后，討論網(wǎng)格劃分寬度d對算法DMDO精度和效率的影響。圖4(a)和圖4(b)分別表示在數(shù)據(jù)集AMSA和IMIS3Days上改變網(wǎng)格劃分寬度d對F1值和運行時間T的影響。

圖4 網(wǎng)格劃分寬度d對實驗結(jié)果的影響Fig.4 Influence of cell width d on experimental results

網(wǎng)格劃分寬度d主要影響目的地挖掘的精細程度。調(diào)節(jié)網(wǎng)格劃分寬度d時應(yīng)相應(yīng)調(diào)整二值化閾值θ和膨脹運算模板寬度w，以分別保持算法過濾停留點噪聲的力度和停留點連通的難易程度基本不變。例如，當網(wǎng)格劃分寬度d增大至原來的2倍時，網(wǎng)格覆蓋區(qū)域的實際面積變?yōu)樵瓉淼?倍，若此時二值化閾值θ和膨脹運算模板寬度w保持不變，則網(wǎng)格將更易滿足二值化閾值θ，更易于被判定為停留網(wǎng)格，從而降低了算法過濾停留點噪聲的力度，并且由于網(wǎng)格覆蓋面積增大，距離較遠的停留點更容易連通，從而增大了算法連通停留點的能力。為了保持算法過濾停留點噪聲的力度和停留點連通的難易程度基本不變，如圖4(a)所示，當網(wǎng)格劃分寬度d從0.1增大至原來的2倍時，二值化閾值θ也應(yīng)從27增大至原來的4倍，膨脹運算模板寬度w應(yīng)從9相應(yīng)減小至5.

如圖4(a)和圖4(b)所示，當減小網(wǎng)格劃分寬度d并相應(yīng)調(diào)整其他兩個參數(shù)時，算法DMDO的精度增高，算法效率降低。原因是減小網(wǎng)格劃分寬度d時，停留點將映射至更為精細的網(wǎng)格，覆蓋面積較小的興趣點更易被算法檢測出來，算法查全率提高，F(xiàn)1值增大。同時，由于網(wǎng)格劃分更為精細，算法需要處理的網(wǎng)格數(shù)量增多，因而運行時間變長，算法效率降低。

兩數(shù)據(jù)集興趣點檢測結(jié)果分別如圖5和圖6所示。從圖5和圖6可直觀看出，DMDO挖掘興趣點的準確性較高。

圖5 數(shù)據(jù)集AMSA興趣點標注及挖掘結(jié)果圖Fig.5 Extracted and predicted results of interest points on dataset AMSA

圖6 數(shù)據(jù)集IMIS3Days興趣點標注及挖掘結(jié)果圖Fig.6 Extracted and predicted results of interest points on dataset IMIS3Days

實驗結(jié)果表明，本文提出的DMDO能夠快速、準確挖掘出研究區(qū)域的真實興趣點。相比DBSCAN算法，對于數(shù)據(jù)集AMSA，準確率平均提高17.94%，算法效率提高6.63倍；對于數(shù)據(jù)集IMIS3Days，準確率平均提高19.98%，算法效率提高9.13倍。相比OPTICS算法，對于數(shù)據(jù)集AMSA，準確率平均提高20.04%，算法效率提高14.61倍；對于數(shù)據(jù)集IMIS3Days，準確率平均提高16.60%，算法效率提高42.19倍。

3 結(jié)論

本文旨在研究準確、高效的興趣點檢測方法。傳統(tǒng)算法易將移動對象偶然的停留誤判為停留點，興趣點檢測的準確性較低，并且對停留點聚類的時間復(fù)雜度較高，時間開銷大。針對傳統(tǒng)算法的不足，本文提出了DMDO，通過矩陣二值化操作濾除停留點噪聲，提高算法準確性，并用膨脹運算替代聚類算法提高算法效率。在開放空間數(shù)據(jù)集AMSA和IMIS3Days上進行實驗，得到如下結(jié)論：

1)DMDO在預(yù)測準確性方面表現(xiàn)出顯著優(yōu)勢。相比DBSCAN算法，在數(shù)據(jù)集AMSA上準確率平均提高17.94%，在數(shù)據(jù)集IMIS3Days上準確率平均提高19.98%；相比OPTICS算法，在數(shù)據(jù)集AMSA上準確率平均提高20.04%，在數(shù)據(jù)集IMIS3Days上準確率平均提高16.60%. 表明本文提出的二值化操作濾除停留點噪聲的力度更強。

2)DMDO在保證預(yù)測準確性的同時，大幅降低了時間開銷。相比DBSCAN算法，在數(shù)據(jù)集AMSA上算法效率提高6.63倍，在數(shù)據(jù)集IMIS3Days上算法效率提高9.13倍。相比OPITCS算法，在數(shù)據(jù)集AMSA上算法效率提高14.61倍，在數(shù)據(jù)集IMIS3Days上算法效率提高42.19倍。表明算法適用于解決大數(shù)據(jù)背景下的移動對象興趣點檢測問題。

未來的研究工作包括：

1)DMDO適用于開放空間的興趣點檢測問題，應(yīng)用于城市軌跡數(shù)據(jù)時，易將城市路口誤判為興趣點，在未來工作中將擴展算法的適用范圍。

2)將研究區(qū)域興趣點劃分層次，例如劃分為重要、較重要、非重要興趣點等，將算法擴展為分層次檢測興趣點的方法。

References)

[1] Danalet A, Farooq B, Bierlaire M. A Bayesian approach to detect pedestrian destination-sequences from WiFi signatures[J]. Transportation Research Part C: Emerging Technologies, 2014, 44: 146-170.

[2] Liao L, Fox D, Kautz H. Extracting places and activities from GPS traces using hierarchical conditional random fields[J]. International Journal of Robotics Research, 2007, 26(1): 119-134.

[3] Cao X, Cong G, Jensen C S. Mining significant semantic locations from GPS data[J]. Proceedings of the VLDB Endowment, 2010, 3(1): 1009-1020.

[4] Qi L, Zheng Z. Trajectory prediction of vessels based on data mining and machine learning[J]. Journal of Digital Information Management, 2016, 14(1): 33-40.

[5] 喬少杰, 李天瑞, 韓楠, 等. 大數(shù)據(jù)環(huán)境下移動對象自適應(yīng)軌跡預(yù)測模型[J]. 軟件學(xué)報, 2015, 26(11): 2869-2883.

QIAO Shao-jie, LI Tian-rui, HAN Nan,et al. Self-adaptive trajectory prediction model for moving objects in big data environment[J]. Journal of Software, 2015, 26(11): 2869-2883.(in Chinese)

[6] Li Y, Guo A, Liu S, et al. A location based reminder system for advertisement[C]∥Proceedings of the 18th ACM International Conference on Multimedia. NY, US: ACM, 2010: 1501-1502.

[7] Chung J, Schmandt C. Going my way: a user-aware route planner[C]∥Proceedings of the SIGCHI Conference on Human Factors in Computing Systems.NY, US: ACM, 2009: 1899-1902.

[8] Zheng Y, Zhang L Z, Ma Z X, et al. Recommending friends and locations based on individual location history[J]. ACM Transactions on the Web (TWEB), 2011, 5(1): 5.

[9] 楊潔. 基于歷史軌跡的位置預(yù)測方法研究[D]. 杭州:杭州電子科技大學(xué), 2015.

YANG Jie. The research on technologies of predicting next location based on historical trajectory[D]. Hangzhou:Hangzhou Dianzi University, 2015.(in Chinese)

[10] Xie K, Deng K, Zhou X. From trajectories to activities: a spatio-temporal join approach[C]∥Proceedings of the 2009 International Workshop on Location Based Social Networks.NY, US: ACM, 2009: 25-32.

[11] Agamennoni G, Nieto J, Nebot E. Mining GPS data for extracting significant places[C]∥IEEE International Conference on Robotics and Automation. NJ, US: IEEE, 2009: 855-862.

[12] Zheng Y, Zhang L Z, Xie X, et al. Mining interesting locations and travel sequences from GPS trajectories[C]∥Proceedings of the 18th International Conference on World Wide Web. NY, US: ACM, 2009: 791-800.

[13] Luo T, Zheng X W, Xu G L, et al. An improved DBSCAN algorithm to detect stops in individual trajectories[J]. ISPRS International Journal of Geo-Information, 2017, 6(3): 63.

[14] Ashbrook D, Starner T. Using GPS to learn significant locations and predict movement across multiple users[J]. Personal and Ubiquitous Computing, 2003, 7(5): 275-286.

[15] Palma A T, Bogorny V, Kuijpers B, et al. A clustering-based approach for discovering interesting places in trajectories[C]∥Proceedings of the 2008 ACM Symposium on Applied Computing. NY, US: ACM, 2008: 863-868.

[16] Zimmermann M, Kirste T, Spiliopoulou M. Finding stops in error-prone trajectories of moving objects with time-based clustering[M]. Berlin, Germany: Springer, 2009: 275-286.

InterestPointDetectionMethodBasedonDilationOperation

WANG Qing1,2,3， DING Chi-biao1,3， FU Kun1,2,3， REN Wen-juan1,2,3
(1.Institute of Electronics, Chinese Academy of Sciences, Beijing 100190, China; 2.Key Laboratory of Technology in GEO-Spatial Information Processing and Application System, Chinese Academy of Sciences, Beijing 100190, China; 3.School of Electronic, Electrical and Communication Engineering, University of Chinese Academy of Sciences, Beijing 100049, China)

An interest point detection method based on dilation operation (DMDO) is proposed to improve the efficiency and accuracy of interest point detection, in which binarization is used to filter the noise, and the dilation operation is used to replace the clustering approach to enhance the efficiency of algorithm. DMDO is applied to two datasets of open space-AMSA and IMIS3Days. Compared to Density-Based Spatial Clustering of Applications with Noise (DBSCAN) , the accuracy of DMDO is increased by 17.94% on dataset AMSA, and by 19.98% on dataset IMIS3Days, while the efficiency is improved by 6.63 times on dataset AMSA, and by 9.13 times on dataset IMIS3Days. Compared to Ordering Point To Identify the Cluster Structure (OPTICS), the accuracy of DMDO is increased by 20.04% on dataset AMSA, and by 16.60% on dataset IMIS3Days, while the efficiency is improved by 14.61 times on dataset AMSA, and by 42.19 times on dataset IMIS3Days. Experimental results demonstrate that, compared with traditional methods, DMDO has higher accuracy with less time overhead. DMDO is applicable to detect the interest points in the era of big data.

information processing technology; trajectory data mining; interest point detection; dilation operation; open space

2017-04-13

王清(1992—)，女，碩士研究生。E-mail: wangqing36@126.com

丁赤飚(1969—)，男，研究員，博士生導(dǎo)師。E-mail: cbding@mail.ie.ac.cn

TP181

A

1000-1093(2017)10-2041-07

10.3969/j.issn.1000-1093.2017.10.021