Copyright © 2005 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Permissions Dept, ACM Inc., fax +1 (212) 869-0481 or e-mail [email protected]. © 2005 ACM 0730-0301/05/0700-0677 $5.00 Efficient Content-Based Retrieval of Motion Capture DataMeinard M¨uller Tido R¨oder Michael ClausenUniversity of Bonn, Department of Computer Science III∗(a) (b) (c) (d) (e) (f) (g)Figure 1: Qualitative features describing geometric relations between the body points of a pose that are indicated by red and black markers.AbstractThe reuse of human motion capture data to create new, realistic mo-tions by applying morphing and blending techniques has become animportant issue in computer animation. This requires the identifi-cation and extraction of logically related motions scattered withinsome data set. Such content-based retrieval of motion capture data,which is the topic of this paper, constitutes a difficult and time-consuming problem due to significant spatio-temporal variationsbetween logically related motions. In our approach, we introducevarious kinds of qualitative features describing geometric relationsbetween specified body points of a pose and show how these fea-tures induce a time segmentation of motion capture data streams.By incorporating spatio-temporal invariance into the geometric fea-tures and adaptive segments, we are able to adopt efficient indexingmethods allowing for flexible and efficient content-based retrievaland browsing in huge motion capture databases. Furthermore, weobtain an efficient preprocessing method substantially acceleratingthe cost-intensive classical dynamic time warping techniques forthe time alignment of logically similar motion data streams. Wepresent experimental results on a test data set of more than one mil-lion frames, corresponding to 180 minutes of motion. The linearityof our indexing algorithms guarantees the scalability of our resultsto much larger data sets.CR Categories: I.3.7 [Computer Graphics]: Three-DimensionalGraphics and Realism—Animation; H.3 [Information Storage andRetrieval]: Information Search and RetrievalKeywords: motion capture, geometric feature, adaptive segmen-tation, indexing, retrieval, time alignment1 IntroductionThe generation of human motion capture data as used in data-drivencomputer animations is a time-consuming and expensive process.∗e-mail: {meinard, roedert, clausen}@cs.uni-bonn.deVarious editing and morphing techniques for the modification andadaptation of existing motion data [Bruderlin and Williams 1995;Witkin and Popovic 1995] or for the synthesis of new, realistic mo-tions from example motions [Giese and Poggio 2000; Pullen andBregler 2002; Kovar and Gleicher 2003] have been developed inthe last few years. Prior to reusing and processing motion capturematerial, one has to solve the fundamental problem of identifyingand extracting suitable motion clips from the database on hand. Indoing so, a user may describe the motion clips to be retrieved invarious ways at different semantic levels. One possible specifica-tion could be a rough textual description such as “a kick of the rightfoot followed by a punch.” Another query mode would involve ashort query motion clip, the task being to retrieve all clips in thedatabase containing parts or aspects similar to the query. This kindof problem is commonly referred to as content-based retrieval. Inthis paper, we present a prototypical system for content-based mo-tion retrieval, where the query consists of a motion clip as well as auser-specified selection of motion aspects to be considered in the re-trieval process. Unlike the work of Kovar and Gleicher [2004], ourtechnique does not support fully automatic “query-by-example,”since the user has to supply additional query-dependent input. Be-ing able to choose certain motion aspects, however, provides theuser with a high degree of flexibility, cf. the subsequent overview.The crucial point in content-based motion retrieval is the notion of“similarity” used to compare different motions. Intuitively, two mo-tions may be regarded as similar if they represent variations of thesame action or sequence of actions, see Kovar and Gleicher [2004].Here the variations may concern the spatial as well as the temporaldomain. For example, the two walking motions shown in Fig. 5 andFig. 6, respectively, may be perceived as similar even though theydiffer considerably in their respective speeds. In other words, log-ically similar motions need not be numerically similar, as is alsopointed out by Kovar and Gleicher [2004]. This may lead to in-complete and dissatisfying retrieval results when using similaritymeasures based on numerical comparison of spatial coordinates.Furthermore, the necessary warping of the time axis to establishframe correspondences is computationally expensive, making thiskind of technique infeasible for large data sets, see also Sect. 2.To bridge the semantic gap between logical similarity as per-ceived by humans and computable numerical similarity measures,we introduce new types of qualitative geometric features and in-duced motion segmentations, yielding spatio-temporal invarianceas needed to compare logically similar motions. This strategyhas far-reaching consequences regarding efficiency, flexibility andautomation in view of indexing, content-based retrieval and timealignment of motion capture data. The following overview summa-rizes the main contributions of this paper.6771.1 Overview1. Geometric Features: We introduce a class of boolean fea-tures expressing geometric relations between certain bodypoints of a pose. As an example of this kind of features, con-sider the test whether the right foot lies in front of or behindthe plane spanned by the left foot, the left hip joint and thecenter of the hip (the root), cf. Fig. 1 (a). Such geometric fea-tures are very robust to spatial variations and allow the identi-fication of logically corresponding events in similar