Determine the center and orientation of an ellipse in $3D$ given two perspective images

Question

An ellipse is hanging somewhere in $3D$ space with unknown $3D$ center coordinates and unknown $3D$ directions of its semi-axes, and unknown lengths of the semi-major and semi-minor axes. What you're given are two images of this ellipse from two cameras which have known centers and known orientations, and known focal distances (these are just the distances between the center of the camera and the projection plane).

From these two images, I would like to determine the ellipse completely, everything about the ellipse, namely, its center coordinates, its axes lengths, and their orientation in space.

How can this task be accomplished ?

This question is inspired by my recent answer to this question, so this provides some context to the current problem.

Answer 1

As noted in a comment, the ellipse lies on the intersection of the two cones having the centers of the cameras as vertices, and the respective images as guiding curves. The intersection of two quadrics is, in general, a quartic curve. As this curve contains an ellipse, then it must be made of two conics, one of them being the ellipse we want to determine. That means there are in general two possible solutions.

To find the intersection, one could find the equations of both cones. This can be done, for instance, by taking nine points on each cone and inserting their coordinates into the general equation of a quadric. But solving the resulting system of equations can be quite tedious.

I'll suggest then a different approach. Take five points $ABCDE$ on the first image and consider the five lines $abcde$ passing through each point and the center $O_1$ of the first camera. The images of these lines, relative to the second camera, can then be constructed: they are five lines lying in the plane of the second image, each of them intersecting it at two points: $(A_1,A_2)$, $(B_1,B_2)$ and so on. If $O_2$ is the center of the second camera, we can then construct the intersection point $P_1$ between line $A_1O_2$ and line $a$, and the intersection point $P_2$ between line $A_2O_2$ and line $a$. Points $P_1$ and $P_2$ lie then on the intersection of the cones, each on a different conic.

We can similarly find the other four couples of points on the intersection: $(Q_1,Q_2)$, $(R_1,R_2)$ and so on. Five of these ten points lie on the first conic, and the others lie on the second conic, but we don't know which lies on which. To find out, we can consider all $32$ possible cases $(P_i,Q_j,R_k,\dots)$ and check if all five points lie on a the same plane: this should be true only in two cases, which are then five points on each of the two possible conics. These can then be constructed.

See here for a geometrical construction of center and axes of an ellipse, given five points.

EDIT.

You can see below an example of the construction, made with GeoGebra. Note that $O_1$ and $O_2$ are on the same side of the plane of the first solution (ellipse $P_2Q_2R_1S_1T_1$) while they are on opposite sides of the plane of the second solution (ellipse $P_1Q_1R_2S_2T_2$). If this kind of information is given one can then isolate the right solution.

Answer 2

This is an alternative to my other solution. Unlike the other solution, the plane of intersection between the two vision cones is constructed algebraically, without the need for the iterative Newton-Raphson iteration to search for the plane, and without trial and error.

We have two "vision" cones from the two cameras, each containing the $3D$ ellipse on its surface. We want to find the intersection of these two cones.

The equations of the cones are of the form

$ (r - e_1)^T A_1 (r - e_1) = 0 $

and

$ (r - e_2)^T A_2 (r - e_2) = 0 $

where $ r = [x, y, z]^T $ and $e_1, e_2$ are the $3D$ coordinates of the two cameras. If we define $ r = [x, y, z, 1]^T$ (homogenous coordinates) then the above two equations become

$ r^T Q_1 r = 0$

and

$ r^T Q_2 r = 0 $

where

$ Q_1 = \begin{bmatrix} A_1 && - A_1 e_1 \\ -e_1^T A_1 && e_1^T A_1 e_2 \end{bmatrix} $

And $Q_2$ is defined similarly. Now define $Q_\alpha$ as follows

$ Q_\alpha = Q_1 + \alpha Q_2 $

Then $\det(Q_\alpha) $ is a quartic polynomial in $\alpha$. Find its roots, and select one of the roots.

Note that if $r$ satisfies $ r^T Q_1 r = r^T Q_2 r = 0 $ then it satisfies $ r^T Q_\alpha r = 0 $. Therefore, all possible solutions for the intersection of the two quadrics (the two cones) must satisfy $ r^T Q_\alpha r = 0 $.

