An efficient solution to the five-point relative pose problem

David Nister

article2004TPAMI2,113 citations

Estimating 3D structure and camera motion from video feeds is vital for autonomous navigation, robotics, and automated mapping. However, traditional uncalibrated reconstruction methods struggle with geometric instability, high computational costs, and severe failure modes when viewing flat or planar environments. While pre-calibrating camera intrinsic parameters resolves many ambiguities, classical calibrated solvers either suffered from excessive mathematical complexity or lacked efficient numerical formulations suitable for real-time applications.

The article set out to develop an exact, highly efficient numerical algorithm for the classical five-point relative pose problem and demonstrate its viability as a real-time hypothesis generator within robust estimation frameworks across multiple views.

The approach derives a direct algebraic elimination method that reduces five point-correspondence constraints into a tenth-degree polynomial matching the problem's theoretical complexity. To achieve high operational speed, the solver integrates tailored linear algebra routines, including specialized matrix factorizations, Sturm sequences for root isolation, and fast triangulation. The algorithm was evaluated through numerical simulations across 100,000 synthetic trials and integrated into a random sample consensus framework tested on diverse real-world video sequences, including turntable objects, handheld imagery, vehicle trajectories, and planar scenes.

The analysis produced several critical findings. First, the solver achieved extreme numerical accuracy, exhibiting median residual errors around 1.39e-10 for generic scenes and 1.76e-10 for planar scenes. Second, the formulation generates an average of only 4.55 real roots per sample, which reduces to an average of 2.74 physically valid hypotheses once positive depth constraints are enforced. Third, individual sample evaluations executed in approximately 120 to 180 microseconds on modest 550 MHz hardware, allowing 500-sample consensus batches to complete in roughly 60 to 67 milliseconds. Finally, when extended across three or more views, the method resolves geometric ambiguities seamlessly, maintaining stable tracking through planar and near-planar scenes without requiring specialized model switching.

These findings indicate that enforcing known camera calibration directly at the hypothesis stage significantly improves both execution speed and tracking robustness. By eliminating the need for complex uncalibrated initialization and costly global optimization steps, systems can achieve low-latency metric reconstructions at high frame rates. In end-to-end demonstrations, the pipeline sustained 26 frames per second on a standard 2.4 GHz processor.

Organizations developing real-time vision systems for robotics, autonomous vehicles, and mapping should adopt this five-point solver within multi-view consensus frameworks to handle generic and planar terrains reliably. Teams should implement the specialized root-finding and matrix decomposition techniques highlighted in the article to minimize processing overhead.

The technique assumes that camera intrinsic parameters are known or approximately fixed, and extreme inaccuracies in assumed focal lengths will distort the reconstructed geometry. While the mathematical and experimental results provide high confidence in the solver's numerical stability and speed, broader operational deployment requires paired feature detection pipelines capable of maintaining sufficient tracking quality under severe noise or rapid motion.

autonomous navigation computational efficiency demonstrations Matrix Solution Two

Nister (2004).pdf

Paper: A Flexible New Technique for Camera Calibration, Zhengyou Zhang (2000). Establishes practical camera calibration routines that determine the intrinsic parameters required by Nistér's calibrated five-point relative pose formulation.
Paper: Shape and motion from image streams under orthography: a factorization method, Carlo Tomasi et al. (1992). Introduces foundational factorization principles for recovering 3D shape and camera motion from multiple image feature tracks.
Paper: Least-Squares Fitting of Two 3-D Point Sets, K. S. Arun et al. (1987). Presents the classic closed-form SVD derivation for estimating rigid transformations between corresponding point sets that underpins geometric camera motion analysis.
Paper: Least-Squares Estimation of Transformation Parameters Between Two Point Patterns, S. Umeyama (1991). Refines closed-form singular-value decomposition solvers for point pattern transformation estimation by strictly enforcing proper rotation matrices.
Paper: An Iterative Image Registration Technique with an Application to Stereo Vision, B. D. Lucas et al. (1981). Provides the seminal gradient-guided feature tracking and registration technique essential for generating the sparse 2D point correspondences fed into relative pose solvers.

