Revisiting Sampson Approximations for Geometric Estimation Problems

Felix Rydell, Angélica Torres, Viktor LarssonCVPR 2024 · DOI · arXiv

Overview

The Sampson approximation is a ubiquitous tool in computer vision, used to efficiently estimate geometric errors in model fitting. Despite its popularity, a rigorous theoretical understanding of its accuracy has been lacking. This paper addresses this gap by deriving the first explicit bounds on the Sampson error, transforming it from an engineering heuristic into a mathematically grounded technique.

The Challenge of Geometric Error

In computer vision, fitting a model (such as an essential matrix) to noisy measurements (like point correspondences) requires minimizing the geometric error. This error represents the smallest perturbation needed for the measurements to satisfy the model's constraints perfectly. However, calculating the true geometric error is often computationally prohibitive. For instance, in two-view epipolar geometry, it involves finding the roots of a degree-6 polynomial.

To circumvent this, researchers frequently employ the Sampson error, a first-order approximation that linearizes the constraints. While widely adopted due to its speed and empirical success, its theoretical properties and failure modes have remained largely unexamined.

Sampson Error as a Linearization Scheme

The authors analyze the Sampson approximation through the lens of optimization, showing it is equivalent to the length of a single Gauss-Newton step from the noisy measurement toward the constraint manifold.

Geometric interpretation of the Sampson error as a linearization of the constraint surface.

The core contribution of this work is the derivation of explicit error bounds. By analyzing the relationship between the model's curvature (Hessian) and its gradient (Jacobian), the authors prove that the Sampson error serves as a reliable upper bound on the geometric error, provided the model is sufficiently linear in the local region. For problems involving multiple constraints, such as three-view geometry, they advocate for a "less is more" approach—using a minimal subset of independent constraints to maintain approximation stability.

Empirical Validation and Results

The theoretical framework was validated using standard benchmarks, including IMC Phototourism, MegaDepth, and 7Scenes. The experiments covered tasks such as two-view pose refinement, vanishing point estimation, and absolute pose estimation.

Comparison of Sampson error and symmetric epipolar error against the true geometric error.

Key findings include:

  • Superior Accuracy: In two-view pose estimation, the Sampson error consistently outperformed other common metrics like the symmetric epipolar error, providing a much closer approximation to the true geometric distance.
  • Significant Speedup: For complex 2D/3D reprojection tasks, the Sampson approximation was approximately 4x faster than full non-linear optimization (2.4ms vs. 10.1ms) while maintaining nearly identical accuracy.
  • Tight Theoretical Bounds: Tests on vanishing point estimation showed that the ratio between Sampson and geometric error remained extremely close to 1 across hundreds of thousands of test cases, confirming the tightness of the derived bounds.

Key Insights and Future Work

The "tightness" of the Sampson approximation is fundamentally determined by the ratio between the model's curvature and its gradient. In regions where the constraint surface is nearly flat or the gradient is steep, the Sampson error is nearly indistinguishable from the true geometric error.

While the current theory provides a robust framework for quadratic constraints, future work is needed to address non-complete intersections where constraints do not reduce dimensionality as expected. Additionally, the authors suggest exploring automated methods for selecting optimal constraint subsets in complex multi-view scenarios to further enhance stability and performance.

Summary updated

BibTeX
@inproceedings{rydell2024revisiting,
  author = {Felix Rydell and Angélica Torres and Viktor Larsson},
  title = {{Revisiting Sampson Approximations for Geometric Estimation Problems}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2024},
  doi = {10.1109/cvpr52733.2024.00477},
}
Figure