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