Invariants of Six Points and Projective Reconstruction From Three Uncalibrated Images.
AbstractThere are three projective invariants of a set of six points in general position in space. It is well known that these invariants cannot be recovered from one image, however an invariant relationship does exist between space invariants and image invariants. This invariant relationship is first derived for a single image. Then this invariant relationship is used to derive the space invariants, when multiple images are available.This paper establishes that the minimum number of images for computing these invariants is three, and the computation of invariants of six points from three images can have as many as three solutions. Algorithms are presented for computing these invariants in closed form.The accuracy and stability with respect to image noise, selection of the triplets of images and distance between viewing positions are studied both through real and simulated images.Applications of these invariants are also presented. Both the results of Faugeras [1] and Hartley et al. [2] for projective reconstruction and Sturms method [3] for epipolar geometry determination from two uncalibrated images with at least seven points are extended to the case of three uncalibrated images with only six points.
Introduction
Geometric invariants are playing a more and more important
role in machine vision applications. A lot of work for
recognition and shape description using invariants has already
been reported, for instance cf. the collection book
[4] and [5], [6], [1], [7], [8], [9], [10], [2], [11], [12]. Most of
the invariants [13], [14] are derived for planar objects using
geometric entities such as points, lines and conics, since in
this case, there exists a plane projective transformation between
object and image space. Plane projective geometry
provides an ideal mathematical tool for describing this. As
for general geometric configurations in space, it has been
shown that it is not possible to estimate invariants from a
single image [15], except for some constraint geometric configurations
[16]. Therefore, one (cf. [17], [1], [2], [11], [18])
basically deals with space projective invariants from two
images, provided that the epipolar geometry, or the fundamental
matrix [19], [20] of the two images is determined a
priori.
This paper is concerned with the computation of the invariants
of sets of six points in space from three images
taken with uncalibrated cameras, assuming that the correspondences
between image points are known. The main
new results obtained in this paper are that the minimum
number of images for computing the invariants of six points
is three; and the computation of invariants from three images
can have as many as three solutions. All solutions
Long Quan is with LIFIA-CNRS-INRIA, 46, avenue Felix Viallet,
38031 Grenoble, France. E-mail: Long.Quan@imag.fr.
are given in closed form. As a consequence of these re-
sults, both Sturm's method for epipolar geometry determination
and projective reconstruction of Faugeras [1] and
Hartley et al. [2] developed for two uncalibrated images is
extended to the case of three uncalibrated images. Inter-
estingly, in both two-camera and three-camera cases, the
maximum number of solutions is three from the minimal
data, i.e. six points for three images and seven points for
two images. Also, with the help of such results, it may
be established that the method of camera self-calibration
proposed by Maybank and Faugeras [21] can be achieved
with only six points of three images taken by the camera.
Part of this work was also presented in [22].
Barrett et al. [17] have considered invariants from multiple
images in order to solve the "transfer problem" in
photogrammetry. Faugeras [1] and Hartley et al. [2] have
shown that a set of points in 3D can be reconstructed up
to a collineation from the point correspondences of two images
taken with uncalibrated cameras. Similar results are
presented by Mohr et al. in [6] for general multiple uncalibrated
images using numerical minimization techniques.
This permits the computation of projective invariants for
sets of points visible from two or more images. In [6], [11],
it is mentioned that it might be possible to get invariants
from three images, however no explicit solutions are ob-
tained. For other sets of geometric entities, invariants are
obtained from two images and some experimental results
are presented in [9], [11], [18]. However all these approaches
using only two images are essentially based on the a priori
determination of the epipolar geometry of the two images.
The epipolar geometry may be algebraically determined,
up to three solutions, with a minimum of seven points by
Sturm's method [3], [19] or other equivalent algebraic methods
based on the matrix representation of the epipolar geometry
[23], [19]. However, Sturm's method is numerically
unstable [20]. When more than eight points are available,
numerical minimization methods are used to determine it.
Therefore, to compute the invariants of six points, the correspondences
of more than six points are needed for two
images.
In comparison with related work, the method proposed in
this paper does not need to first estimate the epipolar geometry
between cameras, only the correspondences of six
points are necessary, however a third image is needed to
get algebraic solutions.
The development of this work is largely inspired by the old
mathematicalwork on invariants of Coble [24] and the more
recent work of Faugeras [1]. We assume that readers are
familiar with elementary projective geometry and invariant
theory, which can be found in [25], [24], [26], [27].
The paper is organized as follows. In Section II, the invari-
TO APPEAR IN IEEE-PAMI, VOL. 17, NO. 1, JANUARY 1995
ants of the set of six points in space are briefly reviewed.
Then in Section III we will show that although invariants of
a general set of points can not be obtained from one image,
there exists a simple invariant relationship between the invariants
of the set of 6 points in space and the invariants
of their projected points in an image. Later in Section IV,
this invariant relationship for one image will be applied to
three images to compute invariants in space. Applications
of the computation of invariants for projective reconstruc-
tion, epipolar geometry determination and self-calibration
are discussed in Section V. Experimental results for the
stability of these invariants and projective reconstruction
are presented in Section VI. Future directions are discussed
in Section VII.
II. Review of invariants of six points in space
Given a set of points or other kind of geometric configu-
rations, the number of invariants is, roughly speaking, the
difference between the dimension of the configuration and
the dimension of the transformation group that acts on the
configuration, if the dimension of the isotropy group of the
configuration is null (cf. [9], [4]). For a set of 6 points in
absolute invariants under
the action of general linear group GL(3) in P 3 . Since each
point in P 3 has 3 degrees of freedom, the dimension of a set
of 6 points is 3 \Theta 6 = 18. The transformation group GL(3)
is represented by a 4 \Theta 4 matrix up to a scaling factor, its
dimension is 4 \Theta 4
These 3 invariants can be formed and interpreted differ-
ently. For instance, following invariant theory, invariants
can be expressed by linear combinations of products of the
determinants of 4 by 4 matrix whose columns are the homogeneous
coordinates of the points. This is mainly a
domain of symmetric functions of the coordinates of the
points. The invariants formed this way can be symmetric,
therefore independent of the order in which the points are
taken. Sometimes, half symmetric functions are also used.
Coble [24] was interested in studying the invariants of associated
sets of points between spaces of different dimensions.
Using the six half symmetrical Jourbet's functions, he investigated
the complete system of the (relative) invariants
of six points of different dimension. We will not go further
into his work, as it is rather complicated and involves
concepts beyond the scope of this paper.
Another way is to consider twisted cubics [25], since there
is a unique twisted cubic that passes through the given 6
general points in P 3 . Any 4 points of a twisted cubic define
a cross ratio, therefore a subordinate one-dimensional
projective geometry is induced on any twisted cubic. So
the 3 invariants of the set of 6 points can be taken as the
3 independent cross ratios of the sets of 4 points on the
twisted cubic. Or more algebraically, we can consider the
invariants of cubic forms. Cubic forms in P 3 have 5 algebraically
independent relative invariants of degree 8, 16, 24,
absolute invariants can be derived
from these 5 relative invariants. However the expressions
for these invariants are very complicated polynomials.
One of the simplest ways to consider these 3 invariants is by
considering the 3 non-homogeneous projective coordinates
of any sixth point with respect to a projective basis defined
by any 5 of them. In the following, we will consider these
invariants, since it seems to us that this is the simplest way
to deal with them, and also because this methodology has
been succeesfully used in [7], [1], [28], [8], [18], particularly
by Faugeras in [1]. Obviously, these non homogeneous projective
coordinates admit direct cross-ratio interpretation
[25].
III. Invariant relationship of six points from
one image
A. Canonical representation of 6 points in space
Given any six points fP in view of
the fundamental theorem for projective space, any five of
them, no 3 of them collinear and no 4 of them coplanar,
can be given preassigned coordinates, thus we can assign
them the canonical projective coordinates as follows
This uniquely determines a space collineation A 4\Theta4 ,
which transforms the original 5 points
into this canonical basis. And for the sixth point, it is
transformed into its projective coordinates (X; Y; Z; T ) T
by A 4\Theta4 . Therefore,
gives the 3 independent absolute invariants
of 6 points.
B. Canonical representation of 6 image points
The projections of these six points onto an image fp
are usually given in non-homogeneous coordinates
take any 4 of them, no 3 of them collinear, and assign them
the canonical projective coordinates in P 2
A plane collineation A 3\Theta3 , can be uniquely
determined. A 3\Theta3 transforms the fifth and sixth points into
Therefore,
give the 4 independent
absolute invariants of 6 image points.
The algebraic determination of A 3\Theta3 can be found in Appendix

