Rotation invariant distance measures for trajectories

ABSTRACT

For the discovery of similar patterns in 1D time-series, it is very typical to perform a normalization of the data (for example a transformation so that the data follow a zero mean and unit standard deviation). Such transformations can reveal latent patterns and are very commonly used in datamining applications. However, when dealing with multidimensional time-series, which appear naturally in applications such as video-tracking, motion-capture etc, similar motion patterns can also be expressed at different orientations. It is therefore imperative to provide support for additional transformations, such as rotation. In this work, we transform the positional information of moving data, into a space that is translation, scale and rotation invariant. Our distance measure in the new space is able to detect elastic matches and can be efficiently lower bounded, thus being computationally tractable. The proposed methods are easy to implement, fast to compute and can have many applications for real world problems, in areas such as handwriting recognition and posture estimation in motion-capture data. Finally, we empirically demonstrate the accuracy and the efficiency of the technique, using real and synthetic handwriting data.

REFERENCES

• 1: Helmut Alt , Kurt Mehlhorn , Hubert Wagener , Emo Welzl, Congruence, similarity and symmetries of geometric objects, Discrete & Computational Geometry, v.3 n.3, p.237-256, Jan., 1988 [doi>10.1007/BF02187910]
• 2: D. Berndt and J. Clifford. Using Dynamic Time Warping to Find Patterns in Time Series. In Proc. of KDD Workshop, 1994.
• 3: L. Paul Chew , Michael T. Goodrich , Daniel P. Huttenlocher , Klara Kedem , Jon M. Kleinberg , Dina Kravets, Geometric pattern matching under Euclidean motion, Computational Geometry: Theory and Applications, v.7 n.1-2, p.113-124, Jan. 1997 [doi>10.1016/0925-7721(95)00047-X]
• 4: Scott D. Cohen , Leonidas J. Guibas, Partial matching of planar polylines under similarity transformations, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.777-786, January 05-07, 1997, New Orleans, Louisiana, United States
• 5: S. Gold, A. Rangarajan, C.-P. Lu, S. Pappu, and E. Mjolsness. New algorithms for 2d and 3d point matching: Pose estimation and correspondence. In Pattern Recognition, vol. 31, no. 8, 1998.
• 6: André P. Guéziec , Xavier Pennec , Nicholas Ayache, Medical Image Registration Using Geometric Hashing, IEEE Computational Science & Engineering, v.4 n.4, p.29-41, October 1997 [doi>10.1109/99.641607]
• 7: Tamer Kahveci , Ambuj K. Singh , Aliekber Gürel, Similarity Searching for Multi-Attribute Sequences, Proceedings of the 14th International Conference on Scientific and Statistical Database Management, p.175, July 24-26, 2002 [doi>10.1109/SSDM.2002.1029718]
• 8: E. Keogh. Exact indexing of dynamic time warping. In Proc. of VLDB, pages 406--417, 2002.
• 9: E. Keogh, K. Chakrabarti, M. Pazzani, and S. Mehrotra. Dimensionality reduction for fast similarity search in large time series databases. In Journal of Knowledge and Information Systems, 2000.
• 10: J. B. A. Maintz and M. A. Viergever. A survey of medical image registration. In Medical Image Analysis, 1998.
• 11: W. Rodriguez, M. Last, A. Kandel, and H. Bunke. 3-dimensional curve similarity using string matching. In 3rd International Symposium on Intelligent Manufacturing Systems, Sakarya, Turkey, 2001.
• 12: B. Scassellati. Retrieving images by 2d shape: a comparison of computation methods with human perceptual judgments. In Storage and Retrieval for Image and Video Databases (SPIE), 1994.
• 13: J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science v.290 no.5500, pages 2319--2323, 2000.
• 14: Michail Vlachos , Marios Hadjieleftheriou , Dimitrios Gunopulos , Eamonn Keogh, Indexing multi-dimensional time-series with support for multiple distance measures, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956777]
• 15: Dimitrios Gunopoulos, Discovering Similar Multidimensional Trajectories, Proceedings of the 18th International Conference on Data Engineering, p.673, February 26-March 01, 2002
• 16: Yunyue Zhu , Dennis Shasha, Warping indexes with envelope transforms for query by humming, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872780]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
rotation invariance, time warping, trajectories