BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR92-1292
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: On Invariants of Sets of Points or Line Segments Under Projection
AUTHOR:: Huttenlocher, Daniel P.
AUTHOR:: Kleinberg, Jon M.  
DATE:: July 1992
PAGES:: 15
ABSTRACT::
We consider the problem of computing invariant functions of the image of a set 
of points or line segments in $\Re^3$ under projection. Such functions are in 
principle useful for machine vision systems, because they allow different 
images of a given geometric object to be described by an invariant `key'. We 
show that if a geometric object consists of an arbitrary set of points or line 
segments in $\Re^3$, and the object can undergo a general rotation, then there 
are no invariants of its image under projection. For certain constrained 
rotations, however, there are invariants (e.g., rotation about the viewing 
direction). Thus, we precisely delimit the conditions for the existence or 
nonexistence of invariants of arbitrary sets of points or line segments under 
projection.
END:: CORNELLCS//TR92-1292
BODY::
On invariants of Sets of Points or Line
Segments Under Projection*
Daniel P. Huflenlocher
Jon M. Kleinberg
TR 92-1292
July1992
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
*This work was supported in part by National Science Foundation PYl grant IRI-
9057928 and matching funds from General Electric, Kodak and Xerox, and in part by
Air Force contract AFOSR-91 -0328.
On Invariants of Sets of Points or Line
Segments Under Projection *
Daniel P. Huttenlocher and Jon M. Kleinberg
Computer Science Dep&tment
Cornell University
Ithaca NY 14853
Abstract
We consider the problem of computing invanant functions of the image of
a set of points or line segments ill ?? under projection. Such functions are
in principle useful for machine vision systems, because they allow different
images of a given geometric object to be described by an invariant `key'. We
show that if a geometric object consists of an arbitrary set of points or line
segments in ?, and the object can undergo a general rotation, then there are
no invariants of its image under projection. For certain constrained rotations,
however, there are invariants (e.g., rotation about the viewing direction).
Thus we precisely delimit the conditions for the existence or nonexistence of
invariants of arbitrary sets of points or line segments under projection.
*This work was supported in part by National Science Foundation PYl grant IRI-9057928
and matching funds from General Electric, Kodak and Xerox, and in part by Air Force contract
AF0SR-91-0328.
1. Introduction
For many problems in computer vision, it is desirable to be able to describe an
object independent of the direction from which it is viewed. In other words, it is
useful to be able to form a `key' corresponding to a given object, where that key
remains unchanged regardless of the relative position and orientation of the object
and the viewer. In order to compute such viewpoint-independent descriptions, a
number of recent investigations have applied techniques from classical invariant
theory (e.g., [3, 6, 7, 8]). Invariant theory is a branch of algebra concerned with
functions for which the value of the function remains unchanged after it is composed
with members of some distinguished set of functions If (cf. [4]). For example, a
function f on the elements of some set 5 is invariant with respect to If, if f(x) =
f(h(x)) for all r E 5, h E If. A function I is said to be trivial if it has the same
value for all x E 5 --H clearly such constant functions are invariant but they are
uninteresting because they cannot distinguish different elements of 5.
If the set of functions If represents the change in the shape of an object as the
viewing direction varies, then any nontrivial invariants with respect to If provide
viewpoint-independent `keys' for describing an object. Such invariants do exist
in certain cases, and have been successfully applied to a number of model-based
recognition problems (in which geometric models of known objects are compared
against an image containing unknown objects) [3, 7]. The classical theory, however,
studies invariants with respect to sets of functions that form a group. In particular,
this means that each functi6n in the set If must have an inverse also in the set.
For many machine vision applications this is an unfortunate constraint, because the
projection of the three-dimensional world onto a tw?dimensional image plane is
not invertible. Thus applications of invariant theory to computer vision have been
primarily restricted to the case where the object being viewed is flat (planar), so
that the viewing transformation forms a group. One notable exception is the work
of [7] which develops invariants under orthographic projection of three orthogonal
vectors in space.
In this paper we investigate the problem of computing invariants of the two-
dimensional images of geometric objects in three-space. We focus on the case of
finite point sets in ?, and then show how to extend the results for point sets to sets
of line segments in ?. We consider the image of a set of points or line segments
in ? under some projection operation (e.g., orthographic or central projection),
where the set may be transformed by the action of some group & acting on
The invariant functions, if they exist, operate on the projections of the point set.
Thus these functions have no direct access to the action of the group G, but only to
the images of those actions under the projection operation (in other words the set
If here is the composition of G with the projection operation). We delineate the
classes of groups for which there exist (or do not exist) invariants of sets of points or
2
line segments under projection. In order to do this, we define a more general notion
of projection that encompasses both central and orthographic projection (among
others).
A number of papers in the computer vision literature have recently considered
the question of the existence of nontrivial invariants of three-dimensional objects
under projection into the plane. One of these works [1] concludes after somewhat
lengthy arguments that there are no (nontrivial) invariants of finite point sets in ?
under Euclidean motion and central projection. Another paper [2] makes an informal
argument that there cannot be invariants under orthographic projection from ? into
?2 A third paper makes a more rigorous argument that there cannot be invariants
under orthographic projection from ? into ?2, and investigates certain restricted
object classes where there are invariants (e.g., symmetric sets) [5]. None of these
investigations precisely characterizes the conditions for the existence of invariants
for point sets under projection, nor do they consider sets of line segments.
Our basic result is that if the group G acting on a three-dimensional set (points
or line segments) contains a rotation about some fixed but arbitrary axis, then there
are no invariants under projection. For certain rotation axes (such as the viewing
direction under orthographic projection) there are invariants. We thus provide a
precise formulation of which groups have (or do not have) nontrivial invariants
under projection.
2. Projections and Invariants
There are at least two standard projections we could consider: orthographic (where
lines of projection are perpendicular to the image plane) and central (where lines of
projection all pass through a single point). Rather than prove all of our results twice,
we use a more general definition of projection, which we introduce here. The set of
lines of projection (or lines of sight) is the key structure underlying a projection. In
general, for each point p E ? there should be some unique corresponding line of
projection on which it lies. Clearly in orthographic projection this is just the line
through p and normal to the viewing plane. For central projection it is the line
through p and the center of projection. Note that in this latter case the center of
projection itself is a degenerate point--Hit does not have a unique projection line, as
all the lines go through it.
We define the set of lines of projection, A, to be a set of lines that cover all of ??,
such that each line e E A has at most one degenerate point. We add an additional
constraint that the set of all degenerate points be small (see condition 3 below).
Denote this set of degenerate points by ?A, and let DA = --H ?A . A given set of
lines of projection, A, thus defines a naturally associated map A : DA . A. That
is, each non-degenerate point of ? (the points of DA) lies on a unique line of A,
and the function A maps each such point to its corresponding line. Note that this
3
definition of a projection does not map points of ? to points of ?2; rather it maps
points of ? to lines of A. These lines could then be cut by some (fixed) viewing
plane, or manifold, yielding a unique point of ?2 for each line of A.
A little more precisely, a projection A is the natural function from DA to A
associated with a given set of projection lines A, where A has the following three
properties:
?EA
2. With ?A = f? fl t' : ?? E A1, each set t fl ?A (? E A) is empty or contains a
single point.
3 ?A contains no ray or circle. (Among other things, this guarantees that it is a
"one-dimensional" subset of ?.)
We wish to note that our results still hold for a projection in which the degener-
ate set is a line (e.g., as would occur with a prism); the proofs, however, become
considerably more involved.
In the following, we consider the case of invariants of point sets under projec-
tion, and defer discussion of sets of line segments (which we call frameworks) until
Section 6. For a finite point set P c DA, we define L = AP in the natural way as
the set of lines ?Ap : p E PJ. While the map A is not invertible, it is often desirable
to speak of a particular set of points that could project to L = AP. We thus define
a realization of L C A to be any set of points that could project to L; i.e. a point
set P C DA such that AP = L. In other words, a realization of L C A is a point
set that results from simply picking one non-degenerate point on each of the lines
?EL.
Next, we would like to define more precisely what is meant by an invariant
function under projection. These functions will operate over finite sets of lines of
A (viewing lines) of some fixed cardinality. We fix the cardinality because it is a
nontrivial invariant, though not a very interesting (nor geometric) one. Moreover,
so as to be able to prove the strongest non-existence results we can, we will assume
that our invariant functions are only defined on sets of n distinct lines of A --H this
means that if one point of P occludes another in the projection, f is simply not
defined. If this assumption is not made, the proofs below become much easier, but
carry less weight as they rely on bizarre degeneracies based on the viewing direction.
We use the notation An to denote the set of all subsets L C A of cardinality n. Let
?A be the set of all functions on sets L E An for some fixed n. We take all elements
of ?? to have some common range set, but the only assumption we make about this
set is that it is at least as large as the reals. Let G be a transformation group that
acts on points in ??, and let A be a projection induced by the covering set A (as
defined above).
4
We will say that I E ?A is invariant with respect to G and A if f(AP) = f(AgP)
for any set of points P such that AP, A9P E An. (Note that P E An exactly when
each point of P lies on some unique line of A, i.e., P C?DA and Vp,p' E P: Ap =
Ap' ? p = p'). Let A(G) C ?A denote the set of all functions in ?A that are
invariant with respect to G and A. Clearly the constant functions are in IA(0)
for all G, A; these are said to be the trivial invariants, and if IA(G) contains only
constant functions, we will say that 1A (G) is trivial.
In other words, IA(G) C ?A is the set of functions on An that remain unchanged
under the action of G on a point set P C DA (where AP and A9P are both sets of
n distinct lines of A). Thus the structure is that of a group acting on a space (DA)
that is not directly `observable' by the functions in ?A (all that the functions see is
An). Classical invariant theory was also developed in part to study the images of
geometric objects under projection (e.g., the planar affine and projective groups).
In the classic case, however, the composition of G and the projection operation A
itself forms a group. Thus the object of study is still a group action. In the general
case that we consider here the composition of G and A is no longer invertible.
Let us make note of a subtlety in all this. Our invariant functions are based on
a priori assumptions about the structure of our sets in ?? and A. That is, we have
the following conditions on P and AP:
o+ The three-dimensional condition: P is a set of n points, none of which lie in
o+ The tw?dimensional condition: No two points of P are mapped to the same
line of A by A.
As noted above, these assumptions make the following non-existence proofs more,
not less, general. In what follows, we shall be careful the realizations and projections
we construct always satisfy this pair of conditions.
There is a powerful inductive technique that we use in our proofs, which relies on
a property of set functions that we will call Property A. Consider two sets 5 and
5' of n elements each that differ in at most one element (i.e., 5 fl 5' has cardinality
at least n--Hi). We say that f has Property A when f(S) = f(S') for any such 5,5'.
The following result now holds for functions on sets of cardinality n.
Lemma 1 1ff has Property A, then f is constant.
Proof. Let T = ?i,...,tnJ, T' = ?`1,...,t'n) Set T0 = T, Tn = T', and for
i = i,...,n --H 1, define Tj = ft'1,...,t'j,tj+1,...,tnj. Then for i = O,...,n --H 1,
f(Tj) = f(Ti+1), by Property A, so f(T) = f(T'). Since T and T' were arbitrary, I
is constant. 1
Using Property A, we will devise a characterization o? groups G that have only
trivial invariants under the projection function A. We wish to note that there are
5
analogous ways of phrasing Property A and Lemma 1 that correspond to labeled
point sets. Our non-existence proofs then carry over to the case of labeled point
sets with almost no modification.
Before developing the last few tools needed to show some general results on ex-
istence and non-existence of invariants, we would like to demonstrate the simplicity
of our main technique by proving one result immediately.
Theorem 2 Let E3 denote the gronp of rigid (Euclidean) motions in ?? (i.e., the
composition of the special orthogonal and translation gronp&). For any projection A,
IA(E3) is trivial.
Proof. Let f be invariant with respect to A and E3, and let L and L' be subsets of
A of size n that differ in at most one element. Let P and P' be realizations of L and
L' such that p,' = for all j # i. (Recall P is a realization of L when AP =
Let ? be the line through p? and p'? For any non-degenerate line e E A, there is a
rigid motion g such that g? = e and neither p? nor p?' lands on  fl ?A Moreover, we
can choose P and P' such that no two points of gP or gP' lie on the same line of A
or in the degenerate set. Then AgP = AgP', so f(L) = f(AgP) = f(AgP') =
thus f has Property A and is constant. I
The key step of this proof is showing that given two arbitrary points in ?, we
can apply an element of E3 that positions them on the same line of projection;
in this way, two point sets differing by a single element cannot be distinguished
by a function invariant with respect to G = E3 and A. Then the result follows
immediately from Lemma 1. This result is a generalization of the claims in [1] and
[2], on the nonexistence of invariants under central and orthographic projection.
Our proof of this fact is very simple and does not rely on any degeneracies, such as
multiple collinear or coplanar points. Moreover, we apply the same general technique
to delineate precisely the conditions for the existence or nonexistence of invariants
under projection.
We also note that
Fact 3 If H is a subgroup of G, then IA(H) D
Thus there are no invariants under projection for any group that contains E3 as a
subgroup.
The proof of Theorem 2 can be generalized to show that other (smaller) groups
do not have nontrivial invariants under projection. By Fact 3, these groups in turn
rule out invariants for any groups containing them. We now turn to developing
some additional tools needed to establish these results. The main difference in the
technique is that for more restricted groups we are no longer able to use the group
action to place two points on some line of A. instead we form a finite sequence of
6
group actions and motions along a line of A that places two points on the same line
of A. (Note that motions along a line of A are not detectable by functions in ?A.) In
the end we derive a precise characterization of those groups with trivial invariants
under projection.
3. Groups With(out) Invariants Under Projection
In the proof of Theorem 2 we used the fact that for any two points p, q E ??, there
exists a Euclidean motion g E E3 that positions p and q on any line of ?. Thus
it was possible to establish Property A. We now consider groups for which this is
no longer the case (the only assumption that we make about the group G is that it
maps lines to lines). Consider the rotation group (i.e., the special orthogonal group
SO3); clearly it is not possible to rotate the line containing two arbitrary points p
and q in order to make it coincident with any line of ??. Thus we make use of the
additional fact that motion of a point along a line e E A is not detectable (all points
along a given viewing line are indistinguishable). We then build a finite sequence of
group actions and motions along  that brings p and q onto a given viewing line.
We express this notion as follows. Let ??, e1 E A and write e() N ? if there exist
g1,...,g?EG,?,...,?,4,...,41EAsuchthatwith?=?, ? = t01 we have
gj(t?j?1 --H?A)fl(4--H?A)#?
= I,...,k,j = 0,1)
(1)
We will sometimes refer to these sequences as a chain from ? to 1; the intermediate
lines t?j are the two "sides" of the chain. If ? N e1 for every pair of lines of A, then
we say that (G, A) has Property B; that is, there is a chain of the form in (1) for
every pair of lines of A. We first prove that N is in fact an equivalence relation
Lemma 4 N is an eqtivalence relation on the elements of A
Proof. Reflexivity and symmetry are easy to show. To establish transitivity, assume
that ? N e' and e' N e11. Thus we have Yi,...,?k E G) ??,. . . ,?, i1,...,41 c A
formingachain bdween?and t; we have h1,...,hp E G, ?i??..??flp0???11?...?flp1 E A
forming a chain between t' and t'.
For i = 1,.. .,p, inductively define v? E A such that v0 = e and hj(vj?1 --H
intersects v? --H ?A (this is always possible by Property 3 of the covering set A). Then
it is easily verified that we have a chain between  and ?, with
hp, hp41, .,h?,g1,.. . ,g? E G
7
and the lines
V1,.. .,Vp,Vp?l,. . . ,v1,e?,. . .,? E A
?111,,71p1,flp01,,?01,?11,,??1EA
forming the two sides of the chain. I
Let F be the set of equivalence classes induced by N, and let Fn denote the set
of all cardinality-n multisets of 1'. Define the function ? : A F to map a line of
A to its equivalence class, and define ? : An ) Fn analogously for multisets. We
are now in a position to consider the relationship between N and the structure of
IA(C).
Lemma 5 Let L0, L1 E An, f?(L0) = ?(M) and f E IA(G), then f(L0) = f(L1).
Proof. As usual, it is enough to assume that L0 and L1 differ by only one element;
that is, there is some ? E L0 and C? E L1 with ?? # ?. The relation N says that
we may find g?,...,g?EG,?,. . . ,eO?,?11,. ,41 E A satisfying the condition of (1).
Using this chain, we are going to construct a sequence of cardinaiity?n subsets of A,
beginning with L0 and ending with L1, such that the property of invariance ensures
f takes the same value on each consecutive pair.
Let ??o' be a realization of L0 and i?' a realization of L1, with p?' and Po11 the
realizations of ? and e1. These are chosen so that 91P??' E ? --H ?A and Y1P?' E ? --H
and neither g?P001 nor g1i?)1I contains two points on the same line of A. By the
properties of the chain from (1) and since ?A contains no ray, it is easy to verify
that these constraints can be satisfied. Set i? = g?P001 and i? = y1P01,. These two
sets differ only by points lying on ? and e11.
Proceeding inductively, assume we have point sets Pj0 and Pj1 differing only by
points that lie one? and ?. Call these points p? and p11. We construct i??' (j =0,1)
by replacing p'? with )9?' E Ap'j such that g?+?p'?' E e'?+1 --H ?A This is possible by the
properties of the chain (1). If necessary, we also adjust the other points (keeping
their projections the same),so that no two are mapped to the same line of A by g?+1.
Now setting P41 = gi+?i?? , we have two point sets differing only by points that lie
on e?+1 and ei+i.
We observe the following facts:
o+ AP?? = AP1?'1, so f(Ai?) = f(APj?')
o+ P41 = gi+?P?", so f(AP4'1) =
Thus by transitivity, f(L0) --H f(AP0) and f(L1) --H f(Ai?). But ?? and i? differ
only by points on ? and 41, which are the same jine of A. Thus, APk0 = Ai?, so
= f(APk1) and f(L0) = f(L1). The result now follows from Lemma 1.1
8
Lemma 6 Let 9 E G, t0,4,e0,,e'1 E A. Assume that e0 N 4, 9(?0 --H ?A) intersects
4' --H ?A, and g(4 --H ?A) intersects `i --H ?A Then 4, N
Proof. Since ?? N 4, there is a chain between them of the form in (1). Applying
g?i to 4' and `? yields a chain from 4' to t1. I
Thus, we can view G as acting on F: if x E f', and t E x such that 9(e --H
intersects e' --H ?A, then 9x is equal to ?(e'). Lemma 6 shows that this is well-defined.
Moreover, it is easily verified that for g,h E G and x E F, g(hx) = (9h)x. We can
extend this group action to Fn, thereby obtaining the main "structure theorem" of
this section.
We will say that a function g refines a function f if for all sets on which g is
constant, f is also constant. We will say that g strictly refines f if 9 refines f and
for some x, y, f(x) = f(y) but g(x) $ 9(y). Call f E IA(G) maximal if there is no
9 E IA(G) that strictly refines it. Then we have
Theorem 7 Let f be a maximal invariant in A(G). Then the cardinality of the
range off is equal to the cardinality of the set of orbits of Fn with respect to G.
Proof. Any function in IA(G) must be constant on all the sets in a single element of
F?, by Lemma 5. Thus, it must be constant on all the sets in a single orbit of Fn.
Now, consider a function f that takes a different value on each orbit of Fn.
Clearly this is possible, since J maps into a set that has cardinality at least as large
as that of the reals. We claim that f is invariant with respect to A and G. if not,
there is some P c DA of cardinality n and 9 E G such that f(AP) $ f(AgP). But
applying 9 to the lines of AP, we get a set of lines that intersect A9P at the points
of 9P c D?; by the definition of an orbit, this means that ?(AP) and ?(AgP)
belong to the same orbit of Fn. Since f is constant on any given orbit, this is a
contradiction.
f is a maximal invariant, since there is clearly no 9 E i\(G) that refines it.
Conversely, every maximal invariant must take a different value on each orbit of l'?,
since otherwise there would exist an invariant strictly refining it. Thus, we have the
stated result. I
We can phrase implications of this result in a number of ways.
Corollary 8 Let G be a group acting on ? and A a projection.
(i) If (G, A) has Property B, then IA(G) is trivial.
(ii) If N partitions A into k equivalence classes, then any function in IA(G) takes
on at most (fl+k?k?ll) values.
9
(iii) If F? has infinitely many orbits with respect to G, then IA(G) contains an
infinite-valued invariant.
Now that we have a clearer picture of what it means for IA(G) to be trivial, we
can try to identify those subgroups of E3 that have only trivial invariants. There is
one more statement we can make about projections in general; after that, we will
turn to the special cases of orthographic and central projection.
Theorem 9 Let A be any projection and G the group of rotations about a point
z E DA. Then IA(G) is triviaL
Proof. We will show that (G, A) has Property B. Let t, t' E A; we consider only the
case in which neither line is Az, as all other cases are easier.
Choose s E e --H ?A and t E ? --H ?A There exists a rotation go such that
gos E Az --H ?A, since there are two points on Az to which s can be rotated and at
most one lies in ?A Consider the set H = I? E G : gs = g0sJ. The set Ht is a
circle; by the definition of a covering set, ?A cannot contain this entire circle. Thus
there exists a rotation g such that gs E Az --H ?A and gt E DA.
Now choose g' such that g'gt E Az --H ?A Thus using g,g' E 0, we have a chain of
the form in (1), with t, Az, Az and ?, Agt, Az constituting the two sides of the chain.
Consider the example in which A is central projection and 0 is the group of all
rotations about the center of projection. This shows that the requirement z E DA
is necessary, since in this example, it is easy to construct non-trivial functions that
are invariant with respect to 0 and A.
4. Orthographic and Central Projection
We now consider groups consisting of a single rotation about an axis; if u is the
axis, we will denote the corresponding rotation group by R?. First we consider the
case of orthographic projection. Denote the orientation of the lines of A by v.
Lemma 10 The group R'L, where u is parallel or perpendicular to ?, has non-trivial,
infinite-value&, invariants.
Proof. If u is parallel to e, then?there are clearly non-trivial invariants (because the
rotation is about the direction of projection). Let us consider the case in which u is
perpendicular to v. If 5 is a 3D point set, then for all 9 E R?, AgS always has the
same projection onto Au. Any non-trivial function based on this projection will be
a non-trivial invariant. I
10
Lemma 11 If u is not parallel or perpendicular to e, then & has only trivial in-
variants.
Proof. As usual, we show that (G, A) has Property B. Let , t E A, and choose any
rotation g such that 9e and 9e' are not vertical. Let 4 and t1 be lines of A that
pass through uand intersect 9e and 9e' respectively. Consider the orbit of 4 with
respect to G --H it is a cone C with axis u and apex 4 fl u, and there is a point at
which t'i intersects C. Thus for some 9' E G, g'C'i intersects 4. Since g'4 intersects
4 (at 4 flu), we have a chain from e to e', with e,4,4 and e',?,9,e'1 as the two
sides. I
These two results can be elegantly summed up in the obvious way:
Theorem 12 R? has non-trivial invariants if and only if u is parallel or perpen-
dicular to v.
Now we turn to central projection. First of all, we observe that if u is a line
through the center of projection, then it is easy to construct non-trivial, infinite-
valued functions invariant with respect to Ru and A. As it turns out, rotations about
any other line result in invariants that are only finite-valued.
Theorem 13 If u does not pass through the center of projection, then the greatest
number of values taken on by a function in IA(Ru) is n + 1.
Proof. Let P be the plane through the center of projection and normal to u. We
note the following three facts.
1. IfeC P, t ? ?, then  and t are not related by N
2. fft,'CP,then??t'.
3. ll?e,??,then??Cffi
These three facts can be verified by arguments very similar to those above. Thus,
partitions DA into 2 equivalence classes, so by Corollary 8, any non-trivial invariant
of & takes on at most n +1 values. Such an invariant exists --H consider the function
that counts the number of lines lying in P.1
We now turn to two applications of the model we have developed here.
11
5. The Overhead Viewing Problem
Consider the following practical problem. We have an overhead camera viewing a
tabletop below, and each object sitting on the table has some small (fixed) number of
stable resting positions. We represent each object as a collection of models, one for
each such stable position. Thus, if we picture the z-axis normal to the workspace, a
given model is essentially free to undergo translation in x?and y, and rotation about
z, the viewing direction. We would like to know whether invariants are useful for
recognizing what is sitting on the table.
Let us consider the two main models of projection --H orthographic and central
--H in turn. For the case of orthographic projection, and a point set P c ? under
these conditions, G and A have a nice commutativity property: if G' is the group
of all rigid motions in x and y, then there is an obvious isomorphism y between
G and G', and we observe that AgP = ?(g)AP. That is, to the overhead camera,
P might as well be a twodimensional point set that is free to undergo full rigid
motion. Hence any classical invariant f of twodimensional point sets with respect
to rigid motion will be a non-trivial invariant with respect to G and A.
Thus in this application, we would simply need to create a separate twodimensional
point set for each stable position of P, and label P with the corresponding finite
set of values of f. Hence, despite the depressing overtones of the preceding sections,
invariants are well-suited to certain practical problems.
The results for central projection, however, are much bleaker. We observed in
Section 4 that there are non-trivial invariants here with respect to rotation about a
line of A; but the addition of translation changes everything, in view of the following
result.
Lemma 14 If A is central projection and G is translation in x and y (no rotation!),
then any function invariant with respect to G and A takes on at most n + 1 values.
Proof. Let P be the plane through the center of projection and perpendicular to e
(the viewing direction). Very much as in the proof of Theorem 13, we have three
important facts.
1. IfC P,t' ? P, then ? and g are not related by N
2. lf?,?'CP,thent?'.
3. lfe,' ? P, then ?Nt'.
As before, an (n+1)-valued invariant would be one that counted the number of lines
in P.1
A final note is that in practice an overhead camera is usually reasonably high
above the workspace, and thus is taking pictures essentially by orthographic projec-
tion. Thus it appears that invariants are very much of use in such a situation.
12
6. Segments and Frameworks
It is somewhat surprising that the model developed so far can be extended, with
almost no effort, to prove that there are no non-trivial invariants of a much broader
class of thr?dimensional objects. Specifically, we consider the case in which an
object is composed of a set of points and line segments rather than simply a set of
points. In effect, we now have a set of n points in which certain pairs of points are
"connected" by a line segment. This is a graph on n vertices, in which each vertex
is labeled by its position in 3-space. Let us fix an n-vertex graph ? = (V, E), and
define a framework F on g to be a set of n distinct labels on the vertices. Thus a
framework is the geometric realization of a graph in ?.
Let R(?) be the set of all frameworks on g. Using this notation, we can represent
the projection of a framework F by simply changing the J?bel Pv on each vertex v to
APv. This will be denoted by AF, and the set of all such AF by AR(?). Our functions
now operate on projections of frameworks, but the definition of invariance remains
the same. Observe, however, the new two- and three-dimensional conditions on our
objects.
o+ The three-dimensional condition: F is a framework on ?, and none of its
points lie in ?A
o+ The two?dimensional condition: No two points of F are mapped to the same
linebyA.
Given F, F' E R(g), we will say that AF and AF' differ by a single vertex if the
labels on their vertices differ by only a single element. As before, we say that a
function f on AR(?) has Property A if f(AF) = f(AF') for all AF, AF' differing by
a single vertex. We observe that Lemma 1 still holds under these definitions.
Now let us consider a function f that is invariant with respect to some G and
A. R?all that AF and AF' are simply the set of n labels on the vertices. Then the
proof of Lemma 5, carries over with no modification t6 show that if AF and AF'
belong to the same equivalence class of An under N, then then for j = 0, 1 we have
a sequence of frameworks F0?', F1?, ....... , Fk'?l', Fk1 such?that
o+ AF1? --H
o+ For some g E G, gi?' = F41.
o+ AF?k=AF?.
Since f is invariant with respect to G and A, f takes on the same value for each
consecutive pair in these sequences, so by transitivity, f(AF) = f(AF'). In the case
in which (G, A) has Property B, we conclude that f has Property A and is trivial.
We therefore have
13
Theorem 15 If(G, A) has Property B and f is a ftnction on AR(?) that is invari-
ant tuith respect to G and A, then f is triviaL
This can be restated in a somewhat looser but more descriptive way.
Corollary 16 If (G, A) has Property B, then the only invariant of a framework with
respect to G and A is its topology as a graph.
This very general theorem includes our results on point sets as a special case,
and it also shows that if (0, A) has Property B, there are no invariants on arbitrary
sets of n segments, n triangles, n tetrahedra, and so on.
7. Summary and Conclusions
We have provided an algebraic characterization of groups and projections for which
there are non-trivial invariants, and discovered that for most commonly considered
cases, there are in fact no non-trivial invariants. Our proofs do not rely on degen-
eracies based on the viewing direction, and thus hold even under the assumption
that functions on images can recognize multiple or occluded points. Moreover, the
proof technique is sufficiently general to show that the ?ame algebraic characteri-
zation holds for invariants of both point sets and wire-frame models. Nevertheless,
there are still cases involving projection in which invariants are useful in object
recognition. The most notable is the overhead viewing problem under orthographic
projection, considered in Section 5.
The challenge now appears to be coming up with reasonable sets of conditions
under which there are non-trivial invariants under projection. For example, what
if we were guaranteed that all the three-dimensional models we were viewing were
drawn from some restricted class? In effect, we would be strengthening the "three-
dimensional conditions" mentioned above, so that the techniques used in our non-
existence proofs --H construction of arbitrary realizations would no longer apply.
We know in fact that there are invariants under projection of sets of points known
to be coplanar: these are precisely the affine invariants. It is also the case that there
are invariants of point sets with reflective symmetry about a plane in ?? [5]. It seems
that a promising idea would be to look for more general classes of three-dimensional
objects for which invariant-based techniques are still of use.
Acknowledgements
The authors would like to thank Paul Chew, John Dalbec, Robert Kleinberg, Paul
Pedersen, Bernd Sturmfels, and Peter Wayner for helpful discussions and comments
on the topic of this paper.
14
References
[1] J. Burns, R. Weiss, and E. Riseman (1991) "View variation of point set and line
segment features" DARPA-ESPRIT Workshop on Invabants in Computer Vision,
Iceland.
[2] D.T. Clemens, and D.W. Jacobs (1991) "Indexing and Object Recognition",
IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(10), pp.
1007--H1017.
[3j D. Forsyth, J.L. Mundy, A. Zisserman, C. Coelho, A. Heller and C. Rothwell
(1991) "Invariant descriptors for 3-D object recognition and pose determination",
JEFF Transactions on Pattern Analysis and Machine Intelligence, 13(10), pp.
971-991.
[4] F. Klein (1939) Elementary Mathematics from an Advanced Standpoint: Geom-
etry, MacMillan, New York.
[5] Y. Moses and 5. Ullman (1992) "Limitations of Non Model-Based Recogni-
tion Schemes", Proceedings of the Second European Computer Vision Conference,
LNCS vol. 488, pp. 820--H828, Springer-Verlag, Berlin.
t6J L. VanGool, P. Kempenaers, and A. Oosterlinck (1991) "Recognition and semi-
differential invariants", Proceedings of the JEFF Confrrence on Computer Vision
and Pattern Recognition, pp. 454--H460.
[7] P. Wayner (1991) "Efficiently Using Invariant Theor? for Model-based Match-
ing", Proceedings of the JEFF Conference on Computer Vision and Pattern Recog-
nition, pp. 473--H478.
[8] I. Weiss (1989) "Projective. Invariants of Shapes" Proceedings of the DARPA
Image Understanding Workshop, pp. 1125--H1134.
15