C. Projection between space and image plane
If we assume a perspective projection as the camera model,
then object space may be considered as embedded in
and image space embedded in . The camera performs
the projection from P 3 upon P 2 , and this projection can
be represented by a 3 \Theta 4 matrix C 3\Theta4 of rank 3 whose
kernel is the projection center. The relation between the
points P i in P 3 and p i in P 2 can be written as
QUAN: INVARIANTS OF 6 POINTS FROM 3 UNCALIBRATED IMAGE 3
are in homogeneous coordinates. i.e.
This can be rewritten in ratio form hiding the scaling factor
For each point, as u i , v i and w i can not all be zero, two independent
equations can always be derived from (1). These
equations express nothing else than the collinearity of the
space points and their corresponding image points. This is
a projective property which is preserved by any projective
transformation.
The calibration process consists of the determination of all
the parameters c ij of the projection matrix C 3\Theta4 . As we are
assuming that we are working with uncalibrated images, it
is meant that C 3\Theta4 is totally unknown.
D. Elimination of camera parameters c ij
For a set of 6 points in image and in space, when the correspondences
are given as
(0;
this leads to 6 equations from (1). All entries c ij
of C 3\Theta4 are unknowns, as we assumed that the camera was
uncalibrated. Since C 3\Theta4 is defined up to a scaling factor,
it counts for 3 \Theta 4 unknowns. So there still remains
one independent equation after eliminating
all unknown camera parameters c ij .
Substituting all canonical projective coordinates of the 6
points in image and in space into equations (1). Then eliminating
we obtain the following homogeneous equation
between
(2)
Invariant interpretation of the equation
The above equation (2) will be arranged and interpreted
as an invariant relationship between the relative invariants
of P 3 and those of P 2 as follows.
respectively
and
I
I
then i j and I j can be interpreted as respectively the relative
invariants of 6 points in P 2 (image) and those of 6 points
in P 3 (space).
are defined up to a common multiplier, so
they are only relative invariants of the 6 points of the image.
The 5 ratios are (absolute) projective
invariants. Since (by the arguments of Section II) for the
set of 6 points in P 2 , there are
projective invariants, therefore the relative invariants
are not independent and are subject to
one additional constraint which is
This can be checked from the above definition of i j .
are relative invariants of P 3 , only the 5
I 6 are projective invariants
in space. Since there are only 3 independent absolute in-
variants, I j
are subject to two additional constraints which
are, by inspection of the definition of I j ,
I 1
I 2
I 5
I 6
and I 2
I 3
I 4
I 5
An independent set of three absolute invariants in space
could be taken to be
I 6
I 6
and
I 3
The set of invariants fff; fi; flg is equivalent to
T .
Then the invariant relation (2) is simply expressed as a
bilinear homogeneous relation,
This relationship is of course independent of any camera
parameters, therefore it can be used for any uncalibrated
images. This clearly shows that the 3D invariants can not
be computed from one single image, since we have only
one invariant relationship for three independent invariants.
This invariant relationship can be used in two different
ways:
ffl to verify whether a given set of points is present in a
model base. That means I j can be computed from the
model base and i j from the image, then the invariant relation
can be used to check for the presence of the model in
the image.
ffl to compute 3D invariants from more than one image, this
leads to the following section.
IV. Computation of the invariants of six points
from three images
In this section, we will focus on how to find the absolute
invariants of 6 points in space, i.e. fff; fi; flg or equivalently
more than one image. To do this, it is
assumed that the 6 point correspondences through images
have already been established.
So from a set of six point in one image, the homogeneous
invariant relation (3) can be written in X;Y; Z; T as
with coefficients i j computed from image points. As there
are only 3 independent invariants for a set of 6 points, we
might hope to solve for these 3 invariants if 3 images of
the set of 6 points are available. The three homogeneous
quadratic equations in X, Y , Z, T from three images can
be written as follows.
here the superscripts (j), distinguish the invariant
quantities of different images.
A. Maximum number of possible solutions
Each equation represents a quadratic surface which has
rank 3. These quadratic forms have no
terms. That means that the quadratic surface goes through
the vertices of the tetrahedron of reference whose coordinates
are (0; 0; 0; 1) T , (0; 0;
This is easily verified by substituting these points in the
equations. In addition, as the coefficients of the quadratic
are subject to the following relations,
so all the equations (4), (5) and (6) necessarily pass through
the unit point (1;
According to Bezout's Theorem, three quadratic surfaces
must meet in points. Since they already pass
through the five known points, so only
points remain. Therefore,
the maximum number of solutions for
three.
B. Find X=T by solving a cubic equation
us try to explicit these 3 solutions. For instance,
if we want to solve for X=T , the two resultants G 1 and G 2
obtained by eliminating Z between F 1 and F 3 and between
F 2 and F 3 are homogeneous polynomials in X, Y and T of
degree 3:
whose coefficients are still subject to
e (j)
where
e (j)
e (j)
e (j)
e (j)
e (j)
e (j)
This is due to the fact that the point (1; is still on the
two cubic curves. The resultant obtained by eliminating Y
between G 1 and G 2 is a homogeneous polynomial in X, T
of degree 8, which can be factorized as,
It is evident that the linear factors lead to trivial solu-
tions. The solution corresponds to the common
points (0; 0; 0; 1) T , (0; 0; . The solution
corresponds to the common points (1; 0; 0;
(0; . The solution
to the common point
us have a close-look at the coefficients of the
quadratic
(2)which depend only on the invariant quantities of the points
of the second image, so the zeros of the quadratic factor
are the parasite solutions introduced by elimination using
resultants, they are not the zeros of fF g. Thus,
the only nontrivial solutions for X=T are those of the cubic
equation,
The implicit expressions for a i (quite long) can be easily
obtained with Maple. The cubic equation may be solved algebraically
by Cardano's formula, either for X=T or T=X.
The choice between solving X=T or T=X depends on the estimation
of the moduli of the roots. According to Cauchy's
Theorem, the moduli of the roots of cubic equations are
bounded by the following,
If the modulus is large enough, that means T is near to
0, in this case it would be better to solve for its reciprocal
T=X instead of X=T .
QUAN: INVARIANTS OF 6 POINTS FROM 3 UNCALIBRATED IMAGE 5
linearly for a given X=T
should be solved for each given . As the
equations are symmetric in X, Y , Z and T , we could obtain
other similar cubic equations for the other two independent
absolute invariants, for instance, Y=T and Z=T or any other
ratios if necessary. However, doing this would lead to much
more than 3 solution sets which is not desirable. We expect
to obtain unique Y for each given
By eliminating Y 2 between G 1 and G 2 , we obtain the following
homogeneous polynomial
where
and
Any zero of H is also a zero of G 1 and G 2 , as H is a linear
combination of G 1 and G 2 with polynomial coefficients, and
H belongs to the ideal generated by G 1 and G 2 .
H can be considered as a linear homogeneous polynomial
in Y and T for a given X=T . Therefore a unique Y : T is
guaranteed from this equation for each given
For a given
is uniquely determined by one of the equations (4), (5) or
(6), for instance taking (4), we have
6
In conclusion, only at most three solutions exist for
hence we establish the following.
Given a set of 6 point correspondences in 3 images taken by
uncalibrated cameras, there are at most 3 solutions for the
three invariants associated to the set of 6 points in space,
such solutions can be found in closed form.
D. Summary of computation
The computation of the invariants of six points can be summarized
in the following simple algorithm.
1. Compute the plane collineation A 3\Theta3 (cf. Appendix)
such that 4 of the 6 points of each image go to the canonical
projective basis. Apply this collineation to the remaining
two points to obtain
2. Compute the relative invariants of each image
from the above transformed image points;
3. Solve the cubic equation
4. For each ff, solve the linear equation
5. For each ff and fi, solve the linear equation (4) F
for
We can note that instead of solving
I
I
for the ratios I
They meet in intersection points in
As the sum of the coefficients is zero, they meet in
the common unit point (1; solutions
remain. The same results, cubic equation, can be obtained
by a little more symbolic computation.
We also note that when 5 images are available, a linear solution
for the ratios I I 6 is possible while
ignoring the quadratic constraints I 1 I
V. Applications of the invariants
In this section, we are exploring some interesting applications
that may be provided by the computed invariants of
six points. The most important is undoubtly the complete
determination of the projection matrices of the three cam-
eras. This gives the most complete projectively invariant
description of the three cameras. It follows that projective
reconstruction as has been achieved by Faugeras [1] and
Hartley et al. [2] and the determination of epipolar transformation
by Sturm's method [3] are extended to the case
of three uncalibrated cameras with fewer points.
A. Complete determination of projection matrices C j
In the case of two uncalibrated cameras, Faugeras [1] used
epipolar geometry to determine the projection matrix up
to projective transformations. Here, in the case of three
uncalibrated images, as the projective coordinates of the
sixth point is algebraically determined. It means that 6
points both in P 2 and P 3 are known up to respectively
a plane and a space collineation. It turns out that the
projection matrix C (j)
3\Theta4 for each camera can be completely
determined.
For each camera, the correspondences of 6 points between
linear homogeneous equations
in the 3 \Theta
that count only for
unknowns due to a common scaling factor. One of
6 TO APPEAR IN IEEE-PAMI, VOL. 17, NO. 1, JANUARY 1995
the 12 equations has been used to derive the invariant relationship
(3) (cf. Section III-D), which was then used
to compute the invariants. Therefore, there remain only
independent linear equations which matches
the 11 unknowns of the projection matrix. After some simple
algebra, the projection matrix for the j-th camera can
be written as follows,
@
c (j)
A
where
c (j)
c (j)
c (j)
and k (j) can be taken as either
or
which are equivalent due to the invariant relationship (3).
B. Projective reconstruction
The complete determination of projection matrices implies
that given any point correspondence in images, the corresponding
point in space can be reconstructed in P 3 up to a
collineation. In fact, projective reconstruction is equivalent
to the computation of the projective invariants of the sets
of points.
Given the point correspondences (u (j)
and the
projection matrices C (j)
3\Theta4 , for 3, we can write two
linear homogeneous equations for the unknows X
of each point for each image as follows,
c (j)
c (j)
c (j)
c (j)
With three images linear system of 6 homogeneous
equations is obtained. An algebraic solution can be
found by solving any three of them. A numerical solution
can also be found by solving this over-determined linear
system. Therefore we establish the following result which
can be considered as an extension to the recent work of
Faugeras [1] and Hartley et al. [2] for reconstruction from
two uncalibrated images.
Given a set of n - 6 point correspondences in 3 images
taken by uncalibrated cameras, the set of points can be re-constructed
in P 3 up to a collineation.
The reconstruction may have as many as three different
solutions from the minimal data of six points.
Notice that this result reduces the number of points needed
to have a projective reconstruction to the strict minimum
of six.
C. Determination of the epipolar geometry
Another consequence of the complete determination of the
projection matrices is that the epipolar geometry of any
pair of the three cameras can be computed with only 6
point correspondences.
Given a set of 6 point correspondences in 3 images taken
by uncalibrated cameras, the epipolar geometry of any pair
of cameras can be determined, up to at most 3 solutions.
This can be compared with Sturm's method [29], [3], reintroduced
into computer vision in [30], [21], [19], which is of
great importance for two uncalibrated cameras. Based on
projective geometry, Sturm's method yields at most three
solutions in general for the epipolar geometry, which are
three of the nine points of intersection of two cubic plane
curves.
Note that although the two approaches developed respectively
for the two-camera and the three-camera cases lead
to equivalent results, the parametrizations used in two
cases are different. Sturm directly used the epipolar transformation
as the parameters for the two uncalibrated cam-
eras, while we used the projective structure of the point
set in space as parameters for the three uncalibrated cam-
eras. The underlying equations of the parametrization for
the three-camera case are simpler, hence a better numerical
stability might be expected. This is to be confirmed by
the experimental results presented in Section VI.
For extracting the epipolar geometry from any given pair
of projection matrices, one can refer, for instance, to [1]
for more details. Here we are content with the following
results.
ffl The epipole in the j-th image with respect to the i-th
camera e ji is given by
where
ffl The epipolar geometry between i-th and j-th cameras,
represented by the fundamental matrix F ij [19] (the generalization
of the essential matrix [23]) is given by
where [e ji ] is the anti-symmetric matrix associated to e ji ,
and C 3\Theta3 is the left 3 \Theta 3 sub-matrix of the 3 \Theta 4 matrix
C 3\Theta4 .
D. Camera self-calibration
The above results can also be applied to the camera self-calibration
proposed by Maybank and Faugeras [21]. According
to [21], [19], [20], from point correspondences of
QUAN: INVARIANTS OF 6 POINTS FROM 3 UNCALIBRATED IMAGE 7
three uncalibrated images and the associated epipolar ge-
ometries, one can calibrate and therefore obtain a Euclidean
reconstruction (only up to a global scaling factor),
if we suppose that all three images are taken by the same
uncalibrated camera.
Using Sturm's method or other equivalent algebraic methods
for estimating the epipolar geometries for each pair
of three cameras, one needs a minimum number of seven
points to do that. While using the method presented above
which considers the three cameras as a whole, the epipolar
geometries of any pair of three cameras can be computed
with only six points. Therefore, we can make the following
statement.
A camera can be self-calibrated with a minimum of 6 point
correspondences in 3 images.
VI. Experimental results
The theoretical results presented above for the computation
of the invariants of 6 points have been implemented.
The accuracy and stability of the invariants with respect to
various factors such as pixel errors, selection of the triplet
of images and positions of the camera are studied both for
simulated and real images. The computation should be accurate
and stable in order for the invariants to be useful
for vision applications. The three invariants used for experiments
are . The
application for projective reconstruction is also presented.
A. The experiment with simulated images
A.1 Simulation set-up
We will first simulate a number of images in which a set of
6 points in space is projected. The simulation is set up as
follows.
ffl First, a real camera is calibrated (cf. [31], [6], [32]).
This is done by placing a known object of about 50cm 3
in front of the camera. The camera is then moved through
9 different viewing positions, spaced at 10 degree intervals
around the calibration object. The intervals between the
first 3 views are slightly bigger than the second 3 views,
and the second 3 views bigger than the third 3 ones. This
creates 9 calibration matrices which are subsequently used
in the simulation.
ffl With these 9 calibration matrices as our perfect cam-
eras, we project several sets of 6 known points into these 9
synthetic images.
ffl Finally the projected positions of the points in the images
are perturbed by varying levels of noise of uniform
distribution.
ffl As the positions of the 6 simulated points in space are
known in advance, their invariants are computed by the
method given in Section II. These invariants are compared
with those calculated from the simulated image data.
In this way, the realism of simulation is preserved, and the
image noise can be quantitatively controlled as well in order
to observe its influence.
The results that will be presented in the following tables are
obtained from the set of 6 points whose (Euclidean) coordinates
are (2:0; 0:0; 12:0) T (0:0; 6:0; 0:0) T (12:0; 0:0; 14:0) T
unit is in cm). The other sets of 6 points are also simulated
with the same calibration matrices and they have similar
numerical behavior and will not be presented in the tables.
A.2 Stability w.r.t. the selection of the triplets of images

Table

I shows the effect of choosing different triplets of synthetic
images on the stability of the 3 invariants. All images
points are perturbed by a uniform noise of \Sigma1:5 pixels. In
the case where the solution is unique, the computed value
is followed by a   in the tables. When multiple solutions
occur, the one that is the closest to the ground truth value
is selected.
Another experimentation was carried out to test the stability
with respect to the change of one of the 3 images.
Four images 4, 5, 6 and 7 are taken, then all triplets are
selected among the four. Here pixel error is set to \Sigma1:5. In
the case of multiple solutions, all 3 possible solutions are
given for each invariant, the solution that corresponds to
the real solution is marked in bold font in Table II. From
this table, we note that sometimes only one real solution is
possible, in this case, it is the unique correct solution. In
the case of existence of multiple solutions, the real solution
is always present independent of the selection of the triplet
and remains numerically stable.


II
Table of invariants computed from different triplets of
synthetic images. With \Sigma1:5 pixel noise for image points, all
3 solutions of fff; fi; flg, if there are, are shown in order to
illustrate their stability.
Image triplet
4, 6, 7
\Gamma3:77994215:791148
0:424841\Gamma0:023215
\Gamma1:588062\Gamma8:050262
4, 5, 6 0.516476 1.899056 0.747555
0:438052\Gamma0:414817
\Gamma1:051868\Gamma13:899986
4, 5, 7 0.516014 1.899551 0.746564
A.3 Stability w.r.t. the pixel errors
For the given triplets of images f1; 2; 3g, f4; 5; 6g and
different pixel noise (uniformly distributed) is
added to illustrate the influence of the pixel errors.

Tables

III, IV and V show that with noise levels up to
\Sigma5:5 pixels, the computed invariants remain numerically
stable, so that degradation with the increasing pixel noise
is graceful.

Tables

III, IV and V also show that the same invariant computed
with completely different triplets of images remains
stable.
From these empirical results, we note that the uniqueness
of solutions depends partly on the positions of the cameras,
for the first and the third triplet, the solutions are always
multiple. For the second one, they are always unique up to
pixel error.
8 TO APPEAR IN IEEE-PAMI, VOL. 17, NO. 1, JANUARY 1995


I
Table of invariants computed from different triplets of synthetic images. The points of images are noised by \Sigma1:5 pixel
error, the invariants ff; fi and fl are computed for each different image triplet. d i
are the differences between each
computed invariant and its mean value. oe is the standard deviation and oe=m is the ratio of the standard deviation to the
mean value.
Image triplet
4, 5, 6 0.516476* -0.0034 1.899056* 0.0035 0.747555* -0.0082
mean
Ground truth


III
Table of invariants computed from the triplet of synthetic images f1; 2; 3g. ff; fi and fl are computed with pixel errors of
different levels. d i
is the difference between the computed value and its mean value.


IV
Table of invariants computed from the triplet of synthetic images f4; 5; 6g. ff; fi and fl are computed with pixel errors of
different levels. d i
is the difference between the computed value and its mean value.


Table of invariants computed from the triplet of synthetic images f7; 8; 9g. ff; fi and fl is computed with pixel errors of
different levels. d i
is the difference between the computed value and its mean value. Note that with the smallest pixel
error \Sigma0:5, the results are not the best ones.
A.4 Stability w.r.t. the distance between cameras
In

Table

I, the different triplets are ordered in increasing
camera distance order, globally, the accuracy of the computed
invariants is slightly improved by increasing camera
distance.
Although the camera distance decreases slightly from
to f4; 5; 6g and f7; 8; 9g, comparing Tables III, IV
and V, the difference of the accuracy of the computed invariants
is not significant, this is due to the fact that the
camera distance for those triplets is already favorable.
In the next section, camera distance influence will be discussed
with real image sequences.
B. The experiment with real images
We first experimented over a sequence of 24 real images.
The object spans about 30cm in space and is placed in
about 2m from the camera. The camera was turned man-
QUAN: INVARIANTS OF 6 POINTS FROM 3 UNCALIBRATED IMAGE 9
ually around the object, and images are taken every one
or two degrees. The first 13 images and the last 11 images
have slightly different lighting condition. One gradient image
of the sequences is displayed in Figure 1. It is important
to note that the images we used are only a small portion,
approximatively 1=4 of the original 512 \Theta 512 images of the
sequence.
ffl Points are automatically tracked over the sequence and
the location of the points are optimized by a nonlinear sub-pixel
corner detector [33]. The automatic tracker may have
2 or 3 points missing for some images, the missing points
are added by hand. The 6 points used for experimentation
are the visible corners of the two cubic objects, marked by
white circles in Figure 1. Concerning the precision of the
image points, although corner detection is itself subpixel
but the precision of points location can not be considered
as subpixel since we can never guarantee that in different
images a corner comes from the same physical point in
space.
ffl The dimensions of cubic objects in space are measured
by hand to serve as ground truth for comparison with the
computed invariants. However these ground truth should
be considered relative, since errors in measuring 3D objects
are inevitable. Measurement error was estimated as
\Sigma2mm.
The results in Table VI show that the computed invariants
from different triplet of images are stable and usable, except
for fl in the third row. We note that the computation
of fl is systematically worse than that of ff and fi, this is
due to its small modulus, although both have almost the
same magnitude of absolute error, about 0:04, the relative
error is much more important for fl than ff. This is also
due to error accumulation, since fl is found using ff and fi.
One possible remedial measure is to change the order of the
computation, or recompute them from the corresponding
original cubic equations.
In this table, we also note the influence of the camera distances
on the stability of the invariants. Since each pair
of neighboring images differs by a rotation of roughly one
degree, the camera distance in Table VI can roughly be
estimated as the rotation angle in degrees with a radius
of two meters. We can see in the table that, globally the
results degrade by decreasing the distance between camera
positions. However the results from the largest distance
do not give the best ones, this can be explained by the
fact that one side of the objects in these extreme positions
are almost tangent to the view line, so the corresponding
corners are not well defined in the images, therefore they
can not be precisely located by the corner detector. The
pixel errors of the points in the extreme images are much
more important than in other images. When the distance
between cameras becomes quite small, for instance 2, corresponding
to the last 2 rows of the table, the results are
considerably degraded, especially for the triplet of the last
row. When the camera distance is 1, the results are too
bad to be useful, the results are not presented in the table.
Another experiment is performed on a sequence of images
of a wooden house. Three views covering about a
Fig. 1. One gradient image of the sequence. The 6 points marked
by a white circle are used for the experiment.
tation of the camera around the wooden house are taken.
The corners marked in Figure 2 are tracked for the three
images using the same procedure as for the previous image
sequence. The 5 reference points are those numbered

Figure

2. Then with any other point, a
set of 6 points is formed. In Table VII, the computed invariants
are compared with that computed by transforming the
estimated Euclidean coordinates (obtained by the method
described in [32]) using the space collineation A 4\Theta4 (cf. Ap-
pendix). In the case of unique real solution, the computed
values are followed by a  . In case of multiple solutions,
the one that is the closest to the known value is selected
by hand.
Fig. 2. One of the wooden house image sequence. The points used
for the experiment are marked by white circles.


VI
Table of invariants ff; fi and fl computed from the real image sequence with different triplets of images. In the second
column, camera dist. means the distance between camera positions. d i
is the difference between the computed value and the
mean value. oe is the computed standard deviation, oe=m the ratio of the standard deviation to the mean value.
Ima. triplet camera dist. ff d 1 fi d 2 fl d 3
13, 17, 21 4 3.592866 0.50 1.370506 0.0034 0.053793 -0.0041
16, 19, 22 3 2.497743* -0.59 1.282863* -0.054 0.038662* -0.019


VII
Table of invariants computed from the three images of the wooden house for the different sets of 6 points. The first
column presents the sets of numbers of 6 points. In the second column, ff 0
and
are transformed Euclidean coordinates
as ground truth. In the last column, ff; fi and fl are computed from three images.
Set of 6 points known (ff 0
computed (ff; fi; fl)
f1,2,5,8,10,11g (0.594573, 0.944785, 0.157327) (0.581565*, 0.925869*, 0.143597*)
f2,3,5,8,10,11g (0.716795, 0.740667, 0.64426) (0.714164, 0.739041, 0.662835)
f2,5,6,8,10,11g (0.681678, 0.241914, 1.7126) (0.742775*, 0.325263*, 1.822018*)
f2,5,8,9,10,11g (0.634079, 0.344556, 3.09316) (0.705443, 0.448216, 3.303431)
C. The experiment on projective reconstruction
As we have seen in Section V that we can use the invariants
to perform projective reconstruction of a point set from 3
uncalibrated images. We experimented on real images of
the wooden house (see Figure 2). All tracked 46 points of
3 images are used.
Although the theoretical multiplicity of the projective re-construction
is at most three from the minimal data. With
more than the minimum number of points in practice, a
unique solution is always obtained. In this experiment, the
set of 5 reference points is f2; 5; 8; 10; 11g (cf. Figure 2).
The sixth point used to compute the projection matrices
is the point numbered 1 in Figure 2, that is the set of 6
points f1; 2; 5; 8; 10; 11g. Since the invariants of this set of
points are uniquely determined (see the first row of Table
VII), the projection matrices are uniquely computed
from these invariants, then any other tracked points are
reconstructed from the projection matrices. The projective
reconstruction is then transformed into its Euclidean
representation (see Fig 3) by applying A \Gamma1
4\Theta4 (see Appendix)
with the known reference points in order to compare the
result with direct Euclidean reconstruction from 5 images
[32].
Note that during all reconstruction process, we need to
solve only one cubic equation in one variable, all other computational
efforts are linear operations.
VII. Conclusion
In the first part of the paper, it is shown that the three
invariants of a set of six points in general position in space
can be algebraically computed from three images of these
points. No further information about camera calibration
and epipolar geometry is needed. It is shown that the
maximum number of solutions is three which are all algebraically
explicited in closed form.
Compared with the computation of the invariants from two
images, which is essentially based on Sturm's method using
seven points, the method proposed in this paper needs only
six points of the three images.
The result obtained in this paper has some important con-
sequences. It allows to extend the results of Faugeras [1]
and Hartley et al. [2] for projective reconstruction and
Sturm's method [3] for determining the epipolar geometry
from two uncalibrated images to the case of three uncalibrated
images with the minimal data of six points instead
of seven. It is also shown that a camera could be self-calibrated
with only six points of three images.
In the second part of the paper, the stability of the invari-
QUAN: INVARIANTS OF 6 POINTS FROM 3 UNCALIBRATED IMAGE 11
Fig. 3. The rectified projective reconstruction from 3 uncalibrated
images: the points are displayed as stars and the line segments as
solid lines. Euclidean reconstruction from five images: the points
are dots and the line segments dashed lines. The 5 reference
points used were f2;5; 8; 10; 11g (cf. Fig. 2).
ants is studied via both simulated and real images with
respect to different factors. The computed invariants are
numerically stable both with respect to pixel noise and to
selection of triplet of images if the distance between cameras
is not too small. This confirms that our parametrization
has a better numerical behavior than Sturm's. We
have also successfully applied the method to perform projective
reconstruction of set of points.
We can remark that the way we computed the canonical
projective coordinates is not symmetric in the six
points, it is therefore order-dependent. The study of order-independent
invariants has no theoretical problems, however
practically it will produce extremely long and complicated
algebraic expression which will compromise numerical
stability.


Appendix


Plane collineation A \Gamma1
The plane collineation matrix A \Gamma1
3\Theta3 , which transforms the
canonical projective basis in P 2 ,
into four given points: fp
is given by@
where
Space collineation A \Gamma1
The space collineation matrix A \Gamma1
4\Theta4 , which transforms the
canonical projective basis,
into five given points, fp
is given byB B @
where
@
x l y l z l 1C C
Then A 3\Theta3 and A 4\Theta4 can then be obtained from its inverse
either analytically by computing cofactors or numerically
by LU decomposition.

Acknowledgements

This work is partly supported by European Esprit BRA
projects Viva which is gratefully acknowledged. We would
also like to thank B. Boufama, P. Gros, R. Horaud, R.
Mohr, D. Sinclair, D. Wang and C. Zhao for providing
interesting discussion and helps.



--R

"What can be seen in three dimensions with an un-calibrated stereo rig?"
"Stereo from uncalibrated cameras"
"Das Problem der Projektivit-at und seine Anwendung auf die Fl-achen zweiten Grades"
Geometric Invariance in Computer Vision
"Affine structure from motion"
"Relative 3D reconstruction using multiples uncalibrated images"
"Geometric solutions to some 3D vision problems"
"Affine shape representation from motion through reference points"
"Projective Invariants for Vision"
"An algebraic/analytic method for reconstruction from image correspondance"
"Invariants of points seen in multiple images"
"Projective Structure from Two Uncalibrated Images : Structure from Motion and Recognition"
"Invariant descriptors for 3D object recognition and pose"
"Projective invariants of shapes"
"View variation of point set and line segment features"
"Extracting projective structure from single perspective views of 3D point sets"
"Invari- ant linear methods in photogrammetry and model-matching"
"3D projective invariants from two im- ages"
"Camera Self-Calibration: Theory and Experiments"
Matrice Fondamentale et Autocalibration en Vision par Ordinateur
"A theory of self calibration of a moving camera"
"Invariants of 6 points from 3 uncalibrated images"
"A computer program for reconstructing a scene from two projections"
Algebraic Geometry and Theta Functions
Algebraic Projective Geome- try
The Algebra of Invariants

"Relative 3D reconstruction using multiple uncalibrated images"
"Die cubische Gleichung, von welcher die L-osung des Problems der Homographie von M. Chasles abh-angt"
"Motion from point matches: Multiplicity of solutions"
"Close-range camera calibration"
"Euclidian constraints for uncalibrated reconstruction"
"Accurate corner detection: an analytical study"
--TR

--CTR
D. Gregory Arnold , Kirk Sturtz , Vince Velten , N. Nandhakumar, Dominant-Subspace Invariants, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.7, p.649-662, July 2000
Bong Seop Song , Kyoung Mu Lee , Sang Uk Lee, Model-based object recognition using geometric invariants of points and lines, Computer Vision and Image Understanding, v.84 n.3, p.361-383, December 2001
Long Quan, Two-Way Ambiguity in 2D Projective Reconstruction from Three Uncalibrated 1D Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.2, p.212-216, February 2001
Fredrik Kahl , Anders Heyden , Long Quan, Minimal Projective Reconstruction Including Missing Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.4, p.418-424, April 2001
Guang Jiang , Long Quan , Hung-Tat Tsui, Circular Motion Geometry Using Minimal Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.6, p.721-731, June 2004
Ronen Basri , Yael Moses, When is it Possible to Identify 3D Objects From Single Images Using Class Constraints?, International Journal of Computer Vision, v.33 n.2, p.95-116, Sept. 1999
Long Quan , Bill Triggs , Bernard Mourrain, Some Results on Minimal Euclidean Reconstruction from Four Points, Journal of Mathematical Imaging and Vision, v.24 n.3, p.341-348, May       2006
Han , Takeo Kanade, Multiple Motion Scene Reconstruction with Uncalibrated Cameras, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.7, p.884-894, July
Peter Meer , Reiner Lenz , Sudhir Ramakrishna, Efficient Invariant Representations, International Journal of Computer Vision, v.26 n.2, p.137-152, Feb. 1998
Maxime Lhuillier , Long Quan, Match Propogation for Image-Based Modeling and Rendering, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.8, p.1140-1146, August 2002
Long Quan , Jingdong Wang , Ping Tan , Lu Yuan, Image-Based Modeling by Joint Segmentation, International Journal of Computer Vision, v.75 n.1, p.135-150, October   2007
Maxime Lhuillier , Long Quan, A Quasi-Dense Approach to Surface Reconstruction from Uncalibrated Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.3, p.418-433, March 2005
Zhengyou Zhang, Determining the Epipolar Geometry and its Uncertainty: A Review, International Journal of Computer Vision, v.27 n.2, p.161-195, Mar 1998
self-calibration;epipolar geometry;uncalibrated images;projective reconstruction;projective geometry;this invariant