1 Introduction

In multiview geometry, the fundamental matrix and the trifocal tensor describe the relative orientation of two and three (uncalibrated) images respectively. If the cameras are calibrated, i.e., we are given the calibration matrices for each view, the fundamental matrix is transformed to the so-called essential matrix. It was first introduced by Longuet-Higgins in [14]. The essential matrix has fewer degrees of freedom and additional algebraic properties, compared to the fundamental matrix. A detailed investigation of these properties is given by Demazure, Faugeras, Maybank and other researchers in [6, 7, 12, 13, 15]. We shortly recall the most important of them in the next section.

The object of study of the present paper is the trifocal tensor for calibrated cameras. We call this entity the calibrated trifocal tensor (CTFT for short), although some authors use the term Euclidean trifocal tensor. It first appeared as a tool of scene reconstruction from line correspondences in the papers by Spetsakis and Aloimonos [23] and Weng et al. [27]. Later, Hartley [10] generalized the trifocal tensor for uncalibrated cameras and showed that it can be applied for projective scene reconstruction from different combinations of point and line correspondences. Afterward, the properties and applications of (uncalibrated) trifocal tensors have been intensively investigated by Hartley, Shashua, Triggs, and many other researchers in [3, 11, 21, 22, 25, 26].

One of the most important problems regarding multifocal tensors is their algebraic characterization, i.e., a set of necessary and sufficient conditions under which an arbitrary tensor of suitable order becomes the multifocal tensor. The conditions are usually given in a form of polynomial equations. While the fundamental matrix is completely characterized by the single equation—its determinant must be zero—the set of essential matrices is characterized by the nine cubic constraints, cf. [6, 15] or Eq. (7) below. The significance of this result lies in its practical applications. A few efficient algorithms for some metric structure-from-motion problems have been developed based on the characterization of essential matrices; see, e.g., [16, 24].

The investigation of constraints characterizing uncalibrated trifocal tensors has received considerable attention in the last two decades: see [4, 17, 20] and recent works [1, 2, 18] for details. We would like to mention that the structure of the set of trifocal tensors is much more complicated compared to the bifocal case. In particular, the characterizations from [2] and [1] consist of 36 and 2071 (!) polynomials, respectively.

On the other hand, constraints on trifocal tensors specific to the calibrated case have not previously been studied in the published literature. The present paper is a first step in this direction. Its main contribution is the characterization of the set of real CTFTs. Namely, we show that the necessary and sufficient conditions for a real trifocal tensor to be calibrated consist of 15 quartic polynomial equations. Most of them arise from the study of certain complex \(3\times 3\) matrix associated with a CTFT. Alternatively, we propose the characterization consisting of 99 quintic polynomial equations.

The rest of the paper is organized as follows. In Sect. 2, we recall some definitions and results from multiview geometry. In Sect. 3, we introduce a new notion—the trifocal essential matrix. On the one hand, it is a generalization of the ordinary (bifocal) essential matrix, and, on the other hand, it is closely related to the calibrated trifocal tensor. We prove the two necessary and sufficient conditions that characterize the set of trifocal essential matrices. In Sect. 4, we define the trifocal essential matrix associated with a CTFT and, based on the characterizations from Sect. 3, we propose our three necessary conditions. They have the form of 15 quartic and 99 quintic homogeneous polynomial equations in the entries of a CTFT. In Sect. 5, we show that in the practically significant real case the 15 quartic constraints are also sufficient. Combining this result with the existing characterization of trifocal tensors, we give a complete set of constraints characterizing a real CTFT. In Sect. 6, we discuss the paper’s results and propose further directions of research. In Appendix, we have included some auxiliary lemmas used in the paper.

2 Preliminaries

2.1 Notation

We preferably use \(\alpha , \beta , \ldots \) for scalars, \(a, b, \ldots \) for column 3-vectors or polynomials, and \(A, B, \ldots \) both for matrices and column 4-vectors. For a matrix A, the entries are \((A)_{ij}\), the transpose is \(A^{{\mathrm {T}}}\), the determinant is \(\det A\), and the trace is \({{\mathrm{tr}}}A\). For two 3-vectors a and b the cross product is \(a\times b\). For a vector a the entries are \((a)_i\), the notation \([a]_\times \) stands for the skew-symmetric matrix such that \([a]_\times b = a \times b\) for any vector b. We use I for the identity matrix.

The group of \(n\times n\) matrices subject to \(R^{{\mathrm {T}}}R = I\) and \(\det R = 1\) is denoted by \({\mathrm {SO}}(n)\) in case R is real and \({{\mathrm {SO}}}(n, {\mathbb {C}})\) if R is allowed to have complex entries.

2.2 Pinhole Cameras

We briefly recall some definitions and results from multiview geometry; see [7, 8, 11, 15] for details.

A pinhole camera is a triple \((O, \Pi , P)\), where \(\Pi \) is the image plane, P is a central projection of points in three-dimensional Euclidean space onto \(\Pi \), and \(O \not \in \Pi \) is the camera center (center of projection P).

Let there be given coordinate frames in 3-space and in the image plane \(\Pi \). Let Q be a point in 3-space represented in homogeneous coordinates as a 4-vector, and q be its image in \(\Pi \) represented as a 3-vector. Projection P is then given by a \(3\times 4\) homogeneous matrix, which is called the camera matrix and is also denoted by P. We have

$$\begin{aligned} q \sim PQ, \end{aligned}$$

where \(\sim \) means an equality up to a scale. For the sake of brevity, we identify further the camera \((O, \Pi , P)\) with its camera matrix P.

The focal length is the distance between O and \(\Pi \), the orthogonal projection of O onto \(\Pi \) is called the principal point. All intrinsic parameters of a camera (such as the focal length and the principal point offsets) are combined into a single upper-triangular matrix, which is called the calibration matrix. A camera is called calibrated if its calibration matrix is known.

By changing coordinates in the image plane, the calibrated camera can be represented in the form

$$\begin{aligned} P = \begin{bmatrix}R&\quad t\end{bmatrix}, \end{aligned}$$

where \(R \in {\mathrm {SO}}(3)\) and \(t \in {\mathbb {R}}^3\) are called the rotation matrix and translation vector, respectively.

2.3 Two-View Case

Let there be given two cameras \(P_1 = \begin{bmatrix} I&\quad 0 \end{bmatrix}\) and \(P_2 = \begin{bmatrix} A&\quad a \end{bmatrix}\), where A is a \(3\times 3\) matrix and a is a 3-vector. Let Q be a point in 3-space, and \(q_k\) be its kth image. Then,

$$\begin{aligned} q_k \sim P_k Q, \quad k = 1, 2. \end{aligned}$$

The incidence relation for a pair \((q_1, q_2)\) says

$$\begin{aligned} q_2^{{\mathrm {T}}} F q_1 = 0, \end{aligned}$$
(1)

where matrix \(F = [a]_\times A\) is called the fundamental matrix. It is important that relation (1) is linear in the entries of F, so that given a number of point correspondences (eight or more), one can estimate the entries of F by solving a linear system.

It follows from the definition of matrix F that \(\det F = 0\). One easily verifies that this condition is also sufficient. Thus we have

Theorem 1

([11]) A real nonzero \(3\times 3\) matrix F is a fundamental matrix if and only if

$$\begin{aligned} \det F = 0. \end{aligned}$$
(2)

The essential matrix E is the fundamental matrix for calibrated cameras \({\hat{P}}_1 = \begin{bmatrix} I&\quad 0 \end{bmatrix}\) and \({\hat{P}}_2 = \begin{bmatrix} R&\quad t\end{bmatrix}\), where \(R \in {\mathrm {SO}}(3)\), t is a 3-vector, that is

$$\begin{aligned} E = [t]_\times R. \end{aligned}$$
(3)

The matrices F and E are related by

$$\begin{aligned} F \sim K_2^{-{\mathrm {T}}} E K_1^{-1}, \end{aligned}$$
(4)

where \(K_k\) is the calibration matrix of the kth camera. It follows that the incidence relation (1) for the essential matrix becomes

$$\begin{aligned} {\hat{q}}_2^{{\mathrm {T}}} E {\hat{q}}_1 = 0, \end{aligned}$$

where \({\hat{q}}_k = K_k^{-1} q_k\) are the so-called normalized coordinates.

Equality (3) can be thought of as the definition of the essential matrix, i.e., it is a \(3\times 3\) nonzero skew-symmetric matrix post-multiplied by a special orthogonal matrix. Moreover, we can even consider complex essential matrices assuming that in (3) vector \(t \in {\mathbb {C}}^3\) and matrix \(R \in {\mathrm {SO}}(3, {\mathbb {C}})\).

The real fundamental matrix has seven degrees of freedom, whereas the real essential matrix has only five degrees of freedom. It is translated into the following property [7, 11, 13]: Two of the singular values of matrix E are equal, and the third is zero. The condition is also sufficient. An equivalent form of this result is given by

Theorem 2

([6, 7]) A real \(3\times 3\) matrix E is an essential matrix if and only if

$$\begin{aligned}&\det E = 0, \end{aligned}$$
(5)
$$\begin{aligned}&{{\mathrm{tr}}}(EE^{{\mathrm {T}}})^2 - 2{{\mathrm{tr}}}((EE^{{\mathrm {T}}})^2) = 0. \end{aligned}$$
(6)

