Exhaustive Linearization for Robust Camera Pose and Focal Length Estimation

Adrián Peñate Sánchez, Juan Andrade-Cetto, Francesc Moreno-NoguerIEEE TPAMI 2013 · DOI

Abstract

This paper introduces UPnP (Uncalibrated Perspective-n-Point), a robust $O(n)$ algorithm designed to estimate both camera pose and focal length from 3D-to-2D point correspondences. By systematically exploring subsets of linearized equations—a technique termed "exhaustive linearization"—the method achieves accuracy nearly identical to calibrated solvers while remaining significantly faster than iterative global optimizers.

Introduction

In computer vision, the Perspective-n-Point (PnP) problem is a fundamental task for applications such as augmented reality and structure-from-motion. It requires determining the camera's position and orientation relative to a set of 3D world points based on their 2D projections. While efficient solutions exist for calibrated cameras, real-world scenarios—such as processing crowdsourced photos or using cameras with auto-zoom—often involve unknown focal lengths, leading to the UPnP problem.

Figure 1: Geometry of the PnP problem, illustrating the transformation between the world coordinate system and the camera coordinate system via rotation R and translation t.

Existing UPnP solutions typically fall into two categories: minimal solvers, which are fast but highly sensitive to noise, and iterative global optimizers, which are accurate but computationally prohibitive for real-time use. This research proposes a non-iterative, $O(n)$ solution that maintains robustness against the pixel inaccuracies inherent in real-world data.

Methodology

The UPnP algorithm builds upon the EPnP (Efficient PnP) framework, which represents 3D points as weighted sums of four control points. When the focal length ($f$) is unknown, the resulting mathematical system involves degree-4 polynomials. Standard linearization techniques often fail in noisy environments because a global least-squares fit can be skewed by poor equation subsets.

Exhaustive Exploration

The core innovation of this work is the handling of the linearized system through exhaustive search:

  • Exhaustive Linearization ($N=2$): For smaller null spaces, the algorithm evaluates all 18 possible triplets of equations in closed form, selecting the one that minimizes reprojection error.
  • Exhaustive Relinearization ($N=3$): To manage the combinatorial explosion in more complex cases (over 500,000 sets), the algorithm utilizes a pre-ordered search based on offline training, checking only the most promising candidates at runtime.
  • Iterative Refinement: A final, rapid Gauss-Newton optimization (typically ~10 iterations) is applied to polish the results.

Experimental Evaluation

The method was rigorously tested across synthetic and real-world datasets:

  • Synthetic Data: Tested with Gaussian noise up to 15 pixels across various focal lengths and point distributions (planar and non-planar).
  • Real Image Sequences: Evaluated using controlled box captures with varying focal lengths and ground truth from EXIF data.
  • Flickr/Google Earth Dataset: Tested on "in the wild" images of Cheverny Castle matched against 3D models.
Figure 5: Comparative analysis showing the percentage of successful estimations and error distributions for standard Least Squares (LSQ) versus the proposed exhaustive approach across varying noise levels.

Key Results and Insights

  • Accuracy and Speed: UPnP's pose estimation accuracy is nearly indistinguishable from calibrated EPnP. It is orders of magnitude faster than global optimizers like $L_\infty$, and while DLT is faster, it lacks the necessary accuracy for robust applications.
  • Robustness to Noise: The paper demonstrates that in noisy systems, the "best" solution is often found within specific subsets of equations rather than through a global average. By prioritizing geometric consistency (e.g., points must be in front of the camera) over pure algebraic least-squares, UPnP achieves superior stability.
  • Handling Ambiguity: The method remains stable even as the camera model approaches the orthographic limit (high focal length) by naturally increasing the dimensionality of its solution space.

Conclusion

UPnP provides a highly efficient and robust bridge between minimal solvers and heavy iterative optimization. While it remains sensitive to noise with very small point sets (near the minimum of 6), its parallelizable nature and ability to handle unknown focal lengths make it a powerful tool for modern computer vision pipelines. Future work may extend this exhaustive approach to estimate other intrinsic parameters like the principal point.

Summary updated

BibTeX
@article{sanchez2013exhaustive,
  author = {Adrián Peñate Sánchez and Juan Andrade-Cetto and Francesc Moreno-Noguer},
  title = {{Exhaustive Linearization for Robust Camera Pose and Focal Length Estimation}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2013},
  doi = {10.1109/tpami.2013.36},
}
Figure