Perspective-1-Ellipsoid: Formulation, Analysis and Solutions of the Camera Pose Estimation Problem from One Ellipse-Ellipsoid Correspondence

In computer vision, camera pose estimation from correspondences between 3D geometric entities and their projections into the image has been a widely investigated problem. Although most state-of-the-art methods exploit low-level primitives such as points or lines, the emergence of very effective CNN-based object detectors in the recent years has paved the way to the use of higher-level features carrying semantically meaningful information. Pioneering works in that direction have shown that modelling 3D objects by ellipsoids and 2D detections by ellipses offers a convenient manner to link 2D and 3D data. However, the mathematical formalism most often used in the related litterature does not enable to easily distinguish ellipsoids and ellipses from other quadrics and conics, leading to a loss of specificity potentially detrimental in some developments. Moreover, the linearization process of the projection equation creates an over-representation of the camera parameters, also possibly causing an efficiency loss. In this paper, we therefore introduce an ellipsoid-specific theoretical framework and demonstrate its beneficial properties in the context of pose estimation. More precisely, we first show that the proposed formalism enables to reduce the pose estimation problem to a position or orientation-only estimation problem in which the remaining unknowns can be derived in closed-form. Then, we demonstrate that it can be further reduced to a 1 Degree-of-Freedom (1DoF) problem and provide the analytical derivations of the pose as a function of that unique scalar unknown. We illustrate our theoretical considerations by visual examples and include a discussion on the practical aspects. Finally, we release this paper along with the corresponding source code in order to contribute towards more efficient resolutions of ellipsoid-related pose estimation problems. The source code is available here: https://gitlab.inria.fr/vgaudill/p1e.

1. This experiment can be reproduced using our code (file main.m, experiment Xp=4)

2. https://members.loria.fr/moberger/Documents/P1E.mp4

The work presented in this paper was carried out at Université de Lorraine, CNRS, Inria, LORIA. The writing effort was partly funded by the Luxembourg National Research Fund (FNR) under the project reference BRIDGES2020/IS/14755859/MEET-A/Aouada.

Authors and Affiliations

1. Université de Lorraine, CNRS, Inria, LORIA, F54000, Nancy, France

   Vincent Gaudillière, Gilles Simon & Marie-Odile Berger

2. SnT - Interdisciplinary Centre for Security, Reliability and Trust, University of Luxembourg, 29 Avenue John F. Kennedy, L1855, Luxembourg, Luxembourg

   Vincent Gaudillière

Corresponding author

Correspondence to Vincent Gaudillière.

Conflict of interest

The authors declare that they have no conflict of interest.

Communicated by Tomas Pajdla.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix A: Equivalent Problem Formulations

To prove that Eqs. (1) and (1’) are equivalent, we demonstrate below that (1) implies (1’) then (1’) implies (1).