It should be mentioned here that constraints (5) and (6) characterize only real essential matrices. There exist “non-essential” complex \(3\times 3\) matrices which nevertheless satisfy both conditions (5) and (6). The most general form of such matrices will be given in the next section.

The following theorem gives another characterization constraint on the entries of essential matrix E. It is also valid in case of complex E.

Theorem 3

([6, 7, 15]) A real or complex \(3\times 3\) matrix E of rank two is an essential matrix if and only if

$$\begin{aligned} ({{\mathrm{tr}}}(EE^{{\mathrm {T}}}) I - 2EE^{{\mathrm {T}}}) E = 0_{3\times 3}. \end{aligned}$$
(7)

We note that there are “non-essential” rank one matrices which satisfy (7). However, it can be shown that all of them are limits of sequences of essential matrices [15]. Thus the closure of the set of essential matrices constitutes an algebraic variety generated by (7).

It is interesting to note that Theorem 3 is a key for developing efficient algorithms of the essential matrix estimation from five-point correspondences in two views [16].

2.4 Three-View Case

A (2, 1) tensor is a valency-3 tensor with two contravariant and one covariant indices. For a (2, 1) tensor T, we write \(T = \begin{bmatrix}T_1&\quad T_2&\quad T_3\end{bmatrix}\), where \(T_k\) are \(3\times 3\) matrices corresponding to the covariant index.

Let there be given three cameras \(P_1 = \begin{bmatrix} I&\quad 0 \end{bmatrix}\), \(P_2 = \begin{bmatrix} A&\quad a \end{bmatrix}\) and \(P_3 = \begin{bmatrix} B&\quad b \end{bmatrix}\), where A and B are \(3\times 3\) matrices, a and b are 3-vectors. The trifocal tensor \(T = \begin{bmatrix}T_1&\quad T_2&\quad T_3\end{bmatrix}\) is a (2, 1) tensor defined by

$$\begin{aligned} T_k = A e_k b^{{\mathrm {T}}} - a e_k^{{\mathrm {T}}} B^{{\mathrm {T}}}, \end{aligned}$$
(8)

where \(e_1\), \(e_2\), \(e_3\) constitute the standard basis in \({\mathbb {R}}^3\). For a trifocal tensor T matrices \(T_k\) are called the correlation slices.

It is clear that \(\det T_k = 0\). If matrices \(T_k\) are of rank two, then let \(l_k\) and \(r_k\) be the left and right null vectors of \(T_k\), respectively. It follows from (8) that \(l_k = [a]_\times A e_k\) and \(r_k = [b]_\times B e_k\). Therefore, the two (sextic in the entries of \(T_1, T_2, T_3\)) epipolar constraints hold [11, 17]:

$$\begin{aligned} \begin{aligned} \det \begin{bmatrix}l_1&\quad l_2&\quad l_3\end{bmatrix} = \det ([a]_\times A)&= 0,\\ \det \begin{bmatrix}r_1&\quad r_2&\quad r_3\end{bmatrix} = \det ([b]_\times B)&= 0. \end{aligned} \end{aligned}$$
(9)

Moreover, for any scalars \(\alpha , \beta , \gamma \), the matrix \(\alpha T_1 + \beta T_2 + \gamma T_3\) is also degenerate (its right null vector is \([b]_\times B (\alpha e_1 + \beta e_2 + \gamma e_3)\)) meaning that

$$\begin{aligned} \det (\alpha T_1 + \beta T_2 + \gamma T_3) = 0. \end{aligned}$$
(10)

This equality is referred to as the extended rank constraint. It is equivalent to ten (cubic in the entries of \(T_1, T_2, T_3\)) equations each of which is the coefficient in \(\alpha ^i \beta ^j \gamma ^k\) with \(i + j + k = 3\).

Theorem 4

([9, 17]) Let \(T = \begin{bmatrix}T_1&\quad T_2&\quad T_3\end{bmatrix}\) be a real (2, 1) tensor such that \({{\mathrm{rank}}}T_k = 2\), \(k = 1, 2, 3\). Let T satisfy the two epipolar (9) and ten extended rank (10) constraints. Let the ranks of matrices \(\begin{bmatrix}l_1&\quad l_2&\quad l_3\end{bmatrix}\) and \(\begin{bmatrix}r_1&\quad r_2&\quad r_3\end{bmatrix}\) equal two. Then T is a trifocal tensor.

Remark 1

The additional rank constraints from Theorem 4 are sometimes referred to as the “general viewpoint assumption.” The following example demonstrates that they cannot be omitted. The (2, 1) tensor

$$\begin{aligned} T = \begin{bmatrix}\begin{bmatrix}0&\quad 1&\quad 0\\ 0&\quad 0&\quad 1\\ 0&\quad 0&\quad 0\end{bmatrix}&\begin{bmatrix}1&\quad 0&\quad 0\\ 0&\quad 1&\quad 0\\ 0&\quad 0&\quad 0 \end{bmatrix}&\begin{bmatrix}1&\quad 0&\quad 0\\ 0&\quad 1&\quad 0\\ 0&\quad 0&\quad 0 \end{bmatrix} \end{bmatrix} \end{aligned}$$

satisfies both the epipolar and extended rank constraints. However it is not a trifocal tensor, i.e., it cannot be represented in form (8). On the other hand, there exist degenerate trifocal tensors such that at least one of matrices \(\begin{bmatrix}l_1&\quad l_2&\quad l_3\end{bmatrix}\), \(\begin{bmatrix}r_1&r_2&r_3\end{bmatrix}\) or even \(T_k\) is of rank less than two.

Also, it should be mentioned that the characterization from Theorem  4 is not unique. There exist other sets of constraints characterizing trifocal tensors, cf. [1, 2, 4, 18, 20].

Let \(q_k\) be the kth image of a point Q in 3-space. The trifocal incidence relation for a triple \((q_1, q_2, q_3)\) says [11]

$$\begin{aligned}{}[q_2]_\times \sum \limits _{j = 1}^3(q_1)_j T_j [q_3]_\times = 0_{3\times 3}. \end{aligned}$$
(11)

Note that matrix relation (11) is linear in the entries of T. It consists of nine scalar equations, but only four of them are linearly independent.

The calibrated trifocal tensor (CTFT) \({\hat{T}}\) is the trifocal tensor for calibrated cameras \(P_1 = \begin{bmatrix} I&\quad 0 \end{bmatrix}\), \(P_2 = \begin{bmatrix} R_2&\quad t_2 \end{bmatrix}\) and \(P_3 = \begin{bmatrix} R_3&\quad t_3 \end{bmatrix}\), where \(R_2, R_3 \in {\mathrm {SO}}(3)\), \(t_2, t_3 \in {\mathbb {R}}^3\), i.e.,

$$\begin{aligned} {\hat{T}}_k = R_2 e_k t_3^{{\mathrm {T}}} - t_2 e_k^{{\mathrm {T}}} R_3^{{\mathrm {T}}}. \end{aligned}$$
(12)

The CTFT is an analog of the essential matrix in three views. The tensors T and \({\hat{T}}\) are related by

$$\begin{aligned} T_j \sim K_2 \sum \limits _{k = 1}^3(K_1^{-{\mathrm {T}}})_{jk}{\hat{T}}_k K_3^{{\mathrm {T}}}, \end{aligned}$$
(13)

where \(K_k\) is the calibration matrix of the kth camera.

For any invertible \(3\times 3\) matrix M and 3-vector t, the following identity holds:

$$\begin{aligned}{}[M^{-1}t]_\times = \det (M^{-1}) M^{{\mathrm {T}}}[t]_\times M. \end{aligned}$$

Therefore, the trifocal incidence relation (11) for the CTFT becomes

$$\begin{aligned}{}[{\hat{q}}_2]_\times \sum \limits _{j = 1}^3({\hat{q}}_1)_j {\hat{T}}_j [{\hat{q}}_3]_\times = 0_{3\times 3}, \end{aligned}$$

where \({\hat{q}}_k = K_k^{-1} q_k\) are the normalized coordinates.

The tensors T and \({\hat{T}}\) have 18 and 11 degrees of freedom, respectively. It follows that matrices \({\hat{T}}_k\) must satisfy a number of additional algebraic constraints. Some of them are described in Sect. 4 below.

3 The Trifocal Essential Matrix and Its Characterization

The trifocal essential matrix is, by definition, a \(3\times 3\) matrix S which can be represented in form

$$\begin{aligned} S = s_1 t_1^{{\mathrm {T}}} + t_2 s_2^{{\mathrm {T}}}, \end{aligned}$$
(14)

where \(t_1, t_2, s_1, s_2 \in {\mathbb {C}}^3\), and vectors \(s_1, s_2\) are nonzero and such that \(s_k^{{\mathrm {T}}}s_k = 0\), \(k = 1, 2\). It is clear that matrices S, \(S^{{\mathrm {T}}}\) and RSQ, where \(R, Q \in {\mathrm {SO}}(3, {\mathbb {C}})\), simultaneously are (or are not) the trifocal essential matrices.

Theorem 5

