ISPRS Commission II, Vol.34, Part 3A „Photogrammetric Computer Vision", Graz, 2002
The restriction of the preceding paragraph does not hold if we em-
ploy the trifocal tensor: Given two homologous points x’ and x”
in the first and the second image one chooses a line 1” through x”.
Then, the point x" can be computed by transferring x’ from the
first to the third view via the homography defined by //77^, i.e.,
x = ne
This transfer via the homography implies the intersection of the
plane defined by the projection center of the second camera O” and
the line 1” with the ray defined by the projection center of the first
camera O' and x' (cf. Fig. 3). This intersection is not defined if I
is taken to be the epipolar line corresponding to x'. The plane de-
fined by the epipolar line and O" comprises the point X which is
projected to x', x", and x'" as well as the projection center O' of the
first camera. In this plane lies also the ray defined by O' and x'.
©
Figure 3: Transfer of a point x' in the first image via a plane defined
by the line 1” in the second image and the projection center of the
second camera O".
On the other hand, if one takes the line perpendicular to the epipolar
line through x", also the projection plane becomes in one direction
perpendicular to the ray defined by x' and O' and thus the intersec-
tion geometry becomes optimal. In (Hartley and Zisserman, 2000)
it is recommended to use optimal triangulation to compute a pair x'
and x" which satisfies x" TF12x’ = 0. We do not do this because
we are focusing on speed rather than on optimum quality. Putting
everything together, our basic algorithm looks as follows:
e Compute l" which goes through x" and is perpendicular to l/ =
F2;x'. From x" — (27, 27,1)! andY! — (I, l7, 17)" follows
I" = (1, 1, a7) + ht)"
e ; jk
e The transfered point is z^ — a" [7/ 77^.
A closer look at this reveals that if one restricts oneself to points on
the epipolar line, then only 15 = —x7/3 + 241} varies. Therefore,
az" I1 TÀ* and "15 T;?* are constant and have to be computed only
once per epipolar line.
S ESTIMATION OF THE TRIFOCAL TENSOR
5.1 Carlsson-Weinshall Duality
We employ the Carlsson-Weinshall duality to calculate a solution for
the trifocal tensor from a minimum of six point triplets (Carlsson,
1995, Weinshall et al., 1995). To utilize an algorithm which gives a
solution for a minimum number of points is important in two ways:
First, for robust estimation based, e.g., on RANSAC (cf. Section
5.2), this considerably reduces the search space. Second, by taking
the minimum number of points we implicitly take the constraints for
a tensor to be a trifocal tensor into account.
The basic idea of the duality is to interchange the roles of points
being viewed by several cameras and the projection centers. Specifi-
cally, if one has an algorithm for n views and m --4 points, then there
is an algorithm for doing projective reconstruction from m views of
n +4 points. By taking into account |F| — 0 (cf. Section 2.3), an al-
gorithm can be constructed for the reconstruction of the fundamental
matrix from two images for which seven homologous points suffice.
From the above follows that m — 3 and n — 2. Le., if we utilize the
dualism we get an algorithm solving for three images and six points.
To determine the fundamental matrix from seven points, we start
with the basic solution for n > 8 homologous points. For it
the homogenous linear equation system reads x//Fx/ — 0 , ie,
Aju — 0 Vi — 1,...,n . With the 9-vector u representing the
elements of F this can be written in the form Au = 0 with A - (A,).
The best estimation for u is the unit singular vector corresponding
to the smallest singular value of the n x 9-matrix A, determined by
singular value decomposition (SVD). The solution is unique up to
an unknown factor, as the system is homogenous. For seven points
the 7 x 9-matrix A has rank 7. The solution for Au = 0 is a 2D
space with the form aF; + (1 — a)F2. Using the fact that F is of
rank 2 leads to |aF1 + (1 — a)F2)| = 0. This results into a cubic
polynomial for which either one or three real solutions exist.
The dual algorithm is described in detail in (Hartley and Zisserman,
2000). Here we only sketch it. The triplets of points of the origi-
nal problem are arranged in a table and the table is transformed so
that the last four points are mapped to the 2D projective basis, i.e.,
(1,0,0)", (0, 1,0)", etc. Then, the last four points are dropped, the
table is transposed and extended by points of the 2D projective basis.
The solution for the dual problem is obtained by the algorithm for
the fundamental matrix. The obtained reconstruction is transformed
in a way that the last four points correspond to the 3D projective
basis. By dualization the problem is mapped back into the original
domain. Finally, the effects of the initial transformation are undone
by a reverse transformation.
5.2 Dealing with Mismatches by RANSAC
Even though there are generic means to reduce mismatches (cf. Sec-
tion 5.3), there are usually far too many for an efficient least squares
solution, if the knowledge about the calibration and the orientation
of the cameras is weak. As our problem is of the type that we only
have relatively few parameters and a high redundancy, the RANSAC
(random sample consensus) approach (Fischler and Bolles, 1981) is
a good choice. RANSAC is based on the idea to select more or less
randomly minimum sets of observations. The correctness of a set is
evaluated by the number of other observations which confirm it.
The minimum number of point correspondences necessary to deter-
mine the trifocal tensor with RANSAC is seven for the fundamen-
tal matrix and six for the trifocal tensor (cf. Section 5.1). At first
sight the number for the trifocal tensor looks better than that for the
fundamental matrix. Yet, one has to consider, that there exist 6?
combinations for six triplets, which is considerably more than the 7?
for seven pairs. This suggests, that we first calculate the correspon-
dences based on the fundamental matrices of the images one and two
as well as one and three and only then match the triplets.
53 Reduction of the Search Space and Results
By means of a hierarchical approach based on image pyramids with
a reduction by a factor 2 for each level, we significantly reduce the
search space. Thereby not only the efficiency but also the robustness
is improved considerably.
A - 214
Se
tre
on
to
le
lai
Fi
ar
un
Oi
lai
im
20
ca
di
ot
