A NEW FRAMEWORK FOR THE FORMATION OF INVARIANTS AND
MULTIPLE-VIEW CONSTRAINTS IN COMPUTER VISION
J. Lasenby , E. Bayro-Corrochano y, A.N. Lasenbyz and G. Sommery
Cambridge University Engineering Department, zCavendish Laboratory, Cambridge
yComputer Science Institute, Christian Albrechts University, Kiel
[e-mail], [e-mail], edb,[e-mail]
ABSTRACT b
In this paper we present geometric algebra as a new
framework for the theory and computation of invariants and
multiple-view constraints in computer vision. We discuss
the formation of 3D projective invariants and a wholly geo-
a
metric formulation of constraints from a number of images.
1. INTRODUCTION
Figure 1: The directed area, or bivector, a^b
Geometric algebra (GA) is a coordinate-free approach to
geometry based on the algebras of Grassmann and Cli ord
the system we adopt here was pioneered by David Hestenes
[5]. We will outline the use of GA in the formulation of Consider a linear function f mapping vectors to vectors
projective geometry and discuss the algebra of incidence. in the same space. We can extend f to act linearly on
Using this we present a new methodology for the study of multivectors via the outermorphism, f, such that
geometric invariance and multiple-view constraints (more
f (a1 ^a2 ^: : : ^ar ) = f (a1 )^f (a2 )^: : : ^f (ar): (2)
detail can be found in [7, 1]). Throughout the paper the
convention of summing over repeated indices is assumed.
f therefore preserves the grade of any r-vector it acts on.
The action of f on general multivectors is then de ned
2. GEOMETRIC ALGEBRA: AN OUTLINE
through linearity. Since the outermorphism preserves grade,
Let G denote the geometric algebra of n-dimensions. This
n
the pseudoscalar of the space must be mapped onto some
is a graded linear space with vector addition, scalar multi-
multiple of itself. The scale factor in this mapping is the
plication and a non-commutative product which is associa-
determinant of f
tive and distributive over addition { this is the geometric
f(I) =det(f)I: (3)
or Cli ord product. Any vector squares to give a scalar.
The geometric product of two vectors a and b is written ab
where
3. PROJECTIVE SPACE
ab = a b + a^b: (1)
The inner product of two vectors, a b, is the standard scalar Points in real 3D space will be represented by vectors in E3
product and produces a scalar. The outer or wedge product (3D Euclidean space). As is usual, we associate a point in
of two vectors, a ^ b, is a new quantity we call a bivector. E3 with a line in a 4D space, R4. In these two spaces we
This is a directed area in the plane containing a and b, de ne basis vectors: f g in R4 and f g in
1 2 3 4 1 2 3
2 2
formed by sweeping a along b { see Figure 1. E3 { noting that = ;1 for j=1,2,3 and = +1 (so that
j
4
Thus, b ^ a will have the opposite orientation making I2 = ;1, where I = ). We identify R4 and E3 with
1 2 3 4
the outer product anticommutative. This is immediately the geometric algebras of 4 and 3 dimensions. Choosing
generalizable to higher dimensions { for example, (a^b)^c, as a selected direction in R4 , we can de ne a mapping
4
a trivector, is the oriented volume formed by sweeping the which associates the bivectors , i = 1 2 3, in R4 with
i 4
area a^b along vector c. The outer product of k vectors is the vectors = , i =1 2 3, in E3. This process is an
i i 4
a k-vector or k-blade, and is said to have grade k. A mul- application of what Hestenes calls the projective split.
tivector (linear combination of objects of di erent type) For a vector X = X1 + X2 + X3 + X4 in R4 the
1 2 3 4
is homogeneous if it contains terms of only a single grade. projective split is achieved by taking the geometric product
Geometric algebra allows us to manipulate multivectors in of X and
4
a way which keeps track of di erent grade objects.
X^ 4
X = X + X^ = X4 1 + X4(1 + x): (4)
4 4 4
In a space of 3 dimensions we can construct a trivector
X4
a^b^c, but no 4-vectors exist. The highest grade element in
a space is called the pseudoscalar. The unit pseudoscalar We think of the vector x as a vector in E3 which is associ-
is denoted by I and is crucial to ideas of duality. ated with the bivector X^ =X4 in R4, i.e.
4
X^ X1 X2 X3
4
3.3. Algebra in projective space
x = = + + (5)
1 2 3
X4 X4 X4 X4
Consider three non-collinear points, P1 P2 P3, represented
by vectors x1 x2 x3 in E3 and by vectors X1 X2 X3 in
X
i
) xi = , for i = 1 2 3. This is equivalent to using
X4
R4 . The line L12 joining points P1 and P2 can be expressed
homogeneous coordinates, X, for x. We therefore have
in R4 by the following bivector,
distinct spaces with a well-de ned way of moving between
L12 = X1 ^X2 : (14)
these spaces.
Similarly, the plane passing through points P1 P2 P3
123
3.1. Formulation of Projective Geometry
is expressed by the following trivector in R4
In a given space any pseudoscalar P can be written as P =
= X1 ^X2 ^X3: (15)
123
I where is a scalar. If I;1 is the inverse of I, then
Consider now a line A = X1 ^X2 intersecting a plane =
PI;1 = II;1 = [P] (6)
Y1^Y2^Y3 { all vectors are in R4. Using the meet operation
we have ,[7, 1],
where we have de ned the bracket, [P], of the pseudoscalar
P. This bracket corresponds to the bracket of the Grassmann- A_ = [X1 X2 Y2Y3 ]Y1 +[X1 X2 Y3Y1 ]Y2 +[X1 X2 Y1 Y2 ]Y3
Cayley algebra. (16)
We de ne the dual A of an r-vector A as where [A1 A2 A3A4] is the magnitude of the pseudoscalar
formed from the four vectors { which agrees with the result
A = AI;1 : (7)
in [2] if the r-extensors of the Grassmann-Cayley algebra
are identi ed with r-blades.
In an n-dimensional space, if A is an r-vector and B is an
The intersection of two planes = X1 ^ X2 ^ X3 and
1
s-vector (such that r + s = n), we have
= Y1^Y2^Y3 is given by the meet of and , which
2 1 2
can be expanded [1] as
[A^B] = (A^B)I;1 = A B : (8)
_ =[X1 X2 X3Y1 ](Y2 ^Y3 ) +[X1 X2 X3Y2 ](Y3^Y1 )
1 2
Here duality is simply multiplication by a element of the
Vn
algebra. One can de ne the join J = A B of an r-vector +[X1 X2 X3Y3](Y1 ^Y2 ) (17)
A and an s-vector B by
producing a line of intersection (bivector in R4). This again
agrees with the expressions given in [2].
J = A^B if A and B are linearly independent: (9)
4. INVARIANTS
If A and B have a common factor we can de ne the `inter-
The `fundamental projective invariant' of points on a line
section' or meet of A and B as A _ B given by
is the cross-ratio. When a point on line L is projected
(A _ B) = A ^B (10)
onto another line L0, distances t and t0 are related by a
t+
projective transformation of the form t0 = . This non-
~ t+ ~
where the dual is taken with respect to the join of A and
linear transformation in E1 can be made linear in R2 by
B. If the join is the whole space the meet is given by
de ning the linear function f1 mapping vectors onto vectors
A _ B =(A ^B )I =(A ^B )(I;1 I)I = (A B) (11)
in R2
f1 ( ) = + ~ f ( ) = + ~ : (18)
1 1 2 2 1 2
according as I2 = 1. We therefore have the very simple
1
relation of A _ B = (A B). For more details see [7, 6].
Consider 2 vectors X1 X2 in R2 . Form the bivector S1 =
X1^X2 = I2 , where I2 = is the pseudoscalar for R2 .
1 1 2
3.2. Projective transformations
We now look at how S1 transforms under f :
1
If a general point (x y z) in 3-D space is projected onto an
0
S1 = X0 ^X0 = f (X1 ^X2 ) = (detf )(X1 ^X2 ): (19)
1 2
image plane point, (x0 y0), the coordinates are related by
1 1
Take 4 points on the line L whose corresponding vectors
x + y + z + x + y + z +
1 1 1 1 2 2 2 2
x0 = y0 = :
in R2 are fXig, i = 1 :: 4, and consider the ratio R1 of 2
~ x + ~y + ~z +~ ~ x + ~y + ~z +~
wedge products, which will transform as follows under f1 ,
(12)
0
(R1 !R1 ):
To make this non-linear transformation in E3 into a linear
^X2
transformation in R4 we de ne a linear function f (in R4 ) X0 ^X0 (detf1 )X1
0 1 2
R1 = = : (20)
where f is given by
X0 ^X0 (detf1 )X3 ^X4
3 4
f( ) = + + + ~
1 1 1 2 2 3 3 4
R1 is therefore invariant under f . In order to convert to
1
f( ) = + + + ~ etc.. (13)
2 1 1 2 2 3 3 4
1D distances we must consider how the bivector S1 in R2
projects down to E1 .
f maps X onto X0 such that the vector x0 = x0 + y0 +
1 2
X1 ^X2 =(T1 + S1 )^(T2 + S2 ) =
1 2 1 2
z0 in E3 is formed from X0 via the projective split. Simi-
3
larly for y0 and z0. (T1 S2 ; T2S1 ) = S1 S2(t1 ; t2 )I2: (21)
1 2
P
i
To form a projective invariant which is independent of the
choice of the arbitrary scalars Si, we then take ratios of
the bivectors Xi ^ Xj (to cancel detf1 ) and multiples of
such ratios so that the Si's cancel. Consider the following
expression
; ;
(X3 ^X1 )I2 1 (X4 ^X2 )I2 1
Inv1 = :
a1
; ;
View 1
(X4 ^X1 )I2 1 (X3 ^X2 )I2 1 a
i b i b3
View 2
a
3
a b
2 1 b
In terms of 1D distances, under the projective transforma- 2
0
tion f1 , Inv1 goes to Inv1 where
a
0
b
S3S1 (t3 ; t1 )S4 S2 (t4 ; t2 ) (t3 ; t1 )(t4 ; t2) 0
0
Inv1 = =
S4S1 (t4 ; t1 )S3 S2 (t3 ; t2 ) (t4 ; t1 )(t3 ; t2)
Figure 2: De ning points of two camera planes
(22)
which is independent of the Si 's and is indeed the 1D cross-
ratio.
Note that when we take ratios of brackets we must ensure
We can now extend these arguments to form invariant
that the same decomposition of Xi ^ Xj occurs in both
quantities in 2 and 3 dimensions by taking multiples of ratios
numerator and denominator so that the arbitrary factors
of trivectors and 4-vectors, e.g.
cancel. For example, Inv3 can be written as
; ;
(X5 ^X4 ^X3)I3 1 (X5 ^X2 ^X1 )I3 1
Inv2 = :
; ; f(X1 ^X2 )^(X3 ^X4)gI4 ; 1 f(X4 ^X5)^(X2 ^X6 )gI4 ; 1
(X5 ^X1 ^X3)I3 1 (X5 ^X2 ^X4)I3 1
f(X1 ^X2 )^(X4 ^X5 )gI4 ; 1 f(X3 ^X4)^(X2 ^X6 )gI4 ; 1
; ;
(X1 ^X2 ^X3 ^X4)I4 1 (X4 ^X5 ^X2 ^X6 )I4 1
(27)
Inv3 = :
; ;
(X1 ^X2 ^X4 ^X5 )I4 1 (X3 ^X4 ^X2 ^X6 )I4 1 where this decomposition rule has been obeyed. In [3] it is
claimed that the following invariant of 6 points
(23)
[X1 X2 X3X4 ][X1 X2 X5 X6]
(28)
4.1. 3D invariants in terms of image coordinates
[X1 X2 X3X5 ][X1 X2 X4X6]
From six general 3D points Pi, i = 1 :: 6, represented by
is not invariant when expressed in Carlsson's terms. Their
vectors fxi Xig in E3 and R4, we can form a number of 3D
solution is to include a large number of correcting scale
projective invariants. One such invariant is
factors. One decomposition of this expression is
[X1 X2 X3 X4][X4X5 X2 X6]
Inv3 = : (24)
f(X1 ^X2 )^(X3 ^X4 )gI4 ; 1 f(X1 ^X2 )^(X5 ^X6)gI4 ; 1
[X1 X2 X4 X5 ][X3X4 X2 X6]
:
f(X1 ^X2 )^(X3 ^X5 )gI4 ; 1 f(X1 ^X2 )^(X4 ^X6)gI4 ; 1
(29)
This is simply equation (23) written in terms of brackets.
Here the same bivectors do not appear in both the numer-
Recent work has used the Grassmann-Cayley algebra [2] to
ator and denominator so the scale factors will not cancel.
compute such invariants from a pair of images using image
However, we are free to rearrange equation (28) in the fol-
coordinates and the fundamental matrix, F. Subsequent
lowing way
work by Csurka and Faugeras [3] attempts to correct some
of Carlsson's expressions by including omitted scale factors.
[X1 X4 X2 X3 ][X1 X5 X2 X6]
: (30)
We will show that the resolution lies simply in reordering
[X1 X5 X2 X3 ][X1 X4 X2 X6]
the bracket decomposition rather than nding large num-
bers of complicated scale factors.
The decomposition now looks like
Consider the scalar S1234 formed from the bracket of 4
f(X1 ^X4)^(X2 ^X3)gI4 ; 1 f(X1 ^X5)^(X2 ^X6 )gI4 ; 1
points
f(X1 ^X5 )^(X2 ^X3)gI4 ; 1 f(X1 ^X4)^(X2 ^X6 )gI4 ; 1
S1234 =[X1 X2X3 X4] = (X1 ^X2 )^(X3 ^X4)I4 ; 1 : (25)
(31)
and we see that the same bivectors appear in both numera-
(Xi ^ Xj) represents the line joining points Pi and Pj. We
tor and denominator and therefore all scale factors cancel.
let a0 and b0 be the centres of projection of the two cameras
Writing
with the two camera image planes de ned by fa1 a2 a3g
and fb1 b2 b3g { see gure 2. The projection of points fPig
[A0B0A0 B0 ][A0B0A0 B0 ]
1423 1423 1526 1526
Inv3 = (32)
are given by the vectors fa0 g and fb0 g. Note our vectors,
i i
[A0B0A0 B0 ][A0B0A0 B0 ]
1523 1523 1426 1426
ai bi ::: etc. are vectors in E3 with R4 representations of
Ai Bi :::, etc.
will indeed produce an invariant thus dispensing with the
Let the intersection of the lines joining points fa0 and a0 g need for the scale factors proposed in [3].
1 2
and fa0 and a0 g be a0 (A0 in R4). B0 is de ned
3 4 1234 1234 1234
similarly in the second image plane. It can be shown [7]
5. POINT CORRESPONDENCES
that by decomposing as in equation (25) it is possible to
For this analysis, let (a1 a2 a3) (b1 b2 b3), (c1 c2 c3 ),
write the bracket S1234 as given in [2]
: : :, (n1 n2 n3) de ne the image planes and let a0 , b0 ,
S1234 =[X1 X2 X3X4 ] [A0B0A0 B0 ]: (26) c0 : : : n0 be the corresponding optical centres.
1234 1234
ij
~
5.1. Two cameras: the bilinear constraint Our tensor Tklm is related to Hartley's tensor, Tpqr [4], via
The projections of a world point Pi (represented by xi and ij
~
Tklm ;! Tpqr (42)
Xi in E3 and R4) will be a0 and b0 in the two image planes
i i
where p =1 if (i l) = (2 3), p =2 if (i l) =(1 3) and p =3
(A0 and B0 in R4). A0 can be expressed as the intersection
i i i
if (i l) =(1 2) (2 1). Similarly, q = 1 if (j m) =(2 3) etc..
of a line and image plane 1, see gure 2:
We also note that for given (i j) only certain values of (l m)
A0 =(A0 ^ Xi) _ (A1 ^ A2 ^ A3) (33)
~
i
give non-zero expressions for T.
The derivation of the trilinear constraints for lines is
=[A0XiA2A3 ]A1 +[A0XiA3A1 ]A2 +[A0Xi A1 A2 ]A3
given in [1].
and similarly for B0 and C0 . We can de ne three planes
i i
through the optical centre of each camera, for example,
5.3. Unifying the point constraints for n-views
j =1 2 3 are planes through A0 de ned by
1 j
If we have n views let us choose 4 of these views and denote
them by A, B, C and N. _ gives a line passing
= A0^A2^A3 = A0^A3^A1 = A0^A1^A2: Aj Bk
11 12 13
through world point P as does _ . We therefore
(34) Cl Nm
have the condition
The epipolar constraint is simply that a0, b0, a0 , b0 are
i i
coplanar. This can be concisely written as LA ^ LB = 0
f _ g^f _ g =0: (43)
Aj Bk Cl Nm
where LA = A0^A0 and LB = B0^B0 , giving [A0B0A0 B0 ] =
i i i i
If N0 = N1 + N2 + N3 then this condition can be
1 2 3
0. Expressed in terms of the A0 B0 this gives
i i
written as
[A0B0 ( A1 + A2 + A3)( B1 + B2 + B3)] A B C N
i1 i2 i3 i1 i2 i3
f( _ )^( _ )g =0: (44)
r s t u
jr ks lt mu
T
= F =0 (35) Therefore for n cameras or a moving sensor the general
i i
equation for computing bi-, tri- and quadri-linear constraints
where Fij = [A0B0 AiBi], is the well known fundamental
is
matrix.
f _ g^f _ g =0 (45)
Kk Ll Mm Nn
where K,L,M and N are any four cameras or any four views
5.2. Three cameras: the trilinear constraints
from a moving observer. This equation subsumes the two
For point correspondences in three views we have constraints and three camera cases, i.e. for two cameras use LK instead
of the following form of f _ g and LL instead of f _ g and for
Kk Ll Mm Nn
three cameras use LK instead of f _ g and f _
Kk Ll Ll
LA ^f _ g =0 LB ^f _ g =0
Bi Cj Ai Cj
g instead of f _ g.
Mm Mm Nn
LC ^f _ g =0 (36)
Ai Bj
6. CONCLUSIONS
where , and are planes de ned by =
Ak Bk Ck Ak
We have shown how geometric algebra can be used in the
A0 ^ Ak ^ A0 etc. The rst constraint in equation (36) is
i
formation and computation of invariants and in deriving
simply saying that line LA and the line of intersection of
a single constraint statement which holds for 1, 2, 3 or 4
planes and must intersect at a point { this point
Bi Cj
views. The framework provides a single mathematical lan-
being P (drop subscript i on P, A0 etc.). We have
guage to replace the multitude of distinct systems currently
LA ^f _ g = (37)
Bi Cj
in use and can be used for most computer vision problems.
(A0 ^A0 )^f(B0 ^ Bi ^ B0) _ (C0 ^ Cj ^ C0)g =0:
i
7. REFERENCES
[1] Bayro-Corrochano, E., Lasenby, J. and Sommer, G. 1996. Ge-
Using A0 = Ai, B0 = Bi and C0 = Ci then enables
i i i
ometric Algebra: a framework for computing point and line
us to write
correspondences and projective structure using n-uncalibrated
cameras. Proceedings of ICPR'96, Vienna.
B0 ^Bi ^B0 = (B0 ^Bi ^Bl) B
l l il
[2] Carlsson, S. 1994. The Double Algebra: and e ective tool for
C
C0 ^Cj ^C0 = (C0 ^Cj ^Cm) (38)
m m computing invariants in computer vision. Applications of In-
jm
variance in Computer V ision, Lecture Notes in Computer Sci-
ence 825. Eds. Mundy, Zisserman and Forsyth. Springer-Verlag.
where the planes etc. have been remaned as given
11
[3] Csurka, G. and Faugeras, O. 1995. Computing three-
above. The constraint in equation (37) is now
dimensional projective invariants from a pair of images us-
B C
ing the Grassmann-Cayley algebra. Geometric Model ling and
(A0 ^Ak )^f ( _ )g =0 (39)
k l m
il jm
Invariants for Computer Vision, Ed. Roger Mohr and Wu
Chengke, Xi'an, China, April 1995.
which can be put into the form
[4] Hartley, R. 1994. Lines and Points in three views { a uni ed ap-
ij
~ proach. In ARPA Image U nderstanding Workshop, Monterey,
Tklm =0 (40)
k l m
California.
[5] Hestenes, D. and Sobczyk, G. 1984. Cli ord Algebra to Ge-
where
ij B C
~ ometric Calculus: A uni ed language for mathematics and
Tklm =[A0 Ak ( _ )]: (41)
il jm
physics. D. Reidel, Dordrecht.
This is a trilinear constraint. There are obviously 9 possible
[6] Hestenes, D. and Ziegler, R. 1991. Projective Geometry with
choices of the pair (ij). However, by expanding the bracket Cli ord Algebra. Acta Applicandae Mathematicae , 23: 25{63.
in equation (41) it can be shown that only 4 of these are [7] Lasenby, J., Bayro-Corrochano, E. and Sommer, G. 1996. A
new methodology for computing invariants in computer vision.
independent. Since we had three original constraints, this
Proceedings of ICPR'96, Vienna.
leads to a total of 12 trilinearity constraints as noted by [4].