Let a \(3\times 3\) matrix S be a trifocal essential matrix. Then \(SS^{{\mathrm {T}}}\) has one zero and two other equal eigenvalues.

Proof

Let S be a trifocal essential matrix, i.e., it can be represented in form (14). The matrix \(SS^{{\mathrm {T}}}\) has zero eigenvalue, as \(\det S = 0\). Taking into account that \(s_2^{{\mathrm {T}}}s_2 = 0\), we get

$$\begin{aligned} SS^{{\mathrm {T}}} = s_1(\mu s_1^{{\mathrm {T}}} + \nu t_2^{{\mathrm {T}}}) + \nu t_2s_1^{{\mathrm {T}}}, \end{aligned}$$
(15)

where we have denoted \(\mu = t_1^{{\mathrm {T}}}t_1\), \(\nu = s_2^{{\mathrm {T}}}t_1\). By Lemma 7 (see the Appendix), the potentially nonzero eigenvalues of (15) are equal to the ones of \(2\times 2\) matrix

$$\begin{aligned} \begin{bmatrix} \nu t_2^{{\mathrm {T}}}s_1&\quad \nu (\mu s_1^{{\mathrm {T}}} + \nu t_2^{{\mathrm {T}}}) t_2 \\ 0&\quad \nu s_1^{{\mathrm {T}}}t_2 \end{bmatrix}, \end{aligned}$$

and the eigenvalues of the latter matrix are both equal to \(\nu s_1^{{\mathrm {T}}}t_2 = (s_1^{{\mathrm {T}}}t_2)(s_2^{{\mathrm {T}}}t_1)\). Theorem 5 is proved. \(\square \)

Theorem 6

A \(3\times 3\) matrix S is a trifocal essential matrix if and only if

$$\begin{aligned}&\det S = 0, \end{aligned}$$
(16)
$$\begin{aligned}&{{\mathrm{tr}}}(SS^{{\mathrm {T}}})^2 - 2{{\mathrm{tr}}}((SS^{{\mathrm {T}}})^2) = 0. \end{aligned}$$
(17)

Proof

The“only if” part is due to Theorem 5 and Lemma 8 (see the Appendix). To prove the “if” part, let S be a \(3\times 3\) matrix satisfying (16), (17). We denote \(c_k\) the kth column of matrix S. Because S is degenerate, there exists a nonzero vector a such that \(Sa = 0\). There are two possibilities.

Case 1: \(a^{{\mathrm {T}}}a \ne 0\). Scaling a and post-multiplying S by an appropriate matrix from \({\mathrm {SO}}(3, {\mathbb {C}})\), we assume without loss of generality that \(a = \begin{bmatrix}0&\quad 0&\quad 1\end{bmatrix}^{{\mathrm {T}}}\). Therefore \(c_3 = 0\).

Suppose first that either \(c_1^{{\mathrm {T}}}c_1 \ne 0\) or \(c_2^{{\mathrm {T}}}c_2 \ne 0\). Without loss of generality we assume \(c_2^{{\mathrm {T}}}c_2 \ne 0\). Pre-multiplying S by an appropriate rotation, we obtain

$$\begin{aligned} S = \begin{bmatrix} \lambda&\quad \mu&\quad 0\\ \nu&\quad 0&\quad 0\\ 0&\quad 0&\quad 0 \end{bmatrix}. \end{aligned}$$

The substitution of S into (17) gives

$$\begin{aligned} ((\mu + \nu )^2 + \lambda ^2)((\mu - \nu )^2 + \lambda ^2) = 0. \end{aligned}$$

It follows that \(\lambda = i(\epsilon _1\mu + \epsilon _2\nu )\), where \(\epsilon _k = \pm 1\). Thus,

$$\begin{aligned} S= & {} \begin{bmatrix} i(\epsilon _1\mu + \epsilon _2\nu )&\quad \mu&\quad 0\\ \nu&\quad 0&\quad 0\\ 0&\quad 0&\quad 0\end{bmatrix} = \begin{bmatrix}i\epsilon _2 \\ 1 \\ 0 \end{bmatrix} \begin{bmatrix} \nu&\quad 0&\quad 0 \end{bmatrix}\\&+ \begin{bmatrix} \mu \\ 0 \\ 0\end{bmatrix} \begin{bmatrix} i\epsilon _1&\quad 1&\quad 0 \end{bmatrix}. \end{aligned}$$

Consider the case \(c_1^{{\mathrm {T}}}c_1 = c_2^{{\mathrm {T}}}c_2 = 0\). Due to Lemma 9 (see Appendix), we can pre-multiply S by an appropriate rotation to get

$$\begin{aligned} S = \begin{bmatrix} \alpha&\quad 1&\quad 0\\ \beta&\quad i&\quad 0\\ \gamma&\quad 0&\quad 0 \end{bmatrix}, \end{aligned}$$

where \(\alpha ^2 + \beta ^2 + \gamma ^2 = 0\). The substitution of S into (17) yields

$$\begin{aligned} 4(i\alpha - \beta )^2 = 0. \end{aligned}$$

It follows that \(\beta = i\alpha \) and \(\gamma = 0\). Therefore, matrix S has rank one and

$$\begin{aligned} S = \begin{bmatrix} \alpha&\quad 1&\quad 0\\ i\alpha&\quad i&\quad 0\\ 0&\quad 0&\quad 0\end{bmatrix} = \begin{bmatrix} 1 \\ i \\ 0 \end{bmatrix} \begin{bmatrix} \alpha&\quad 1&\quad 0 \end{bmatrix} + 0 s^{{\mathrm {T}}}, \end{aligned}$$

where s is an arbitrary 3-vector satisfying \(s^{{\mathrm {T}}} s = 0\). Thus in either case S is a trifocal essential matrix, as required.

Case 2: \(a^{{\mathrm {T}}}a = 0\). Due to Lemma 9, we can post-multiply S by an appropriate matrix from \({\mathrm {SO}}(3, {\mathbb {C}})\) and suppose without loss of generality that \(a = \begin{bmatrix}0&\quad 1&\quad i\end{bmatrix}^{{\mathrm {T}}}\). Therefore \(c_3 = ic_2\).

By direct computation, equality (17) becomes \((c_1^{{\mathrm {T}}}c_1)^2 = 0\), i.e., \(c_1^{{\mathrm {T}}}c_1 = 0\). This yields

$$\begin{aligned} S = \begin{bmatrix}\alpha&\quad \lambda&\quad i\lambda \\ \beta&\quad \mu&\quad i\mu \\ \gamma&\quad \nu&\quad i\nu \end{bmatrix} = \begin{bmatrix} \alpha \\ \beta \\ \gamma \end{bmatrix} \begin{bmatrix} 1&\quad 0&\quad 0 \end{bmatrix} + \begin{bmatrix}\lambda \\ \mu \\ \nu \end{bmatrix} \begin{bmatrix}0&\quad 1&\quad i\end{bmatrix}, \end{aligned}$$

where \(\alpha ^2 + \beta ^2 + \gamma ^2 = 0\), i.e., S is a trifocal essential matrix. Theorem 6 is proved. \(\square \)

We notice that constraints (16), (17) coincide with constraints (5), (6) from Theorem 2. Hence, if a trifocal essential matrix is real, then it is an essential matrix.

In general, a trifocal essential matrix does not satisfy cubic constraint (7). The proof consists in exhibiting a counterexample. Let \(s_1 = s_2 = \begin{bmatrix}1&\quad i&\quad 0\end{bmatrix}^{{\mathrm {T}}}\), \(t_1 = t_2 = \begin{bmatrix}1&\quad 0&\quad 0\end{bmatrix}^{{\mathrm {T}}}\). Then \(S = \begin{bmatrix} 2&\quad i&\quad 0\\ i&\quad 0&\quad 0\\ 0&\quad 0&\quad 0\end{bmatrix}\) and the eigenvalues of \(SS^{{\mathrm {T}}}\) are 0, 1, 1. However,

$$\begin{aligned} ({{\mathrm{tr}}}(SS^{{\mathrm {T}}})I - 2SS^{{\mathrm {T}}})S = -4\begin{bmatrix}1&i&\quad 0 \\ i&\quad -1&\quad 0\\ 0&\quad 0&\quad 0 \end{bmatrix} \ne 0_{3\times 3}. \end{aligned}$$

Nevertheless, there exists an analog of identity (7) for trifocal essential matrices.

Theorem 7

A \(3\times 3\) matrix S is a trifocal essential matrix if and only if

$$\begin{aligned} ({{\mathrm{tr}}}(SS^{{\mathrm {T}}}) I - 2SS^{{\mathrm {T}}})^2 S = 0_{3\times 3}. \end{aligned}$$
(18)

Proof

Let us denote

$$\begin{aligned} \Phi (M) = ({{\mathrm{tr}}}(MM^{{\mathrm {T}}}) I - 2MM^{{\mathrm {T}}})^2 M \end{aligned}$$

and

$$\begin{aligned} \varphi (M) = {{\mathrm{tr}}}(MM^{{\mathrm {T}}})^2 - 2{{\mathrm{tr}}}((MM^{{\mathrm {T}}})^2). \end{aligned}$$

Then it is straightforward to show that, for arbitrary \(3\times 3\) matrix M, the following identity holds:

