以矩形交集偵測路徑相似度

Measuring trajectory similarity via moving rectangle intersection detection

李泳翰(Li, Yung Han)

指導教授 ： 李哲榮

國立清華大學/電機資訊學院/資訊工程學系/碩士(2016年)

摘要

相似度測量在軌跡分析中是一門重要的分類，因為它可以作為很多進階應用上
的基礎，例如搜尋相似度，軌跡叢聚和軌跡分類。而發現共通的子軌跡在空間
和時間上的接近程度是相當有用的應用。在這篇論文中我們將會調查兩個軌跡
之間的相似度背後的意義。不像傳統的相似度測量，我們將會提出一個新的方
法去計算兩個軌跡之間的相似度。我們將這個方法稱為以矩形交集偵測路徑相
似度(MRID)。這個方法主要有兩個優勢，第一個是匹配的方式是線段對線段而
不是傳統方式的點對點，所以表達相似度並不會用距離來表達。第二個是在壓
縮軌跡之後仍能保持大部分的相似軌跡對。對於這個方法我們主要有三個流
程，首先我們將所有軌跡用方柱體來表示，然後，對每一對軌跡對，我們找出
它們的交集的體積並計算出來，最後，我們藉由那些交集體積定義新的相似度
測量。
在我們的實驗中，我們使用實地測量的GPS 數據去評估我們的方法的有效性。
實驗結果表明：（1）在未壓縮的軌跡的情況下，MRID 的精度比LCSS 還高，
（2）MRID 可以在軌跡壓縮的情況計算相似度，（3）MRID 可以在線性時間內運
行。

關鍵字

軌跡分析 ； 相似度衡量 ； 移動物件

並列摘要

Similarity measurement is an important problem in trajectory analysis because
it serves as a foundation for many applications, such as trajectory search, cluster-
ing, and classication. Previously, most methods treat a trajectory as a sequence
of points, and use point-to-point matching methods to measure the similarity of
trajectories. In this thesis, we model a trajectory as a sequence of moving rect-
angles along the time axis. Each moving rectangle creates an oblique rectangular
column, aka a cuboid, in the three dimensional space spanned by the x-y axes and
the time domain. The volume of the intersection between the cuboids formed from
two sequence of moving rectangles is used as the similarity measurement between
two trajectories. We developed an effective algorithm, called Moving Rectangle In-
tersection Detection (MRID), to calculate the intersections. MRID runs linear time
in terms of number of trajectory points, and can be integrated with trajectory com-
pression algorithms to achieve even faster execution time. Experiments that use real
GPS data show that MRID has better accuracy and performance than the Longest
Common Subsequence (LCSS) method, which is a representative algorithm in the
point based methods.

並列關鍵字

Trajectory analysis ； Similarity measure ； Moving objects

參考文獻

and similar parts of trajectories. In Proceedings of the 17th ACM SIGSPATIAL

International Conference on Advances in Geographic Information Systems, GIS

tions Workshops, pages 1{5, May 2010.

in moving object trajectories.

Arnold P. Boedihardjo. Computing similarity between a pair of trajectories.