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