$$\begin{aligned} \Phi (M) = 4M^*\det M - M\varphi (M), \end{aligned}$$
(19)

where \(M^*\) is meant the matrix of cofactors of M.

Let matrix S be a trifocal essential matrix. By Theorem 6, \(\det S = \varphi (S) = 0\). Then it follows from (19) that \(\Phi (S) = 0_{3\times 3}\), i.e., (18) holds. The “only if” part is proved.

Conversely, let a \(3\times 3\) matrix S satisfy (18), i.e., \(\Phi (S) = 0_{3\times 3}\). It suffices to show that \(\det S = 0\). Suppose, by hypothesis, that \(\det S \ne 0\). Then, post-multiplying (18) by \(S^{-1}\), we get

$$\begin{aligned} ({{\mathrm{tr}}}(SS^{{\mathrm {T}}}) I - 2SS^{{\mathrm {T}}})^2 = 0_{3\times 3}. \end{aligned}$$

It follows that all the eigenvalues of \({{\mathrm{tr}}}(SS^{{\mathrm {T}}}) I - 2SS^{{\mathrm {T}}}\) are zeroes and

$$\begin{aligned} {{\mathrm{tr}}}({{\mathrm{tr}}}(SS^{{\mathrm {T}}}) I - 2SS^{{\mathrm {T}}}) = {{\mathrm{tr}}}(SS^{{\mathrm {T}}}) = 0. \end{aligned}$$

The substitution of this into (18) yields \((\det S)^5 = 0\) in contradiction to the hypothesis \(\det S \ne 0\). Thus, \(\det S = 0\) and, by (19), \(\varphi (S) = 0\). By Theorem 6, matrix S is a trifocal essential matrix. Theorem 7 is proved. \(\square \)

To summarize, the above theorems imply the following statements.

  • The pair of scalar constraints (16), (17) of degrees 3 and 4 respectively is equivalent to the single matrix constraint (18) of degree 5.

  • The most general form of a \(3\times 3\) matrix satisfying Eqs. (16) and (17) is the trifocal essential matrix given by (14).

  • If a trifocal essential matrix is real, then it is an essential matrix.

  • Every essential matrix is a trifocal essential matrix, but the converse is not true in general.

4 Three Necessary Conditions on a Calibrated Trifocal Tensor

A new notion of trifocal essential matrix, introduced in the previous section, turns out to be closely related to calibrated trifocal tensors. The connection is established by the following lemma.

Lemma 1

Let \({\hat{T}} = \begin{bmatrix}{\hat{T}}_1&{\hat{T}}_2&{\hat{T}}_3\end{bmatrix}\) be a CTFT. Then a \(3\times 3\) matrix \(S_{{\hat{T}}} = \alpha {\hat{T}}_1 + \beta {\hat{T}}_2 + \gamma {\hat{T}}_3\), where numbers \(\alpha , \beta , \gamma \) are such that \(\alpha ^2 + \beta ^2 + \gamma ^2 = 0\), is a trifocal essential matrix, i.e., it can be represented in form (14).

Proof

We notice that

$$\begin{aligned} S_{{\hat{T}}}= & {} \alpha {\hat{T}}_1 + \beta {\hat{T}}_2 + \gamma {\hat{T}}_3 = R_2 s t_3^{{\mathrm {T}}} - t_2 s^{{\mathrm {T}}} R_3^{{\mathrm {T}}}\\= & {} s_2 t_3^{{\mathrm {T}}} + (-t_2) s_3^{{\mathrm {T}}}, \end{aligned}$$

where \(s = \begin{bmatrix}\alpha&\quad \beta&\quad \gamma \end{bmatrix}^{{\mathrm {T}}}\), and \(s_k = R_k s\) are 3-vectors satisfying

$$\begin{aligned} s_k^{{\mathrm {T}}} s_k = s^{{\mathrm {T}}}R_k^{{\mathrm {T}}}R_k s = s^{{\mathrm {T}}}s = 0. \end{aligned}$$

It follows that \(S_{{\hat{T}}}\) is a trifocal essential matrix. Lemma 1 is proved. \(\square \)

The trifocal essential matrix associated with a CTFT \({\hat{T}} = \begin{bmatrix}{\hat{T}}_1&{\hat{T}}_2&{\hat{T}}_3\end{bmatrix}\) is defined by

$$\begin{aligned} S_{{\hat{T}}}(s) = \sum \limits _{j = 1}^3 (s)_j{\hat{T}}_j = \alpha {\hat{T}}_1 + \beta {\hat{T}}_2 + \gamma {\hat{T}}_3, \end{aligned}$$
(20)

where \(s = \begin{bmatrix}\alpha&\beta&\gamma \end{bmatrix}^{{\mathrm {T}}}\) and \(s^{{\mathrm {T}}}s = 0\). It is worth emphasizing that \(S_{{\hat{T}}}(s)\) is a \(3\times 3\) degenerate matrix which generically has complex entries.

We are going to apply the two characterizations from Sect. 3 to derive the necessary conditions on the entries of CTFT \({\hat{T}}\).

In the rest of this section, calibrated trifocal tensors are allowed to have complex entries, that is in (12) matrices \(R_2, R_3\) belong to \({\mathrm {SO}}(3, {\mathbb {C}})\), and vectors \(t_2, t_3\) are in \({\mathbb {C}}^3\).

Let us introduce six symmetric matrices (\(k = 1, 2, 3\)):

$$\begin{aligned} \begin{aligned} U_k&= {\hat{T}}_k {\hat{T}}_k^{{\mathrm {T}}},\\ V_k&= {\hat{T}}_k {\hat{T}}_{k + 1}^{{\mathrm {T}}} + {\hat{T}}_{k + 1} {\hat{T}}_k^{{\mathrm {T}}}. \end{aligned} \end{aligned}$$
(21)

Here \(k + 1\) should be read as \(k \pmod 3 +1\), i.e., \(V_3 = {\hat{T}}_3 {\hat{T}}_1^{{\mathrm {T}}} + {\hat{T}}_1 {\hat{T}}_3^{{\mathrm {T}}}\).

Theorem 8

(First necessary condition) Let \({\hat{T}} = \begin{bmatrix}{\hat{T}}_1&{\hat{T}}_2&{\hat{T}}_3\end{bmatrix}\) be a CTFT, matrices \(U_k\), \(V_k\) be defined in (21). Then the entries of \({\hat{T}}\) are constrained by the following equations:

$$\begin{aligned}&\psi (U_3 - U_1, U_3 - U_1) - \psi (V_3, V_3) = 0, \end{aligned}$$
(22)
$$\begin{aligned}&\psi (U_3 - U_1, V_1) + \psi (V_2, V_3) = 0, \end{aligned}$$
(23)
$$\begin{aligned}&\psi (U_1 - U_2, V_1) = 0, \end{aligned}$$
(24)

where \(\psi (X, Y) = {{\mathrm{tr}}}(X){{\mathrm{tr}}}(Y) - 2{{\mathrm{tr}}}(XY)\). Six more equations are obtained from (22) to (24) by a cyclic permutation of indices \(1 \rightarrow 2 \rightarrow 3 \rightarrow 1\). The resulting nine equations are linearly independent.

Proof

Let \(S_{{\hat{T}}} = \alpha {\hat{T}}_1 + \beta {\hat{T}}_2 + \gamma {\hat{T}}_3\) be a trifocal essential matrix associated with \({\hat{T}}\). By Theorem 6, the following equation holds:

$$\begin{aligned} {{\mathrm{tr}}}(S_{{\hat{T}}}S_{{\hat{T}}}^{{\mathrm {T}}})^2 - 2{{\mathrm{tr}}}((S_{{\hat{T}}}S_{{\hat{T}}}^{{\mathrm {T}}})^2) = 0. \end{aligned}$$
(25)

The definition of matrices \(U_k\), \(V_k\) (see (21)) permits us to write

$$\begin{aligned} S_{{\hat{T}}}S_{{\hat{T}}}^{{\mathrm {T}}} = \alpha ^2 U_1 + \beta ^2 U_2 + \gamma ^2 U_3 + \alpha \beta V_1 + \beta \gamma V_2 + \gamma \alpha V_3. \end{aligned}$$

Substituting this into (25), we find the coefficients in \(\alpha ^4\), \(\alpha ^3\beta \) and \(\alpha \beta ^3\) taking into account that \(\gamma ^2 = -\alpha ^2 - \beta ^2\). Because \(\alpha \) and \(\beta \) are arbitrary, these coefficients must vanish:

$$\begin{aligned} \alpha ^4&:\psi (U_3 - U_1, U_3 - U_1) - \psi (V_3, V_3) = 0, \end{aligned}$$
(26)
$$\begin{aligned} \alpha ^3\beta&:\psi (U_1 - U_3, V_1) - \psi (V_2, V_3) = 0, \end{aligned}$$
(27)
$$\begin{aligned} \alpha \beta ^3&:\psi (U_2 - U_3, V_1) - \psi (V_2, V_3) = 0. \end{aligned}$$
(28)

Thus we get (22) = (26), (23) =  – (27), and (24)  =  (27) – (28). It is clear that we can get six more constraints on \({\hat{T}}_k\) from (22) to (24) by a cyclic permutation of the indices.

