“Automated extraction and parameterization of motions in large data sets” by Kovar and Gleicher

Large motion data sets often contain many variants of the same kind of motion, but without appropriate tools it is difficult to fully exploit this fact. This paper provides automated methods for identifying logically similar motions in a data set and using them to build a continuous and intuitively parameterized space of motions. To find logically similar motions that are numerically dissimilar, our search method employs a novel distance metric to find “close” motions and then uses them as intermediaries to find more distant motions. Search queries are answered at interactive speeds through a precomputation that compactly represents all possibly similar motion segments. Once a set of related motions has been extracted, we automatically register them and apply blending techniques to create a continuous space of motions. Given a function that defines relevant motion parameters, we present a method for extracting motions from this space that accurately possess new parameters requested by the user. Our algorithm extends previous work by explicitly constraining blend weights to reasonable values and having a run-time cost that is nearly independent of the number of example motions. We present experimental results on a test data set of 37,000 frames, or about ten minutes of motion sampled at 60 Hz.

1. AGRAWAL, R., FALOUTSO, C., AND SWAMI, A. 1993. Efficient similarity search in sequence databases. In Proceedings of the 4th International Conference on Foundations of Data Organizations and Algorithms (FODO), Springer Verlag, 69–84. Google ScholarDigital Library
2. ALLEN, B., CURLESS, B., AND POPOVIĆ, Z. 2002. Articulated body deformation from range scan data. ACM Transactions on Graphics 21, 3, 612–619. Google ScholarDigital Library
3. ARIKAN, O., AND FORSYTHE, D. A. 2002. Interactive motion generation from examples. ACM Transactions on Graphics 21, 3, 483–490. Google ScholarDigital Library
4. ARIKAN, O., FORSYTH, D. A., AND O’BRIEN, J. 2003. Motion synthesis from annotations. ACM Transactions on Graphics 22, 3, 402–408. Google ScholarDigital Library
5. BÖHM, C., BERCHTOLD, S., AND KEIM, D. A. 2001. Searching in high-dimensional spaces: index structures for improving the performance of multimedia databases. ACM Computing Surveys 33, 3, 322–373. Google ScholarDigital Library
6. BRUDERLIN, A., AND WILLIAMS, L. 1995. Motion signal processing. In Proceedings of ACM SIGGRAPH 1995, Annual Conference Series, 97–104. Google ScholarDigital Library
7. CARDLE, M., VLACHOS, M., BROOKS, S., KEOGH, E., AND GUNOPULOS, D. 2003. Fast motion capture matching with replicated motion editing. In Proceedings of SIGGRAPH 2003 Technical Sketches & Applications.Google Scholar
8. CASTELLI, V., AND BERGMAN, L. 2001. Image Databases: Search and Retrieval of Digital Imagery. John Wiley & Sons. Google ScholarDigital Library
9. CHAN, K., AND FU, W. 1999. EFFICIENT time series matching by wavelets. In Proceedings of the 15th IEEE International Conference on Data Engineering, 126–133. Google ScholarDigital Library
10. FALOUTSOS, C., RANGANATHAN, M., AND MANOLOPOULOS, Y. 1994. Fast subsequence matching in time-series databases. In Proceedings of 1994 ACM SIGMOD International Conference on Management of Data, 419–429. Google ScholarDigital Library
11. FUNKHOUSER, T., MIN, P., KAZHDAN, M., CHEN, J., HALDERMAN, A., AND DOBKIN, D. 2003. A search engine for 3D models. ACM Transactions on Graphics 22, 1, 83–105. Google ScholarDigital Library
12. GROCHOW, K., MARTIN, S., HERTZMANN, A., AND POPOVIĆ, Z. 2004. Style-based inverse kinematics. ACM Transactions on Graphics 23, 3. Google ScholarDigital Library
13. GUTTMAN, A. 1984. R-trees: a dynamic index structure for spatial searching. In Proceedings of 1984 ACM SIGMOD International Conference on Management of Data, 47–57. Google ScholarDigital Library
14. JENKINS, O. C., AND MATARIĆ, M. 2002. Deriving action and behavior primitives from human motion data. In Proceedings of 2002 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-2002), 2551–2556.Google ScholarCross Ref
15. KEOGH, E., CHAKRABARTI, K., PAZZANI, M., AND MEHROTRA. 2001. Locally adaptive dimensionality reduction for indexing large time series databases. In Proceedings of 2001 ACM SIGMOD International Conference on Management of Data, 151–162. Google ScholarDigital Library
16. KIM, T., PARK, S., AND SHIN, S. 2003. Rhythmic-motion synthesis base on motion-beat analysis. ACM Transactions on Graphics 22, 3, 392–401. Google ScholarDigital Library
17. KOVAR, L., AND GLEICHER, M. 2003. Flexible automatic motion blending with registration curves. In Proceedings of ACM SIGGRAPH/Eurographics Symposium on Computer Animation 2003. Google ScholarDigital Library
18. KOVAR, L., GLEICHER, M., AND PIGHIN, F. 2002. Motion graphs. ACM Transactions on Graphics 21, 3, 473–482. Google ScholarDigital Library
19. LEE, J., CHAI, J., REITSMA, P., HODGINS, J., AND POLLARD, N. 2002. Interactive control of avatars animated with human motion data. ACM Transactions on Graphics 21, 3, 491–500. Google ScholarDigital Library
20. LIU, F., ZHUAN, Y., WU, F., AND PAN, Y. 2003. 3D motion retrieval with motion index tree. Computer Vision and Image Understanding 92, 2–3, 265–284. Google ScholarDigital Library
21. PARK, S. I., SHIN, H. J., AND SHIN, S. Y. 2002. On-line locomotion generation based on motion blending. In Proceedings of ACM SIGGRAPH/Eurographics Symposium on Computer Animation 2002. Google ScholarDigital Library
22. ROSE, C., COHEN, M., AND BODENHEIMER, B. 1998. Verbs and adverbs: multidimensional motion interpolation. IEEE Computer Graphics and Application 18, 5, 32–40. Google ScholarDigital Library
23. ROSE, C., SLOAN, P., AND COHEN, M. 2001. Artist-directed inverse-kinematics using radial basis function interpolation. Computer Graphics Forum 20, 3.Google ScholarCross Ref
24. ROWEIS, S. T., AND SAUL, L. K. 2000. Nonlinear dimensionality reduction by locally linear embedding. Science 290, 5500, 2323–2326.Google Scholar
25. TENENBAUM, J. B., DE SILVA, V., AND LANGFORD, J. C. 2000. A global geometric framework for nonlinear dimensionality reduction. Science 290, 5500, 2319–2323.Google Scholar
26. UNUMA, M., ANJYO, K., AND TEKEUCHI, T. 1995. Fourier principles for emotion-based human figure animation. In Proceedings of ACM SIGGRAPH 95, Annual Conference Series, 91–96. Google ScholarDigital Library
27. VELTKAMP, R. C., BURKHARDT, H., AND KRIEGEL, H. P. 2001. State-of-the-Art in Content-Based Image and Video Retrieval. Kluwer Academic Publishers.Google Scholar
28. VLACHOS, M., HADJIELEFTHERIOU, M., GUNOPULOS, D., AND KEOGH, E. 2003. Indexing multi-dimensional time-series with support for multiple distance measures. In 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 216–225. Google ScholarDigital Library
29. WANG, J., AND BODENHEIMER, B. 2003. An evaluation of a cost metric for selecting transitions between motion segments. In Proceedings of ACM SIGGRAPH/Eurographics Symposium on Computer Animation 2003. Google ScholarDigital Library
30. WILEY, D., AND HAHN, J. 1997. Interpolation synthesis of articulated figure motion. IEEE Computer Graphics and Application 17, 6, 39–45. Google ScholarDigital Library
31. ZORDAN, V., AND HODGINS, J. 2002. Motion capture-driven simulations that hit and react. In Proceedings of ACM SIGGRAPH/Eurographics Symposium on Computer Animation 2002. Google ScholarDigital Library