An efficient search algorithm for motion data using weighted PCA

ABSTRACT

Good motion data is costly to create. Such an expense often makes the reuse of motion data through transformation and retargetting a more attractive option than creating new motion from scratch. Reuse requires the ability to search automatically and efficiently a growing corpus of motion data, which remains a difficult open problem. We present a method for quickly searching long, unsegmented motion clips for subregions that most closely match a short query clip. Our search algorithm is based on a weighted PCA-based pose representation that allows for flexible and efficient pose-to-pose distance calculations. We present our pose representation and the details of the search algorithm. We evaluate the performance of a prototype search application using both synthetic and captured motion data. Using these results, we propose ways to improve the application's performance. The results inform a discussion of the algorithm's good scalability characteristics.

REFERENCES

• 1: Okan Arikan , David A. Forsyth , James F. O'Brien, Motion synthesis from annotations, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 2: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Wu, An optimal algorithm for approximate nearest neighbor searching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.573-582, January 23-25, 1994, Arlington, Virginia, United States
• 3: Christopher M. Bishop, Neural networks for pattern recognition, Oxford University Press, Oxford, 1996
• 4: Jernej Barbič , Alla Safonova , Jia-Yu Pan , Christos Faloutsos , Jessica K. Hodgins , Nancy S. Pollard, Segmenting motion capture data into distinct behaviors, Proceedings of the 2004 conference on Graphics interface, p.185-194, May 17-19, 2004, London, Ontario, Canada
• 5: Armin Bruderlin , Lance Williams, Motion signal processing, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.97-104, September 1995 [doi>10.1145/218380.218421]
• 6: L. W. Campbell , D. A. Becker , A. Azarbayejani , A. F. Bobick , A. Pentland, Invariant features for 3-D gesture recognition, Proceedings of the 2nd International Conference on Automatic Face and Gesture Recognition (FG '96), p.157, October 14-16, 1996
• 7: {CKHP02} Chu S., Keogh E. J., Hart D., Pazzani M. J.: Iterative deepening dynamic time warping for time series. In SDM (2002).
• 8: {CVB*03} Cardle M., Vlachos M., Brooks S., Keogh E., Gunopulos D.: Fast motion capture matching with replicated motion editing. In SIGGRAPH 2003, Sketches and Applications (jul 2003), ACM Press.
• 9: Pascal Glardon , Ronan Boulic , Daniel Thalmann, PCA-Based Walking Engine Using Motion Capture Data, Proceedings of the Computer Graphics International (CGI'04), p.292-298, June 16-19, 2004 [doi>10.1109/CGI.2004.73]
• 10: F. Sebastin Grassia, Practical parameterization of rotations using the exponential map, Journal of Graphics Tools, v.3 n.3, p.29-48, 1 March 1998
• 11: {HRS94} Hollars M. G., Rosenthal D. E., Sherman M. A.: SD Fast User's Manual, 1994.
• 12: Charles E. Jacobs , Adam Finkelstein , David H. Salesin, Fast multiresolution image querying, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.277-286, September 1995 [doi>10.1145/218380.218454]
• 13: {Joh03} Johnson M. P.: Exploiting Quaternions to Support Expressive Interactive Character Motion. PhD thesis, Massachusettes Institute of Technology, 2003.
• 14: Lucas Kovar , Michael Gleicher, Flexible automatic motion blending with registration curves, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 15: Lucas Kovar , Michael Gleicher, Automated extraction and parameterization of motions in large data sets, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 16: {KGP02} Kovar L., Gleicher M., Pighin F.: Motion graphs, 2002.
• 17: Eamonn J. Keogh , Michael J. Pazzani, Scaling up Dynamic Time Warping to Massive Dataset, Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery, p.1-11, September 15-18, 1999
• 18: {KPZ*04} Keogh E., Palpanas T., Zordan V., Gunopulos D., Cardle M.: Indexing large human-motion databases. In VLDB 2004 (2004).
• 19: Yan Li , Tianshu Wang , Heung-Yeung Shum, Motion texture: a two-level statistical model for character motion synthesis, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 20: {McC94} McCloud S.: Understanding Comics. Perennial Currents, 1994.
• 21: IEEE MultiMedia, MPEG-7: The Generic Multimedia Content Description Standard, Part 1, IEEE MultiMedia, v.9 n.2, p.78-87, April 2002 [doi>10.1109/93.998074]
• 22: {Mou05} Mount D. M.: ANN Programming Manual, 2005.
• 23: Michael Neff , Eugene Fiume, Methods for exploring expressive stance, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028531]
• 24: {PG04} P. Glardon R. Boulic D. T.: A coherent locomotion engine extrapolating beyond experimental data. In CASA 2004 Proceedings (2004).
• 25: Sam Roweis, EM algorithms for PCA and SPCA, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.626-632, July 1998, Denver, Colorado, United States
• 26: {SL02} Skočaj D., Leonardis A.: Weighted incremental subspace learning. In Workshop on Cognitive Vision, proceedings (Zurich, Switzerland, September 19--20 2002).
• 27: Christian von Hardenberg , François Bérard, Bare-hand human-computer interaction, Proceedings of the 2001 workshop on Perceptive user interfaces, November 15-16, 2001, Orlando, Florida [doi>10.1145/971478.971513]
• 28: Dimitrios Gunopoulos, Discovering Similar Multidimensional Trajectories, Proceedings of the 18th International Conference on Data Engineering, p.673, February 26-March 01, 2002

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism