More Web Proxy on the site http://driver.im/

research-article

Fast local and global similarity searches in large motion capture databases

Authors:

Björn Krüger,

Jochen Tautges,

Arno ZinkeAuthors Info & Claims

SCA '10: Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation

Pages 1 - 10

Published: 02 July 2010 Publication History

Abstract

Fast searching of content in large motion databases is essential for efficient motion analysis and synthesis. In this work we demonstrate that identifying locally similar regions in human motion data can be practical even for huge databases, if medium-dimensional (15--90 dimensional) feature sets are used for kd-tree-based nearest-neighbor-searches. On the basis of kd-tree-based local neighborhood searches we devise a novel fast method for global similarity searches. We show that knn-searches can be used efficiently within the problems of (a) "numerical and logical similarity searches", (b) reconstruction of motions from sparse marker sets, and (c) building so called "fat graphs", tasks for which previously algorithms with preprocessing time quadratic in the size of the database and thus only applicable to small collections of motions had been presented. We test our techniques on the two largest freely available motion capture databases, the CMU and HDM05 motion databases comprising more than 750 min of motion capture data proving that our approach is not only theoretically applicable but also solves the problem of fast similarity searches in huge motion databases in practice.

References

[1]

{AFO03} Arikan O., Forsyth D. A., O'Brien J. F.: Motion synthesis from annotations. ACM Transactions on Graphics 22, 3 (2003), 402--408. 3, 6

Digital Library

[2]

{AI08} Andoni A., Indyk P.: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51, 1 (2008), 117--122. 2

Digital Library

[3]

{BBK01} Böhm C., Berchtold S., Keim D. A.: Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases. ACM Comput. Surv. 33, 3 (2001), 322--373. 1, 2

Digital Library

[4]

{BCvdPP08} Beaudoin P., Coros S., van de Panne M., Poulin P.: Motion-motif graphs. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2008), Gross M., James D., (Eds.). 2, 3, 6

Digital Library

[5]

{Car04} Carnegie Mellon University Graphics Lab: CMU Motion Capture Database, 2004. mocap.cs.cmu.edu.2

[6]

{CH05} Chai J., Hodgins J. K.: Performance animation from low-dimensional control signals. ACM Trans. Graph. 24, 3 (2005), 686--696. SIGGRAPH 2005. 2, 3, 8, 9

Digital Library

[7]

{CH07} Chai J., Hodgins J. K.: Constraint-based motion optimization using a statistical dynamic model. ACM Transactions on Graphics 26, 3 (2007). SIGGRAPH 2007. 9

Digital Library

[8]

{CLRS01} Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.: Introduction to Algorithms. MIT Press, 2001. 6

Digital Library

[9]

{EMMT04} Egges A., Molet T., Magnenat-Thalmann N.: Personalised real-time idle motion synthesis. In 12th Pacific Conference on Computer Graphics and Applications (PG 2004) (2004), pp. 121--130. 2

Digital Library

[10]

{Fal96} Faloutsos C.: Searching Multimedia Databases by Content. Springer, 1996. 2

Digital Library

[11]

{FHP07} Faloutsos C., Hodgins J., Pollard N.: Database techniques with motion capture. In SIGGRAPH '07: ACM SIGGRAPH 2007 courses (San Diego, California, 2007), ACM, p. 1. 2

Digital Library

[12]

{HG07} Heck R., Gleicher M.: Parametric motion graphs. In I3D '07: Proceedings of the 2007 symposium on Interactive 3D graphics and games (New York, NY, USA, 2007), ACM Press, pp. 129--136. 2, 6, 9

Digital Library

[13]

{HJBC05} Hildenbrand D., J. Z., Bayro-Corrochano E.: Inverse kinematics computation in computer graphics and robotics using conformal geometric algebra. In International Conference on Clifford Algebras and their Applications (2005). 3

[14]

