Fast Training of Pose Detectors in the Fourier Domain

João F. Henriques, Pedro Martins, Rui F. Caseiro, Jorge BatistaNeurIPS 2014

Introduction

In computer vision, objects rarely appear in a single "standard" pose. To build robust systems, researchers often use data augmentation, creating "virtual samples" by rotating, scaling, or flipping images. While this makes models more robust, it creates a massive computational burden: training a separate classifier for every possible pose is slow, and the resulting dataset is highly redundant because the samples are just transformed versions of each other.

This paper introduces a mathematical framework to accelerate the training of pose detectors by orders of magnitude. By generalizing the "Fourier trick"—previously used only for translations—to any cyclic transformation (like rotation or walking cycles), the authors demonstrate how to train multiple pose-specific classifiers simultaneously in the Fourier domain without sacrificing accuracy.

Methods and Key Insights

Existing "fast" methods exploited the fact that cyclic translations create circulant matrices, which can be diagonalized using the Discrete Fourier Transform (DFT). However, it wasn't clear if this "Fourier trick" could work for more complex changes, like a car rotating in a satellite image or a pedestrian’s legs moving through a walking cycle.

The authors propose a cyclic orthogonal model for image transformations.

Illustration of cyclic transformations and their feature representations
  1. The Generalization: They show that if a transformation is cyclic (returning to the start after $s$ steps) and orthogonal (preserving the image's "energy" or norm), the resulting Gram matrix—which stores the similarity between all pairs of transformed images—is circulant. The "aha moment" is realizing that while the pixels don't shift linearly like a translation, the relationships between transformed versions of an image follow a circulant pattern.
  2. The Dual Problem: While the raw data matrix itself isn't circulant for rotations, its representation in the "dual space" (used in Ridge Regression and SVMs) is. This allows the authors to move the entire optimization problem into the Fourier domain.
  3. Simultaneous Training: Instead of training one detector at a time, their closed-form solution allows them to train an entire ensemble of pose-specific classifiers (e.g., one for 0°, 10°, 20°, etc.) at essentially the same computational cost as training a single one.
  4. Implicit Transformation: Remarkably, the algorithm doesn't need to "know" the math behind the transformation. It only needs the transformed images (either virtually generated or from natural pose annotations). You don't need a perfect mathematical model of a "walking cycle." As long as you have a sequence of images representing the cycle, the Fourier-based optimization can digest it.
  5. Negative Samples are "Free": The authors found a clever shortcut for negative samples (background images). Since a background patch doesn't have a "pose," it can be treated as constant across all transformations. In the Fourier domain, a constant signal only exists at the zero-frequency (DC) component, allowing the algorithm to ignore negative samples in almost all subproblems, further boosting speed.

Experiments and Results

The authors evaluated their method on three distinct tasks:

  • Google Earth: Satellite imagery for car detection, focusing on planar rotation (30 virtual rotations per sample).
  • TUD-Campus & TUD-Crossing: Pedestrian datasets used to model the non-rigid deformation of a walking cycle.
  • KITTI: A popular autonomous driving benchmark used here to test out-of-plane rotations (viewing cars from different angles in a street scene).

The proposed "Fourier training" achieved performance comparable to standard, "naive" training methods but was 29x to 107x faster.

  • Speed: On the TUD pedestrian dataset, training with Support Vector Regression (SVR) dropped from 40.5 seconds (standard) to just 0.1 seconds (Fourier).
  • Accuracy: Average Precision (AP) remained nearly identical. For example, on Google Earth, the Fourier method achieved 73.0% AP compared to the standard 73.2%.
  • Robustness: Even for difficult out-of-plane rotations in KITTI—which stretch the assumptions of the model—the speedup remained massive (15s vs 454s) with only a slight dip in precision.

Limitations and Future Work

The method relies on three main assumptions: linearity, orthogonality, and cyclicity.

  • Interpolation Artifacts: Standard image rotation uses interpolation, which isn't perfectly linear or orthogonal, though the authors found that simple renormalization (ensuring all samples have the same $L^2$ norm) fixes most issues in practice.
  • Non-Cyclic Poses: Not all transformations are cyclic (e.g., scaling or zooming). The authors suggest that these might be approximated using cyclic shifts, similar to how previous work handled translation.
  • Complex Viewpoints: Out-of-plane rotations (like seeing the side vs. the front of a car) involve parts of the object appearing and disappearing, which violates the "orthogonal" assumption. While the method still works, its performance lead over standard methods is smaller in these cases.

The authors suggest that future work could involve composing multiple transformations (e.g., simultaneous rotation and scale) or scaling the method to even larger, more diverse datasets.

Summary updated

BibTeX
@inproceedings{henriques2014fast,
  author = {João F. Henriques and Pedro Martins and Rui F. Caseiro and Jorge Batista},
  title = {{Fast Training of Pose Detectors in the Fourier Domain}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure