3D trajectory matching by pose normalization

ABSTRACT

Recent technological advances have made it possible to collect large amounts of 3D trajectory data. Such data play an essential role in numerous applications and are becoming increasingly important in mobile computing. One of the fundamental challenges in many of these application areas is the assessment of similarity between trajectories. As objects moving in a 3D space may often exhibit a similar motion pattern but may differ in location, orientation, and scale, the similarity assessment method employed must be invariant to these seven degrees of freedom. Previous work has addressed this problem primarily through local measures, such as curvature and torsion and has mostly concentrated on 2D trajectory data. This paper introduces a novel non iterative 3D trajectory matching framework that is translation, rotation, and scale invariant. We achieve this through the introduction of a pose normalization process that is based on physical principles, which incorporates both spatial and temporal aspects of trajectory data. We also introduce a new shape signature that utilizes the invariance that is achieved through pose normalization. The proposed scheme was tested both on simulated data and on real world data and has shown to offer improved robustness compared to local measures.

REFERENCES

• 1: Donald J. Berndt , James Clifford, Finding patterns in time series: a dynamic programming approach, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 2: R. G. Brown and P. Y. C. Hwang. Introduction to random signals and applied kalman filtering. John Wiley & Sons, New York, 3rd edition edition, 1997.
• 3: 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
• 4: H. Eglowstien. Reach out and touch your data. BYTE, pages 283--290, July 1990.
• 5: M. Elad, A. Tal, and S. Ar. Directed search in a 3D objects database using svm. Technical report, HP Labs. August 23, 2000.
• 6: B. Graham. Using an accelerometer sensor to measure human hand motion. Master thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 2000.
• 7: M. S. Grewal, L. R. Weill, and A. P. Andrews. Global positioning system, inertial navigation, and integration. John Wiley & Sons, New York, NY, 2001.
• 8: S. Hettich and S. D. Bay. The textscUCI textscKDD archive {http://kdd.ics.uci.edu}. Irvine, CA: University of California, Department of Information and Computer Science, 1999.
• 9: A. R. Ismail and S. S. Asfour. Discrete wavelet transform: a tool in smoothing kinematic data. Journal of Biomechanics, 32:317--321, 1999.
• 10: N. Kehtarnavaz , J. P. deFigueiredo, A 3-D Contour Segmentation Scheme Based on Curvature and Torsion, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.5, p.707-713, September 1988 [doi>10.1109/34.6780]
• 11: Eamonn J. Keogh , Michael J. Pazzani, Scaling up dynamic time warping for datamining applications, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.285-289, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347153]
• 12: M. Koertgen, G.-J. Park, M. Novotni, and R. Klein. 3D shape matching with 3D shape contexts. 2003.
• 13: Similarity Search for Multidimensional Data Sequences, Proceedings of the 16th International Conference on Data Engineering, p.599, February 28-March 03, 2000
• 14: M. Lipschultz. Differential Geometry. Schaum's Outlines Series. McGraw-Hill, New York, 1969.
• 15: D. McNeill. Hand and mind: what gestures reveal about thought. The University of Chicago Press, 1992. 416 pages.
• 16: W. Rodriguez, M. Last, A. Kandel, and H. Bunke. 3-dimensional curve similarity using string matching. Robotics and Autonomous Systems, 49(2004):165--172, 2004.
• 17: R. J. Stone. Position and orientation sensing in virtual environments. Sensor Review, 16(1):40--46, 1996.
• 18: David J. Sturman , David Zeltzer, A Survey of Glove-based Input, IEEE Computer Graphics and Applications, v.14 n.1, p.30-39, January 1994 [doi>10.1109/38.250916]
• 19: Michail Vlachos , D. Gunopulos , Gautam Das, Rotation invariant distance measures for trajectories, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014144]
• 20: M. Vlachos, D. Gunopulos, and G. Kollios. Robust similarity measures for mobile object trajectories. pages 721--726, Aix-en-Provence, France, 2002.
• 21: M. Vlachos, M. Hadjieleftheriou, D. Gunopulos, and E. Keogh. Indexing multi-dimensional time-series with support for multiple distance measures. Washington, DC, 2003.
• 22: Dimitrios Gunopoulos, Discovering Similar Multidimensional Trajectories, Proceedings of the 18th International Conference on Data Engineering, p.673, February 26-March 01, 2002
• 23: M. Vlachos, J. Lin, E. Keogh, and D. Gunopulos. A wavelet-based anytime algorithm for k-means clustering of time series. In proceedings of Workshop on Clustering High Dimensionality Data and Its Applications at the 3rd SIAM International Conference on Data Mining, San Francisco, CA, 2003.
• 24: D. Vranic and D. Saupe. 3D shape descriptor based on 3D fourier transform. pages 271--274, Budapest, Hungary, 2001.
• 25: D. V. Vranic, D. Saupe, and J. Richter. Tools for 3D-object retrieval: Karhune-loeve transform and spherical harmonics. Cannes, France, 2001.
• 26: D. Zhang and G. Lu. Review of shape representation and description techniques. Pattern Recognition, 37:1--19, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms

Keywords:
3D trajectory, matching, pose normalization, spatiotemporal analysis