Supervised Descent Method for Solving Nonlinear Least Squares Problems in Computer Vision

Xuehan Xiong, Fernando De la TorrearXiv 2014 · OpenReview

TL;DR

This paper introduces the Supervised Descent Method (SDM), a novel approach for solving nonlinear least squares (NLS) problems common in computer vision. SDM learns "generic descent maps" from data, allowing it to efficiently optimize complex functions without needing to compute potentially problematic Jacobians or Hessians, achieving state-of-the-art results in tasks like facial feature detection.

What Problem Does This Paper Address?

Many computer vision tasks, such as aligning images, tracking objects, or estimating 3D poses, boil down to solving nonlinear least squares (NLS) optimization problems. Traditional methods like Newton's method are powerful but struggle with issues common in computer vision: functions that aren't smoothly differentiable (like those derived from SIFT or HoG features), and Hessian matrices that can be large and not positive definite, leading to unstable or slow convergence. These limitations make existing methods computationally expensive and less robust in real-world scenarios.

Methods

The core innovation is the Supervised Descent Method (SDM). Instead of relying on analytical derivatives (Jacobian and Hessian), SDM learns generic descent maps (DMs). These DMs are essentially learned average "descent directions" and scaling factors that guide the optimization process.

Here's how it works:

  • Training: SDM is trained in a supervised manner. For a given NLS problem, it samples initial parameter configurations and their corresponding optimal solutions. It then learns a sequence of DMs that iteratively move the initial parameters towards the optimal ones. This training process involves minimizing an expected loss function, which can often be solved efficiently.
  • Testing: During inference, SDM uses the learned DMs to iteratively update the parameters. Each update step involves applying a learned DM and a sample-specific component (e.g., the difference between the current prediction and the target). This avoids the need to compute Jacobians or Hessians at each step, making it significantly faster and more robust.
  • Relaxed and Generalized SDM: The paper also introduces variations:
  • Relaxed SDM: Learns a sequence of DMs, allowing for more flexible adaptation to complex optimization landscapes.
  • Generalized SDM: Addresses scenarios where the target (e.g., template image) might differ between training and testing, crucial for tasks like pose estimation.

Datasets

The paper evaluates SDM on several datasets:

  • Synthetic analytic functions: Used to demonstrate the theoretical convergence properties and compare with Newton's method.
  • Rigid tracking: Experiments were conducted on a public dataset featuring six different planar textures (mansion, sunset, Paris, wood, building, bricks) with various transformations.
  • Facial feature detection:
    • LFPW dataset: A dataset of faces with variations in pose, illumination, and expression.
  • LFW-A&C dataset: A subset of the LFW dataset with annotated facial landmarks.
  • Facial feature tracking:
    • RU-FACS dataset: Consists of 29 sequences of faces in a constrained environment.
  • Youtube Celebrities dataset: A public dataset of celebrity videos with significant pose variations and occlusions.
  • 3D Pose Estimation: Synthetic data generated by projecting 3D objects (cube, face, human body) under varying camera parameters and noise.

Key Insights and Ideas

  • Learning Optimization: The fundamental idea is to learn the optimization process itself, rather than relying solely on analytical methods. This allows SDM to adapt to the specific characteristics of computer vision problems.
  • Generic Descent Maps: The concept of learning "average" descent directions (DMs) is key. These maps encapsulate knowledge about the optimization landscape that is broadly applicable, making the method robust to variations.
  • Avoiding Derivatives: By learning DMs, SDM bypasses the computationally expensive and often unstable computation of Jacobians and Hessians, especially for non-differentiable features.
  • State-of-the-Art Performance: SDM achieves competitive or superior results across various challenging computer vision tasks, particularly in facial feature detection.
  • Robustness to Ill-Conditioning: SDM demonstrates better robustness than Newton's method on ill-conditioned functions where Newton's method might diverge or get stuck.

Key Results

  • Rigid Tracking: SDM outperformed the classical Lucas-Kanade (LK) tracker in 28 out of 30 sequences, showing particular strength in translation and robustness to illumination changes.
  • Facial Feature Detection: SDM achieved state-of-the-art results on the LFPW dataset (average error of 3.47 vs. 3.43 for a prior method) and comparable results on LFW-A&C (median alignment error of 2.7 vs. 2.8 for PRA).
  • Facial Feature Tracking: The SDM tracker never lost track in the RU-FACS dataset and demonstrated reliable tracking on the challenging Youtube Celebrities dataset, even with large pose variations and occlusions.
  • 3D Pose Estimation: SDM achieved comparable rotation accuracy to POSIT but significantly better translation accuracy, attributed to SDM's ability to handle perspective projection better than POSIT's scaled orthographic assumption.
  • Speed: SDM is significantly faster per iteration than Newton's method and comparable to or faster than other methods in practice, especially when derivative computations are avoided.

Limitations and Future Work

  • Local Convergence: The paper notes that the generic DM is guaranteed to exist and work well within a local neighborhood of the optimal parameters. Training with a very large range of parameters can lead to performance degradation.
  • Future Work: The authors suggest partitioning the output space into grids and training separate SDMs for each grid to handle larger parameter ranges and achieve global optimization. They also mention exploring SDM for other optimization problems.

Summary updated

Abstract

Many computer vision problems (e.g., camera calibration, image alignment, structure from motion) are solved with nonlinear optimization methods. It is generally accepted that second order descent methods are the most robust, fast, and reliable approaches for nonlinear optimization of a general smooth function. However, in the context of computer vision, second order descent methods have two main drawbacks: (1) the function might not be analytically differentiable and numerical approximations are impractical, and (2) the Hessian may be large and not positive definite. To address these issues, this paper proposes generic descent maps, which are average "descent directions" and rescaling factors learned in a supervised fashion. Using generic descent maps, we derive a practical algorithm - Supervised Descent Method (SDM) - for minimizing Nonlinear Least Squares (NLS) problems. During training, SDM learns a sequence of decent maps that minimize the NLS. In testing, SDM minimizes the NLS objective using the learned descent maps without computing the Jacobian or the Hessian. We prove the conditions under which the SDM is guaranteed to converge. We illustrate the effectiveness and accuracy of SDM in three computer vision problems: rigid image alignment, non-rigid image alignment, and 3D pose estimation. In particular, we show how SDM achieves state-of-the-art performance in the problem of facial feature detection. The code has been made available at www.humansensing.cs.cmu.edu/intraface.
BibTeX
@misc{xiong2014supervised,
  author = {Xuehan Xiong and Fernando De la Torre},
  title = {{Supervised Descent Method for Solving Nonlinear Least Squares Problems in Computer Vision}},
  year = {2014},
  eprint = {1405.0601},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1405.0601},
}
Figure