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.
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.
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