Minimal Decomposition of Model-Based Invariants.
Model-based invariants are relations between model parameters and image measurements, which are independent of the imaging parameters. Such relations are true for all images of the model. Here we describe an algorithm which, given L independent model-based polynomial invariants describing some shape, will provide a linear re-parameterization of the invariants. This re-parameterization has the properties that: (i) it includes the minimal number of terms, and (ii) the shape terms are the same in all the model-based invariants. This final representation has 2 main applications: (1) it gives new representations of shape in terms of hyperplanes, which are convenient for object recognition&semi; (2) it allows the design of new linear shape from motion algorithms. In addition, we use this representation to identify object classes that have universal invariants.
Introduction
An image provides us with relations between 3 different
kind of parameters: image measurements,
shape parameters, and imaging parameters (e.g.,
camera parameters). Here we restrict ourselves to
the domain of multiple points in multiple frames,
where the image measurements are 2D point co-
ordinates, and the shape parameters are 3D point
coordinates. There has been much interest in relations
involving only image measurements and
imaging parameters (e.g., the epipolar geometry
and the essential matrix [8]). In this paper
we are interested in the dual relations involving
only shape measurements and imaging parame-
ters, which are called model-based invariants.
The analysis of invariants arose much interest
in computer vision and pattern recognition. As
we use the concept here, an invariant is a relation
between the image measurements and the model
(or shape) parameters. This relation does not depend
on variables of the imaging process, such as
the camera orientation (viewing position). There
are 2 types of invariants:
Model-free invariant: there exist image measurements
which always identify the object,
so that their value is completely determined
by the object regardless of the details of the
imaging process. This is usually called an invariant
in the literature. Such invariant relations
do not exist for 2D images of general
3D objects [1, 10]; for special classes of ob-
76 D. Weinshall
jects, such as planar or symmetrical objects,
invariant relations may be found [10, 12].
Model-based invariant: a relation which includes
mixed terms, representing image measurements
or model parameters. Model-based
invariant relations exist for many interesting
cases [16].
Typically, model-based invariants are complex
polynomial relations between the known image
measurements and the unknown shape parame-
ters. In the external calibration literature, where
the dual relations between camera parameters and
image measurements are ordinarily used, it proved
very useful to re-parameterize the original relations
in a linear form; this turned the computation
of camera parameters into a linear problem. Obviously
the problem is linear in some new variables,
that could be complex functions of the original
camera parameters. Examples are the epipolar
geometry with the essential matrix [8] or the fundamental
bilinear matrix [9], the trilinear tensor
[14, 5], and the quadrilinear tensor [15, 18, 4].
In the context of model-based invariants, this
lead us to the following questions:
Given a model-based invariant, how do we
nd its \optimal" (or most compact) linear
re-parameterization? in other words, how do
we rewrite it with the minimal number of
terms, that truly re
ect the number of degrees
of freedom of the system? Given L
model-based invariants, what is the simultaneous
minimal linear decomposition of these
relations?
By simultaneous we specically mean that the
shape terms are the same in all relations. The
reason we seek such simultaneous decomposition
of model-based invariants is that when the shape
terms are the same, all relations can be used simultaneously
in applications such as direct shape
reconstruction.
Our attempt to answer these questions was motivated
by two applications: one is object recog-
nition, the other is 3D reconstruction:
If shape is reconstructed from images for the
sole purpose of recognition, the parametric
representation of the shape in the model-based
invariants captures all the relevant information
on the shape. Our algorithm produces
a set of L linear relations with a minimal
number of terms (these are the equation's un-
knowns), say n. We would now need at least
e frames to compute shape. This automatically
gives us new linear shape reconstruction
algorithms, which are likely to be more robust
than other linear algorithms. Often the shape
(or depth) can be computed directly from the
reconstructed models, as will be shown in the
examples below.
Clearly, for the initial indexing step in object
recognition, model-based invariants are most
suitable (imaging parameters may be computed
and used later during the verication
step). More specically, a model-based invariant
represents a relation between image
measurements and shape parameters that is
true in all images of the model. The database
which includes these models may be thought
of as a big multi-dimensional table, where an
object corresponds to the manifold dened by
its model-based invariant, and individual images
are points on (or pointers into) these
manifolds. In such a framework indexing is
quick (but the representation is very space in-
e-cient).
Our algorithm provides an automatic tool
to compute low dimensional linear representations
of the model-based invariants; when
used, these representations simplify the complexity
of the recognition process by reducing
the indexing complexity. In other words,
the representation of objects is made simpler
because simple manifolds - hyperplanes -
are stored; recognition is made easier because
an image provides a pointer - a point which
should lie on the hyperplane representing the
object depicted in the image.
One other application motivated our work:
model-based invariants have a special meaning
when the number of linear terms is no larger
than 2. In this case it is possible to separate the
shape dependency from the dependency on image
measurements, and get a model-free invariant - a
\true" invariant. Such invariant relations do not
normally exist [1, 10] unless the class of objects is
restricted [10, 12]. Our theory allows us to iden-
Minimal decomposition of model-based invariants 77
tify the kind of class constraints that can be used
to reduce the number of linear terms, so that a
model-based invariant becomes a model-free invariant