Paper: Structure-from-Motion Revisited, Johannes L. Schönberger et al. (2016). Integrates minimal-sample geometric hypothesis solvers within a comprehensive, state-of-the-art structure-from-motion pipeline (COLMAP).
Paper: Modeling the World from Internet Photo Collections, Noah Snavely et al. (2008). Applies minimal relative-pose estimators within robust multi-view RANSAC and bundle adjustment workflows to reconstruct massive Internet photo collections.
Paper: ORB-SLAM: A Versatile and Accurate Monocular SLAM System, Raul Mur-Artal et al. (2015). Deploys efficient calibrated pose estimation and geometric model verification inside a real-time monocular SLAM system.
Paper: ORB-SLAM3: An Accurate Open-Source Library for Visual, Visual–Inertial, and Multimap SLAM, Carlos Campos et al. (2020). Extends real-time visual pose estimation into a unified multi-map visual-inertial SLAM library supporting various camera geometries.
Paper: Building Rome in a day, Sameer Agarwal et al. (2009). Scales structure-from-motion algorithms relying on pairwise geometric verification to city-scale image collections via distributed computing.
Paper: Direct Sparse Odometry, Jakob Engel et al. (2016). Develops direct visual odometry that contrasts with feature-based minimal pose solvers by optimizing photometric error directly across image gradients.
Paper: MonoSLAM: Real-Time Single Camera SLAM, Andrew J. Davison et al. (2007). Implements real-time single-camera probabilistic tracking and mapping, building upon fundamental calibrated motion estimation principles.
Paper: SuperGlue: Learning Feature Matching With Graph Neural Networks, Paul-Edouard Sarlin et al. (2020). Enhances feature correspondence quality for geometric hypothesis generators like the five-point solver using graph neural networks and optimal transport.
Paper: PoseNet: A Convolutional Network for Real-Time 6-DOF Camera Relocalization, Alex Kendall et al. (2015). Replaces traditional multi-view algebraic pose solvers with an end-to-end convolutional neural network for direct 6-DoF camera relocalization.
Paper: Unsupervised Learning of Depth and Ego-Motion from Video, Tinghui Zhou et al. (2017). Learns relative camera ego-motion and depth unsupervised from monocular video, offering a learning-based alternative to exact algebraic geometric solvers.

1. Introduction
2. Preliminaries and Notation
3. The Five-Point Algorithm
3.1 Recovering R and t from E
3.2 Efficiency Considerations
4. Planar Structure Degeneracy
5. Applying the Algorithm Together with Random Sample Consensus
6. Results
7. Summary and Conclusions
Appendixes
A Definition of Sturm Chain
B Efficient Singular Value Decomposition of the Essential Matrix
C Efficient Triangulation of an Ideal Point Correspondence
References

Knowls