\(\boxed {(1) \implies (1')}\) Multiply (1) on the right by \({\varvec{\Delta }}\) to obtain \(A{\varvec{\Delta }}=\sigma B'{\varvec{\Delta }}\) (see Appendix B). Whence

Left-multiplying by \(B'^{-1}\)

Then right-multiplying by \(A^{-1}\)

Finally (\(\sigma \ne 0\))

\(\boxed {(1') \implies (1)}\) Multiply (1’) on the right by A then on the left by \(B'\) to obtain

Then right-multiply by \({\varvec{\Delta }}\) to obtain \(\mu B'{\varvec{\Delta }}=\frac{\mu }{\sigma } A{\varvec{\Delta }}\), whence (\(\mu \ne 0\)) \(A{\varvec{\Delta }}=\sigma B'{\varvec{\Delta }}\).

Injecting that result into he previous equation leads to

Appendix B: Proof of Result 2

Let us first prove that the couple {A,B’} has exactly two distinct generalized values, that are non zero and of opposite signs.

Proof

The generalized eigenvalues of {A,B’} are non-zero because \(B'^{-1}A\) is not singular.

We can then observe that

is an annihilator polynomial of \(B'^{-1}A\) (see proof in Appendix C):

In linear algebra, the minimal polynomial \(\pi (.)\) is defined as the monic annihilator polynomial having the lowest possible degree. It can be shown (Lang, 2002) that (i) \(\pi (.)\) divides any annihilator polynomial and (ii) the roots of \(\pi (.)\) are identical to the roots of the characteristic polynomial. Since Q is an annihilator polynomial of degree 2, we can thus infer that \(B'^{-1}A\), and thus \(\{A,B'\}\), has at most two distinct eigenvalues.

We are now going to prove by contradiction that {A,B’} has exactly two distinct eigenvalues. Let’s thus assume that the couple has only one eigenvalue with multiplicity 3 denoted \(\sigma _0\).

Since A is positive definite and \(B'\) is symmetric, the couple {A,B’} has the following properties (Golub and Van Loan, 1996) (Corollary 8.7.2, p. 462):

1. 1.

   their generalized eigenvalues are real,

2. 2.

   their reducing subspaces are of the same dimension as the multiplicity of the associated eigenvalues,

3. 3.

   their generalized eigenvectors form a basis of \({\mathbb {R}}^3\), and those with distinct eigenvalues are A-orthogonal.

According to property 2. above, we have

i.e.

which is impossible because A represents an ellipsoid whereas \(B'\) represents a cone. So \(\varvec{\{A,B'\}}\) has exactly two distinct generalized eigenvalues.

Let’s then denote \(\sigma _1\) (multiplicity 1) and \(\sigma _2\) (multiplicity 2) these two eigenvalues. Observing that \(\frac{1}{\sigma _1}\) and \(\frac{1}{\sigma _2}\) are the generalized eigenvalues of \(\{B',A\}\), we can write, according to Avron et al. (2008) (Theorem 3)

If \(\sigma _1\) and \(\sigma _2\) were of the same sign, then \(\forall \textbf{X}\in {\mathbb {R}}^3\backslash \mathbf{\{0\}}\), \(\textbf{X}^\top B'\textbf{X}\) would be of that sign (since \(\textbf{X}^\top A\textbf{X}>0\)). Yet, it is impossible since \(B'\) is neither positive nor negative definite (cone). We thus conclude that the two distinct eigenvalues are of opposite signs. \(\square \)

Let us now prove that \(\sigma \) is the generalized eigenvalue of {A,B’} with multiplicity 1

Proof

Let’s consider \((\sigma _1,{\varvec{\delta }}_1)\) and \((\sigma _2,{\varvec{\delta }}_2)\) the generalized eigenvalues and eigenvectors of \(\{A,B'\}\), such that \(\Vert {\varvec{\delta }}_i\Vert =1\).

We are going to prove (3) by contradiction.

Let’s suppose that there is \(k\in {\mathbb {R}}^*\) such that \((A,\sigma _2,k{\varvec{\delta }}_2)\) is solution of Equation (1).

By injecting these values into (1), we therefore have

where

According to property 2 of the proof of Result 2,

whence, since A is invertible,

However, defining

the subspace of dimension 2 orthogonal to \({\varvec{\delta }}_2\), we observe that, \(\forall \textbf{X}\in {\varvec{\delta }}_2^{\perp }\),

Since A is positive definite, \({\varvec{\delta }}_2^\top A{\varvec{\delta }}_2>0\), whence it comes

It means that

whence the direct sum

is a subspace of \({\mathbb {R}}^3\) with dimension

We end up with a contradiction since \(4>dim({\mathbb {R}}^3)=3\).

As a result, triplets \((A,\sigma _2,k{\varvec{\delta }}_2)\) cannot be solutions of (1), thus solutions are necessarily in the form \((A,\sigma _1,k{\varvec{\delta }}_1)\), where \(k\in {\mathbb {R}}^*\). \(\square \)

Appendix C: Proving that \(Q(B'^{-1}A)=0\)

Replacing (2) into (1), we obtain:

We can then deduce the following expression for A:

Whence, denoting I the identity matrix and defining \(f=\frac{\sigma }{1-\sigma {\varvec{\Delta }}^\top B'{\varvec{\Delta }}}\), then left-multiplying by \(B'^{-1}\), we obtain

Squaring that expression leads to

Defining \(\mu =1-\sigma {\varvec{\Delta }}^\top B'{\varvec{\Delta }}=1-{\varvec{\Delta }}^\top A{\varvec{\Delta }}\):

Finally, we have

Whence, denoting \(Q(x)=\mu x^2-(\mu +1)\sigma x+\sigma ^2\),

Appendix D: Characterizations of \(\mu \)

Proof of result 3

The trace of \(B'^{-1}A\) is given by its eigenvalues:

Whence, by squaring the matrix,

Therefore, since \(tr(I)=3\) and \(\sigma =\sigma _1\), applying the operator tr() to Eq. (B30) leads to

which is equivalent to

i.e.

\(\square \)

Proof of result 4

Determinant of \(B'^{-1}A\) is given by its eigenvalues:

i.e.

We obtain (5) by injecting (3) (4) into (D31) and using \(\mu <0\).

\(\square \)

Appendix E: Proof of Co-occurences

Obviously, only circular cones can be tangent to a sphere. Furthermore, we are going to prove that only a non-circular elliptic cone can be tangent to a triaxial ellipsoid.

Let’s prove it by contradiction, and assume that the projection cone has a revolution axis (circular cone).

Let’s also assume that the ellipsoid center \(\textbf{C}\) does not belong to that axis. Since the ellipsoid is tangent to the cone, any new ellipsoid obtained by rotating the original one around the cone revolution axis shall still be tangent to the cone, thus be solution of (1). Yet, in this case, the locus of ellipsoid centers would be a circle located in a plane orthogonal to that axis and whose center would belong to it. Every center would thus be at a fixed distance to the cone vertex \(\textbf{E}\), whence there would be an infinite number of \({\varvec{\Delta }}\) solutions for the same \(\sigma \), given (6). However, this contradicts Eq. (18). Therefore, the ellipsoid center must belong to the revolution axis of the cone.

If the ellipsoid center belonged to the cone revolution axis, then \({\varvec{\Delta }}\) would be parallel to that axis, i.e. would be an eigenvector of \(B'\), whence an eigenvector of A given (1’). However, in such a case, the symmetries of the cone-ellipsoid pair would impose that the tangent ellipse (intersection between the ellipsoid and the polar plane derived from \(\textbf{E}\) (Wylie, 2008)) belongs to a plane orthogonal to the cone revolution axis, that is also a principal axis of the ellipsoid. Therefore, that tangent ellipse should be both a circle (orthogonal section of a circular cone) and a non-circular ellipse (section of an ellipsoid by a plane parallel to one of its principal planes), which is impossible. Therefore, the cone cannot have a revolution axis.

Appendix F: Vandermonde Matrix

A Vandermonde matrix is a matrix with the terms of a geometric progression in each row or column:

The determinant of a square Vandermonde matrix (when \(m=n\)) is given by

Therefore, V is not singular (i.e. \(det(V)\ne 0\)) if and only if all \(x_i\) are distinct.

Appendix G: Demonstration of Result  10

Proof

Given that A has two distinct eigenvalues, its minimal polynomial is

\(\pi _A\) being an annihilator polynomial of A, evaluating \(\pi _A(A)\) gives

where

Left-multiplying by \({\varvec{\Delta }}^\top \) and right-multiplying by \({\varvec{\Delta }}\) gives

Injecting the expressions of \({\varvec{\Delta }}^\top A^2{\varvec{\Delta }}\), \({\varvec{\Delta }}^\top A{\varvec{\Delta }}\) and \({\varvec{\Delta }}^\top {\varvec{\Delta }}\) as functions of m from (17) into (G32) and observing that

and that

we obtain, after simplification

Let’s call \(P_{spheroid}(x)\) the above polynomial whose m is root:

Developing \(tr(B')\) and \(tr(B'^{-1})\), one can observe that it can be rewritten

At this stage, one can note that the sign of d is the sign of \(\lambda _{B',simple}\):

Thus the signs of the roots of \(P_{spheroid}(x)\) are:

Since \(m<0\), the only possible value for it is the second one. Therefore, \(\sigma \) is given by:

Let’s now focus on \({\varvec{\Delta }}\), and consider the first two equations of System 17:

Considering the ellipsoid frame, its left hand side can be rewritten in a matrix form:

That Vandermonde matrix is not singular given that \( \lambda _{A,single}\ne \lambda _{A,double}\), thus the system can be inverted.

After developing the right hand side, we finally obtain

and

Therefore,

\({\varvec{\Delta }}\) is thus an eigenvector of A corresponding to eigenvalue \(\lambda _{A,single}\), i.e. coincides with the revolution axis of the spheroid.

Equation (2) then requires that \({\varvec{\Delta }}\) is also an eigenvector of \(B'\). It must be the one corresponding to the revolution axis of the cone since, if not, the ellipsoid center would be located outside of the cone. In that respect, both axes of revolutions (cone and spheroid) coincide, and \(\Vert {\varvec{\Delta }}\Vert \) is given by:

\(\square \)

Appendix H: Ellipsoid and Cone Types

See Tables 3 and 4.

Appendix I: Theorem 1: Maple code

Appendix J: Theorem 8: Maple code

Appendix K: Solving the Polynomial Equation in Theorem 3

In case #1, the signs of \(B'\) eigenvalues ensure that

then that

Let’s denote \(S_i\) the root of \(P_i(x)\) with multiplicity 1, and \(D_i\) the root with multiplicity 2, such that

Considering the signs of \(\lambda _{B',i}\) and the fact that \(\lambda _{A,simple}<\lambda _{A,double}\), it comes

One can therefore note that the roots of \(P_1(x)\) and \(P_2(x)\) are negative, while those of \(P_3(x)\) are positive. Since, in addition, \(k_3<0\), we have

Let’s now focus on the signs of \(P_1(x)\) and \(P_2(x)\) to determine the locus of possible m values. Since \(\lambda _{B',1}<\lambda _{B',2}\), their roots verify

Therefore, one can distinguish between two configurations regaring the roots order:

or

For the first case, the variations of the three polynomials are presented in Table 5.

One can observe that the three polynomials are never all non-negative, thus this configuration is impossible. For the second case, however, there is one value for which all three polynomials are non-negative: \(D_1\) (see Table 6).

Appendix L: Proof of Result 12

Proof

Left-multiplying \(A=\lambda _{A,triple}I\) by \({\varvec{\Delta }}^\top \) right-multiplying it by \({\varvec{\Delta }}\), we obtain

Injecting the first two equations of System (17), we then have

Developing \(tr(A^{-1})\) and \(tr(B'^{-1})\) leads to

Furthermore, one can observe that

Whence, injecting this into the former equation:

Denoting

the last equation means that m is root of the polynomial

Yet, R is an obvious root of this polynomial:

Even if obtaining a formal expression of the two other roots is not straighforward, Vieta’s formulas provide the following constraints:

If roots \(x_1\) are \(x_2\) complex, then R is the only possible value for m. If they are real, then, since \(R<0\) (\(B'\) eigenvalues are of opposite signs), the second formula requires that \(x_1\) and \(x_2\) are of the same sign, and the first formula requires that they are positive. Finally,

Corresponding \(\sigma \) value is:

Applying tr() to Eq. (1’) gives the value of \(\Vert {\varvec{\Delta }}\Vert ^2\):

Given

and

the right hand side can be rewritten

i.e.

\(\square \)

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions