Determining the coordinates of the vertices of a triangle from its camera image

Question

Suppose you have a pinhole camera (no lens) with known position and orientation with respect to the world.

Now with this camera, you take an image of a triangle that has known side lengths of arbitrary position/orientation in space.

The camera has a known focal length.

Can you determine the coordinates of the vertices of the triangle, using only the image and the position/orientation of the camera together with its focal length ?

Is there more than one possible set of coordinates for the vertices ?

My approach:

I'll assume that the projection plane lies between the projection center of the camera. Set up a coordinate system for the camera with its origin at the projection center, and with its $X$ axis pointing from the center of the image to the right of the image, and its $Y$ axis pointing from the center of the image to the top of the image. The $Z$ axis follows from that (using the right hand rule).

Let $z_0$ be the focal length (which is known). The equation of this plane in the coordinates of the camera coordinate frame that we just set up is $ Z = - z_0 $

Therefore, the coordinates of the three image points in this coordinate system are

$ P_1 = \begin{bmatrix} Q_1 \\ - z_0 \end{bmatrix} $

$ P_2 = \begin{bmatrix} Q_2 \\ - z_0 \end{bmatrix} $

$ P_3 = \begin{bmatrix} Q_3 \\ - z_0 \end{bmatrix} $

where $Q_1, Q_2, Q_3$ are the coordinates of the three vertices in the image (they are two-dimensional vectors).

Now construct rays from the origin of the camera coordinate system to $P_1, P_2, P_3$. These rays will be

$ p_1(t_1) = t_1 P_1 $

$p_2 (t_2) = t_2 P_2 $

$p_3 (t_3) = t_3 P_3 $

Now we know the side lengths, so let $a = \overline{V_1 V_2} $, $b = \overline{V_2 V_3} $ and $c = \overline{V_1 V_3} $, then

$ ( p_1 - p_2 ) \cdot (p_1 - p_2) = a^2 $

$ (p_2 - p_3) \cdot (p_2 - p_3) = b^2 $

$ (p_1 - p_3) \cdot (p_1 - p_3) = c^2 $

This is a system of three quadratic equations in the unknowns $t_1, t_2, t_3$.

It can be solved by Mathematica, (or WolframAlpha.com) or other mathematical software.

Since I'm not subscribed to Mathematica or WolframAlpha.com and I don't know the Mathematica script language, and the fact that I've already developed code for solving three quadratic equations in three unknowns, that's what I used to solve the system.

This code that I've developed is included in this Excel file which contains the source code for the functions "solve_rd_system" (that solves the system $A x = b$, where $A$ is $ m \times n$), and the function "intersect_three_quadrics" which solves a system of three quadratic equations in three unknowns, and also other functions that solve a system of two quadratic equations in two unknowns. These are included in this file as macros (VBA script). Click on the link, to open the online file, then click on "Editing" and choose "Open in Desktop App". This will open the file in your desktop Excel program. Click "View" then select "Macros".

This solves my problem.

A very simple part remains, which is as follows: having determined $t_1, t_2, t_3$, we now have $p_1, p_2, p_3$ as coordinates of the three vertices relative to the camera coordinate frame. To convert these into world coordinates, we use the given position and orientation of the camera. If the world position is $E$ and the orientation is specified by rotation matrix $R$ , then the coordinates of the three vertices are

$ V_1 = E + R p_1 $

$ V_2 = E + R p_2 $

$ V_3 = E + R p_3 $

I look forward to your input (remarks) concerning this simple straightforward method that I've explained above.

Alternative solutions are welcome and highly appreciated.

Answer 1

Your general approach is sound.

Is there more than one possible set of coordinates for the vertices?

Yes, there are multiple solutions.

Firstly, for every solution you find, if you change the signs of all the $t_i$ you get another solution which is the mirror image of the first, reflected in the pinhole of the camera. You might only care about solutions in front of the camera, with $t_i<0$. But you didn't say so.

But even in front of the camera, you may have multiple solutions. Here is

\begin{align*} P_1&=\begin{bmatrix}4\\7\\-1\end{bmatrix} & P_2&=\begin{bmatrix}-3\\5\\-1\end{bmatrix} & P_3&=\begin{bmatrix}6\\-1\\-1\end{bmatrix} \\ a &=8 & b &= 10 & c &= 17 \\ t_1 &\approx -0.838 & t_2 &\approx -1.488 & t_3 &\approx -1.650 \\ t_1' &\approx -0.161 & t_2' &\approx -1.449 & t_3' &\approx -1.686 \end{align*}

In general your system of three equations can have up to 8 solutions. That is including the mirror images you get from flipping all the signs, and including solutions resulting in complex numbers. In a few experiments I did I never got more than 4 real solutions, the remaining 4 always had a non-zero imaginary part. But I don't have a convincing argument that this will always be the case, so until further notice I'd assume that 8 real solutions might be possible.

I'm not subscribed to Mathematica or WolframAlpha.com and I don't know the Mathematica script language

I was about to suggest that you can use WolframAlpha.com without any scripting language, using math input instead. But I'm no longer sure since so far I couldn't convince it to run my example above.

I'm using Sage instead. You could use https://sagecell.sagemath.org/ for a very basic interface without any registration, or you could sign up for CoCalc or install Sage locally.

Here is the example above in Sage code:

PR.<t1, t2, t3> = QQ[]
z0 = 1
P1 = vector(QQ, [ 4,  7, -z0])
P2 = vector(QQ, [-3,  5, -z0])
P3 = vector(QQ, [ 6, -1, -z0])
a =  8
b = 10
c = 17
p12 = t1*P1 - t2*P2
p13 = t1*P1 - t3*P3
p23 = t2*P2 - t3*P3
ideal([p12*p12-a*a, p13*p13-b*b, p23*p23-c*c]).variety(QQbar)

I define PR to be a polynomial ring in three indeterminates, t1, t2 and t3. I define the vectors from the example, then define three polynomials which are zero when your equations are met. I search for common zeros of all three of them using the variety computation, using $\bar{\mathbb Q}$, the set of algebraic numbers, as the underlying field. So even if the answer shows some decimal approximation, behind the scenes I have an exact representation of these numbers as zeros of some polynomial. But this depends on the input coordinates being rational numbers, as indicated by the QQ (Sage notation for $\mathbb Q$) in a number of places. If your inputs are floating point numbers, you might want to convert to a rational approximation first. If you use variety(AA) instead of variety(QQbar), you only get solutions using the algebraic reals $\mathbb A$, i.e. ignoring complex solutions with non-zero imaginary part.

This code that I've developed is included in this Excel file

Haven't looked at the Excel file, don't have an Excel at hand just now. I'm a bit surprised your code didn't answer the question of whether there might be multiple solutions. You might want to check its output against what Sage computes.