Knowl 1 — Five-Point Relative Pose Algorithm
algorithm
The five-point algorithm computes the possible relative camera rotations $R$ and translations $t$ between two calibrated perspective views given five corresponding normalized point correspondences $q_i \leftrightarrow q'_i$ for $i \in \{1, \dots, 5\}$ . Image points $q_i = [u_i, v_i, 1]^T$ and $q'_i = [u'_i, v'_i, 1]^T$ are represented in homogeneous coordinates premultiplied by the inverse of their respective calibration matrices $K_1^{-1}$ and $K_2^{-1}$ , satisfying the epipolar constraint ${q'}_i^T E q_i = 0$ , where $E = [t]_\times R$ is the $3 \times 3$ essential matrix.
Input: Five calibrated point correspondences $q_i \leftrightarrow q'_i$ , $i = 1, \dots, 5$ .
Output: Up to 10 candidate relative poses $(R, t)$ satisfying the epipolar and cheirality constraints.
1. Form the $5 \times 9$ matrix where each row is the Kronecker-like vector:
$\tilde{q}^T = [q_1 q'_1, q_2 q'_1, q_3 q'_1, q_1 q'_2, q_2 q'_2, q_3 q'_2, q_1 q'_3, q_2 q'_3, q_3 q'_3]$ .
2. Compute a 4-dimensional basis $\{\tilde{X}, \tilde{Y}, \tilde{Z}, \tilde{W}\}$ spanning the right nullspace of this $5 \times 9$ matrix via QR factorization with pivoting.
3. Reshape $\tilde{X}, \tilde{Y}, \tilde{Z}, \tilde{W}$ into $3 \times 3$ matrices $X, Y, Z, W$ , setting $E(x, y, z) = x X + y Y + z Z + W$ (fixing scale by $w = 1$ ).
4. Substitute $E(x, y, z)$ into the nine cubic essential matrix constraints $E E^T E - \frac{1}{2} \text{trace}(E E^T) E = 0$ to construct a $9 \times 20$ linear system $A$ in 20 monomials ordered as $x^3, y^3, x^2 y, x y^2, x^2 z, y^2 z, x^2, y^2, x y z, x y, x z^2, x z, x, y z^2, y z, y, z^3, z^2, z, 1$ .
5. Perform Gauss-Jordan elimination with partial pivoting on $A$ to eliminate the five monomials $x^3, y^3, x^2 y, x y^2, x^2 z$ , and linearly combine rows to form five polynomial equations of the form $(p_i(z)) x y + (q_i(z)) x + (r_i(z)) y + s_i(z) = 0$ .
6. Arrange four of these equations into two $4 \times 4$ polynomial matrices $B(z)$ and $C(z)$ acting on $[x y, x, y, 1]^T$ .
7. Compute the 11th-degree determinant polynomials $n(z) = \det(B(z))$ and $o(z) = \det(C(z))$ and eliminate the degree-11 term: $p(z) = n(z) o_{11} - o(z) n_{11}$ , yielding a 10th-degree polynomial in $z$ .
8. Compute all real roots $z_k$ of $p(z)$ using Sturm sequences to isolate roots followed by bisection polishing.
9. For each real root $z_k$ , compute $[x_k, y_k]^T$ from the nullvector of $B(z_k)$ , construct $E_k = x_k X + y_k Y + z_k Z + W$ , decompose $E_k$ into rotation $R_k$ and unit translation $t_k$ , and resolve the four-fold pose ambiguity via a cheirality test on a triangulated point.
return All valid relative camera poses $(R_k, t_k)$ .
Knowl 2 — Algebraic Reduction of Cubic Essential Matrix Constraints to a Tenth-Degree Polynomial
model/method
The essential matrix $E$ parameterized by four basis matrices spanning the nullspace of five epipolar constraints is given by $E = x X + y Y + z Z + w W$ , with $w = 1$ . The matrix $E$ must satisfy the nine cubic polynomial constraints

$E E^T E - \frac{1}{2}\text{trace}(E E^T) E = 0.$

Expanding these nine equations produces a linear system $A v = 0$ , where $A$ is a $9 \times 20$ coefficient matrix and $v$ is a vector of 20 monomials ordered as:

$v = [x^3, y^3, x^2 y, x y^2, x^2 z, y^2 z, x^2, y^2, x y z, x y, x z^2, x z, x, y z^2, y z, y, z^3, z^2, z, 1]^T.$

Gauss-Jordan elimination with partial pivoting on $A$ produces rows $(a)$ through $(i)$ . From these rows, four additional polynomial equations $(j), (k), (l), (m)$ are constructed:
$(j) &\equiv (e) - z(g) \\ (k) &\equiv (f) - z(h) \\ (l) &\equiv (d) - x(h) + P(c) + z Q(e) + R(e) + S(g) \\ (m) &\equiv (c) - y(g) + L(d) + z M(f) + N(f) + O(h), \end{aligned}$$ where $L, M, N, O, P, Q, R, S$ are scalar coefficients obtained from the elimination. Denoting a polynomial in $z$ of degree $n$ by $[n]$, the five equations $(i), (j), (k), (l), (m)$ take the bilinear form in $x$ and $y$: $$\begin{aligned} (i) &= x y [1] + x [2] + y [2] + [3] = 0 \\ (j) &= x y [1] + x [3] + y [3] + [4] = 0 \\ (k) &= x y [1] + x [3] + y [3] + [4] = 0 \\ (l) &= x y [2] + x [3] + y [3] + [4] = 0 \\ (m) &= x y [2] + x [3] + y [3] + [4] = 0. \end{aligned}$$ These are arranged into two $4 \times 4$ matrices $B$ (using equations $(i), (j), (k), (l)$) and $C$ (using equations $(i), (j), (k), (m)$) multiplying $[x y, x, y, 1]^T = 0$. Because a non-trivial nullvector exists, the determinant polynomials $(n) = \det(B)$ and $(o) = \det(C)$ must vanish. Both $(n)$ and $(o)$ have degree 11 in $z$. Cancelling the 11th-degree term between them yields the 10th-degree polynomial: $$(p) \equiv (n) o_{11} - (o) n_{11} = 0,$$ whose roots provide the solutions for $z$.$
Knowl 3 — Camera Pose Extraction and Cheirality Disambiguation from the Essential Matrix
algorithm
Given a valid essential matrix $E = [t]_\times R$ , its singular value decomposition is factorized as $E \sim U \operatorname{diag}(1, 1, 0) V^T$ , where $U, V \in SO(3)$ such that $\det(U) > 0$ and $\det(V) > 0$ . Defining

$D = \begin{bmatrix} 0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix},$

the unit translation vector is $t_u = [u_{13}, u_{23}, u_{33}]^T$ and candidate rotations are $R_a = U D V^T$ and $R_b = U D^T V^T$ . Setting the first camera matrix to $P_1 = [I \mid 0]$ , there are four possible second camera matrices: $P_A = [R_a \mid t_u]$ , $P_B = [R_a \mid -t_u]$ , $P_C = [R_b \mid t_u]$ , and $P_D = [R_b \mid -t_u]$ . $P_C$ is the twisted pair of $P_A$ obtained by a $180^\circ$ rotation around the baseline via the projective transformation

$H_t = \begin{bmatrix} I & 0 \\ -2v_{13} & -2v_{23} & -2v_{33} & -1 \end{bmatrix},$

while $P_B$ and $P_D$ are reflections of $P_A$ and $P_C$ via $H_r = \operatorname{diag}(1, 1, 1, -1)$ .
Input: Essential matrix $E$ , one calibrated point correspondence $q \leftrightarrow q'$ .
Output: True second camera matrix $P \in \{P_A, P_B, P_C, P_D\}$ .
1. Compute $U, V \in SO(3)$ from the SVD of $E$ .
2. Compute $t_u = [u_{13}, u_{23}, u_{33}]^T$ , $R_a = U D V^T$ , and $R_b = U D^T V^T$ .
3. Form camera candidate $P_A = [R_a \mid t_u]$ .
4. Triangulate $q \leftrightarrow q'$ using $([I \mid 0], P_A)$ to obtain homogeneous world point $Q$ .
5. Compute camera cheirality signs $c_1 = Q_3 Q_4$ (first camera) and $c_2 = (P_A Q)_3 Q_4$ (second camera).
6. if $c_1 > 0$ and $c_2 > 0$ then
7. return $P_A$
8. else if $c_1 < 0$ and $c_2 < 0$ then
9. return $P_B$
10. else
11. $Q' = H_t Q$
12. if $Q_3 (Q')_4 > 0$ then
13. return $P_C$
14. else
15. return $P_D$
16. end if
17. end if
Knowl 4 — Closed-Form Singular Value Decomposition of an Essential Matrix
algorithm
For a rank-2 essential matrix $E = [e_a, e_b, e_c] \in \mathbb{R}^{3 \times 3}$ with two equal non-zero singular values, an exact singular value decomposition $E = U \operatorname{diag}(\sigma, \sigma, 0) V^T$ with $\det(U) = 1$ and $\det(V) = 1$ is computed in closed form without general iterative SVD.
Input: Essential matrix $E = [e_a, e_b, e_c]$ with column vectors $e_a, e_b, e_c \in \mathbb{R}^3$ .
Output: Orthonormal matrices $U = [u_a, u_b, u_c]$ and $V = [v_a, v_b, v_c]$ in $SO(3)$ .
1. Compute vector cross-products $p_1 = e_a \times e_b$ , $p_2 = e_a \times e_c$ , and $p_3 = e_b \times e_c$ .
2. Select the pair of columns with the cross-product of largest magnitude; assume without loss of generality that $e_a \times e_b$ has the largest magnitude.
3. Compute right singular vectors:
    $v_c = \frac{e_a \times e_b}{\|e_a \times e_b\|}$
    $v_a = \frac{e_a}{\|e_a\|}$
    $v_b = v_c \times v_a$
4. Compute left singular vectors:
    $u_a = \frac{E v_a}{\|E v_a\|}$
    $u_b = \frac{E v_b}{\|E v_b\|}$
    $u_c = u_a \times u_b$
5. Form $V = [v_a, v_b, v_c]$ and $U = [u_a, u_b, u_c]$ .
return $U, V$
Knowl 5 — Root Isolation and Polishing via Sturm Chains for the Tenth-Degree Pose Polynomial
algorithm
To extract the real roots of the 10th-degree polynomial $p(z) = \sum_{i=0}^{10} p_i z^i$ , a Sturm chain $f_0, f_1, \dots, f_{10}$ is constructed, where $f_{10}(z) = p(z)$ and $f_9(z) = p'(z)$ . For $i = 10, 9, \dots, 2$ , polynomial division gives:

$f_i(z) = (k_i z + m_i) f_{i-1}(z) - f_{i-2}(z),$

where $f_{i-2}(z) = -r_i(z)$ is the negative remainder. Base terms are $f_0(z) = m_0$ and $f_1(z) = k_1 z + m_1$ . Once coefficients $k_1, \dots, k_{10}$ and $m_0, \dots, m_{10}$ are precomputed, the Sturm chain at any $z$ is evaluated via the two-term recurrence:

$f_i(z) = (k_i z + m_i) f_{i-1}(z) - f_{i-2}(z), \quad i = 2, \dots, 10.$

This recursive evaluation requires 38 floating point operations, plus 10 operations to count sign changes $s(z)$ . The number of real roots in an interval $[a, b]$ equals $s(a) - s(b)$ . Root isolation proceeds by subdividing intervals until each sub-interval contains exactly one root, followed by 30 iterations of bisection root polishing to achieve high precision in constant time.
Knowl 6 — Closed-Form Triangulation of Ideal Point Correspondences via Plane Intersection
algorithm
Given camera matrices $P_1 = [I \mid 0]$ and $P_2 = P$ , an essential matrix $E$ , and an ideal point correspondence $q \leftrightarrow q'$ such that rays intersect, the 3D space point $Q = [X_1, X_2, X_3, X_4]^T$ is computed directly as the intersection of three backprojected planes.
Input: Calibrated homogeneous image points $q, q'$ , essential matrix $E$ , and second camera matrix $P$ .
Output: Homogeneous 3D coordinate vector $Q$ .
1. Compute the epipolar line in the first image: $a = E^T q'$ .
2. Define backprojected plane $c$ in the second image perpendicular to $E q$ : $c = q' \times (\operatorname{diag}(1, 1, 0) E q)$ .
3. Backproject $c$ into world space: $C = P^T c \in \mathbb{R}^4$ .
4. Set the ray direction from the first camera $d = q$ .
5. Compute the world point $Q$ via the intersection of ray $d$ with plane $C$ :
$Q = \begin{bmatrix} d_1 C_4 \\ d_2 C_4 \\ d_3 C_4 \\ -(d_1 C_1 + d_2 C_2 + d_3 C_3) \end{bmatrix}$
return $Q$
This formulation is projective-invariant, correctly triangulates world points at infinity ( $Q_4 = 0$ ), and for non-ideal correspondences finds the point on the backprojected ray from $q'$ that minimizes the reprojection error in the first image.
Knowl 7 — Three-View Calibrated RANSAC Hypothesis Generation and Planar Degeneracy Resolution
model/method
Uncalibrated relative motion estimation degenerates on planar scenes into a continuous two-degree-of-freedom ambiguity, requiring heuristic model selection. In contrast, calibrated relative pose on a planar scene yields at most a two-fold ambiguity for two views, which is uniquely resolved across three views.

A three-view RANSAC framework operates without planar-degeneracy detection:
1. Sample 5 point tracks across views 1, 2, and 3.
2. Apply the five-point algorithm to the correspondences in views 1 and 3 to generate candidate camera matrices $([I \mid 0], P_3)$ .
3. For each candidate $([I \mid 0], P_3)$ , triangulate the 5 scene points $Q_i$ .
4. Recover the middle camera pose $P_2$ using a 3-point calibrated perspective pose (P3P) algorithm on three of the triangulated points, yielding up to four pose solutions.
5. Disambiguate the candidate poses of $P_2$ using the remaining two triangulated points.
6. Evaluate reprojection errors across all 5 points in all three views to select a single unique hypothesis per 5-track sample.
7. Score all sample hypotheses across all available point tracks using a robust statistical consensus measure.

Knowl 8 — Ambiguity Degrees of Freedom in Planar Structure Estimation

data/table

Planar scene structure induces different degrees of ambiguity depending on the camera calibration state and the number of views, as detailed in the following table:

	1 View Known Structure	2 Views Unknown Structure	$n > 2$ Views Unknown Structure
Known intrinsics	Unique	Two-fold or unique	Unique
Unknown fixed focal length	Unique in general	1 d.o.f.	Unique in general
Unknown variable intrinsics	3 d.o.f.	2 d.o.f.	$3n - 4$ d.o.f.

For calibrated cameras, two views of an unknown plane yield at most two essential matrix solutions (collapsing to a unique solution if the baseline is perpendicular to the plane or when cheirality is resolved, unless all points are closer to one camera). Three calibrated views always yield a unique Euclidean reconstruction, eliminating planar degeneracy without switching models.

Knowl 9 — Hypothesis and Root Count Distribution for the Five-Point Algorithm

data/table

The number of real roots obtained from the 10th-degree polynomial (Step 5) and the number of physically valid camera pose hypotheses remaining after enforcing cheirality (Step 6) exhibit the following empirical distributions across random point and view configurations:

Nr Hypotheses	0	1	2	3	4	5	6	7	8	9	10
Step 5 (Roots)	0	–	0.12	–	0.50	–	0.36	–	0.15	–	$4.9 \times 10^{-4}$
Step 6 (Valid)	$4.2 \times 10^{-6}$	0.17	0.28	0.29	0.17	$5.8 \times 10^{-2}$	$2.5 \times 10^{-2}$	$1.5 \times 10^{-3}$	$6.6 \times 10^{-4}$	$1.5 \times 10^{-6}$	$2 \times 10^{-7}$

Across $10^5$ trials, the 10th-degree polynomial has an average of 4.55 real roots (which only occur in even numbers). After enforcing cheirality on $10^7$ trials, the average number of physically valid pose hypotheses is 2.74. Exactly ten distinct physically valid, well-separated solutions occur with frequency $2 \times 10^{-7}$ .

Knowl 10 — Computational Timings and Numerical Accuracy of the Five-Point Solver

data/table

The computational cost per stage for the five-point algorithm and its multi-view extensions, benchmarked on a 550 MHz CPU, is summarized below:

Step 1 is nullspace extraction via QR, Step 2 is expansion of cubic constraints, Step 3 is Gauss-Jordan elimination on matrix $A$ , Step 4 is determinant expansion and degree-11 cancellation, Step 5 is Sturm-chain root extraction, and Step 6 is SVD and cheirality disambiguation. Total execution time for a 500-sample RANSAC process is approximately 60 ms for two views and 67 ms for three views. Evaluated on $10^5$ double-precision trials, the solver achieves a median numerical residual error $\min_i \min(\|\hat{E}_i/\|\hat{E}_i\| - E/\|E\|\|, \|E/\|E\| + \hat{E}_i/\|\hat{E}_i\|\|)$ of $1.39 \times 10^{-10}$ for generic 3D scenes and $1.76 \times 10^{-10}$ for planar scenes.

Coverage note — None was omitted.

References

1.P. Beardsley, A. Zisserman and D. Murray, Sequential updating of projective and affine structure from motion, International Journal of Computer Vision, 23(3): 235-259, 1997.
2.M. Demazure, Sur Deux Problemes de Reconstruction, Technical Report No 882, INRIA, Rocquencourt, France, 1988.
3.O. Faugeras and S. Maybank, Motion from Point Matches: Multiplicity of Solutions, International Journal of Computer Vision, 4(3):225-246, 1990.
4.O. Faugeras, What Can be Seen in Three Dimensions with an Uncalibrated Stereo Rig?, Proc. European Conference on Computer Vision, pp. 563-578, 1992.
5.O. Faugeras, Three-Dimensional Computer Vision: a Geometric Viewpoint, MIT Press, ISBN 0-262-06158-9, 1993.
6.M. Fischler and R. Bolles, Random Sample Consensus: a Paradigm for Model Fitting with Application to Image Analysis and Automated Cartography, Commun. Assoc. Comp. Mach., 24:381-395, 1981.
7.W. Gellert, K. K¨ustner, M. Hellwich and H. K¨astner, The VNR Concise Encyclopedia of Mathematics, Van Nostrand Reinhold Company, ISBN 0-442-22646-2, 1975.
8.R. Haralick, C. Lee, K. Ottenberg and M. N¨olle, Review and Analysis of Solutions of the Three Point Perspective Pose Estimation Problem, International Journal of Computer Vision, 13(3):331-356, 1994.
9.R. Hartley, Estimation of Relative Camera Positions for Uncalibrated Cameras, Proc. European Conference on Computer Vision, pp. 579-587, 1992.
10.R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, Cambridge University Press, ISBN 0-521-62304-9, 2000.
11.A. Heyden and G. Sparr, Reconstruction from Calibrated Cameras - a New Proof of the Kruppa-Demazure Theorem, Journal of Mathematical Imaging & Vision, 10:1-20, 1999.
12.D. Hook and P. McAree, Using Sturm Sequences To Bracket Real Roots of Polynomial Equations, Graphic Gems I, Academic Press, ISBN 0-122-86166-3, pp. 416-423, 1990.
13.B. Horn, Relative Orientation, International Journal of Computer Vision, 4:59-78, 1990.
14.E. Kruppa, Zur Ermittlung eines Objektes aus zwei Perspektiven mit Innerer Orientierung, Sitz.-Ber. Akad. Wiss., Wien, Math. Naturw. Kl., Abt. IIa., 122:1939-1948, 1913.
15.H. Longuet-Higgins, The Reconstruction of a Plane Surface from Two Perspective Projections, Proc. R. Soc. Lond. B, 277:399-410, 1986.
16.S. Maybank, Theory of Reconstruction from Image Motion, Springer-Verlag, ISBN 3-540-55537-4, 1993.
17.S. Negahdaripour, Closed-Form Relationship Between the Two Interpretations of a Moving Plane, J. Optical Society of America, 7(2):279-285, 1990.
18.D. Nist´er. Reconstruction From Uncalibrated Sequences with a Hierarchy of Trifocal Tensors, Proc. European Conference on Computer Vision, Volume 1, pp. 649-663, 2000.
19.D. Nist´er. Automatic dense reconstruction from uncalibrated video sequences, PhD Thesis, Royal Institute of Technology KTH, ISBN 91-7283-053-0, March 2001.
20.J. Oliensis and Y. Genc, New Algorithms for Two-Frame Structure from Motion, Proc. International Conference on Computer Vision, pp. 737-744 ,1999.
21.J. Philip, A Non-Iterative Algorithm for Determining all Essential Matrices Corresponding to Five Point Pairs, Photogrammetric Record, 15(88):589-599, October 1996.
22.M. Pollefeys, R. Koch and L. Van Gool, Self-Calibration and Metric Reconstruction in spite of Varying and Unknown Internal Camera Parameters, International Journal of Computer Vision, 32(1):7-25, 1999.
23.M. Pollefeys, F. Verbiest and L. Van Gool, Surviving Dominant Planes in Uncalibrated Structure and Motion Recovery, Proc. European Conference on Computer Vision, Volume 2, pp. 837-851, 2002.
24.W. Press, S. Teukolsky, W. Vetterling and B. Flannery, Numerical recipes in C, Cambridge University Press, ISBN 0-521-43108-5, 1988.
25.P. Stefanovic, Relative Orientation - a New Approach, I. T. C. Journal, 1973-3:417-448, 1973.
26.P. Torr and D. Murray, The Development and Comparison of Robust Methods for Estimating the Fundamental Matrix, International Journal of Computer Vision, 24(3):271-300, 1997.
27.P. Torr, A. Fitzgibbon and A. Zisserman, The Problem of Degeneracy in Structure and Motion Recovery from Uncalibrated Image Sequences, International Journal of Computer Vision, 32(1):27-44, August 1999.
28.B. Triggs, Routines for Relative Pose of Two Calibrated Cameras from 5 Points, Technical Report, http://www.inrialpes.fr/movi/people/Triggs INRIA, France, 2000.
29.B. Triggs, P. McLauchlan, R. Hartley and A. Fitzgibbon, Bundle Adjustment - a Modern Synthesis, Springer Lecture Notes on Computer Science, Springer Verlag, 1883:298-375, 2000.
30.R. Tsai and T. Huang, Uniqueness and Estimation of Three-Dimensional Motion Parameters of Rigid Objects with Curved Surfaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(1):13-27, 1984.
31.Z. Zhang, Determining the Epipolar Geometry and its Uncertainty: a Review, International Journal of Computer Vision, 27(2):161-195, 1998.

Citation

MLA

Nister, D. “An Efficient Solution to the Five-point Relative Pose Problem”. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 6, 2004, pp. 756–70, https://doi.org/10.1109/TPAMI.2004.17.

APA

Nister, D. (2004). An efficient solution to the five-point relative pose problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(6), 756–770. https://doi.org/10.1109/TPAMI.2004.17

Chicago

Nister, D. 2004. “An Efficient Solution to the Five-point Relative Pose Problem”. IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (6): 756–70. https://doi.org/10.1109/TPAMI.2004.17.

Harvard

Nister, D. (2004) “An efficient solution to the five-point relative pose problem”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(6), pp. 756–770. Available at: https://doi.org/10.1109/TPAMI.2004.17.

Vancouver

1. Nister D (2004) An efficient solution to the five-point relative pose problem. IEEE Transactions on Pattern Analysis and Machine Intelligence 26:756–770

BibTeX

@article{Nister_2004, title={An efficient solution to the five-point relative pose problem}, volume={26}, ISSN={0162-8828}, url={http://dx.doi.org/10.1109/TPAMI.2004.17}, DOI={10.1109/tpami.2004.17}, number={6}, journal={IEEE Transactions on Pattern Analysis and Machine Intelligence}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Nister, D.}, year={2004}, month=June, pages={756–770} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Step	1	2	3	4	5	6	Three-Point Pose	Mean Two Views	Mean Three Views
Execution time ( $\mu$ s)	8	12	23	14	6 / root	8 / root	5 / root	121	134

An efficient solution to the five-point relative pose problem

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Five-Point Relative Pose Algorithm

Knowl 2 — Algebraic Reduction of Cubic Essential Matrix Constraints to a Tenth-Degree Polynomial

Knowl 3 — Camera Pose Extraction and Cheirality Disambiguation from the Essential Matrix

Knowl 4 — Closed-Form Singular Value Decomposition of an Essential Matrix

Knowl 5 — Root Isolation and Polishing via Sturm Chains for the Tenth-Degree Pose Polynomial

Knowl 6 — Closed-Form Triangulation of Ideal Point Correspondences via Plane Intersection

Knowl 7 — Three-View Calibrated RANSAC Hypothesis Generation and Planar Degeneracy Resolution

Knowl 8 — Ambiguity Degrees of Freedom in Planar Structure Estimation

Knowl 9 — Hypothesis and Root Count Distribution for the Five-Point Algorithm

Knowl 10 — Computational Timings and Numerical Accuracy of the Five-Point Solver

References

Citation

BibTeX

Access the Paper