Non-Negative Kernel Sparse Coding for the Classification of Motion Data

Babak Hosseini, Felix Hülsmann, Mario Botsch, Barbara HammerarXiv 2019 · OpenReview

Abstract

We are interested in the decomposition of motion data into a sparse linear combination of base functions which enable efficient data processing. We combine two prominent frameworks: dynamic time warping (DTW), which offers particularly successful pairwise motion data comparison, and sparse coding (SC), which enables an automatic decomposition of vectorial data into a sparse linear combination of base vectors. We enhance SC as follows: an efficient kernelization which extends its application domain to general similarity data such as offered by DTW, and its restriction to non-negative linear representations of signals and base vectors in order to guarantee a meaningful dictionary. Empirical evaluations on motion capture benchmarks show the effectiveness of our framework regarding interpretation and discrimination concerns.

Introduction

Human motion data, captured via professional MOCAP or consumer devices like Kinect, presents significant processing challenges. It is typically high-dimensional, varies in duration, and often lacks semantic labels. The goal is to automatically identify the "building blocks" of movements in a way that is both computationally efficient and human-interpretable.

Existing approaches face two primary hurdles. First, temporal variability: motions like a "wave" gesture occur at different speeds and durations, making fixed-length vector models ineffective. Second, interpretability: standard Sparse Coding (SC) often utilizes negative coefficients, which lacks physical meaning in motion (one cannot "subtract" a movement). This research proposes a framework that bridges these gaps by combining Dynamic Time Warping (DTW) with non-negative sparse coding.

Methodology: LC-NNKSC

The proposed framework, Label-Consistent Non-Negative Kernel Sparse Coding (LC-NNKSC), introduces several key innovations:

  1. Kernelization via DTW: By employing a kernel function based on DTW distances, the model handles variable-length sequences by focusing on pairwise similarities rather than raw coordinates.
  2. Non-Negativity Constraints: Both dictionary atoms (base patterns) and sparse coefficients are restricted to non-negative values. This ensures a "parts-based" representation where complex motions are additive sums of simpler prototypes.
  3. Label Consistency (LC): A supervised term is added to the optimization objective to ensure that motions within the same class share similar sparse representations, enhancing classification performance.
  4. Optimization Algorithms: The authors developed NN-KOMP (Non-Negative Kernel Orthogonal Matching Pursuit) for sparse coding and NN-K-FISTA for dictionary updates to solve the resulting non-convex optimization problem.

Experimental Results

The framework was evaluated on four benchmarks: the CMU Motion Dataset, Cricket Umpire’s Signals, Articulatory Words (facial movements), and a specialized Squat Dataset.

Table 1: Comparison of classification accuracy (Acc) and reconstruction error (Rec. Err) across four datasets.

As shown in Table 1, LC-NNKSC consistently outperforms baseline methods such as LC-KKSVD, k-Nearest Neighbors (kNN), and Kernel-Kmeans. Notably, it achieved 100% accuracy on the Squat dataset and 90.91% on the CMU dataset. Furthermore, despite the non-negativity constraints, the reconstruction error remained remarkably low, demonstrating that negative coefficients are not necessary for accurate motion representation.

Interpretability and Sparsity

A core advantage of the non-negative approach is the resulting dictionary's interpretability. The model acts as a "parts-based" learner where dictionary atoms become class prototypes.

Table 2: Sparsity and discriminative power metrics for the learned dictionaries.

Table 2 highlights the high dictionary sparseness achieved by the model. In many cases, dictionary atoms were exclusively associated with a single motion class, making the classification process transparent. Sparsity serves as a natural semantic prior, forcing the model to identify recurring, meaningful signals that align with the underlying motion categories.

Conclusion

LC-NNKSC represents a significant advancement in motion analysis, moving away from "black box" models toward systems that provide physical prototypes for their classifications. While the $O(N^2)$ complexity of the DTW kernel matrix presents a scalability challenge for massive datasets, the framework's high accuracy and interpretability make it a powerful tool for understanding complex human movement. Future work may explore generative applications and further refinements for unsupervised category discovery.

Summary updated

Abstract

We are interested in the decomposition of motion data into a sparse linear combination of base functions which enable efficient data processing. We combine two prominent frameworks: dynamic time warping (DTW), which offers particularly successful pairwise motion data comparison, and sparse coding (SC), which enables an automatic decomposition of vectorial data into a sparse linear combination of base vectors. We enhance SC as follows: an efficient kernelization which extends its application domain to general similarity data such as offered by DTW, and its restriction to non-negative linear representations of signals and base vectors in order to guarantee a meaningful dictionary. Empirical evaluations on motion capture benchmarks show the effectiveness of our framework regarding interpretation and discrimination concerns.
BibTeX
@misc{hosseini2019non,
  author = {Babak Hosseini and Felix Hülsmann and Mario Botsch and Barbara Hammer},
  title = {{Non-Negative Kernel Sparse Coding for the Classification of Motion Data}},
  year = {2019},
  eprint = {1903.03891},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1903.03891},
}
Figure