Canonical Time Warping for Alignment of Human Behavior

Feng Zhou, Fernando De la TorreNeurIPS 2009 · OpenReview

Overview

Aligning time-series data is a fundamental challenge in scientific disciplines ranging from computer vision to robotics. Consider the task of comparing two people walking: one individual might have longer strides, while the other walks at a faster pace; furthermore, one might be recorded from a side angle while the other is filmed from the front.

To address these complex alignment issues, researchers have introduced Canonical Time Warping (CTW). CTW is a novel framework designed to align human behavior data—such as motion capture sequences or facial expressions—across different subjects and viewpoints. By elegantly combining the spatial flexibility of Canonical Correlation Analysis (CCA) with the temporal flexibility of Dynamic Time Warping (DTW), CTW can synchronize complex sequences even when they exhibit different feature dimensions or significant stylistic variations.

The Challenge of Spatio-Temporal Alignment

Existing methods for aligning time-series data typically struggle with one of two primary obstacles:

  1. Temporal Variability: Standard spatial alignment methods cannot effectively handle changes in speed or "warped" time across sequences.
  2. Spatial and Feature Variability: Standard temporal methods, like Dynamic Time Warping (DTW), generally require the data to exist in the same coordinate system or possess the exact same number of features.

The authors identified a critical gap: there is a need for a unified approach to find a common "latent space" where two different signals can be aligned both in terms of what is happening (spatial) and when it happens (temporal).

Methodology: CTW and LCTW

The core contribution of this paper is Canonical Time Warping (CTW), described as a direct and clean extension of two classic algorithms:

  • Canonical Correlation Analysis (CCA): Traditionally used to find the linear relationship between two sets of variables, CCA acts as a spatial transformer in CTW, projecting different features into a common coordinate system.
  • Dynamic Time Warping (DTW): A well-known algorithm used for finding the optimal alignment between two sequences that vary in speed.

How CTW Works: CTW minimizes a least-squares objective function that simultaneously solves for two sets of parameters:

  1. Projection Matrices ($V_x, V_y$): These matrices "rotate" and "scale" the features so they match spatially.
  2. Warping Matrices ($W_x, W_y$): These matrices "stretch" or "compress" the time axis to match temporally.

To handle more complex scenarios, the authors also introduce Local Canonical Time Warping (LCTW). While standard CTW applies a single, global transformation to an entire sequence, LCTW allows for multiple local spatial deformations. This is crucial for long, complex sequences where a subject's movement style might change mid-action.

Datasets and Evaluation

The researchers evaluated CTW and LCTW on three distinct types of data to test its robustness and versatility:

  1. Synthetic Data: 3D spatio-temporal signals with added noise were used to test the algorithm's robustness against irrelevant features.
  2. CMU-Multimodal Activity Database (CMU-MMAC): Motion capture data of subjects cooking. This involved complex 60-dimensional feature vectors representing 20 body joints.
  3. RU-FACS Database: Video data of 29 subjects performing facial expressions. The researchers used 18 landmarks around the mouth (36D vectors) to align specific "AU12" events (smiling).
Examples of the motion capture (left) and facial expression (right) data used to evaluate CTW.

Key Insights

  • Inherent Feature Selection: One of the most significant findings is that CTW effectively performs feature selection. In synthetic experiments, CTW successfully ignored noisy dimensions that led standard DTW astray, "learning" which parts of the data were relevant for alignment.
  • Cross-Dimensional Alignment: Because CTW utilizes CCA-style projections, it can align signals of entirely different dimensionalities. For example, it could theoretically align a 3D accelerometer signal with a 60D motion capture signal.
  • The "Stochastic Selection" Trade-off: In LCTW, the authors propose a stochastic process to balance time warping and spatial transformation. This prevents the model from "cheating" by over-warping space to compensate for temporal lags, or vice versa.

Results

The proposed methods demonstrated significant improvements over existing baselines:

  • Superior Accuracy: In synthetic tests, both CTW and LCTW achieved significantly lower alignment errors compared to standard DTW, Derivative DTW (DDTW), and Iterative Motion Warping (IMW).
  • Better Peak Alignment: In the facial expression experiments, the alignment paths produced by CTW were much closer to manually labeled "peak" frames (e.g., the height of a smile) than those produced by DTW.
  • Visual Synchronization: Qualitative results on motion capture data showed that CTW could synchronize subjects even when their physical proportions and movement styles differed significantly, producing highly natural-looking overlays of the two subjects.

Limitations and Future Work

While powerful, the framework has a few limitations. The optimization for CTW is non-convex, meaning the algorithm could potentially get stuck in a sub-optimal local minimum. The authors mitigate this using specific initialization strategies (like PCA), but it remains a theoretical hurdle. Additionally, LCTW introduces several hyperparameters (such as the number of local bases and regularization weights) that were manually set for these experiments, suggesting a need for automated parameter selection in future iterations. Finally, the alternating optimization scheme is computationally more complex than a single pass of standard DTW.

Summary updated

Abstract

Alignment of time series is an important problem to solve in many scientific disciplines. In particular, temporal alignment of two or more subjects performing similar activities is a challenging problem due to the large temporal scale difference between human actions as well as the inter/intra subject variability. In this paper we present canonical time warping (CTW), an extension of canonical correlation analysis (CCA) for spatio-temporal alignment of the behavior between two subjects. CTW extends previous work on CCA in two ways: (i) it combines CCA with dynamic time warping for temporal alignment; and (ii) it extends CCA to allow local spatial deformations. We show CTWs effectiveness in three experiments: alignment of synthetic data, alignment of motion capture data of two subjects performing similar actions, and alignment of two people with similar facial expressions. Our results demonstrate that CTW provides both visually and qualitatively better alignment than state-of-the-art techniques based on dynamic time warping.
BibTeX
@inproceedings{zhou2009canonical,
  author = {Feng Zhou and Fernando De la Torre},
  title = {{Canonical Time Warping for Alignment of Human Behavior}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=S1bDlFbOZB},
}
Figure