{HMF07} Hunt W., Mark W. R., Fussell D.: Fast and lazy build of acceleration structures from scene hierarchies. In IEEE Symposium on Interactive Ray Tracing (RT '07) (2007), pp. 47--54. 9

Digital Library

[15]

{KG04} Kovar L., Gleicher M.: Automated extraction and parameterization of motions in large data sets. ACM Transactions on Graphics 23, 3 (2004), 559--568. SIGGRAPH 2004. 1, 2, 3, 6, 8

Digital Library

[16]

{KGP02} Kovar L., Gleicher M., Pighin F.: Motion graphs. ACM Transactions on Graphics 21, 3 (2002), 473--482. SIGGRAPH 2002. 1, 2, 6

Digital Library

[17]

{KPZ*04} Keogh E., Palpanas T., Zordan V. B., Gunopulos D., Cardle M.: Indexing large human-motion databases. In VLDB '04: Proceedings of the Thirtieth international conference on Very large data bases (2004), VLDB Endowment, pp. 780--791. 1, 2

Digital Library

[18]

{LCR*02} Lee J., Chai J., Reitsma P. S. A., Hodgins J. K., Pollard N. S.: Interactive control of avatars animated with human motion data. In SIGGRAPH '02: Proceedings of the 29th annual conference on Computer graphics and interactive techniques (San Antonio, Texas, 2002), ACM Press, pp. 491--500. 1, 3

Digital Library

[19]

{MA06} Mount D. M., Arya S.: ANN: A Library for Approximate Nearest Neighbor Searching. Programming manual, Department of Computer Science, University of Maryland, College Park, Maryland, U.S.A., 2006. 4

[20]

{MP07} McCann J., Pollard N.: Responsive characters from motion fragments. ACM Transactions on Graphics 26, 3 (2007). SIGGRAPH 2007. 2, 6

Digital Library

[21]

{MR06} Müller M., Röder T.: Motion templates for automatic classification and retrieval of motion capture data. In SCA '06: Proceedings of the 2006 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2006), ACM Press, pp. 137--146. 2

Digital Library

[22]

{MRC05} Müller M., Röder T., Clausen M.: Efficient content-based retrieval of motion capture data. ACM Trans. Graph. 24, 3 (2005), 677--685. SIGGRAPH 2005. 2

Digital Library

[23]

{MRC*07} Müller M., Röder T., Clausen M., Eberhardt B., Krüger B., Weber A.: Documentation: Mocap Database HDM05. Computer Graphics Technical Report CG-2007-2, Universität Bonn, May 2007. www.mpi-inf.mpg.de/resources/HDM05. 2

[24]

{Mül07} Müller M.: Information Retrieval for Music and Motion. Springer, 2007. 6

Digital Library

[25]

{MW03} Myers J. L., Well A. D.: Research design and statistical analysis. Mahwah, N.J.: Lawrence Erlbaum Associates, 2003. 4

[26]

{MYHW08} Meng J., Yuan J., Hans M., Wu Y.: Mining motifs from human motion. In Eurographics 2008 -- Short Papers (2008), Mania K., Reinhard E., (Eds.), pp. 71--74. 2, 7

[27]

{Nar96} Nardelli E.: Distributed k-d trees. In Proceedings 16th Conference of Chilean Computer Science Society (SCCC '96) (1996), pp. 142--154. 9

[28]

{SH07} Safonova A., Hodgins J. K.: Construction and optimal search of interpolated motion graphs. ACM Transactions on Graphics 26, 3 (2007). SIGGRAPH 2007. 2, 6, 9

Digital Library

[29]

{SHP04} Safonova A., Hodgins J. K., Pollard N. S.: Synthesizing physically realistic human motion in low-dimensional, behavior-specific spaces. ACM Transactions on Graphics 23, 3 (2004), 514--521. SIGGRAPH 2004. 2, 3

Digital Library

[30]

{SO06} Shin H. J., Oh H. S.: Fat graphs: constructing an interactive character with continuous controls. In SCA '06: Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation (Aire-la-Ville, Switzerland, 2006), Eurographics Association, pp. 291--298. 2, 6, 9

Digital Library

[31]

{TGB00} Tolani D., Goswami A., Badler N. I.: Real-time inverse kinematics techniques for anthropomorphic limbs. Graph. Models Image Process. 62, 5 (2000), 353--388. 2, 3

Digital Library

[32]

{vBE09} van Basten B. J. H., Egges A.: Evaluating distance metrics for animation blending. In FDG '09: Proceedings of the 4th International Conference on Foundations of Digital Games (New York, NY, USA, 2009), ACM, pp. 199--206. 2

Digital Library

[33]

{WB03} Wang J., Bodenheimer B.: An evaluation of a cost metric for selecting transitions between motion segments. In SCA '03: Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation (Aire-la-Ville, Switzerland, Switzerland, 2003), Eurographics Association, pp. 232--238. 3

Digital Library

[34]

{WB08} Wang J., Bodenheimer B.: Synthesis and evaluation of linear motion transitions. ACM Trans. Graph. 27, 1 (2008), 1--15. 3

Digital Library

Cited By

Men QLeung H(2019)Retrieval of spatial---temporal motion topics from 3D skeleton dataThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-019-01690-x35:6-8(973-984)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00371-019-01690-x
Choi MKwon T(2019)Motion rankThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-018-1498-635:2(289-300)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00371-018-1498-6
Aristidou ACohen-Or DHodgins JChrysanthou YShamir A(2018)Deep motifs and motion signaturesACM Transactions on Graphics10.1145/3272127.327503837:6(1-13)Online publication date: 4-Dec-2018
https://dl.acm.org/doi/10.1145/3272127.3275038
Show More Cited By

Index Terms

Fast local and global similarity searches in large motion capture databases
1. Computing methodologies
  1. Computer graphics
    1. Animation
2. Information systems
  1. Information retrieval

Recommendations

Efficient motion retrieval in large motion databases
I3D '13: Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games

There has been a recent paradigm shift in the computer animation industry with an increasing use of pre-recorded motion for animating virtual characters. A fundamental requirement to using motion capture data is an efficient method for indexing and ...
Video de-interlacing by adaptive 4-field global/local motion compensated approach

A de-interlacing algorithm using adaptive 4-field global/local motion compensated approach is presented. It consists of block-based directional edge interpolation, same-parity 4-field motion detection, global/local motion estimation and compensation. ...
Efficient three-dimensional motion pattern retrieval in large motion capture databases

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCA '10: Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation

July 2010

256 pages

Conference Chairs:
François Faure
Grenoble University, INRIA, LJK-CNRS
,
Caroline Larboulette
Universidad Rey Juan Carlos, Madrid
,
Program Chairs:
Zoran Popović
University of Washington
,
Miguel Otaduy
Universidad Rey Juan Carlos, Madrid

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 02 July 2010

Check for updates

Qualifiers

Research-article

Funding Sources

Deutsche Forschungsgemeinschaft

Conference

SCA '10

Sponsor:

SIGGRAPH
EUROGRAPHICS

SCA '10: The ACM SIGGRAPH / Eurographics Symposium on Computer Animation 2010

July 2 - 4, 2010

Madrid, Spain

Acceptance Rates

SCA '10 Paper Acceptance Rate 24 of 56 submissions, 43%;

Overall Acceptance Rate 183 of 487 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
494
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Men QLeung H(2019)Retrieval of spatial---temporal motion topics from 3D skeleton dataThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-019-01690-x35:6-8(973-984)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00371-019-01690-x
Choi MKwon T(2019)Motion rankThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-018-1498-635:2(289-300)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00371-018-1498-6
Aristidou ACohen-Or DHodgins JChrysanthou YShamir A(2018)Deep motifs and motion signaturesACM Transactions on Graphics10.1145/3272127.327503837:6(1-13)Online publication date: 4-Dec-2018
https://dl.acm.org/doi/10.1145/3272127.3275038
Carreno-Medrano PGibet SMarteau P(2018)Perceptual Validation for the Generation of Expressive Movements from End-Effector TrajectoriesACM Transactions on Interactive Intelligent Systems10.1145/31509768:3(1-26)Online publication date: 5-Jul-2018
https://dl.acm.org/doi/10.1145/3150976
Sedmidubsky JElias PZezula P(2018)Effective and efficient similarity searching in motion capture dataMultimedia Tools and Applications10.1007/s11042-017-4859-777:10(12073-12094)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s11042-017-4859-7
Kruger BVogele AWillig TYao AKlein RWeber A(2017)Efficient Unsupervised Temporal Segmentation of Motion DataIEEE Transactions on Multimedia10.1109/TMM.2016.263503019:4(797-812)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TMM.2016.2635030
Bernard JDobermann EBögl MRöhlig MVögele AKohlhammer JAndrienko NSedlmair M(2016)Visual-interactive segmentation of multivariate time seriesProceedings of the EuroVis Workshop on Visual Analytics10.5555/3057675.3057684(31-35)Online publication date: 6-Jun-2016
https://dl.acm.org/doi/10.5555/3057675.3057684
Jiang FYang XFeng LCai YThalmann D(2016)Real-time full-body motion reconstruction and recognition for off-the-shelf VR devicesProceedings of the 15th ACM SIGGRAPH Conference on Virtual-Reality Continuum and Its Applications in Industry - Volume 110.1145/3013971.3013987(309-318)Online publication date: 3-Dec-2016
https://dl.acm.org/doi/10.1145/3013971.3013987
Andrews SHuerta IKomura TSigal LMitchell K(2016)Real-time Physics-based Motion Capture with Sparse SensorsProceedings of the 13th European Conference on Visual Media Production (CVMP 2016)10.1145/2998559.2998564(1-10)Online publication date: 12-Dec-2016
https://dl.acm.org/doi/10.1145/2998559.2998564
Wang ZFeng YQi TYang XZhang J(2016)Adaptive multi-view feature selection for human motion retrievalSignal Processing10.1016/j.sigpro.2014.11.015120:C(691-701)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1016/j.sigpro.2014.11.015
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents