International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004 
  
  
Figure 1: The matching corners for two views 
6 TRILINEAR TENSORS 
While this fundamental matrix has a high probability of 
being correct, it is not necessarily the case that every corre- 
spondence that supports the matrix is valid. This is because 
the fundamental matrix encodes only the epipolar geome- 
try between two images. A pair of corners may support 
the correct epipolar geometry by accident. This can occur, 
for example, with a checkerboard pattern when the epipo- 
lar lines are aligned with the checkerboard squares. In this 
case, the correctly matching corners can not be found using 
only epipolar lines (i.e. computing only the fundamental 
matrix). This type of ambiguity can only be dealt with by 
computing the trilinear tensor. 
Assume that we see the point X = [X,Y, Z]”, in three 
camera views, and that 2D co-ordinates of its projections 
aedi [ud] d equ vd] oi uu" v, 1). In 
addition, in a slight abuse of notation, we define u; as the 
i'th element of u; ie. u4 — u, and so on. It has been shown 
that there is a 27 element quantity called the trilinear tensor 
T relating the pixel co-ordinates of the projection of this 
3D point in the three images (Shashua, 1995). Individual 
elements of 7" are labeled 7; 1, where the subscripts vary in 
the range of 1 to 3. If the three 2D co-ordinates (1, u’, u”) 
truly correspond to the same 3D point, then the following 
four trilinear constraints hold: 
IH rp Ze tr ir — 7 ~ — 
uw" Tj3u; — uw Tia3ü; Fu T7310; — T5410; — 0 
v" T;,3ü; — v"^u'T;33ü; -- uT;33ü; — T;,2ü; — 0 
u"Ti33ü; — u"v/T;330; ^- v/T;3;ü; — T;231ü; — 0 
H 2 LER -— I T A 
U Ti23ü; — v v Tia3U; FU Ti32U; — T1220; — 0 
In each of these four equations ¢ ranges from | to 3, so 
that each element of ü is referenced. The trilinear tensor 
was previously known only in the context of Euclidean line 
correspondences (Spetsakis and Aloimonos, 1990). Gen- 
eralization to projective space is relatively recent (Hartley, 
1995, Shashua, 1995). 
The estimate of the tensor is more numerically stable than 
the fundamental matrix, since it relates quantities over three 
716 
views, and not two. Computing the tensor from its corre- 
spondences is equivalent to computing a projective recon- 
struction of the camera position and of the corresponding 
points in 3D projective space. 
6.1 Computing the Trilinear Tensor 
We compute the trilinear tensor from the correspondences 
that form the support set of two adjacent fundamental ma- 
trices in the image sequence. Previously we computed the 
fundamental matrix for every pair of images. Now we fil- 
ter out those image pairs that do not have more than a cer- 
tain number of supporting matches. This leaves a subset 
of these n? image pairs that have valid fundamental matri- 
ces. Consider three images, ?, 7 and k and their associated 
fundamental matrices F;; and F;,. Assume that these fun- 
damental matrices have a large enough set of supporting 
correspondences, which we call SF}; and SF). Say a par- 
ticular element of SF; is (1; yi, xj, y;) and similarly an 
element of SF, is (17, y; x1, y). Now if these two sup- 
porting correspondences overlap, that is if (7;, y;) equals 
(25, y;) then the triple created by concatenating them is a 
member of CT;;, the possible support set of tensor T;;,. 
The set of all such possible supporting triples is the input 
to the random sampling process that computes the tensor. 
The result is the tensor 7;;,, and a set of triples (corner in 
the three images) that actually support this tensor, which 
we call 57;;,. 
A tensor is computed for every possible triple of images. 
In theory this is O(n?), but in practice it is much less. The 
reason is that only a fraction (usually from 10 to 30 per- 
cent) of the n? possible fundamental matrices are valid. 
And from this fraction, an even smaller fraction of the pos- 
sible triples are valid. 
7 CHAIN THE CORRESPONDENCES 
The result of this process is a set of trilinear tensors for 
three images along with their supporting correspondences. 
Say that we have a sequence of images numbered from 
1 to n. Assume the tensors 75; and 7}; have support- 
ing correspondences (xi, Yi, 2, Yj, Tk, Yx) in STi, and 
(2%, 4s Th, Uno 27597) in ST;u. Those correspondences 
for which (z, yj, xy, yx) equals (25, y5, 1, yi) represent 
the same corner in images i, j, k and /. In such cases we 
say that this corner identified in 7;;; is continued by T;xi. 
The goal of this step is to compute the maximal chains of 
supporting correspondences for a tensor sequence. This is 
done in a breadth first search using the supporting tensor 
correspondences as input. Individual correspondences that 
are continued by a given tensor are chained for as long as 
is possible. The output of the process is a unique identi- 
fier for a 3D corner, and its chain of 2D feature correspon- 
dences in a sequence of images. This corner list is then 
sent directly to the commercial bundle adjustment program 
Photomodeler (Photomodeler by EOS Systems Inc., n.d.) 
using a Visual Basic routine that communicates through a 
DDE interface. 
  
  
    
  
  
  
   
   
  
  
  
  
  
  
  
  
  
  
  
   
  
   
   
  
   
   
    
  
  
  
  
  
  
   
   
  
  
  
   
   
     
    
  
   
   
   
   
  
   
  
  
  
   
   
    
— S PAR TS 0€ & nM 
apa b hama C9. |