In this paper we assume that a set of L model-based
invariants, which describe the images of
some set of objects, is initially given. In Section
3 we describe an algorithm which produces a
linear re-parameterization of the invariants, with
minimal number of terms. In Section 4 we generalize
this algorithm to produces a linear re-parameterization
of the L invariants simultane-
ously, such that at the end the shape terms are
the same in all the re-parameterized model-based
invariants.
Jacobs [3, 6] studied the complexity of invariants
and model-based invariants in their raw form.
In [6] he showed that for 6 points in a single perspective
image, there exists a nonlinear model-based
invariant with 5 unknowns. We obtained a
linear re-parameterization with 5 terms, thus the
linear representation is no more complex than the
nonlinear one in this example. In ECCV '96 [19]
we reported a follow up of the basic technique described
in Section 3: we united two approaches,
the elimination discussed in [18] and the linear re-parameterization
of one relation described in Section
3, to accomplish an automatic process that
optimizes indexing given a general vision problem.
2. Model-based invariants for n projective
points in 1 image
To demonstrate the procedures described in Sections
3,4 we will work out 2 examples in detail,
where the model is of 6 or 7 points and the projection
model is perspective. We start by using
homogeneous coordinates to represent the 3D co-ordinates
of the points; thus the representation
of the i-th point is
Since we are working in P 3 , 5 points dene a ba-
sis; we select the rst 5 points to be a certain
projective basis, leading to the following
representation of the 3D shape of the points:
Similarly we use homogeneous coordinates to
represent the projected 2D coordinates of the
points; thus the representation of the i-th image
point is Since we are working
in P 2 , 4 points dene a basis; we select the
rst 4 points to be the projective basis, leading
to the following representation of the image of the
points:
c 2A
Given any image of the points, we can always compute
the 2D projective transformation which will
transform the points to the representation given
above.
In [2] we showed how to compute model-based
invariants in such cases. In this section we review
these relations for the special cases of 6 projective
points and 7 projective points. Note that the
model-based invariants listed below have many
terms. Clearly these expressions are of little value
for linear reconstruction and indexing unless we
can re-parameterize them in a \simpler" way.
2.1. Model-based invariants for 6 projective
points
The model-based invariants in this case are obtained
from the observation that the following matrix
has rank 3 [2, 4], and thus its determinant
should be 0:6 6 6 6 6 4
This gives the following constraint (see derivation
in [2, 17], cf. with [11]):
78 D. Weinshall
a
a
a
2.2. Model-based invariants for 7 projective
points
The model-based invariants in this case are obtained
from the observation that the following matrix
has rank 3 [2, 4], and thus each of its 15 4  4
minors should vanish:6 6 6 6 6 6 6 6 6 6 6 4
In [2] we show that there are only 4 algebraic
independent constraints which involve all 7 projective
points, one of them is the following (the
other 3 look similar):
a 1 a
a
3. Minimal linear invariant: one relation
Let S denote the set of parameters describing the
object shape. Let D denote the data - a set
of image measurements. Let I = ff l (S;
0g L
l=1 denote the set of independent model-based
invariants; we assume that each model-based invariant
is polynomial.
We start with the simple case where I includes a
single We seek a decomposition
of f() in the following compact way, explicitly
separating image variables D from shape
variables S:
r
k and h k are polynomial functions of the shape
S and the image D respectively. We call (1) the
canonical representation of f(S; D). Note that if
f(S; D) is algebraic, as we assume here, such a
decomposition always exists.
In the simplest case where would
become:
Thus if 2, the model-based invariant
is really a model-free (a \true") invariant.
3.1. Algorithm
The algebraic expression f(S;
be written as a sum of multiplications since f() is
polynomial; we start by arbitrarily choosing one
Minimal decomposition of model-based invariants 79
such representation for f(S; D):
are constants, s i and d j are distinct
products of element of S and D respectively,
and Q is the n m
matrix whose elements are q ij .
Denition 1. Q is the complexity-matrix of
the relation f(S;
Theorem 1. The minimal linear decomposition
r
k (S)  h k (D) has r terms,
where r is equal to the rank of the complexity-
matrix Q.
Proof: The theorem follows from (2), the
fact that elementary operations on the rows and
columns of a matrix are algebraic operations, and
because the rank of a matrix is the minimal number
of outer products of vectors that sum to the
matrix. Note, however, that this representation
obtains the minimal number of terms in a limited
context, where a term can only be a linear combination
of s i 's or d j 's.
Algorithm to compute the minimal linear
model-based invariant:
1. Compute the SVD (or similar) decomposition
of the rank of Q is equal to the
number of non-0 elements in the diagonal matrix
.
2. By construction
r
where
Although the rank of Q is unique, the decomposition
above is not; other expressions can all
be derived using the same SVD decomposition.
For example, we can decompose the complexity
matrix Q as
where H denotes any regular r  r matrix. Now
and h 0
H . Thus there are essentially
independent decompositions
of type (1).
3.2. Example: 6 projective points
We use the notations of Section 2 and the deni-
tions above, where:
denotes the set of 4 shape variables X 1 , Y 1 ,
the 3D projective coordinates of the
6th point.
D denotes the set of 6 image variables a 0 , b 0 ,
these are the image measurements
- the projective image coordinates of
the points.
In this case we get the following model-based
invariant (see Section 2.1):
a 0 a 1 Z 1
In order to represent f(S; D) as a sum of multiplications
as required in (2), we observe the following

1. There are 10 shape monomials s i , thus
and
2. There are 9 image monomials d j , thus
and
D. Weinshall
3. The complexity matrix Q is 10  9, where
Q[i; j] is the coe-cient of s i d j in the expression
above. For example, from the rst term
in the expression above Q[6;
We use Gaussian elimination to decompose Q
as
Many matrices U satisfy these conditions, and we
choose a relatively \simple" one:
Since the rank of Q is 5, we can rewrite the
model-based invariant f(S; D) as follows:
where (3), (5) give
and (4), (5) give
4. Minimal linear invariant: multiple relation

Let S, D and I = ff l (S;
l=1 as in Section
3. We now consider the general case where I
includes L > 1 relations. We look for a simultaneous
decomposition of the L relations, such that
they have a minimal number of terms, and the
shape terms are identical in all the relations. More
specically, we look for a simultaneous decomposition

f l (S;
r
where g k and h l
are polynomial functions of the
shape S and the image D respectively. Note that
k (S), the shape terms, do not depend on the index
l - this is what we mean by simultaneous decomposition
of the L relations.
4.1. Algorithm
We start by writing each algebraic expression
f l (S; as a sum of multiplications:
f l (S; D)
q l
where s i and d j are distinct products of element
of S and D respectively,
l is the nm matrix whose elements
are q l
ij . From Def. 1, Q l is the complexity-
matrix of the relation f l (S;
Minimal decomposition of model-based invariants 81
Denition 2. Q, the matrix obtained by concatenating
the L matrices Q l from left to right, is
the joint complexity-matrix of I.
Note that the size of Q is nLm. Note also the
asymmetrical role of rows and columns here: the
row variables are shape variables, and thus should
be the same for all invariants; the column variables
are data variables, and thus can (and should) vary
for dierent invariants.
Theorem 2. The minimal simultaneous linear
decomposition f l (S;
r
k (S)  h k (D) has
r terms, where r is equal to the rank of the joint
complexity-matrix Q.
The proof is similar to the proof of theorem 1,
with the same restriction: the number of terms is
minimal in a limited context, where a term can
only be a linear combination of s i 's or d j 's.
We can now derive the following algorithm to
compute the minimal simultaneous linear decomposition
of model-based invariants:
1. Compute the SVD (or similar) decomposition
of the joint complexity matrix
2. For each invariant, nd a decomposition Q
below we specically use (V l
denotes the pseudo-inverse
of (U).
3. By construction
f l (S;
r
where
4.2. Example: 7 projective points
We use the notations of Section 2 and the deni-
tions of Section 3, where:
denotes the set of 8 shape variables X 1 , Y 1 ,
the 3D projective
coordinates of the 6th and 7th points.
D denotes the set of 9 image variables a 0 , b 0 ,
these are the image
measurements - the projective image coordinates
of the points.
In this case we have 4 independent model-based
invariants (see derivation in Section 2.2); one is
given below, the other 3 look similar and are therefore
omitted.
a
a
a
a
a
In order to represent D) as a sum of multiplications
as in (2), we observe the following:
1. There are 16 shape monomials s i , thus
and
2. There are 27 image monomials d j , thus
a
D. Weinshall
3. The complexity matrix Q 1 is
is the coe-cient of s i d j in the expression
above. example, contains the
coe-cient of a 0 a 1 a 2 X 1 X 2 from the expression
above, which happens to be -1. Thus we get
the following full description of Q
Similarly, we rewrite f 2 (S; D), f 3 (S; D), and
f 4 (S; D), to construct Q 2 , Q 3 and Q 4 in a similar
way. The joint complexity matrix Q is constructed
by concatenating its size is
The rank of Q is computed to be 11. Using
Gaussian elimination, we compute a decomposition
108  11. Many matrices U satisfy these condi-
tions, and we choose the following relatively \sim-
ple" one:
U is used to obtain the individual decompositions

Finally, we rewrite the model-based invariants
f l (S; D), l = 1::4. For example, take f 1 (S; D):
where
and (10), (11), (12) give
a 2 a
a 2 a
Minimal decomposition of model-based invariants 83
a 2 a
5. Adding class constraints
Once it has been shown that model-free invariants
do not exist for unconstrained objects [1, 10],
attention had turned to characterizing the constraints
(or classes of objects) which would lead to
model-free invariants [10, 12]. The present analysis
allows us to ask this question as part of a more
general problem: what class constraints on objects
reduce the number of terms in the minimal linear
decomposition? In this section we determine sucient
conditions on class constraints to reduce the
number of terms, in particular to reduce it to 2
(implying the existence of model-free invariants).
We start from a relation
r
are polynomial functions
of the shape and image measurements respec-
tively. Every class constraint of the form
0, where (S) divides some
reduces
the number of terms in the minimal decomposition
by at least 1. Thus:
Theorem 3. (class constraints:) To reduce
the minimal number of terms from r to p < r, the
class constraints should provide at most (r p)
independent constraints of the form  i
where each  i (S) divides some
modulo the
Clearly there is a tradeo between complexity
(the number of terms), which is higher for
more general (and less constrained) classes, and
the density of the database, which is smaller for
more general classes (as there are fewer types of
such general objects).
Example: given 6 points and a perspective
From the minimal model-based invariant developed
in Section 3.2, and the theorem above,
it immediately follows that if any of the parameters
of the 6th point,
parameters of
the 6th point are equal, then 3. Thus if
4 of the 6 points are coplanar, the number of
terms in the minimal model-based invariant is
3.
If 2 pairs of the 4 parameters
are equal then namely, there is a model-free
invariant. The geometry of this case is as
follows: one point lies on the line of intersection
of 2 of the planes, each spanned by
triplets of the remaining 5 points.
6. Reconstruction example: lab sequence
We use a real sequence of images from the 1991
motion workshop, which includes 16 images of a
robotic laboratory obtained by rotating a robot
arm 120 (one frame is shown in Fig. 1).
like points were tracked. The depth values of the
points in the rst frame ranged from 13 to 33 feet;
moreover, a wide-lens camera was used, causing
distortions at the periphery which were not compensated
for. (See a more detailed description in
[13] Fig. 4, or [7] Fig. 3.)
We compute the shape of the tracked points as
follows. We rst choose an arbitrary basis of 5
points; for each additional point we:
1. compute g(S) as dene in (7), using all the
available frames to solve an over-determined
linear system of equations, where each frame
provides the constraint given in (6).
2. compute the homogeneous coordinates of the
6th point [ ~
W ] from g(S) using
~
~
~
3. in order to compare the results with the real
3D shape of the points, we multiply the projective
homogeneous coordinates by the actual
84 D. Weinshall
9 101214161820
Fig. 1. One frame from the lab sequence.
3D coordinates of the projective basis points,
to obtain the equivalent Euclidean representation

The real 3D coordinates of about half the points
in the sequence, and the corresponding reconstructed
3D coordinates, are the following:
real shape:6 6 4
0:3 1:7 0:3 1:8 5:3 9:9 3:2
4 2:6 4:4 6:3 4:2 1:6 2:8
2:3 1:5 0:6 0:5 1:5 0:5
reconstructed shape:6 6 4
0:3 1:8 0:6 0:9 3:8 8:9 0:8
3:6 1:3 5 6:2 4:4 1:5 0:7
2:4 0:7 0:6 0:3 1:3 0:4
1:3 4:8 2:6 1:8 0:4 0:7
The median relative error, where the relative
error is the error at each point divided by the
distance of the point from the origin, is 12%.
7.

Summary

We described an automatic process to simplify
model-based invariants by re-parameterizing them
in a linear way, and with a minimal number of
terms. We demonstrated this process on 2 ex-
amples, using model-based invariants of 6 and 7
points under perspective projection. Thus, for ex-
ample, we obtained 4 homogeneous linear equations
with 11 unknowns using the invariants of 7
points. We can use these invariants to compute
the shape of the 7 points with a linear algorithm,
using at least 3 frames and least squares optimization
(since the data is redundant).

Acknowledgements

This research was supported by the Israeli Ministry
of Science under Grant 032.7568. Vision
research at the Hebrew University is supported
by the U.S. O-ce of Naval Research under Grant
N00014-93-1-1202, R&T Project Code 4424341|
01.



--R

View variation of point-set and line segment features
Duality of reconstruction and positioning from projective views.
Space and time bounds on indexing 3-D models from 2-D images
On the geometry and algebra of the point and line correspondences between N images.
Lines and points in three views - an integrated approach

Matching 3-D models to 2-D images
Sensitivity of the pose re
A computer algorithm for reconstructing a scene from two projections.
The fundamental ma- trix: theory
Limitations of non model-based recognition schemes
Invariants of 6 points from 3 uncalibrated images.
Extracting projective structure from single perspective views of 3d point sets.
Description and reconstruction from image trajectories of rotational motion.
Trilinearity in visual recognition by align- ment
The geometry of projective reconstruction I: matching constraints and the joint image.

Shape tensors for e-cient and learnable indexing
Elimination: An approach to the study of 3D-from-2D
Complexity of index- ing: E-cient and learnable large database indexing
--TR

--CTR
Vincenzo Caglioti, Minimal Representations of 3D Models in Terms of Image Parameters under Calibrated and Uncalibrated Perspective, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.9, p.1234-1238, September 2004
model-based invariants;universal invariants;projective reconstruction