We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Elastic Translation Invariant Matching of Trajectories.
- Authors
Michail Vlachos; George Kollios; Dimitrios Gunopulos
- Abstract
Abstract We investigate techniques for analysis and retrieval of object trajectories. We assume that a trajectory is a sequence of two or three dimensional points. Trajectory datasets are very common in environmental applications, mobility experiments, video surveillance and are especially important for the discovery of certain biological patterns. Such kind of data usually contain a great amount of noise, that makes all previously used metrics fail. Therefore, here we formalize non-metric similarity functions based on the Longest Common Subsequence (LCSS), which are very robust to noise and furthermore provide an intuitive notion of similarity between trajectories by giving more weight to the similar portions of the sequences. Stretching of sequences in time is allowed, as well as global translating of the sequences in space. Efficient approximate algorithms that compute these similarity measures are also provided. We compare these new methods to the widely used Euclidean and Dynamic Time Warping distance functions (for real and synthetic data) and show the superiority of our approach, especially under the strong presence of noise. We prove a weaker version of the triangle inequality and employ it in an indexing structure to answer nearest neighbor queries. Finally, we present experimental results that validate the accuracy and efficiency of our approach.
- Subjects
SECURITY systems; ALGORITHMS; ELECTRONIC surveillance; NOISE
- Publication
Machine Learning, 2005, Vol 58, Issue 2-3, p301
- ISSN
0885-6125
- Publication type
Article
- DOI
10.1007/s10994-005-5830-9