Finding Syntactic Structures from Human Motion Data

Jong Pil Park, Kang Hoon Lee, Jehee LeeComputer Graphics Forum 2011 · DOI

TL;DR

This paper introduces a novel method for analyzing and synthesizing human motion by learning context-free grammars directly from motion capture data. This allows for the automatic discovery of "syntactic structures" within movements, enabling the generation of new, diverse motions that preserve the original motion's inherent patterns and flow.

What Problem Does This Paper Address?

Synthesizing realistic and varied human motion from limited motion capture data is a long-standing challenge in computer graphics. While existing methods can create smooth transitions and blend motions, they often struggle to capture and reproduce the higher-level, meaningful "syntactic structures" that define activities like dance or sports. Simply rearranging motion frames can lead to sequences that lack the natural flow and combinatorial logic of well-formed actions. This paper aims to bridge this gap by automatically learning these underlying structures from raw motion data, enabling more intelligent and semantically coherent motion synthesis.

Methods

The core of the approach involves two main stages:

  1. Identifying Terminal Symbols (Segmentation and Clustering):
    • The input motion is first segmented into a series of subsequences, representing elementary actions.
  2. An optimization process is employed to find the best segmentation and assign these segments to a predefined number of "terminal symbols." This involves balancing the repetitiveness of symbols (how often they appear) with their clarity (how distinct the associated movements are).
  3. This optimization uses a two-level heuristic search: a genetic algorithm for coarse segmentation and simulated annealing for fine-tuning.
  4. The Partitioning Around Medoids (PAM) algorithm is used to cluster similar motion segments into groups, each representing a terminal symbol.
  5. Learning Grammars (Grammar Induction):
    • Once the motion is encoded as a string of terminal symbols, a context-free grammar is learned from this string.
  6. Instead of learning a single grammar for the entire string (which would only reproduce the original motion), the authors partition the string into substrings and learn a grammar that can represent multiple instances. This allows for flexibility and the generation of novel sequences.
  7. The alignment-based learning (ABL) algorithm, a standard in computational linguistics, is adapted for this purpose. The key challenge here is finding an optimal partitioning of the string into "sentences" (substrings) that leads to the most compact and flexible grammar, evaluated using a minimum description length principle.

Finally, Motion Synthesis is achieved by generating new strings from the learned grammar and replacing each terminal symbol with a corresponding motion segment, stitching them together sequentially.

Datasets

The paper demonstrates its approach on a variety of human motion datasets, including:

  • Break-dancing
  • Boxing
  • Basketball
  • Locomotion (mentioned in the abstract)

The authors do not introduce new datasets but rather apply their method to existing, diverse motion capture data to showcase its generality.

Key Insights and Ideas

  • Motion as Language: The fundamental insight is treating human motion as a form of language, with elementary actions as "words" (terminal symbols) and their combinations as "sentences" governed by grammatical rules. This linguistic analogy provides a powerful framework for understanding and generating complex motion.
  • Automatic Discovery of Structure: The method automatically discovers hierarchical syntactic structures in motion data without requiring manual annotation or predefined labels. This is crucial for complex activities where these structures are not immediately obvious.
  • Grammar for Synthesis: Learning a context-free grammar allows for the generation of novel motion sequences that not only appear smooth but also adhere to the learned "rules" of movement, leading to more semantically meaningful and plausible animations.
  • Balancing Repetitiveness and Clarity: The optimization for identifying terminal symbols highlights the trade-off between making symbols common (repetitive) and making them distinct (clear), a critical aspect for effective symbolic representation of motion.

Key Results

  • The approach successfully learned grammars from diverse motion types (break-dancing, boxing, basketball), capturing their underlying syntactic structures.
  • Synthesized motions reproduced the characteristic patterns of the original motions, demonstrating the preservation of learned syntactic structures.
  • Qualitative comparisons suggest that motions synthesized by their grammar-based approach are more natural and less "disharmonious" than those produced by simpler finite state machine models, which lack hierarchical structure.
  • The paper provides experimental data (Table 1) showing the number of frames, segments, terminals, and rules learned for different motion types and varying numbers of terminals. For instance, break-dancing with 20 terminals resulted in an average of 128.6 rules.

Limitations and Future Work

  • Symbolic vs. Perceptual Equivalence: A key limitation acknowledged is the potential mismatch between symbolic representation and perceptual equivalence. A single symbol might represent perceptually different movements, or vice-versa, which could affect the naturalness of synthesized motions. Future work could investigate perceptually meaningful clustering criteria.
  • Spatial and Temporal Constraints: The current grammar-based approach does not directly allow users to impose specific spatial or temporal constraints (e.g., target locations, trajectories). While interactive editing is possible, this is a significant limitation compared to methods like motion graphs. The authors plan to explore genetic programming to address this by handling tree-based solution spaces.
  • Number of Terminals (K): Determining the optimal number of terminal symbols (K) is currently done through visual analysis and is considered a balancing factor between clarity and flexibility. Developing a more generalized rule for selecting K is a future research direction.
  • Training Data Size: For certain motions (e.g., basketball), a limited number of training examples might lead to grammars that generate more cyclic references than expected, resulting in more shots than intended in the basketball example. This suggests that the quantity and diversity of training data are important for learning robust grammars.

Summary updated

BibTeX
@article{park2011finding,
  author = {Jong Pil Park and Kang Hoon Lee and Jehee Lee},
  title = {{Finding Syntactic Structures from Human Motion Data}},
  journal = {Computer Graphics Forum},
  year = {2011},
  doi = {10.1111/j.1467-8659.2011.01968.x},
}
Figure