Finally, the resulting nine polynomials can not be linearly dependent, since each of them contains monomials that are not contained in all the other polynomials. Examples of such monomials for (22), (23) and (24) are \(({\hat{T}}_3)^2_{11}({\hat{T}}_1)^2_{11}\), \(({\hat{T}}_3)^2_{11}({\hat{T}}_1)_{11}({\hat{T}}_2)_{11}\) and \(({\hat{T}}_1)^3_{11}({\hat{T}}_2)_{11}\) respectively. Theorem 8 is proved.

From now on, the nine equalities from Theorem 8 will be referred to as the eigenvalue constraints.

Lemma 2

Let \(T = \begin{bmatrix}T_1&T_2&T_3\end{bmatrix}\) be a (2, 1) tensor satisfying the ten extended rank and nine eigenvalue constrains. Then matrix \(S_T = \alpha T_1 + \beta T_2 + \gamma T_3\) with \(\alpha ^2 + \beta ^2 + \gamma ^2 = 0\) is a trifocal essential matrix.

Proof

The extended rank constraints imply \(\det S_T = 0\). Taking into account that \(\gamma ^2 = -\alpha ^2 - \beta ^2\), we conclude that the expression

$$\begin{aligned} \varphi (S_T) = {{\mathrm{tr}}}(S_TS_T^{{\mathrm {T}}})^2 - 2{{\mathrm{tr}}}((S_TS_T^{{\mathrm {T}}})^2) \end{aligned}$$

contains 9 monomials:

$$\begin{aligned} \alpha ^4, \alpha ^3\beta , \alpha ^3\gamma , \alpha ^2\beta ^2, \alpha ^2\beta \gamma , \alpha \beta ^3, \alpha \beta ^2\gamma , \beta ^4, \beta ^3\gamma . \end{aligned}$$

It is directly verified that the coefficients in all of them are linear combinations of the nine polynomials from Theorem 8, i.e., \(\varphi (S_T) = 0\). By Theorem 6, \(S_T\) is a trifocal essential matrix, as required. \(\square \)

Theorem 9

(Second necessary condition) Let \({\hat{T}} = \begin{bmatrix}{\hat{T}}_1&{\hat{T}}_2&{\hat{T}}_3\end{bmatrix}\) be a CTFT. Then the entries of \({\hat{T}}\) are constrained by the 99 linearly independent quintic (of degree 5) polynomial equations.

Proof

Let \(S_{{\hat{T}}} = \alpha {\hat{T}}_1 + \beta {\hat{T}}_2 + \gamma {\hat{T}}_3\) be a trifocal essential matrix associated with \({\hat{T}}\). By Theorem 7, the following equation holds:

$$\begin{aligned} ({{\mathrm{tr}}}(S_{{\hat{T}}}S_{{\hat{T}}}^{{\mathrm {T}}}) I - 2S_{{\hat{T}}}S_{{\hat{T}}}^{{\mathrm {T}}})^2 S_{{\hat{T}}} = 0_{3\times 3}. \end{aligned}$$
(29)

We notice that equality (29) is quintic in the entries of matrix \(S_{{\hat{T}}}\). Taking into account that \(\gamma ^2 = -\alpha ^2 - \beta ^2\), every entry in the l.h.s. of (29) contains 11 monomials in variables \(\alpha \), \(\beta \) and \(\gamma \). Because the coefficient in each of these monomials must vanish, there are in total 99 quintic polynomial constraints on the entries of \({\hat{T}}\). Theorem 9 is proved. \(\square \)

Remark 2

An explicit form of the quintic polynomial equations from Theorem 9 is as follows:

$$\begin{aligned}&(\Psi _1(U_{13}) - \Psi _1(V_3)){\hat{T}}_1 - \Psi _2(U_{13}, V_3){\hat{T}}_3 = 0_{3\times 3}, \end{aligned}$$
(30)
$$\begin{aligned}&\Psi _2(U_{13}, V_3){\hat{T}}_1 + (\Psi _1(U_{13}) - \Psi _1(V_3)){\hat{T}}_3 = 0_{3\times 3}, \end{aligned}$$
(31)
$$\begin{aligned}&(\Psi _2(U_{13}, V_2) + \Psi _2(V_1, V_3)){\hat{T}}_1 + \Psi _2(U_{13}, V_3){\hat{T}}_2\nonumber \\&\quad + (\Psi _2(U_{13}, V_1) - \Psi _2(V_2, V_3)){\hat{T}}_3 = 0_{3\times 3}, \end{aligned}$$
(32)
$$\begin{aligned}&(\Psi _2(U_{13}, V_1) - \Psi _2(V_2, V_3)){\hat{T}}_1 + (\Psi _1(U_{13}) - \Psi _1(V_3)){\hat{T}}_2\nonumber \\&\quad - (\Psi _2(U_{13}, V_2) + \Psi _2(V_1, V_3)){\hat{T}}_3 = 0_{3\times 3}, \end{aligned}$$
(33)

where matrices \(U_k\), \(V_k\) are defined in (21), \(U_{jk} = U_j - U_k\), and

$$\begin{aligned} \Psi (X, Y)&= ({{\mathrm{tr}}}(X)I - 2X)({{\mathrm{tr}}}(Y)I - 2Y),\\ \Psi _1(X)&= \Psi (X, X),\\ \Psi _2(X, Y)&= \Psi (X, Y) + \Psi (Y, X). \end{aligned}$$

Equations (30)–(33) give \(4\times 9 = 36\) constraints on \({\hat{T}}\). We get 72 more equations from (30) to (33) by a cyclic permutation of indices \(1 \rightarrow 2 \rightarrow 3 \rightarrow 1\). In total, there are 108 quintic constraints. Let \(M_k\) be the kth version of the L.H.S. of (32). Then we have

$$\begin{aligned} M_1 + M_2 + M_3 \equiv 0_{3\times 3}. \end{aligned}$$

It follows that eqs. (30)–(33) give only \(108 - 9 = 99\) constraints. Their linear independence is verified directly.

Theorem 10

A (2, 1) tensor \(T = \begin{bmatrix}T_1&T_2&T_3\end{bmatrix}\) satisfies the ten extended rank and nine eigenvalue constrains if and only if it satisfies the 99 quintic constraints from Theorem 9.

Proof

The result immediately follows from Lemma 2 and the two characterizations of trifocal essential matrices (Theorems 6 and 7). \(\square \)

Theorem 10 implies the equivalence of the two sets of constraints. From this point of view the quintic polynomials contribute nothing new and seem to be redundant. Nevertheless, we expect them to be useful in deriving more (quintic) polynomial constraints on CTFTs. We return to this question in Sect. 6.

Finally, we propose the third necessary condition on a CTFT. It seems not to be directly related to the matrix \(S_{{\hat{T}}}\). However, this condition could be useful in applications, since it consists of another set of quartic polynomial equations that are satisfied by a calibrated trifocal tensor.

Theorem 11

(Third necessary condition) Let \({\hat{T}} = \begin{bmatrix}{\hat{T}}_1&\quad {\hat{T}}_2&\quad {\hat{T}}_3\end{bmatrix}\) be a CTFT. Then the entries of \({\hat{T}}\) satisfy the following equations:

$$\begin{aligned}&{{\mathrm{tr}}}(U_2)^2 - {{\mathrm{tr}}}(V_3)^2 - {{\mathrm{tr}}}(U_2^2 - V_3^2 + (U_3 - U_1)^2) = 0, \end{aligned}$$
(34)
$$\begin{aligned}&{{\mathrm{tr}}}(V_2){{\mathrm{tr}}}(U_1 - 2U_2 - U_3) - {{\mathrm{tr}}}(V_1){{\mathrm{tr}}}(V_3) + 2{{\mathrm{tr}}}(V_2 U_2) = 0, \end{aligned}$$
(35)

where matrices \(U_k\), \(V_k\) are defined in (21). Four more equations are obtained from (34) to (35) by a cyclic permutation of indices \(1 \rightarrow 2 \rightarrow 3 \rightarrow 1\). The resulting six equations are linearly independent.

Proof

Let tensor \({\hat{T}}\) be represented in form (12). First we replace \({\hat{T}}\) with \({\hat{T}}' = \begin{bmatrix}R_2^{{\mathrm {T}}}{\hat{T}}_1R_3&R_2^{{\mathrm {T}}}{\hat{T}}_2R_3&R_2^{{\mathrm {T}}}{\hat{T}}_3R_3\end{bmatrix}\). Then the correlation slices of \({\hat{T}}'\) are simplified to \({\hat{T}}'_k = e_kt_3^{{\mathrm {T}}} - t_2e_k^{{\mathrm {T}}}\). A straightforward computation proves that \({\hat{T}}'\) satisfies eqs. (34) – (35) and the four their consequences. Then so does \({\hat{T}}\), since \(U_k = R_2 U'_k R_2^{{\mathrm {T}}}\) and \(V_k = R_2 V'_k R_2^{{\mathrm {T}}}\).

The resulting six polynomials can not be linearly dependent, as each of them contains monomials that are not contained in all the other polynomials. Examples of such monomials for (34) and (35) are \(({\hat{T}}_3)^2_{11}({\hat{T}}_1)^2_{11}\) and \(({\hat{T}}_2)_{11}({\hat{T}}_3)^3_{11}\) respectively. Theorem 11 is proved. \(\square \)