Diagonalizing $Q_\alpha$ into

$ Q_\alpha = R D R^T $

For this particular application, the diagonal matrix $D$ can always be re-arranged as follows:

$ D = \begin{bmatrix} D_{11} && 0 && 0 && 0 \\ 0 && D_{22} && 0 && 0 \\ 0 && 0 && 0 && 0 \\ 0 && 0 && 0 && 0 \end{bmatrix} $

where $D_{11} \gt 0 $ and $ D_{22} \lt 0 $. Define $p = R^T r $, then

$ p^T D p = 0 $

and the general soltion for $p$ is

$ p = t_1 \begin{bmatrix} \dfrac{1}{\sqrt{D_{11}}} \\ \pm \dfrac{1}{\sqrt{-D_{22}}} \\ 0 \\ 0 \end{bmatrix} + t_2 \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} + t_3 \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} $

Since $ r = R p $ has its $4$-th coordinate equal to $1$, then we have to impose

$ [0, 0, 0, 1] R p = 1 $

And this puts a linear constraint on the three parameters $t_1, t_2, t_3$, so that now $p$ is expressable as follows

$ p = p_0 + t_1 p_1 + t_2 p_2 $

From which it follows that

$ r = R p = R p_0 + t_1 R p_1 + t_2 R p_2 $

And this is the parametric equation of the plane(s) of the $3D$ ellipse. Corresponding to the sign choice of $\dfrac{1}{\sqrt{-D_{22}}}$, we have two possible planes.

What remains is to intersect these two planes with either cone to obtain the two equations of the two possible $3D$ ellipses.

This completes the solution of the problem.

Answer 3

First of all, set up the viewing reference frame for both cameras. The cameras centers and viewing directions and orientations are given, as well as the "focal distance" which is the distance between the center of the camera and the projection plane, which lies between the viewed object and the center of the camera.

The first camera local frame can be represented by the rotation matrix $V_1$ and its center by the vector $C_1$, so that the world coordinates of a point and its coordinates in the camera's local frame are related by

$\mathbf{p} = \mathbf{C_1} + V_1 \mathbf{q_1} $

and similarly for the second camera

$ \mathbf{p} = \mathbf{C_2} + V_2 \mathbf{q_2} $

where $\mathbf{p}$ is the coordinate vector of a point in $3D$ and $\mathbf{q_1}, \mathbf{q_2} $ are the coordinate vectors in the cameras frame of refence (local frames).

The idea of this solution is as follows: From each image ellipse that lies in the projection plane of a camera, connect the center of the camera to the ellipse that lies in the image plane, and extend these line segments into rays. The collection of the rays forms a cone. We thus have two cones from the two cameras. Set up a "unknown" plane of the viewed ellipse. This plane is such that its intersection with the cones is identical.

It is assumed that the ellipses in the two images are identifiable in parametric form, i.e. the ellipse in each image is given by

$ \mathbf{E}(t) = \mathbf{E_0} + \mathbf{f_1} \cos(t) + \mathbf{f_2} \sin(t) $

One way to identify the ellipse is by bounding the the ellipse by a rectangle whose sides are parallel to the coordinate axes, and finding where the ellipse in the image is tangent the right side of the border. This is explained in detail in my solution of the problem that inspired this problem.

In that solution, it is also explained how to construct the algebraic equation of the cone whose vertex is the camera center and which contains the given ellipse.

Given the two cones equations, I'll create a variable plane whose normal vector is

$\mathbf{n} = [ \sin(\theta) \cos(\phi), \sin(\theta) \sin(\phi), \cos(\theta) ]^T $

And that passes through an unknown point $\mathbf{r_0}$. To find the plane of the viewed ellipse, I used Newton-Raphson method, where the two unknowns are $\theta$ and $\phi$, such that the iteration will search for the values of these two variables that will result in similar ellipses of intersection, with the same orientation.

The Newton-Raphson iteration converged within $5$ iterations to a solution of normed error of $10^{-9}$.

Using the equation of the two cones and the given normal vector, it is possible to determine the vector $\mathbf{r_0}$.

This completes the solution of the problem, the intersection of the plane with either cone is fully determined.