An Efficient Algebraic Solution to the Perspective-Three-Point Problem

Tong Ke; Stergios Roumeliotis

Source-linked AI summary

An Efficient Algebraic Solution to the Perspective-Three-Point Problem

Tong Ke, Stergios Roumeliotis

arXiv:1701.08237v1Jan 28, 2017cs.CV

TL;DR

P3P estimates camera position and orientation from bearing observations of three known features. This paper solves for orientation algebraically before position, and reports better speed, accuracy, and robustness than recent alternatives.

Problem
P3P asks for camera pose from observations of known points; its minimal three-point case is often used with RANSAC to remove outliers.
Source: §1 · p. 1
Method
The approach eliminates camera position and feature distances, then algebraically solves for camera orientation using a quartic polynomial.
Source: §1 · p. 1
Results
The method outperforms in speed, accuracy, and robustness to close-to-singular cases.
Source: §4 · p. 6
Takeaways & Limitations
The approach provides a closed-form P3P solution that avoids computing feature distances first and avoids numerically unstable tangent or cotangent functions.
Source: §4 · p. 6
Some simplified expressions require lengthy algebraic derivations that the paper omits due to space limitations.
Source: §2.2 · p. 3

Abstract

from arXiv · show

In this work, we present an algebraic solution to the classical perspective-3-point (P3P) problem for determining the position and attitude of a camera from observations of three known reference points. In contrast to previous approaches, we first directly determine the camera's attitude by employing the corresponding geometric constraints to formulate a system of trigonometric equations. This is then efficiently solved, following an algebraic approach, to determine the unknown rotation matrix and subsequently the camera's position. As compared to recent alternatives, our method avoids computing unnecessary (and potentially numerically unstable) intermediate results, and thus achieves higher numerical accuracy and robustness at a lower computational cost. These benefits are validated through extensive Monte-Carlo simulations for both nominal and close-to-singular geometric configurations.

1. INTRODUCTION

P3P estimates camera pose from known point observations, but prior formulations can incur costly computations and numerical error. This work solves directly for camera orientation and reports gains in speed, accuracy, and robustness over recent alternatives.

1. INTRODUCTION

Prior P3P methods commonly solve for feature distances first; computing orientation afterward can be costly and propagate numerical error, while geometric alternatives use potentially unstable intermediate terms.PnP determines camera pose from observations of known point features, and its minimal three-point case is used with RANSAC for outlier removal.Source: §1 · p. 1
The approach eliminates camera position and feature distances, then algebraically solves orientation through a quartic polynomial.This avoids first computing feature distances, as in and.Source: §1 · p. 1
About 40% of the time required by is needed by the algorithm’s implementation.The introduction identifies as the current state of the art.Source: §1 · p. 1
The method achieves better accuracy than under nominal conditions, with root polishing further improving precision while remaining faster.Root polishing is optional and applies to solutions of the quartic polynomial.Source: §1 · p. 1
The method is more robust than when the three points are almost collinear or very close to each other.Source: §1 · p. 1

2. PROBLEM FORMULATION AND SOLUTION

The section formulates camera-pose recovery from three known feature positions and bearing measurements, then eliminates position and distances to solve for orientation before recovering position.

2.1 Problem Definition

Three known feature positions and their bearing measurements define the camera position and rotation to be estimated.Source: §2.1 · p. 2

2.2 Solving for the orientation

Pairwise subtraction and projection remove camera position and feature distances d_i, yielding three equations only in camera orientation.Here d_i is the distance between the camera and feature f_i.Source: §2.2 · p. 2
The rotation convention is left-handed, and the scalar equation in θ2 is solved using Rodrigues’ rotation formula.Source: §2.2 · p. 2
Only one θ2 branch need be considered because the other yields the same rotation, while positive feature distances select the valid solution among alternatives.Source: §2.2 · pp. 2, 4
Eliminating θ3 produces a quartic polynomial involving a trigonometric function of θ1, whose roots can be computed in closed form.The method uses Ferrari’s method and Cardano’s formula; optional Newton root polishing improves accuracy for a minimal processing-cost increase.Source: §2.2 · pp. 2, 4
Several simplified terms’ lengthy algebraic derivations are omitted because of space limitations.Source: §2.2 · p. 3
A faster rotation-recovery method avoids first computing θ1 and θ3 and then assembling the rotation matrix.Source: §2.2 · p. 4

2.3 Solving for the position

After solving for orientation, the camera position is computed using feature 3; a three-feature least-squares alternative favors accuracy over speed.Source: §2.3 · p. 4

3. EXPERIMENTAL RESULTS

The experimental section describes a simulation-based comparison of the proposed implementation with two alternative solutions, but the supplied passages report no outcomes.

The C++ implementation uses the TooN linear algebra library, as does method.Source: §3 · p. 4
Simulation data are used to test the implementation and compare it with methods and.Source: §3 · p. 4
Algorithm 1 takes three bearing measurements as input and returns camera position and orientation.Source: §3 · p. 5

4 Compute the fij’s using (29)-(36)

In nominal simulations, the method achieves two-orders-of-magnitude better accuracy than and, and runs faster; it also has the best accuracy in the tested close-to-singular cases. Root polishing further improves numerical precision, especially orientation accuracy, at a small processing cost.

4 Compute the fij’s using (29)-(36)

The nominal accuracy test runs three algorithms on 50,000 randomly generated configurations without noise or rounding error in the bearing measurements.For each P3P problem, three landmarks are sampled uniformly within a 0.4 × 0.3 × 0.4 cuboid centered at the origin; errors use the closest root to ground truth.Source: §3.1 · p. 5, §4 · p. 5

3.1 Numerical accuracy

By two orders of magnitude, our approach outperforms and in nominal position and orientation accuracy.The reported distributions and means are shown in the nominal orientation and position histograms and pose-error table.Source: §3.1 · p. 5, Figure 3 · p. 5, Figure 4 · p. 5
Applying root polishing typically uses two iterations of Newton’s method, significantly improving numerical precision, especially for orientation, while taking only 0.01 µs per iteration, or about 4% of total processing time.Source: §3.1 · p. 5

3.2 Processing cost

At 0.54 µs per problem, the method runs 2.5× faster than and uses 40% of ’s time; takes 1.5 µs versus ’s 1.3 µs.The timing test covers 100,000 randomly generated problems; the paper notes that used one repeated feature configuration with caching.Source: §3.2 · pp. 5–6

3.3 Robustness

In both tested close-to-singular cases, our method achieves the best accuracy among the three algorithms.The tests perturb feature positions uniformly within [−0.05 0.05] around singular configurations and compare median errors without root polishing; the cases include collinear landmarks and coincident bearing measurements.Source: §3.3 · p. 6, Table 2 · p. 6, Table 3 · p. 6

4. CONCLUSION AND FUTURE WORK

The paper presents a closed-form algebraic approach to P3P that avoids unstable functions and simpler intermediate expressions than and. It reports improved speed, accuracy, and robustness to close-to-singular cases, and identifies generalized non-central-camera P3P as ongoing work.

4. CONCLUSION AND FUTURE WORK

The approach computes P3P solutions in closed form without first solving for feature distances, reducing numerical-error propagation.It avoids numerically unstable tangent or cotangent functions and uses simpler expressions than and.Source: §4 · p. 6
The method outperforms and in speed, accuracy, and robustness to close-to-singular cases.Source: §4 · p. 6
The authors identify extending the approach to generalized non-central-camera P3P as ongoing work.Source: §4 · p. 6

5. APPENDIX

The appendix supplies derivations for the attitude constraints and a least-squares alternative for position recovery, then compares the implementation with OpenCV.

5.1 Proof of k′

k′3 equals k2 × k1, a unit vector because k2 is perpendicular to k1.Source: §5.1 · p. 7

5.2 Equivalence between the two solutions of θ2

The two possible θ2 solutions yield a same-form constraint system, so no additional θ1 or θ3 solutions need consideration beyond those found for G_CC.Source: §5.2 · p. 7

5.3 Determining the sign of sin θ′

Because the distances d_i are positive, the sign of sin θ′1 can be determined to select the valid one among the two G_CC solutions.Source: §5.3 · p. 7

5.4 Least-squares solution for the position

The position GpC can also be solved by least squares; QR decomposition and backsolve avoid computing the distances d_i.This alternative is slower but more accurate than (56).Source: §5.4 · pp. 7–8

5.6 Derivation of fij and ¯¯C

The appendix derives expressions for fij from (26) and (28), and also derives the expression for ¯¯C.Source: §5.6 · pp. 8–9

5.7 Comparison with the P3P code in OpenCV

OpenCV has lower numerical accuracy than the authors’ code and averages 3 µs per P3P solve versus 0.52 µs for their code.The comparison uses the same setup as Section 3.Source: §5.7 · p. 9