Algebraic and Geometric Tools to Compute Projective and Permutation Invariants.
AbstractThis paper studies the computation of projective invariants in pairs of images from uncalibrated cameras and presents a detailed study of the projective and permutation invariants for configurations of points and/or lines. Two basic computational approaches are given, one algebraic and one geometric. In each case, invariants are computed in projective space or directly from image measurements. Finally, we develop combinations of those projective invariants which are insensitive to permutations of the geometric primitives of each of the basic configurations.
Introduction
Various visual or visually-guided robotics tasks may be carried out using only a
projective representation which show the importance of projective informations
at different steps in the perception-action cycle. We can mention here the obstacle
detection and avoidance [14], goal position prediction for visual servoing
or 3D object tracking [13]. More recently it has been shown, both theoretically
and experimentally, that under certain conditions an image sequence taken
with an uncalibrated camera can provide 3-D Euclidean structure as well. The
latter paradigm consists in recovering projective structure first and then upgrading
it into Euclidean structure [16,4]. Additionally, we believe that computing
structure without explicit camera calibration is more robust than using calibration
because we need not make any (possibly incorrect) assumptions about the
Euclidean geometry (remembering that calibration is itself often erroneous).
All these show the importance of the projective geometry as well in computer
vision than in robotics, and the various applications show that projective informations
can be useful at different steps in the perception-action cycle. Still the
study of every geometry is based on the study of properties which are invariant
under the corresponding group of transformations, the projective geometry is
characterized by the projective invariants.
This paper is dedicated to the study of the various configurations of points
and/or lines in 3D space; it gives algebraic and geometric methods to compute
projective invariants in the space and/or directly from image measurements. In
the 3D case, we will suppose that we have an arbitrary three-dimensional projective
representation of the object obtained by explicit projective reconstruction.
In the image case, we will suppose that the only information we have is the image
measurements and the epipolar geometry of the views and we will compute
three-dimensional invariants without any explicit reconstruction.
First we show that arbitrary configurations of points and/or lines can be decomposed
into minimal sub-configurations with invariants, and these invariants
characterize the the original configuration. This means that it is sufficient to
study only these minimal configurations (six points, four points and a line, three
points and two lines, and four lines). For each configuration we show how to compute
invariants in 3D projective space and in the images, using both algebraic
and geometric approaches.
As these invariants generally depend on the order of the points and lines, we
will also look for features which are both projective and permutation invariants.
Projective Invariants
Definition 1. Suppose that p is a vector of parameters characterizing a geometric
configuration and T is a group of linear transformations, such that
ae are y are vectors of homogeneous coordinates.
A function I(p) is invariant under the action of the group T if
is the value of I after the transformation T.
If I 1 are n invariants, any f(p) = f(I
variant. So if we have several invariants, it is possible that not all of them are
functionally independent. The maximum number of independent invariants for
a configuration is given by the following proposition [5,6]:
Proposition 2. If S is the space parameterizing a given geometric configuration
(for example six points, four lines) and T is a group of linear transformations,
the number of functionally independent invariants of a configuration p of S under
the transformations of T is:
where Tp is the isotropy sub-group of the configuration p defined as
aepg.
Generally, minp2S (dim(Tp certain types of configurations have
non trivial isotropy sub-groups. For example, for Euclidean transformations,
the distance between two 3D points is an invariant and dim(S) \Gamma dim(T
Consequently, minp2S (dim(Tp ))) 6= 0. Indeed, the sub-group of
rotations about the axis defined by two points, leaves both of the points fixed.
The most commonly studied transformation groups in computer vision are
the Euclidean, affine and projective transformations. Since we want to work with
weakly calibrated cameras, we will use projective transformations. As projective
transformations of 3D space have points 3 and lines 4,
using proposition 2, we can easily see that we need at least six points, four points
and a line, two points and three lines, three points and two lines or four lines to
produce some invariants. We will say that these configurations are minimal.
Taking a non-minimal configuration of points and lines, we can decompose it
into several minimal configurations. It is easy to show that the invariants of the
sub configurations characterize the invariants of the original configuration. This
means that we only need to be able to compute invariants for minimal configu-
rations. For example, consider a configuration of seven points denoted M i;i=1::7 .
From proposition 2 there are 3 \Theta 7 \Gamma independent invariants. To obtain a
set of six independent invariants characterizing the configuration it is sufficient to
compute the three independent invariants - i;i=1::3 of the configuration M i;i=1::6
and the three independent invariants - i;i=1::3 of the configuration M i;i=2::7 .
We only discuss configurations of points and lines, not planes. Invariants of
configurations of planes and/or lines can be computed in the same way as those
of points and/or lines, by working in the dual space [12,2]. For the same reasons,
we do not need to consider in detail configurations of two points and three lines.
Indeed, these configurations define six planes which correspond to configurations
of six points in the dual space [2]. The other four minimal configurations we will
study in detail are: six points, four points and a line , three points and two lines
and four lines.
1.1 Projective Invariants Using Algebraic Approach
Consider eight points in space represented by their homogeneous coordinates
compute the following ratio of determinants:
k denotes the value oe(k) for an arbitrary permutation oe of f1;
The invariant I can be computed also from a pair of images using only image
measurements and the fundamental matrix using the Grassmann-Cayley, also
called the double algebra as below [1,3]:
and (fi ?
stands for the expression sign(fi ?
Note that if we change the bases in the images such that ff
are the image coordinates in the new bases, the corresponding fundamental
matrix is F
so the quantities
are independent of the bases chosen.
1.2 Six Point Configurations
Now consider a configuration of six points A i;i=1::6 in 3D projective space. From
proposition 2, there are 3 independent invariants for this configuration. Using
(2) and (3) we can deduce the following three invariants:
I
13\Gamma26
34\Gamma25
I
14\Gamma36
I
To show that they are independent, change coordinates so that A i;i=1::5 become
a standard basis. Denote the homogeneous coordinates of A 6 in this basis by
Computing I j;j=1::3 in this basis we obtain I
s and
I
s . These invariants are clearly independent.
Alternatively, one can also take a geometric approach to compute six point
invariants. The basic idea is to construct cross ratios using the geometry of
the configuration. In this case we will give two different methods that compute
independent projective invariants.
The first method constructs a pencil of planes using the six points. Taking
two of the points, for example A 1 and A 2 , the four planes defined by A 1 ; A 2 and
A k;k=3::6 belong to the pencil of planes through the line A 1 A 2 . Their cross ratio
is an invariant of the configuration. Taking other pairs of points for the axis of
the pencil gives further cross ratios. The relation between these and I j;j=1::3 is:
The second method [5] consists in constructing six coplanar points from the
six general ones and computing invariants in the projective plane. For exam-
ple, if take the plane A 1 A 2 A 3 and cut it by the three lines A 4 A 5 , A 4 A 6 and
A 5 A 6 obtaining the intersections M 1 , M 2 and M 3 coplanar with A i;i=1:3 . Five
coplanar points, for example A i;i=1::3 ; M i;i=1;2 , give two cross ratios
Any other set of five, for example A i;i=1::3 ; M i=1;3 , gives two further cross
only three of the four cross ratios are independent. Indeed
The relation between - i;i=1::3 and
I j;j=1::3 are -
I3 and -
So we have several methods of computing geometric invariants in 3D space.
To do this, we need an arbitrary projective reconstruction of the points. However,
the invariants can be also be computed directly from the images by using the
fact that the cross ratio is preserved under perspective projections.
First consider the case of the pencil of planes. We know that the cross ratio
of four planes of a pencil is equal to the cross ratio of their four points of
intersections with an arbitrary transversal line. So if we are able to find the image
of the intersection point of a line and a plane we can also compute the required
cross ratio in the image. The coplanar point method uses the same principle,
computing the intersection of a line and a plane from image measurements.
We want to compute the images of the intersection of a line A 3 A 4 and a plane
only the projections of the five points in two images a i;i=1::5 and
a 0
i;i=1::5 and the fundamental matrix between the two images. Take a point p in
the first image and a point p 0 in the second one. These points are the projections
we are looking for if and only if
3 \Theta a 0
verify (details in [2]):
(a 0
2 \Theta a 0
1 \Theta (Fp \Theta (a 0
3 \Theta a 0
F
(a 2 \Theta a 5 ) \Theta (a 1 \Theta p)
The first equation is linear. The second one is quadratic, but it is shown in [2]
that it can be decomposed into two linear components, one of which is irrelevant
(zero only when p belongs the epipolar line of a 0
finally we obtain two linear
equations which give the solution for p and
3 \Theta a 0
Another way to compute the intersection of a plane and a line from image
measurements is to use the homography induced between the images by the
plane. Let us denote the homography induced by the 3D plane \Pi by H. The
image n 0 of the intersection N of a line L and the plane \Pi is then
To compute the homography H of the plane A 1 A 2 A 5 , we use the fact that
ae i a 0
We denote a
a 0
and the
coefficients of the matrix H by h ij . Then for each j 2 f1; 2; 5; eg, we have:
As H is defined only up to a scale factor, it has only eight independent degrees
of freedom and can be computed from the eight equations of (5).
1.3 Configurations of One Line and Four Points
Denoting the four points by A i;i=1::4 and the line by L we obtain (cf. (2) and
(3)) the following invariant:
arbitrary two distinct points on
the line L, ff are the projections of A i;i=1::4 and L in the two images,
Using the geometric approach, the four planes LA i;i=1::4 belong to a pencil
so they define an invariant cross ratio -. Another approach, given by Gros in [5]
is to consider the four planes defined by the four possible triplets of points and
cut the line L with them. This gives another cross ratio - 0 for the configuration.
Of course, we only have one independent invariant, so there are relations between
I , - and - 0 . Indeed, we have
The method of computing - and - 0 directly from the images is basically the
same as for the configuration of six points .
1.4 Configurations of Three Points and Two Lines
The following two ratios are independent invariants for configurations of three
points A i;i=1::3 and two lines L k;k=1;2 in 3D:
I
I
These invariants can also be obtained as follows. Cut the two lines with the plane
defined by the three points to give R 1 and R 2 . The five coplanar points
define a pair of invariants, for example
Another way to compute a pair of independent invariants for this configuration
is to consider the three planes L 1 A i;i=1::3 and the plane A 1 A 2 A 3 and cut
them by L 2 This gives a cross ratio - 0
-2 . Changing the role of L 1 and L 2
gives another cross ratio - 0
. The cross ratios - i;i=1;2 and - 0
i;i=1;2 can
be computed directly in the images in the same way as the cross ratios of the
configuration of six points (finding images of intersections of lines and planes).
Configurations of Four Lines
Consider four lines L i;i=1::4 in 3D projective space. This configuration has
rameters, so naively we might expect to have independent invariant.
However, the configuration has a 1D isotropy subgroup, so there are actually
two independent invariants [6,5,2].
The existence of two independent cross ratios can also be shown geometri-
cally. Assume first that the lines are in general position, in the sense that they
are skew and none of them can be expressed as a linear combination of three
others. Consider the first three lines L i;i=1::3 . As no two of them are coplanar,
there is a one parameter family K of lines meeting all three of them. K sweeps
out a quadric surface in space, ruled by the members of K and also by a complementary
family of generators L, to which L 1 , L 2 and L 3 belong [11,6]. Members
of K are mutually skew, and similarly for L, but each member of K intersect each
member of L exactly once. Another property of generators is that all members
of each family can be expressed as a linear combination of any three of them.
By our independence assumptions, the fourth line L 4 does not belong to either
family (if L 4 belonged to L it would be a linear combination of the L i;i=1::3
and if L 4 was in K it would cut each of the lines L i;i=1::3 ). Hence, L 4 cuts the
surface in two real or imaginary points, A 4 and B 4 (these may be identical if
L 4 is tangent to the surface). For each point of the surface there is a unique line
of each family passing through it. Denote the lines of K passing through A 4 and
respectively. Let these lines cut the L i;i=1::3 in A i;i=1::3 and
respectively. In this way, we obtain two cross ratios:
Before continuing, consider the various degenerate cases.
- Provided that the first three lines are mutually skew, they still define the two
families K and L. The fourth line can then be degenerate in the following
ways:
ffl If L 4 intersects one (L i ) or two (L of the three lines, we have the
same solution as in the general case with A
respectively.
ffl If L 4 2 K intersects all three lines L i;i=1::3 , the two transversals T 1 and
are equal to L 4 and the cross ratios are no longer defined.
ffl If L 4 2 L (linear combination of the lines L i;i=1::3 ) every line belonging
to K cuts the four lines L i;i=1::4 and there is only one characteristic cross
ratio.
Given two pairs of coplanar lines, say L there are two
transversals intersecting all four lines. One is the line between the intersection
of L 1 and L 2 and the intersection of L 3 and L 4 . In this case the cross ratio
1. The other is the line of intersection of the planes defined by
defining a second cross ratio [5].
- If three of the lines are coplanar, say L i;i=1::3 , the plane \Pi containing them
intersects L 4 in a point A 4 . If the lines L i;i=1::3 belong to a pencil with center
the lines L i;i=1::3 and BA 4 define one cross ratio. Otherwise, we
have no invariants.
Finally, if all of the lines lie in the same plane \Pi, the possible cases are that
they belong to a pencil and define one cross ratio or they do not belong to
a pencil and there are no invariants.
As in the preceding cases, we can also compute the invariants using the
algebraic
I
I
where l i and l 0
i are the projections of the L i;i=1::4 in the images, fi
l i . The relation between I i;i=1;2 and - j;j=1;2 is I
and I conversely, given I 1 and I 2 , - 1 and - 2 are the solutions of
the equation As I 1 and I 2 are real, - 1 and - 2 are
either real or a complex conjugate pair.
Computation of - 1 and - 2 in 3D: First, we suppose that we know a projective
representation of the lines in some projective basis. They can be represented
by their Pl-ucker coordinates L
We look for lines T that intersect the L i;i=1::4 . If
it represents a transversal line if and only if:
ae
l (i)
This is a homogeneous system in the six unknowns p i;i=1::6 , containing four
linear equations and one quadratic one. It always has two solutions:
(p k
k=1;2 defined up to a scale factor, which may be real or
complex conjugates. These lines cut the L i;i=1::4 in A i;i=1::3 and B i;i=1::3 which
Computation of - 1 and - 2 from a Pair of Views: Define F to be the
fundamental matrix and l
i ) to be the
projections of the lines L i;i=1::4 into the images. Consider a line l in the first
image, with intersections x l with the lines l i;i=1::4 . If the intersections
i of the epipolar lines with the l 0
i;i=1::4 in the second image all lie on
some line l 0 , then l and l 0 are the images of a transversal line L. The condition
of this can be written:
ae
This system of equations is difficult to deal with directly. To simplify the
computation we make a change of projective basis, so that the new basis satisfies
The fundamental matrix
then becomes
and the two pencils of epipolar lines take the form
Using this parameterization, and after simplifications [2] we obtain:
complex conjugates, are the significant 1 solutions
of the system:
ae
with
Projective and Permutation Invariants
The invariants of the previous sections depend on the ordering of the underlying
point and line primitives. However, if we want to compare two configurations,
we often do not know the correct relative ordering of the primitives. If we work
with order dependent invariants, we must compare all the possible permutations
of the elements. For example, if I k;k=1::3 are the three invariants of a set of
points A i;i=1::6 and we would like to know if another set B i;i=1::6 is projectively
equivalent, we must compute the triplet of invariants for each of the 6!=720
1 The other two solutions are (1; 0;
our parameterization we can consider without lost of generality that t i
possible permutations of the B i . This is a very costly operation, which can be
avoided if we look for permutation-invariant invariants. 3
Definition 3. A function I is a projective and permutation invariant for a configuration
formed by elements only if we have for all projective
transformations T and for all permutations - 2 S k
The projective invariants we computed were all expressed as cross ratios, which
are not permutation invariants. As the group of permutations S 4 has 24 elements,
there are potentially 24 possible cross ratios of four collinear points. However, not
all of these are distinct, because the permutations -
have the same effect on the cross ratio. We know that all permutations can be
written as products of transpositions of adjoining elements. For S 4 there are
three such transpositions 4). The
effect of - 1 and - 3 is F 1
- and that of - 2 is F 2 -. If we compute all
the possible combinations of these functions, we obtain the following six values:
- .
To obtain permutation invariant cross ratios of four elements, it is sufficient to
take an arbitrary symmetric function of the - i;i=1::6 . The simplest two symmetric
functions J
are not interesting
because they give constant values. Taking the second order basic symmetric functions
unbounded
functions. Further invariants can be generated by taking combinations of the former
ones
proposed in [8] bounded
between 2 and 2.8 or
J2 bounded between 2 and 14. These functions
are characterized by the fact that they have the same value for each of the six
arguments - i;i=1::6 .
Let us see what happens in the case of six points in projective space. We
saw that the invariants of the points A i;i=1::6 given by (4) correspond to cross
ratios of pencils of planes. Define: I
A -(1) A -(2) A g. It is easy to see that I
I 231456 , I I 132456 and I
We are interested in the effect of permutations of points on the invariant
. The first remark is that if we interchange the first two elements the
value is the same: I which is obvious from a geometric viewpoint
as A 1 A 2 A k and A 2 A 1 A k represent the same plane.
If we fix the first two points and permute the last four, we permute the four
planes giving the cross ratio. So if we apply one of the above symmetric functions,
for example J , the results will be invariant. Using the following proposition
proved in [2] we can find all the possible values for J(I -(1)-(2)-(3)-(4)-(5)-(6) ).
3 We generalize here the work of Meer et al. [8] and Morin [9] on the invariants of five
coplanar points to 3D configurations of points and lines.
Proposition 4. An arbitrary permutation - of S 6 can be written as a product
of four permutations - 1k - 2n - 1m ,
is a permutation of the last four elements.
Denote the value of I -(1)-(2)-(3)-(4)-(5)-(6) by -(I 123456 ). We have then -(I 123456
applying (for example) J , we obtain:
because - changes only the order of the four planes giving the cross ratio. But
- 1k has no effect on the value of the cross ratio: - 11 is the identity and - 12 interchanges
the first two elements but leaves the planes invariant, so J(-(I 123456
J((- 2n (- 1m (I 123456 ))).
Consequently, we obtain only C 2
different possible values instead of
These will be denoted by Jmn = J((- 2n (- 1m (I 123456 ))). It is easy
to see that
ng. The geometric meaning of this is that we fix the pair of
points giving the axis of the pencil of planes.
As a function of I 1 ; I 2 and I 3 , the 15 values are:
Note that the values of I 1 ; I 2 ; I 3 depend on the order of the points, but any
other ordering gives the same values in different ordering. For this reason, we
sort the 15 values after computing them to give a vector that characterizes the
configuration independently of the order of underlying points.
Now, consider the configuration of a line and four unordered points. This
case is a very simple case because we have a cross ratio, so it is enough to take
the value of the function J(I) where I is the invariant given by (6). Similarly
to compute permutation invariants of four lines in space, we apply J to the pair
of cross ratios - 1 and - 2 given in the section 1.5. It turn out that the order
of the two sets of intersection points of the four lines with the two transversals
change in the same way under permutations of the lines. When - 1 and - 2 are
complex conjugates, J(- 1 ) and J(- 2 ) are also complex conjugates, but if we
want to work with real invariants it is sufficient to take J
The fourth basic configuration is the set of three points and two lines. We saw
that we can compute invariants for this configuration using the invariants of five
coplanar points. In this case it is sufficient to apply the results of [8], which show
that if I 1 and I 2 are a pair of invariants for five coplanar points we can take the
sorted list with elements: J(I 1
), to obtain
a permutation invariant. But this means that we make mixed permutations of
points and lines, which is unnecessary because when we want to compare two
such configurations we have no trouble distinguishing lines from points. When
we have five points in the plane A 1 A 2 A 3 we will require that the center points
of the considered pencils of lines be chosen among A i;i=1::3 and not among the
intersection points R j;j=1;2 (see section 1.4). In this way we have the cross ratios
of the form - . If we interchange A 1 and
A 2 , we obtain I 2 . Interchanging A 2 and A 3 gives 1
I1 and interchanging A 1 and
A 3 we obtain I1
I2 . The permutation of the two lines (i.e. R 1 and R 2
I1 .
Hence, applying J we find that the sorted list of elements
is a projective and permutation invariant for this configuration.
2.1 Some Ideas Concerning More Complex Configurations
Consider a configuration of N ? 6 points 4 From proposition 2, this configuration
has 3N independent invariants. Denote the N points by A i;i=1::N
and the 3(N \Gamma 5) invariants of this configuration by - k
3 are the invariants of the sub-configurations A
As the invariants - k
i depend on the order of the points, we try to generalize
the above approach to the N point case. First note that the invariants
are cross ratios of four planes of a pencil I
Ng. Consequently, for a given
set fi; j; k; l; m;ng ae
different values J(I ijklmn ).
But, there are C 6
N subsets of six points, so we have C 6
6 different values which
can be computed from the 3(N \Gamma 5) independent invariants - k
We show how to obtain these values in the case of 7 points, but the approach
is the same for N ? 7. Denote the independent invariants of
this configuration by - 1
The C 6
values can be obtained by calculating for each subset of six
points fi; j; k; l; m;ng ae 7g such that
the values I I ikjlmn and I I ijklmn in function of - j
subsets
I
I
I 3 - 1
and then apply (10). Finally, we sort the resulting list of 105 elements.
Conclusion
We have presented a detailed study of the projective and permutation invariants
of configurations of points, lines and planes. These invariants can be used as a
basis for indexing, describing, modeling and recognizing polyhedral objects from
perspective images.
4 We will consider only the case of points. The other cases can be handled similarly,
but the approach is more complex and will be part of later work.
The invariants of complex configurations can be computed from those of
minimal configurations into which they can be decomposed. So it was sufficient
to treat only the case of minimal configurations. Also, in projective space there is
a duality between points and planes that preserves cross ratios, so configurations
of planes or planes and lines can be reduced to point and point-line ones.
For each configuration we gave several methods to compute the invariants.
There are basically two approaches - algebraic and geometric - and in each
case we showed the relations between the resulting invariants. We analyzed the
computation of these invariants in 3D space assuming that the points and lines
had already been reconstructed in an arbitrary projective basis, and we also gave
methods to compute them directly from correspondences in a pair of images. In
the second case the only information needed is the matched projections of the
points and lines and the fundamental matrix.
Finally, for each basic configuration we also gave permutation and projective
invariants, and suggested ways to treat permutation invariance for more
complicated configurations.

Acknowledgment

We would like to thank Bill Triggs for his carefully reading
of the draft of this manuscript.



--R

Multiple image invariants using the double algebra.
Modelisation projective des objets tridimensionnels en vision par ordi- nateur
Computing three-dimensional projective invariants from a pair of images using the Grassmann-Cayley algebra
From projective to euclidean reconstruction.
3D projective invariants from two images.
Invariants of lines in space.
Visually guided object grasping.
Correspondence of coplanar features through p 2
Quelques contributions des invariants projectifs 'a la vision par ordina- teur. Th'ese de doctorat
A comparison of projective reconstruction methods for pairs of views.
Algebraic Projective Geometry.
G'eom'etries affine
Geometric invariants for verification in 3-d object tracking
Applications of non-metric vision to some visual guided tasks
A robust technique for matching two uncalibrated images through the recovery of the unknown epipolar geometry.
Metric calibration of a stereo rig.
--TR

--CTR
Franoise Dibos , Patrizio Frosini , Denis Pasquignon, The Use of Size Functions for Comparison of Shapes Through Differential Invariants, Journal of Mathematical Imaging and Vision, v.21 n.2, p.107-118, September 2004
Yihong Wu , Zhanyi Hu, Camera Calibration and Direct Reconstruction from Plane with Brackets, Journal of Mathematical Imaging and Vision, v.24 n.3, p.279-293, May       2006
Arnold W. M. Smeulders , Marcel Worring , Simone Santini , Amarnath Gupta , Ramesh Jain, Content-Based Image Retrieval at the End of the Early Years, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.12, p.1349-1380, December 2000
indexation;uncalibrated stereo;grassmann-cayley algebra;projective reconstruction;projective and permutation invariants;cross ratio