The 15 equalities from Theorems 8 and 11 will be further referred to as the quartic constraints.

Remark 3

Let us briefly describe the way by which the six constraints from Theorem 11 were initially derived. The nine eigenvalue polynomial equations consist in total of 2160 monomials. We constructed the dense matrix A of size \(2160\times 2160\) such that each row of A is the monomial vector taken on a randomly generated CTFT. Using the singular value decomposition of A, we found that the null space of A has dimension 15. It is meant that in addition to the eigenvalue constraints, there must exist six more quartic equations linearly independent with them. The (small integer) coefficients of these equations were derived by the Gauss–Jordan elimination on the basis vectors of the null space of A.

Remark 4

The eigenvalue constraints do not imply the six equalities from Theorem 11. The following trifocal tensor gives a counterexample:

$$\begin{aligned} T = \begin{bmatrix}\begin{bmatrix} 0&\quad 0&\quad 0\\ 0&\quad 0&\quad 1\\ 0&\quad -1&\quad 0\end{bmatrix}&\quad \begin{bmatrix} 0&\quad 0&\quad 1\\ 0&\quad 0&\quad 0\\ -1&\quad 0&\quad 0 \end{bmatrix}&\begin{bmatrix} 0&\quad 0&\quad 1\\ 0&\quad 0&\quad 1\\ -1&\quad -1&\quad 0 \end{bmatrix}\end{bmatrix}. \end{aligned}$$

One verifies that T satisfies the eigenvalue constraints, but not the six ones from Theorem 11. Hence T is not calibrated.

Remark 5

Generically, over the field of complex numbers, the quartic constraints are insufficient for a trifocal tensor T to be calibrated. Here is a counterexample. Consider a (2, 1) tensor

$$\begin{aligned} T = \begin{bmatrix} \begin{bmatrix} i&\quad 0&\quad 0\\ 0&\quad i&\quad 0\\ 0&\quad 0&\quad 0 \end{bmatrix}&\quad \begin{bmatrix} 0&\quad 0&\quad i\\ -i&\quad -1&\quad 1\\ 0&\quad 0&\quad 0 \end{bmatrix}&\begin{bmatrix} 1&\quad 0&\quad 0\\ -i&\quad 0&\quad 0\\ i&\quad 1&\quad 0 \end{bmatrix} \end{bmatrix}. \end{aligned}$$
(36)

It is trifocal, as

$$\begin{aligned} T_k = \begin{bmatrix} 1&\quad 0&\quad 0\\ 0&\quad -1&\quad 0\\ 0&\quad 0&\quad 1 \end{bmatrix} e_k \begin{bmatrix} i&\quad 1&\quad 0\end{bmatrix} - \begin{bmatrix} i \\ 1 \\ 0 \end{bmatrix} e_k^{{\mathrm {T}}} \begin{bmatrix}0&\quad -i&\quad 0\\ 0&\quad 0&\quad -1\\ i&\quad 0&\quad 0 \end{bmatrix}. \end{aligned}$$

Moreover, T satisfies all the 15 quartic constraints. Suppose that T is calibrated. Then there must exist 3-vectors \(u_k, v_k, t_2, t_3\) such that \(u_k^{{\mathrm {T}}} u_k = v_k^{{\mathrm {T}}} v_k = 1\) and

$$\begin{aligned} T_k = u_k t_3^{{\mathrm {T}}} - t_2 v_k^{{\mathrm {T}}}. \end{aligned}$$

Let us define an ideal:

$$\begin{aligned} J = \langle T_k - u_k t_3^{{\mathrm {T}}} + t_2 v_k^{{\mathrm {T}}}, u_k^{{\mathrm {T}}} u_k - 1, v_k^{{\mathrm {T}}} v_k - 1 \mid k = 1, 2, 3\rangle . \end{aligned}$$

Then \(J \subset {\mathbb {C}}[\xi _1, \ldots , \xi _{24}]\), where \(\xi _j\) are the entries of vectors \(t_2, t_3, u_1, u_2, u_3, v_1, v_2\) and \(v_3\). It is straightforward to show by the computation of the Gröbner basis of J that \(1 \in J\). It follows that the affine variety defined by J is empty, and thus T cannot be calibrated.

5 A Characterization of Real Calibrated Trifocal Tensors

In this section, we are going to obtain a three-view analog of Theorem 2. First, it will be shown that a real trifocal tensor is calibrated if and only if it satisfies the 15 quartic constraints (Theorem 12). After that, it is straightforward to combine this result with the characterization of trifocal tensors, e.g., from [2] to get a complete set of constraints characterizing a real CTFT (Theorem 13).

First we prove several lemmas.

Lemma 3

Let \(T = \begin{bmatrix}T_1&T_2&T_3\end{bmatrix}\) be a real or complex (2, 1) tensor and \(T' = \begin{bmatrix}T'_1&T'_2&T'_3\end{bmatrix}\) be a tensor defined by

$$\begin{aligned} T'_j = Q_2 \sum \limits _{k = 1}^3(Q_1)_{jk}T_k Q_3^{{\mathrm {T}}}, \end{aligned}$$
(37)

