Sparse Coding for Learning Interpretable Spatio-Temporal Primitives

Taehwan Kim, Gregory Shakhnarovich, Raquel UrtasunNeurIPS 2010 · OpenReview

Overview

This paper introduces a novel sparse coding framework designed to extract interpretable, structured "building blocks"—or primitives—from human motion data. By formulating the problem as a tensor factorization with specific temporal and structural constraints, the authors' approach outperforms traditional sparse coding and matching pursuit algorithms. It successfully recovers the underlying patterns of movement even in the presence of heavy noise or missing data.

The Challenge: Temporal Structure in Motion

In computer vision, sparse coding has proven highly effective for learning "dictionaries" of natural images, essentially finding the fundamental patches (like edges or textures) that can be combined to recreate a picture. However, applying this directly to human motion is challenging.

Motion is not just a sequence of independent frames; it possesses a deep temporal structure. Previous attempts to find "motor synergies" (the primitives of movement) often focused on static poses or used greedy algorithms like Matching Pursuit, which struggle with optimization and often produce noisy, uninterpretable results. The critical gap identified by the authors is the lack of a framework capable of learning primitives that are both spatially meaningful (capturing which joints move together) and temporally consistent (capturing how that movement evolves over time).

Methodology: Constrained Tensor Factorization

To address these limitations, the authors move beyond simple matrix factorization and cast the problem as a tensor factorization. To ensure the learned primitives are genuinely interpretable, they introduce three specific types of constraints to the optimization process:

  1. Tensor Group Norms: Instead of merely optimizing for "sparsity" (having few active elements), the model uses group norms. This encourages the system to utilize a small, concise number of primitives and inherently prefers shorter primitives over unnecessarily long ones.
  2. Smoothness Constraints: Human motion is naturally fluid. The model penalizes high "curvature" in the learned dictionary elements, ensuring the resulting primitives resemble natural, continuous movement rather than jagged, high-frequency noise.
  3. Diagonal Activation Constraint: This is a critical innovation. In traditional sparse coding, an activation can flicker on and off erratically. The authors impose a structural constraint ($H_{i,j,k} = H_{i,j+1,k+1}$) that forces a primitive, once triggered, to remain active with constant strength for its entire duration. If a "step" primitive begins, the model is forced to follow through with the complete step.
Comparison of learned primitives (W) and activations (H) across different methods. Our approach yields smooth primitives and clear diagonal activations.

The optimization is solved via alternate minimization: the algorithm fixes the dictionary ($W$) to solve for activations ($H$), and then vice versa. While the overall problem is non-convex, each sub-step is convex and converges reliably.

Datasets and Evaluation

The researchers evaluated their approach using the CMU Motion Capture (mocap) dataset, focusing on walking sequences (multiple cycles from a single subject) and running sequences (data from different subjects to test generalization). They utilized Principal Component Analysis (PCA) to reduce the high-dimensional 59D joint data into lower-dimensional spaces for rigorous testing and visualization.

Key Findings and Results

  • Structure Outperforms Pure Sparsity: Standard sparse coding often overfits to noise because it has too much representational freedom. By forcing the model to adhere to temporal rules via the diagonal constraint, the proposed model naturally ignores noise, as noise does not follow these structured temporal patterns.
  • Robustness to Noise: In experiments injected with Gaussian noise, the proposed method maintained a significantly lower reconstruction error than the baselines. Standard sparse coding, in particular, failed by attempting to "code" the noise itself.
  • Superior Recovery and Initialization Independence: Compared to Matching Pursuit (MP) and standard Sparse Coding (SC), the proposed method was the only one capable of recovering the "ground truth" primitives and their correct timing in synthetic tests. Furthermore, unlike MP, which is highly sensitive to initialization, the tensor approach proved robust, reaching high-quality solutions whether initialized with random noise or smooth curves.
  • "Hallucinating" Missing Data: Because the model learns the underlying shape of a movement primitive, it can accurately reconstruct a sequence even if large segments of the data are missing, effectively filling in the blanks using the learned temporal structure.
Reconstruction error across varying noise levels (variance). The proposed approach (black line) maintains lower error compared to baselines.

Limitations and Future Work

The authors note that their method currently assumes a maximum fixed length for primitives, although the group norm penalty helps mitigate this limitation in practice. Additionally, the alternate minimization approach finds a local minimum rather than a guaranteed global one, though empirical results suggest these local minima are highly effective.

For future work, the authors propose applying these spatio-temporal dictionary techniques to video data. This could enable the learning of "dynamic textures" or fundamental visual actions directly from raw video streams, expanding the technique far beyond skeletal mocap data.

Summary updated

Abstract

Sparse coding has recently become a popular approach in computer vision to learn dictionaries of natural images. In this paper we extend sparse coding to learn interpretable spatio-temporal primitives of human motion. We cast the problem of learning spatio-temporal primitives as a tensor factorization problem and introduce constraints to learn interpretable primitives. In particular, we use group norms over those tensors, diagonal constraints on the activations as well as smoothness constraints that are inherent to human motion. We demonstrate the effectiveness of our approach to learn interpretable representations of human motion from motion capture data, and show that our approach outperforms recently developed matching pursuit and sparse coding algorithms.
BibTeX
@inproceedings{kim2010sparse,
  author = {Taehwan Kim and Gregory Shakhnarovich and Raquel Urtasun},
  title = {{Sparse Coding for Learning Interpretable Spatio-Temporal Primitives}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=HkWgAIbO-S},
}

Loading related content...

Figure