UTSM: A Trajectory Similarity Measure Considering Uncertainty Based on an Amended Ellipse Model
Abstract
:1. Introduction
- We propose an amended ellipse model derived from [4] that could better describe the uncertainty in a trajectory by dynamically computing the model’s shape parameters based on the motion features of each segment of the trajectory.
- We present a new similarity measure based on the model, called the Uncertain Trajectory Similarity Measure (UTSM). Validated by experiments on both synthetic data and real-world data, UTSM shows a better ability to compare similarity between trajectories, and it is also more robust to noise and outliers and more tolerant of different sample frequencies and asynchronous sampling.
2. Preliminaries and Problem Definition
2.1. Basic Concepts
- Spatiotemporal TrajectoryA space-time trajectory is a continuous curve formed by the motion of a moving object in Euclidean space over a certain period. The morphology of the trajectory can be accurately described by a continuous function. However, in reality, the spatial position of the moving object is generally recorded by a sensor at a fixed or random frequency. The object’s trajectory is usually represented by a sequence of positions containing spatial and temporal information, such as:
- Interpolation ErrorSince sensor recorded data are a sequence of sampling points that are not continuous in either time or space, the sampling points are generally connected in chronological order to describe the overall morphology of the trajectory. The data gap between adjacent sampling points is usually filled by linear interpolation, and the trajectory is transformed into a polygonal line. Interpolation is essentially an estimate and approximation of missing data and will inevitably introduce uncertainty in the gap between adjacent sampling points. The error introduced by this procedure is called Interpolation Error (InE) in this paper.
- Positioning ErrorDue to the accuracy limit of the positioning sensors or different signal intensities of different areas, the positioning data of the sampling points in a trajectory generally have a certain amount of error. This is also called measurement error. The mean spatial accuracy of a standard GPS receiver is near two meters horizontally at a 95% confidence interval [5] and worse in occluded areas because of the weak signal. In this paper, this kind of error is defined as Positioning Error (PoE).
- Trajectory SimilarityA similarity measure or similarity function is generally a real valued function that quantifies the similarity between two objects. Trajectory similarity refers to the degree of similarity between a pair of trajectories, including their spatiotemporal position, shape trend, motion characteristics, etc., which together can measure the overall similarity of their movement. Distance is a typical similarity measure, such as Euclidean distance, Hausdorff distance, Frechet distance, etc. However, distance is inversely proportional to similarity. The smaller the distance between two trajectories, the greater their similarity. An artificially defined similarity model can also be used to express the similarity between trajectories. In practical applications, similarity metrics are often normalized to the interval of for heterogeneous comparison.The performance of different trajectory similarity measures will be further discussed in Section 3.
2.2. Problem Statement
3. Related Work
3.1. Spatiotemporal Trajectory Data Models
3.2. Uncertainty in Spatiotemporal Trajectories
3.3. Trajectory Similarity Measures
3.3.1. Geometric Distance Metric
3.3.2. Time Based Distance Metric
3.3.3. Similarity Measures that Consider Uncertainty
4. Proposed Approach
4.1. Amended Ellipse Model
4.1.1. Initial Model without Positioning Error
- If a segment has roughly the same direction as both its neighbors, its b will be very small, and the eccentricity would be rather large, i.e., the segment’s area of uncertainty is a narrow ellipse (Figure 7), which is consistent with our usual perception that an object moving in a straight line tends to have smaller location uncertainty. For the similarity measure proposed in the following part, these “straight” kinds of curves tends to have less similarity with each other because of the smaller area of uncertainty.
- A segment with large turning angles to its neighbors will have a bigger b, contributing to a smaller eccentricity and a wider ellipse (Figure 8). The phenomenon is also consistent with the intuitive perception that an object moving at sharp angles tends to have greater location uncertainty. For the proposed similarity measure, these “winding” kind of curves have a greater tendency to have greater similarity with each other as a result of the bigger overlap** area of adjacent uncertainty extents.
4.1.2. Model Considering Positioning Error
4.2. Uncertain Trajectory Similarity Measure
- Every match between P and Q will have a positive effect on .
- A continuous match will bring an additional increase in .
- A mismatch has a non-positive effect on , i.e., no effect or a negative effect.
4.3. Algorithms
Algorithm 1: shape_estimator. |
|
Algorithm 2: UTSM_calculator. |
|
5. Experimental Evaluation
- evaluate the effectiveness of UTSM in measuring the similarity between trajectories.
- validate the robustness of UTSM to outliers, different sampling rates, and asynchronous sampling.
5.1. Experiment Setup
- Marine Cadastre: This maritime AIS dataset records approximately 30 attributes for 150,000 ships around the U.S. territory with a frequency of one GPS reading per two to 10 seconds. Each trajectory contained various numbers of anchor points ranging from 10 to 3000.
- T-Drive dataset: This is comprised of bare-bone trajectories extracted from real track data of New York taxi trips. The sample data we used contained more than 20,000 trajectories. Each trajectory contained 100 to 500 anchor points.
- Simulated trajectories with outliers: We added some outlier points to the original real-world trajectories
- Simulated trajectories with different sampling rates: We carried out resampling operations with different intervals based on selected real trajectories.
- Artificial asynchronous trajectories: We manually sampled points asynchronously from the sinusoidal curve at irreducible frequencies.
5.2. Evaluation and Discussion
5.2.1. Computational Efficiency
5.2.2. Effectiveness
5.2.3. Robustness to Outliers
5.2.4. Tolerance to Different Sampling Rates
5.2.5. Tolerance to Asynchronous Sampling
5.2.6. Summary
6. Conclusions and Future Work
Supplementary Materials
Author Contributions
Notation | Definition |
---|---|
Maximum velocity of a moving object | |
t | Time interval between two consecutive points |
Euclidean distance between point pand point q | |
InE | Interpolation error |
PoE | Positioning error |
E( | Elliptical uncertain area of a segment, which is also the projection on a 2D location plane of the corresponding bead body. |
E(P) | The union area of all the ellipses obtained from every pair of consecutive points. |
S(P, Q) | Similarity between trajectory P and Q |
NS(P, Q) | Normalized similarity between trajectory P and Q |
Offset | 5 | 10 | 20 | 50 | 100 | 200 |
---|---|---|---|---|---|---|
Hausdorff | 0.0855 | 0.0437 | 0.0221 | 0.0089 | 0.0044 | 0.0022 |
Frechet | 0.0855 | 0.0437 | 0.0221 | 0.0089 | 0.0044 | 0.0022 |
DTW | 0.0003 | 0.0001 | 7.4E-5 | 3.3E-5 | 1.8E-5 | 9.4E-6 |
LCSS | 0.9906 | 0.9625 | 0.9031 | 0.8187 | 0.7562 | 0.6875 |
ERP | 0.0003 | 0.0001 | 7.0E-5 | 2.8E-5 | 1.4E-5 | 7.0E-6 |
EDR | 0.9906 | 0.9625 | 0.9125 | 0.8656 | 0.7968 | 0.7281 |
Area | 4.1E-6 | 2.0E-6 | 1.0E-6 | 4.1E-7 | 1.0E-7 | 1.0E-7 |
Simple | 0.4556 | 0.3235 | 0.1270 | 0.0566 | 0.0286 | 0.0171 |
UTSM | 0.2831 | 0.2091 | 0.0020 | 0.0010 | 0.0004 | 0.0002 |
Measures | Effectiveness | Robustness | ||
---|---|---|---|---|
Outlier | Sampling Frequency | Asynchronous Sampling | ||
Hausdorff | √ | |||
Frechet | √ | |||
DTW | √ | |||
LCSS | √ | √ | √ | |
ERP | ||||
EDR | √ | |||
Area | ||||
Simple | √ | √ | √ | |
UTSM | √ | √ | √ | √ |
© 2019 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
Share and Cite
Guo, N.; Shekhar, S.; **ong, W.; Chen, L.; **g, N. UTSM: A Trajectory Similarity Measure Considering Uncertainty Based on an Amended Ellipse Model. ISPRS Int. J. Geo-Inf. 2019, 8, 518. https://doi.org/10.3390/ijgi8110518
Guo N, Shekhar S, **ong W, Chen L, **g N. UTSM: A Trajectory Similarity Measure Considering Uncertainty Based on an Amended Ellipse Model. ISPRS International Journal of Geo-Information. 2019; 8(11):518. https://doi.org/10.3390/ijgi8110518
Chicago/Turabian StyleGuo, Ning, Shashi Shekhar, Wei **ong, Luo Chen, and Ning **g. 2019. "UTSM: A Trajectory Similarity Measure Considering Uncertainty Based on an Amended Ellipse Model" ISPRS International Journal of Geo-Information 8, no. 11: 518. https://doi.org/10.3390/ijgi8110518