where \(Q_1, Q_2, Q_3 \in {\mathrm {SO}}(3, {\mathbb {C}})\). Then T and \(T'\) simultaneously

  1. 1.

    are (or are not) calibrated trifocal tensors;

  2. 2.

    satisfy (or do not satisfy) the 10 extended rank and 15 quartic constraints.

Proof

1. Let T be a CTFT, so that its correlation slices can be represented in form (12). Then,

$$\begin{aligned} T'_j= & {} Q_2 \sum \limits _{k = 1}^3(Q_1)_{jk}T_k Q_3^{{\mathrm {T}}} \\= & {} (Q_2R_2Q_1^{{\mathrm {T}}}) e_j (Q_3t_3)^{{\mathrm {T}}} - (Q_2t_2) e_j^{{\mathrm {T}}} (Q_3R_3Q_1^{{\mathrm {T}}})^{{\mathrm {T}}}, \end{aligned}$$

i.e., \(T'\) is a CTFT as well. On the other hand, if T is not a CTFT, then so is not \(T'\), since

$$\begin{aligned} T_k = Q_2^{{\mathrm {T}}} \sum \limits _{j = 1}^3(Q_1)_{jk}T'_j Q_3. \end{aligned}$$
(38)

2. Let T be a (2, 1) tensor satisfying the 10 extended rank and 15 quartic constraints. Let us construct the matrix \(S_T(s) = \sum \limits _{k = 1}^3(s)_k T_k\), where s is an arbitrary 3-vector. The ten extended rank constraints are then equivalent to \(\det S_T(s) = 0\). We get

$$\begin{aligned} S_{T'}(s) = \sum \limits _{j = 1}^3(s)_j T'_j = Q_2S_T(Q_1^{{\mathrm {T}}}s) Q_3^{{\mathrm {T}}}, \end{aligned}$$
(39)

and thus \(\det S_{T'}(s) = 0\), i.e., tensor \(T'\) satisfies the ten extended rank constraints as well.

Further, if the vector s is such that \(s^{{\mathrm {T}}}s = 0\), then Lemma 2 implies that \(S_T(s)\) is a trifocal essential matrix. It follows from (39) that so is \(S_{T'}(s)\). After that, using the same arguments as in the proof of Theorem 8, one shows that tensor \(T'\) satisfies the nine eigenvalue constraints.

It remains to prove that \(T'\) satisfies also the six constraints from Theorem 11. We denote by \(p_k(T)\) the l.h.s. of the kth quartic equation on tensor T so that \(p_{10}, \ldots , p_{15}\) are the six polynomials from Theorem 11. Then, by a straightforward computation, we get

$$\begin{aligned} p_j(T') = \sum \limits _{k = 1}^{15} \xi _{jk}\, p_k(T), \qquad j = 10, \ldots , 15, \end{aligned}$$
(40)

where \(\xi _{jk}\) are polynomial expressions depending only on the entries of matrix \(Q_1\). It follows that if \(p_k(T) = 0\) for all k, then also \(p_j(T') = 0\) for all j.

Finally, if T does not satisfy the extended rank and quartic equations, then due to (38) so does not \(T'\). This completes the proof of Lemma 3. \(\square \)

Lemma 4

Let \(T = \begin{bmatrix}T_1&T_2&T_3\end{bmatrix}\) be a real trifocal tensor. Then there exist matrices \(Q_1, Q_2, Q_3 \in {\mathrm {SO}}(3)\) such that T can be transformed by (37) to the trifocal tensor

$$\begin{aligned} T' = \begin{bmatrix}\begin{bmatrix} 0&\quad 0&\quad \lambda _1\\ 0&\quad 0&\quad 0\\ \nu _1&\quad \rho _1&\quad \sigma _1 \end{bmatrix}&\quad \begin{bmatrix} 0&\quad 0&\quad 0\\ 0&\quad 0&\quad \mu _2\\ \nu _2&\quad \rho _2&\quad \sigma _2 \end{bmatrix}&\begin{bmatrix} 0&\quad 0&\quad 0\\ 0&\quad 0&\quad 0\\ 0&\quad \rho _3&\quad \sigma _3 \end{bmatrix}\end{bmatrix}, \end{aligned}$$
(41)

where \(\lambda _1\), \(\mu _2\), \(\nu _1\), \(\nu _2\), \(\rho _k\), \(\sigma _k\) are real scalars.

Proof

We are going to explicitly construct rotations \(Q_1\), \(Q_2\) and \(Q_3\) such that T is transformed to \(T'\) by (37). Since T is a trifocal tensor, we have

$$\begin{aligned} T_k = A_2 e_k a_3^{{\mathrm {T}}} - a_2 e_k^{{\mathrm {T}}} A_3^{{\mathrm {T}}}. \end{aligned}$$

Let \(H_j \in {\mathrm {SO}}(3)\) be the Householder matrix such that \(H_j a_j = \begin{bmatrix}0&0&\gamma _j\end{bmatrix}^{{\mathrm {T}}}\), \(j = 2, 3\). First we pre- and post-multiply each \(T_k\) by \(H_2\) and \(H_3^{{\mathrm {T}}}\), respectively, and denote by \(B_j\) a \(2\times 3\) matrix consisting of the first two rows of \(H_jA_j\). After that, we make the singular value decomposition of \(\gamma _3B_2\) to decompose it in form

$$\begin{aligned} \gamma _3B_2 = U \begin{bmatrix} \lambda _1&\quad 0&\quad 0\\ 0&\quad \mu _2&\quad 0 \end{bmatrix} V^{{\mathrm {T}}}, \end{aligned}$$

where \(U \in {\mathrm {SO}}(2)\) and \(V \in {\mathrm {SO}}(3)\). Finally, let \(W \in {\mathrm {SO}}(2)\) be a rotation such that \((WB_3V)_{13} = 0\). We set

$$\begin{aligned} Q_1 = V^{{\mathrm {T}}}, \quad Q_2 = \begin{bmatrix} U^{{\mathrm {T}}}&\quad 0\\ 0&\quad 1\end{bmatrix} H_2, \quad Q_3 = \begin{bmatrix} W&\quad 0\\ 0&1 \end{bmatrix} H_3. \end{aligned}$$
(42)

One verifies that the trifocal tensor T is transformed to (41) by the rotations \(Q_1\), \(Q_2\) and \(Q_3\) defined in (42). Lemma 4 is proved. \(\square \)

We denote by \(p_1, \ldots , p_{15}\) the 15 quartic polynomials on the trifocal tensor \(T'\) defined by (41) and consider the ideal

$$\begin{aligned} J = \langle p_1, \ldots , p_{15} \rangle \subset {\mathbb {C}}[\lambda _1, \nu _1, \rho _1, \sigma _1, \mu _2, \nu _2, \rho _2, \sigma _2, \rho _3, \sigma _3]. \end{aligned}$$
(43)

Let \(\sqrt{J}\) be the radical of J. We are going to derive several polynomials that belong to \(\sqrt{J}\). For convenience we divide them into two parts presented in Lemmas 5 and 6.

Lemma 5

The polynomials

$$\begin{aligned}&(\lambda _1^2 - \mu _2^2) (\lambda _1^2 + \sigma _1^2), \end{aligned}$$
(44)
$$\begin{aligned}&(\lambda _1^2 - \mu _2^2) (\mu _2^2 + \sigma _2^2), \end{aligned}$$
(45)
$$\begin{aligned}&\rho _3 (\nu _1\sigma _1 + \nu _2\sigma _2), \end{aligned}$$
(46)
$$\begin{aligned}&\rho _3 (\nu _1\rho _1 + \nu _2\rho _2), \end{aligned}$$
(47)
$$\begin{aligned}&\rho _3 (\rho _3^2 + \sigma _3^2) (\nu _1^2 + \nu _2^2 - \rho _1^2 - \rho _2^2 - \rho _3^2), \end{aligned}$$
(48)
$$\begin{aligned}&(\rho _3^2 + \sigma _3^2) (\rho _1\sigma _1 + \rho _2\sigma _2 + \rho _3(\sigma _3 + \mu _2))\nonumber \\&\quad \times (\rho _1\sigma _1 + \rho _2\sigma _2 + \rho _3(\sigma _3 - \mu _2)), \end{aligned}$$
(49)
$$\begin{aligned}&\rho _3(\rho _3^2 + \sigma _3^2) (\nu _1^2 + \nu _2^2 - \sigma _1^2 - \sigma _2^2 - (\sigma _3 + \mu _2)^2)\nonumber \\&\quad \times (\nu _1^2 + \nu _2^2 - \sigma _1^2 - \sigma _2^2 - (\sigma _3 - \mu _2)^2) \end{aligned}$$
(50)

belong to \(\sqrt{J}\), where J is defined in (43).

Proof

Let p be any polynomial from (44) to (50). We construct an ideal \(\tilde{J} = J + \langle 1 - \tau p \rangle \subset {\mathbb {C}}[\lambda _1, \ldots , \sigma _3, \tau ]\), where \(\tau \) is a new variable. By direct computation of the Gröbner basis of \(\tilde{J}\), we get \(1 \in \tilde{J}\). Hence, by Lemma 10 (see Appendix), \(p \in \sqrt{J}\). Lemma 5 is proved. \(\square \)

Remark 6

Surprisingly, the computation of the Gröbner basis of each \(\tilde{J}\) takes only a few seconds in Maple even over the field of rationals. In our computations, we used the graded reverse lexicographic order [5]:

$$\begin{aligned} \lambda _1> \nu _1> \rho _1> \sigma _1> \mu _2> \nu _2> \rho _2> \sigma _2> \rho _3> \sigma _3 > \tau . \end{aligned}$$

Lemma 6

The polynomials

$$\begin{aligned}&(\nu _1^2 + \rho _1^2 + \sigma _1^2)(\sigma _1^2 + \sigma _2^2 - \rho _3^2 + \lambda _1^2 - \mu _2^2), \end{aligned}$$
(51)
$$\begin{aligned}&(\nu _2^2 + \rho _2^2 + \sigma _2^2)(\sigma _1^2 + \sigma _2^2 - \rho _3^2 - \lambda _1^2 + \mu _2^2), \end{aligned}$$
(52)
$$\begin{aligned}&\nu _1\nu _2 + \rho _1\rho _2 + \sigma _1\sigma _2, \end{aligned}$$
(53)
$$\begin{aligned}&\nu _1^2 + \rho _1^2 + \sigma _1^2 - \nu _2^2 - \rho _2^2 - \sigma _2^2 + \lambda _1^2 - \mu _2^2, \end{aligned}$$
(54)
$$\begin{aligned}&(\nu _1^2 + \rho _1^2 + \sigma _1^2 - \rho _3^2 - (\sigma _3 + \mu _2)^2 + \lambda _1^2 - \mu _2^2)\nonumber \\&\quad \times (\nu _1^2 + \rho _1^2 + \sigma _1^2 - \rho _3^2 - (\sigma _3 - \mu _2)^2 - \lambda _1^2 + \mu _2^2) \end{aligned}$$
(55)

belong to \(\sqrt{J}\), where J is defined in (43).

Proof

See the proof of Lemma 5. \(\square \)

Theorem 12

A real trifocal tensor \(T = \begin{bmatrix}T_1&T_2&T_3\end{bmatrix}\) is calibrated if and only if it satisfies the 15 quartic constraints from Theorems 8 and 11.

Proof

The “only if” part is due to Theorems 8 and 11. We now prove the “if” part.

Let \(T = \begin{bmatrix}T_1&T_2&T_3\end{bmatrix}\) be a real trifocal tensor satisfying the 15 quartic equations \(p_1 = \ldots = p_{15} = 0\). By Lemmas 3 and 4, there exist matrices \(Q_1, Q_2, Q_3 \in {\mathrm {SO}}(3)\) such that the trifocal tensor \(T'\) defined by (37) has form (41) and satisfies the 15 quartic equations as well.

First we note that if \(\lambda _1^2 - \mu _2^2 \ne 0\), then, as the trifocal tensor is real, we get from Lemma 5:

$$\begin{aligned} \lambda _1 = \sigma _1 = \mu _2 = \sigma _2 = 0. \end{aligned}$$

However, this is in contradiction to \(\lambda _1^2 - \mu _2^2 \ne 0\). As a result, a real solution to the 15 quartic equations on \(T'\) exists if and only if \(\lambda _1^2 = \mu _2^2\). Let us consider two cases: \(\rho _3 \ne 0\) and \(\rho _3 = 0\).

Case 1: \(\rho _3 \ne 0\). Then, \(\rho _3^2 + \sigma _3^2 \ne 0\) and, by Lemma 5, the entries of tensor \(T'\) are constrained by

$$\begin{aligned}&\nu _1\sigma _1 + \nu _2\sigma _2 = \nu _1\rho _1 + \nu _2\rho _2 = \nu _1^2 + \nu _2^2 - \rho _1^2 - \rho _2^2 - \rho _3^2 \nonumber \\&\quad = (\rho _1\sigma _1 + \rho _2\sigma _2 + \rho _3(\sigma _3 + \mu _2))(\rho _1\sigma _1 + \rho _2\sigma _2\nonumber \\&\qquad + \rho _3(\sigma _3 - \mu _2)) \nonumber \\&\quad = (\nu _1^2 + \nu _2^2 - \sigma _1^2 - \sigma _2^2 - (\sigma _3 + \mu _2)^2)\nonumber \\&\qquad \times (\nu _1^2 + \nu _2^2 - \sigma _1^2 - \sigma _2^2 - (\sigma _3 - \mu _2)^2) = 0. \end{aligned}$$
(56)

The correlation slices of \(T'\) can be represented in form

$$\begin{aligned} T'_k = A_2 e_k \begin{bmatrix}0\quad&\quad 0&\quad \mu _2\end{bmatrix} - \begin{bmatrix} 0 \\ 0 \\ -1\end{bmatrix} e_k^{{\mathrm {T}}} A_3^{{\mathrm {T}}}, \end{aligned}$$

where

$$\begin{aligned} A_2 = \begin{bmatrix} \epsilon _1&\quad 0&\quad 0\\ 0&\quad 1&\quad 0\\ 0&\quad 0&\quad \epsilon _2 \end{bmatrix}, \qquad A_3 = \begin{bmatrix}\nu _1&\nu _2&0\\ \rho _1&\quad \rho _2&\quad \rho _3\\ \sigma _1&\quad \sigma _2&\quad \sigma _3 - \epsilon _2\mu _2 \end{bmatrix}, \end{aligned}$$

and \(\epsilon _k = \pm 1\). It follows that \(A_2 = \pm R_2\), where \(R_2 \in {\mathrm {SO}}(3)\). Hence it suffices to show that \(A_3 = \theta R_3\), where \(\theta \) is a nonzero scalar and \(R_3 \in {\mathrm {SO}}(3)\). If we suppose that

$$\begin{aligned}&\rho _1\sigma _1 + \rho _2\sigma _2 + \rho _3(\sigma _3 - \epsilon _2\mu _2)\\&\quad = \nu _1^2 + \nu _2^2 - \sigma _1^2 - \sigma _2^2 - (\sigma _3 - \epsilon _2\mu _2)^2 = 0, \end{aligned}$$

then we are done, since due to (56) \(A_3A_3^{{\mathrm {T}}} = \theta ^2 I\) with \(\theta ^2 = \rho _1^2 + \rho _2^2 + \rho _3^2 \ne 0\).

On the other hand, if

$$\begin{aligned}&\rho _1\sigma _1 + \rho _2\sigma _2 + \rho _3(\sigma _3 - \epsilon _2\mu _2)\nonumber \\&\quad = \nu _1^2 + \nu _2^2 - \sigma _1^2 - \sigma _2^2 - (\sigma _3 + \epsilon _2\mu _2)^2 = 0, \end{aligned}$$
(57)

then we add these polynomials to J and denote the resulting ideal by \(J_1\). By the computation of the Gröbner basis of \(J_1\), we get \((\rho _3\mu _2\sigma _3)^3 \in J_1\). Since \(\rho _3 \ne 0\), it follows that either \(\mu _2 = 0\) or \(\sigma _3 = 0\). In both cases, equalities (56) and (57) imply \(A_3A_3^{{\mathrm {T}}} = \theta ^2 I\) with \(\theta ^2 = \rho _1^2 + \rho _2^2 + \rho _3^2 \ne 0\), and hence tensor \(T'\) is calibrated.

Case 2: \(\rho _3 = 0\). By Lemma 6, the entries of tensor \(T'\) are constrained by (we take into account that \(\lambda _1^2 = \mu _2^2\)).

$$\begin{aligned} (\nu _1^2 + \rho _1^2 + \sigma _1^2)(\sigma _1^2 + \sigma _2^2) = (\nu _2^2 + \rho _2^2 + \sigma _2^2)(\sigma _1^2 + \sigma _2^2) = 0. \end{aligned}$$

Since tensor \(T'\) is real, it follows that \(\sigma _1 = \sigma _2 = 0\). Again by Lemma 6, we have

$$\begin{aligned} \nu _1\nu _2 + \rho _1\rho _2= & {} \nu _1^2 + \rho _1^2 - \nu _2^2 - \rho _2^2\\= & {} (\nu _1^2 + \rho _1^2 - (\sigma _3 + \mu _2)^2) (\nu _1^2 + \rho _1^2 - (\sigma _3 - \mu _2)^2) = 0. \end{aligned}$$

Suppose first that \(\nu _1^2 + \rho _1^2 \ne 0\). Then the correlation slices of \(T'\) can be represented in form

$$\begin{aligned} T'_k = A_2 e_k \begin{bmatrix}0&\quad 0&\quad \mu _2\end{bmatrix} - \begin{bmatrix} 0 \\ 0 \\ -1\end{bmatrix} e_k^{{\mathrm {T}}} A_3^{{\mathrm {T}}}, \end{aligned}$$

where

$$\begin{aligned} A_2 = \begin{bmatrix} \epsilon _1&\quad 0&\quad 0\\ 0&\quad 1&\quad 0\\ 0&\quad 0&\quad \epsilon _2 \end{bmatrix}, \qquad A_3 = \begin{bmatrix} \nu _1&\nu _2&0\\ \rho _1&\rho _2&0\\ 0&0&\sigma _3 - \epsilon _2\mu _2 \end{bmatrix}, \end{aligned}$$

\(\epsilon _k = \pm 1\). So that \(A_2 = \pm R_2\) and \(A_3 = \theta R_3\), where \(R_2, R_3 \in {\mathrm {SO}}(3)\) and \(\theta ^2 = \nu _1^2 + \rho _1^2 \ne 0\).

Finally, if \(\nu _1^2 + \rho _1^2 = 0\), then \(\nu _1 = \rho _1 = \nu _2 = \rho _2 = 0\) and \(T'\) is calibrated as well, since

$$\begin{aligned} T'_k = \begin{bmatrix} \epsilon _1&\quad 0&\quad 0\\ 0&\quad 1&\quad 0\\ 0&\quad 0&\quad \epsilon _2\end{bmatrix} e_k \begin{bmatrix} 0&0&\mu _2 \end{bmatrix} - 0 e_k^{{\mathrm {T}}} R_3^{{\mathrm {T}}}, \end{aligned}$$

where \(R_3\) is arbitrary rotation matrix.

Thus we have shown that the trifocal tensor \(T'\) is calibrated in either case. By Lemma 3, the tensor T is calibrated too. Theorem 12 is proved. \(\square \)

Finally, combining Theorem 12 with the characterization of trifocal tensors from [2], we get the following three-view analog of Theorem 2.

Theorem 13

A real (2, 1) tensor is a CTFT if and only if it satisfies the following constraints:

  • 10 extended rank constraints;

  • 20 equations of degree 9 and 6 of degree 12; see [2, Theorem 2.3];

  • 15 quartic constraints.

6 Discussion

Here are some remarks on the results of the paper and possible further directions of research.

  1. 1.

    We have defined a new notion—the trifocal essential matrix. Algebraically, it is a complex \(3\times 3\) matrix associated with a given CTFT \({\hat{T}}\) by the contraction of \({\hat{T}}\) and an arbitrary 3-vector whose squared components sum to zero. In this paper, the trifocal essential matrix plays a technical role. However its deeper investigation should help to explain why its properties are so close to the properties of an ordinary (bifocal) essential matrix. It is also interesting to what extent the trifocal essential matrix can be generalized in case of quadrifocal geometry.

  2. 2.

    Based on the characterization of trifocal essential matrices, we have derived the three necessary conditions on a CTFT (Theorems 8, 9 and 11). They have form of 15 quartic and 99 quintic polynomial equations. It is worth emphasizing again that these constraints relate to the calibrated case only and do not hold for arbitrary trifocal tensors. Moreover, we have shown that the 15 quartic constraints are also sufficient for a real trifocal tensor to be calibrated (Theorem 12). Combining this result with the 36 polynomial equations from [2], we get the characterization of a real CTFT (Theorem 13). On the other hand, some of new 36 constraints may be redundant in the real calibrated case. This question requires more research.

  3. 3.

    As we have seen at the end of Sect. 4, the quartic constraints do not characterize CTFTs over the field of complex numbers. Hence, there must exist other polynomial equations not related to the trifocal essential matrix. In degree 5, we can expect to derive some of them from the 99 quintic constraints using similar arguments as in Remark 3.

  4. 4.

    The characterization of real calibrated trifocal tensors provides a new tool in investigating three-view metric structure-from-motion problems such as relative pose estimation and self-calibration. This could be a promising direction of future research, since we know that similar results for essential matrices have led to the efficient algorithms for analogous two-view problems [16, 24].

    The approach could be as follows. The linear incidence relations are first used to parameterize the trifocal tensor. Then the system of 51 polynomial equations is constructed and solved using either Gröbner bases or numerical methods. Theorem 13 guarantees that the true solution (which is always real) is a root of that system. However, a number of spurious complex solutions may occur. For example, the problem of relative pose estimation from four points and one line correspondences in three views is known to have a unique solution in general [19]. We constructed the Gröbner basis for that problem and found that it has 192 (!) spurious complex roots.

    To improve the practical applicability of the paper’s results we need a characterization of CTFTs over the field of complex numbers. The present paper provides a basis for that future research.