Algebraic Functions For Recognition.
AbstractIn the general case, a trilinear relationship between three perspective views is shown to exist. The trilinearity result is shown to be of much practical use in visual recognition by alignmentyielding a direct reprojection method that cuts through the computations of camera transformation, scene structure and epipolar geometry. Moreover, the direct method is linear and sets a new lower theoretical bound on the minimal number of points that are required for a linear solution for the task of reprojection. The proof of the central result may be of further interest as it demonstrates certain regularities across homographies of the plane and introduces new view invariants. Experiments on simulated and real image data were conducted, including a comparative analysis with epipolar intersection and the linear combination methods, with results indicating a greater degree of robustness in practice and a higher level of performance in reprojection tasks.
Introduction
We establish a general result about algebraic connections
across three perspective views of a 3D scene and demonstrate
its application to visual recognition via alignment.
We show that, in general, any three perspective views of a
scene satisfy a pair of trilinear functions of image coordi-
nates. In the limiting case, when all three views are ortho-
graphic, these functions become linear and reduce to the
form discovered by [38]. Using the trilinear result one can
manipulate views of an object (such as generate novel views
from two model views) without recovering scene structure
(metric or non-metric), camera transformation, or even the
geometry. Moreover, the trilinear functions can be
recovered by linear methods with a minimal configuration
of seven points. The latter is shown to be new lower bound
on the minimal configuration that is required for a general
linear solution to the problem of re-projecting a 3D scene
onto an arbitrary novel view given corresponding points
across two reference views. Previous solutions rely on recovering
the epipolar geometry which, in turn, requires a
minimal configuration of eight points for a linear solution.
The central results in this paper are contained in Theorems
3. The first theorem states that the variety
of views / of a fixed 3D object obtained by an un-calibrated
pin-hole camera satisfy a relation of the sort
are two arbitrary views of
the object, and F has a special trilinear form. The coefficients
of F can be recovered linearly without establishing
first the epipolar geometry, 3D structure of the object, or
A. Shashua is with the Artificial Intelligence Laboratory and the Center
for Biological Computational Learning, Massachusetts Institute of Tech-
nology, Cambridge, MA 02139.
camera motion. The auxiliary Lemmas required for the
proof of Theorem 1 may be of interest on their own as
they establish certain regularities across projective transformations
of the plane and introduce new view invariants
(Lemma 4).
Theorem 2 addresses the problem of recovering the co-efficients
of the trilinear functions in the most economical
way. It is shown that among all possible trilinear functions
across three views, there exists at most four linearly
independent such functions. As a consequence, the coefficients
of these functions can be recovered linearly from
seven corresponding points across three views.
Theorem 3 is an obvious corollary of Theorem 1 but contains
a significant practical aspect. It is shown that if the
views are obtained by parallel projection, then F
reduces to a special bilinear form - or, equivalently, that
any perspective view / can be obtained by a rational linear
function of two orthographic views. The reduction to a
bilinear form implies that simpler recognition schemes are
possible if the two reference views (model views) stored in
memory are orthographic.
These results may have several applications (discussed in
Section VI), but the one emphasized throughout this paper
is for the task of recognition of 3D objects via alignment.
The alignment approach for recognition ([37, 16], and references
therein) is based on the result that the equivalence
class of views of an object (ignoring self occlusions) undergoing
3D rigid, affine or projective transformations can be
captured by storing a 3D model of the object, or simply
by storing at least two arbitrary "model" views of the object
- assuming that the correspondence problem between
the model views can somehow be solved (cf. [27, 5, 33]).
During recognition a small number of corresponding points
between the novel input view and the model views of a
particular candidate object are sufficient to "re-project"
the model onto the novel viewing position. Recognition is
achieved if the re-projected image is successfully matched
against the input image. We refer to the problem of predicting
a novel view from a set of model views using a
limited number of corresponding points, as the problem of
re-projection.
The problem of re-projection can in principal be dealt
with via 3D reconstruction of shape and camera mo-
tion. This includes classical structure from motion methods
for recovering rigid camera motion parameters and
metric shape [36, 18, 35, 14, 15], and more recent methods
for recovering non-metric structure, i.e., assuming
the objects undergo 3D affine or projective transforma-
tions, or equivalently, that the cameras are uncalibrated
[17, 25, 39, 10, 13, 30]. The classic approaches for perspective
views are known to be unstable under errors in image
measurements, narrow field of view, and internal camera
calibration [3, 9, 12], and therefore, are unlikely to be of
practical use for purposes of re-projection. The non-metric
approaches, as a general concept, have not been fully tested
on real images, but the methods proposed so far rely on recovering
first the epipolar geometry - a process that is also
known to be unstable in the presence of noise.
It is also known that the epipolar geometry alone is sufficient
to achieve re-projection by means of intersecting
lines [24, 6, 8, 26, 23, 11] using at least eight corresponding
points across the three views. This, however,
is possible only if the centers of the three cameras are non-collinear
- which can lead to numerical instability unless
the centers are far from collinear - and any object point
on the tri-focal plane cannot be re-projected as well. Fur-
thermore, as with the non-metric reconstruction methods,
obtaining the epipolar geometry is at best a sensitive process
even when dozens of corresponding points are used
and with the state of the art methods (see Section V for
more details and comparative analysis with simulated and
real images).
For purposes of stability, therefore, it is worthwhile exploring
more direct tools for achieving re-projection. For
instance, instead of reconstruction of shape and invariants
we would like to establish a direct connection between
views expressed as a functions of image coordinates alone
- which we call "algebraic functions of views". Such a result
was established in the orthographic case by [38]. There
it was shown that any three orthographic views of an object
satisfy a linear function of the corresponding image coordinates
- this we will show here is simply a limiting case
of larger set of algebraic functions, that in general have a
trilinear form. With these functions one can manipulate
views of an object, such as create new views, without the
need to recover shape or camera geometry as an intermediate
step - all what is needed is to appropriately combine
the image coordinates of two reference views. Also, with
these functions, the epipolar geometries are intertwined,
leading not only to absence of singularities, and a lower
bound on the minimal configuration of points, but as we
shall see in the experimental section to more accurate performance
in the presence of errors in image measurements.
Part of this work (Theorem 1 only) was presented in concise
form in [31].
II. Notations
We consider object space to be the three-dimensional
projective space P 3 , and image space to be the two-dimensional
projective space P 2 . Let \Phi ae P 3 be a set
of points standing for a 3D object, and let /
views (arbitrary), indexed by i, of \Phi. Given two cameras
with centers located at O; O respectively, the
epipoles are defined to be at the intersection of the line OO 0
with both image planes. Because the image plane is finite,
we can assign, without loss of generality, the value 1 as
the third homogeneous coordinate to every observed image
point. That is, if (x; y) are the observed image coordinates
of some point (with respect to some arbitrary origin -
say the geometric center of the image), then
denotes the homogeneous coordinates of the image plane.
Note that this convention ignores special views in which a
point in \Phi is at infinity in those views - these singular
cases are not modeled here.
Since we will be working with at most three views at
a time, we denote the relevant epipoles as follows: let
be the corresponding epipoles between
views
the corresponding
epipoles between views corresponding
image points across three views will be denoted by
1). The term
"image coordinates" will denote the non-homogeneous co-ordinate
representation of P 2 , e.g., (x; y);
for the three corresponding points.
Planes will be denoted by - i , indexed by i, and just -
if only one plane is discussed. All planes are assumed to
be arbitrary and distinct from one another. The
denotes equality up to a scale, GLn stands for the group
of n \Theta n matrices, and PGLn is the group defined up to a
scale.
III. The Trilinear Form
The central results of this paper are presented in the
following two theorems. The remaining of the section is
devoted to the proof of this result and its implications.
Theorem 1 (Trilinearity) Let arbitrary
perspective views of some object, modeled by a set of
points in 3D. The image coordinates (x;
of three corresponding points across
three views satisfy a pair of trilinear equations of the following
and
where the coefficients ff j , fi j , are fixed for
all points, are uniquely defined up to an overall scale, and
The following auxiliary propositions are used as part of the
proof.
the projective mapping (homography) / 1 7! / 2 due to some
plane -. Let A be scaled to satisfy p 0
are corresponding points coming from
an arbitrary point P corresponding
coming from an arbitrary point
The coefficient k is independent of / 2 , i.e., is invariant to
the choice of the second view.
The lemma, its proof and its theoretical and practical implications
are discussed in detail in [28, 32]. Note that the
particular case where the homography A is affine, and the
is on the line at infinity, corresponds to the construction
of affine structure from two orthographic views
[17]. In a nutshell, a representation R 0 of P 3 (tetrad of
coordinates) can always be chosen such that an arbitrary
plane - is the plane at infinity. Then, a general uncalibrated
camera motion generates representations R which
can be shown to be related to R 0 by an element of the
affine group. Thus, the scalar k is an affine invariant within
a projective framework, and is called a relative affine invariant
. A ratio of two such invariants, each corresponding
to a different reference plane, is a projective invariant [32].
For our purposes, there is no need to discuss the methods
for recovering k - all we need is to use the existence of
a relative affine invariant k associated with some arbitrary
reference plane - which, in turn, gives rise to a homography
A.
due to the same plane -, are said to be scale-compatible
if they are scaled to satisfy Lemma 1, i.e., for any point
projecting onto there exists a
scalar k that satisfies
for any view / i , where v i 2 / i is the epipole with / 1 (scaled
arbitrarily).
PGL 3 be two homographies of / 1 7! / 2 due to planes
respectively. Then, there exists a scalar s, that satisfies
the equation:
for some coefficients ff; fi; fl.
Proof: Let q 2 / 1 be any point in the first view. There
exists a scalar s q that satisfies v
as shown in [29],
homography / 1 7! / 2 due to any plane.
Therefore, well. The mapping of two distinct
points q; v onto the same point v 0 could happen only if H is
the homography due to the meridian plane (coplanar with
the projection center O), thus Hp
s q is a fixed scalar s. The latter, in turn, implies that H is
a matrix whose columns are multiples of v 0 .
Lemma 3 (Auxiliary for Lemma
Let A; A 0 2 PGL 3 be homographies from / 1 7! / 2 due
to distinct planes - respectively, and
be homographies from / 1 7! / 3 due to -
where Cv - v.
Proof: Let
are homographies
from
are homographies from
A
we have
. Note that the only difference
between A 1 and B 1 is due to the different location of
the epipoles v; - v, which is compensated by C (Cv - v).
3 be the homography from / 1 to - 2 , and
the homography from - 2 to - 1 . Then with
proper scaling of E 1 and E 2 we have
and with proper scaling of C we have,
Lemma 4 (Auxiliary - Uniqueness)
For scale-compatible homographies, the scalars s; ff; fi; fl of
Lemma 2 are invariants indexed by That is,
given an arbitrary third view / 3 , let be the homographies
from / 1 7! / 3 due to -
be scale-compatible with A, and B 0 be scale-compatible with
A 0 . Then,
Proof: We show first that s is invariant, i.e., that
sB 0 is a matrix whose columns are multiples of v 00 . From
Lemma 2, and Lemma 3 there exists a matrix H, whose
columns are multiples of v 0 , a matrix T that satisfies A
AT , and a scalar s such that I \Gamma
multiplying both sides by BC, and then pre-multiplying
by C \Gamma1 we obtain
From Lemma 3, we have . The matrix
A \Gamma1 H has columns which are multiples of v (because
whose columns are multiple
of -
v, and BCA \Gamma1 H is a matrix whose columns are multiples
of v 00 . Pre-multiplying BCA \Gamma1 H by C \Gamma1 does not
change its form because every column of BCA
simply a linear combination of the columns of BCA \Gamma1 H.
As a result, is a matrix whose columns are multiples
of v 00 .
. Since the homographies
are scale compatible, we have from Lemma 1
the existence of invariants k; k 0 associated with an arbitrary
is due to - 1 , and k 0 is due to
Then from Lemma 2 we have
is arbitrary, this could happen
only if the coefficients of the multiples of v 0 in H and
the coefficients of the multiples of v 00 in -
H, coincide.
Proof of Theorem: Lemma 1 provides the existence part
of theorem, as follows. Since Lemma 1 holds for any plane,
choose a plane - 1 and let A; B be the scale-compatible
homographies
for every point corresponding points p 0 2
there exists a scalar k that satisfies: p 0
. We can isolate k from both
equations and obtain:
\Gammay
are the row vectors of A
and B and v
Because of
the invariance of k we can equate terms of (1) with terms
of (2) and obtain trilinear functions of image coordinates
across three views. For example, by equating the first two
terms in each of the equations, we obtain:
3 a 3 )
In a similar fashion, after equating the first term of (1)
with the second term of (2), we obtain:
3 a 3 )
Both equations are of the desired form, with the first six
coefficients identical across both equations.
The question of uniqueness arises because Lemma 1
holds for any plane. If we choose a different plane, say
then we must show that the
new homographies give rise to the same coefficients (up to
an overall scale). The parenthesized terms in (3) and (4)
have the general form: v 0
j a i , for some i and j. Thus,
we need to show that there exists a scalar s that satisfies
(b
This, however, follows directly from Lemmas 2 and 4.
The direct implication of the theorem is that one can
generate a novel view (/ 3 ) by simply combining two model
views The coefficients ff j and fi j of the combination
can be recovered together as a solution of a linear
system of 17 equations corresponding
points across the three views (more than nine points
can be used for a least-squares solution).
In the next theorem we obtain the lower bound on the
number of points required for solving for the coefficients of
the trilinear functions. The existence part of the proof of
Theorem 1 indicates that there exists nine trilinear functions
of that type, with coefficients having the general form
a i . Thus, we have at most 27 distinct coefficients
(up to a uniform scale), and thus, if more than two of
the nine trilinear functions are linearly independent, we
may solve for the coefficients using less than nine points.
The next theorem shows that at most four of the trilinear
functions are linearly independent and consequently seven
points are sufficient to solve for the coefficients.
Theorem 2 There exists nine distinct trilinear forms of
the type described in Theorem 1, of which at most four are
linearly independent. The coefficients of the four trilinear
forms can be recovered linearly with seven corresponding
points across the three views.
Proof: The existence of nine trilinear forms follow directly
from (1) and (2). Let ff
. The nine forms
are given below (the first two are (3) and (4) repeated for
For a given triplet the first four functions on
the list produce a 4 \Theta 27 matrix. The rank of the matrix
is four because it contains four orthogonal columns
(columns associated with ff
these functions are linearly independent. Since we have 27
coefficients, and each triplet contributes four linear
equations, then seven corresponding points across the three
views provide a sufficient number of equations for a linear
solution for the coefficients (given that the system is determined
up to a common scale, seven points produce two
extra equations which can be used for consistency checking
or for obtaining a least squares solution).
The remaining trilinear forms are linearly spanned by
the first four, as follows:
where the numbers in parenthesis represent the equation
numbers of the various trilinear functions.
Taken together, both theorems provide a constructive
means for solving for the positions x 00 ; y 00 in a novel view
given the correspondences across two model views.
This process of generating a novel view can be easily accomplished
without the need to explicitly recover structure,
camera transformation, or even just the epipolar geometry
- and requires fewer corresponding points than any other
known alternative.
The solution for x 00 ; y 00 is unique without constraints on
the allowed camera transformations. There are, however,
certain camera configurations that require a different set of
four trilinear functions from the one suggested in the proof
of Theorem 2. For example, the set of equations (5), (6),(9)
and (10) are also linearly independent. Thus, for example,
in case v 0
3 vanish simultaneously, i.e., v
then that set should be used instead. Similarly, equations
(3), (4),(9) and (10) are linearly independent, and should
be used in case v 0 situations arise with
which can be dealt by
choosing the appropriate basis of four functions from the
six discussed above. Note that we have not addressed the
problem of singular configurations of seven points. For ex-
ample, its clear that if the seven points are coplanar, then
their correspondences across the three views could not possibly
yield a unique solution to the problem of recovering
the coefficients. The matter of singular surfaces has been
studied for the eight-point case necessary for recovering the
epipolar geometry [19, 14, 22]. The same matter concerning
the results presented in this paper is an open problem.
Moving away from the need to recover the epipolar geometry
carries distinct and significant advantages. To get a
better idea of these advantages, we consider briefly the process
of re-projection using epipolar geometry. The epipolar
intersection method can be described succinctly (see
[11]) as follows. Let F 13 and F 23 be the matrices ("funda-
mental" matrices in recent terminology [10]) that satisfy
by incidence of p 00
with its epipolar line, we have:
Therefore, eight corresponding points across the three
views are sufficient for a linear solution of the two fundamental
matrices, and then all other object points can be re-projected
onto the third view. Equation (12) is also a trilinear
form, but not of the type introduced in Theorem 1. The
differences include (i) epipolar intersection requires the correspondences
coming from eight points, rather than seven,
(ii) the position of p 00 is solved by a line intersection process
which is singular in the case the three camera centers are
collinear; in the trilinearity result the components of p 00
are solved separately and the situation of three collinear
cameras is admissible, (iii) the epipolar intersection process
is decomposable, i.e., only two views are used at a
time; whereas the epipolar geometries in the trilinearity
result are intertwined and are not recoverable separately.
The latter implies a better numerically behaved method in
the presence of noise as well, and as will be shown later, the
performance, even using the minimal number of required
points, far exceeds the performance of epipolar intersection
using many more points. In other words, by avoiding the
need to recover the epipolar geometry we obtain a significant
practical advantage as well, since the epipolar geometry
is the most error-sensitive component when working
with perspective views.
The connection between the general result of trilinear
functions of views and the "linear combination of views"
result [38] for orthographic views, can easily be seen by
setting A and B to be affine in P 2 , and v 0
example, (3) reduces to
which is of the form
As in the perspective case, each point contributes four
equations, but here there is no advantage for using all four
of them to recover the coefficients, therefore we may use
only two out of the four equations, and require four corresponding
points to recover the coefficients. Thus, in the
case where all three views are orthographic, x 00 (y 00 ) is expressed
as a linear combination of image coordinates of the
two other views - as discovered by [38].
IV. The Bilinear Form
Consider the case for which the two reference (model)
views of an object are taken orthographically (using a tele
lens would provide a reasonable approximation), but during
recognition any perspective view of the object is al-
lowed. It can easily be shown that the three views are then
connected via bilinear functions (instead of trilinear):
Theorem 3 (Bilinearity) Within the conditions of Theorem
1, in case the views / 1 and / 2 are obtained by parallel
projection, then the pair of trilinear forms of Theorem 1 reduce
to the following pair of bilinear equations:
and
Proof: Under these conditions we have from Lemma 1 that
A is affine in P 2 and v 0
reduces to:
Similarly, (4) reduces to:
Both equations are of the desired form, with the first four
coefficients identical across both equations.
The remaining trilinear forms undergo a similar reduc-
tion, and Theorem 2 still holds, i.e., we still have four linearly
independent bilinear forms. Consequently, we have
coefficients up to a common scale (instead of 27) and
four equations per point, thus five corresponding points
(instead of seven) are sufficient for a linear solution.
A bilinear function of three views has two advantages
over the general trilinear function. First, as mentioned
above, only five corresponding points (instead of seven)
across three views are required for solving for the coeffi-
cients. Second, the lower the degree of the algebraic func-
tion, the less sensitive the solution may be in the presence
of errors in measuring correspondences. In other words,
it is likely (though not necessary) that the higher order
terms, such as the term x 00 x 0 x in Equation 3, will have a
higher contribution to the overall error sensitivity of the
system.
Compared to the case when all views are assumed ortho-
graphic, this case is much less of an approximation. Since
the model views are taken only once, it is not unreasonable
to require that they be taken in a special way, namely, with
a tele lens (assuming we are dealing with object recogni-
tion, rather than scene recognition). If this requirement is
satisfied, then the recognition task is general since we allow
any perspective view to be taken during the recognition
process.
V. Experimental Data
The experiments described in this section were done in
order to evaluate the practical aspect of using the trilinear
result for re-projection compared to using epipolar intersection
and the linear combination result of [38] (the latter
we have shown is simply a limiting case of the trilinear
result).
The epipolar intersection method was implemented as
described in Section III by recovering first the fundamental
matrices. Although eight corresponding points are sufficient
for a linear solution, in practice one would use more
than eight points for recovering the fundamental matrices
in a linear or non-linear squares method. Since linear least
squares methods are still sensitive to image noise, we used
the implementation of a non-linear method described in
[20] which was kindly provided by T. Luong and L. Quan
(these were two implementations of the method proposed
in [20] - in each case, the implementation that provided
the better results was adopted).
The first experiment is with simulation data showing
that even when the epipolar geometry is recovered accu-
rately, it is still significantly better to use the trilinear result
which avoids the process of line intersection. The second
experiment is done on a real set of images, comparing
the performance of the various methods and the number of
corresponding points that are needed in practice to achieve
reasonable re-projection results.
A. Computer Simulations
We used an object of 46 points placed randomly with z
coordinates between 100 units and 120 units, and x; y co-ordinates
ranging randomly between -125 and +125. Focal
length was of 50 units and the first view was obtained by
fx=z; fy=z. The second view (/ 2 ) was generated by a rotation
around the point (0; 0; 100) with axis (0:14; 0:7; 0:7)
and by an angle of 0:3 radians. The third view (/ 3 ) was
generated by a rotation around an axis (0; 1; 0) with the
same translation and angle. Various amounts of random
noise was applied to all points that were to be re-projected
onto a third view, but not to the eight or seven points
that were used for recovering the parameters (fundamental
matrices, or trilinear coefficients). The noise was random,
added separately to each coordinate and with varying levels
from 0.5 to 2.5 pixel error. We have done 1000 trials as fol-
lows: 20 random objects were created, and for each degree
of error the simulation was ran 10 times per object. We
collected the maximal re-projection error (in pixels) and
the average re-projection error (averaged of all the points
that were re-projected). These numbers were collected separately
for each degree of error by averaging over all trials
(200 of them) and recording the standard deviation as well.
Since no error were added to the eight or seven points that
were used to determine the epipolar geometry and the tri-linear
coefficients, we simply solved the associated linear
systems of equations required to obtain the fundamental
matrices or the trilinear coefficients.
The results are shown in Figure 1. The graph on the left
shows the performance of both algorithms for each level of
image noise by measuring the maximal re-projection error.
We see that under all noise levels, the trilinear method is
significantly better and also has a smaller standard devi-
ation. Similarly for the average re-projection error shown
in the graph on the right.
This difference in performance is expected, as the tri-linear
method takes all three views together, rather than
every pair separately, and thus avoids line intersections.
B. Experiments On Real Images

Figure

shows three views of the object we selected for
the experiment. The object is a sports shoe with added texture
to facilitate the correspondence process. This object
was chosen because of its complexity, i.e., it has a shape of
a natural object and cannot easily be described parametrically
(as a collection of planes or algebraic surfaces). Note
that the situation depicted here is challenging because the
re-projected view is not in-between the two model views,
i.e., one should expect a larger sensitivity to image noise
than in-between situations. A set of 34 points were manually
selected on one of the frames, / 1 , and their correspondences
were automatically obtained along all other frames
used in this experiment. The correspondence process is
based on an implementation of a coarse-to-fine optical-
flow algorithm described in [7]. To achieve accurate correspondences
across distant views, intermediate in-between
frames were taken and the displacements across consecutive
frames were added. The overall displacement field was
then used to push ("warp") the first frame towards the target
frame and thus create a synthetic image. Optical-flow
was applied again between the synthetic frame and the target
frame and the resulting displacement was added to the
overall displacement obtained earlier. This process provides
a dense displacement field which is then sampled to
obtain the correspondences of the 34 points initially chosen
in the first frame. The results of this process are shown in

Figure

2 by displaying squares centered around the computed
locations of the corresponding points. One can see
that the correspondences obtained in this manner are rea-
sonable, and in most cases to sub-pixel accuracy. One can
readily automate further this process by selecting points
in the first frame for which the Hessian matrix of spatial
derivatives is well conditioned - similar to the confidence
values suggested in the implementations of [4, 7, 34] -
however, the intention here was not so much as to build a
complete system but to test the performance of the trilinear
re-projection method and compare it to the performance of
epipolar intersection and the linear combination methods.
The trilinear method requires at least seven corresponding
points across the three views (we need 26 equation,
and seven points provide 28 equations), whereas epipolar
intersection can be done (in principle) with eight points.
Fig. 1. Comparing the performance of the epipolar intersection method (the dotted line) and the trilinear functions method (dashed line) in the
presence of image noise. The graph on the left shows the maximal re-projection error averaged over 200 trials per noise level (bars represent standard
deviation). Graph on the right displays the average re-projection error averaged over all re-projected points averaged over the 200 trials per noise
level.
Fig. 2. Top Row: Two model views, / 1 on the left and / 2 on the right (image size are 256 \Theta 240). The overlayed squares illustrate the corresponding
points (34 points). Bottom Row: Third view / 3 . Note that / 3 is not in-between / 1 and / 2 , making the re-projection problem more challenging (i.e.,
performance is more sensitive to image noise than in-between situations).
Fig. 3. Re-projection onto / 3 using the trilinear result. The re-projected points are marked as crosses, therefore should be at the center of the squares
for accurate re-projection. On the left, the minimal number of points were used for recovering the trilinear coefficients (seven points); the average
pixel error between the true an estimated locations is 0.98, and the maximal error is 3.3. On the right 10 points were used in a least squares fit;
average error is 0.44 and maximal error is 1.44.
Fig. 4. Results of re-projection using intersection of epipolar lines. In the lefthand display the ground plane points were used for recovering the
fundamental matrix (see text), and in the righthand display the fundamental matrices were recovered from the implementation of [20] using all 34
points across the three views. Maximum displacement error in the lefthand display is 25.7 pixels and average error is 7.7 pixels. Maximal error in the
righthand display is 43.4 pixels and average error is 9.58 pixels.
The question we are about to address is what is the number
of points that are required in practice (due to errors in
correspondence, lens distortions and other effects that are
not adequately modeled by the pin-hole camera model) to
achieve reasonable performance?
The trilinear result was first applied with the minimal
number of points (seven) for solving for the coefficients,
and then applied with 8,9, and 10 points using a linear
least-squares solution (note that in general, better solutions
may be obtained by using SVD or Jacobi methods instead
of linear least-squares, but that was not attempted here).
The results are shown in Figure 3. Seven points provide a
re-projection with maximal error of 3.3 pixels and average
error of 0.98 pixels. The solution using
an improvement with maximal error of 1.44 and average
error of 0.44 pixels. The performance using eight and nine
points was reasonably in-between the performances above.
Using more points did not improve significantly the results;
for example, when all 34 points were used the maximal
error went down to 1.14 pixels and average error stayed at
pixels.
Next the epipolar intersection method was applied. We
used two methods for recovering the fundamental matrices.
One method is by using the implementation of [20], and the
other is by taking advantage that four of the corresponding
points are coming from a plane (the ground plane). In the
former case, much more than eight points were required
in order to achieve reasonable results. For example, when
using all the 34 points, the maximal error was 43.4 pixels
and the average error was 9.58 pixels. In the latter case,
we recovered first the homography B due to the ground
plane and then the epipole v 00 using two additional points
(those on the film cartridges). It is then known (see [28,
21, 32]) that F is the anti-symmetric
matrix of v 00 . A similar procedure was used to recover
F 23 . Therefore, only six points were used for re-projection,
Fig. 5. Results of re-projection using the linear combination of views method proposed by [38] (applicable to parallel projection). Top Row: In the
lefthand display the linear coefficients were recovered from four corresponding points; maximal error is 56.7 pixels and average error is 20.3 pixels. In
the righthand display the coefficients were recovered using 10 points in a linear least squares fashion; maximal error is 24.3 pixels and average error
is 6.8 pixels. Bottom Row: The coefficients were recovered using all 34 points across the three views. Maximal error is 29.4 pixels and average error
is 5.03 pixels.
but nevertheless, the results were slightly better: maximal
error of 25.7 pixels and average error of 7.7 pixels. Figure 4
shows these results.
Finally, we tested the performance of re-projection using
the linear combination method. Since the linear combination
method holds only for orthographic views, we are actually
testing the orthographic assumption under a perspective
situation, or in other words, whether the higher (bilin-
and trilinear) order terms of the trilinear equations are
significant or not. The linear combination method requires
at least four corresponding points across the three views.
We applied the method with four, 10 (for comparison with
the trilinear case shown in Figure 3), and all 34 points
(the latter two using linear least squares). The results are
displayed in Figure 5. The performance in all cases are significantly
poorer than when using the trilinear functions,
but better than the epipolar intersection method.
VI. Discussion
We have seen that any view of a fixed 3D object can be
expressed as a trilinear function with two reference views
in the general case, or as a bilinear function when the reference
views are created by means of parallel projection.
These functions provide alternative, much simpler, means
for manipulating views of a scene than other methods.
Moreover, they require fewer corresponding points in the-
ory, and much fewer in practice. Experimental results show
that the trilinear functions are also useful in practice yielding
performance that is significantly better than epipolar
intersection or the linear combination method (although
we emphasize that the linear combination was tested just
to provide a base-line for comparison, i.e., to verify that
the extra bilinear and trilinear terms indeed contribute to
better performance).
In general two views admit a "fundamental" matrix (cf.
[10]) representing the epipolar geometry between the two
views, and whose elements are subject to a cubic constraint
(rank of the matrix is 2). The trilinearity results (Theorems
imply, first, that three views admit a "fundamental"
tensor with 27 distinct elements. Second, the robustness
of the re-projection results may indicate that the elements
of this tensor, are either independent, or constrained by a
second order polynomial. In other words, in the two-view
case, the elements of the fundamental matrix lie on third-degree
hypersurface in P 9 . In the error-free case, a linear
solution, ignoring the cubic constraint, is valid. However,
in the presence of errors, the linear solution does not guarantee
that the point in P 9 (representing the solution) will
lie on the hypersurface, hence a non-admissible solution is
obtained. The non-linear solutions proposed by [20], do not
address this problem directly, but in practice yield better
behaved solutions than the linear ones. Since the trilinear
case yields good performance in practice using linear meth-
ods, we arrive to the conjecture above. The notion of the
"fundamental" tensor, its properties, relation to the geometry
of three views, and applications to 3D reconstruction
from multiple views, constitutes (in my mind) an important
future direction.
The application that was emphasized throughout the paper
is visual recognition via alignment. Reasonable performance
was obtained with the minimal number of required
points (seven) with the novel view (/ 3 ) - which may be
too many if the image to model matching is done by trying
all possible combinations of point matches. The existence
of bilinear functions in the special case where the model
is orthographic, but the novel view is perspective, is more
encouraging from the standpoint of counting points. Here
we have the result that only five corresponding points are
required to obtain recognition of perspective views (pro-
vided we can satisfy the requirement that the model is or-
thographic). We have not experimented with bilinear functions
to see how many points would be needed in practice,
but plan to do that in the future. Because of their simplic-
ity, one may speculate that these algebraic functions will
find uses in tasks other than visual recognition - some of
those are discussed below.
There may exist other applications where simplicity is of
major importance, whereas the number of points is less of
a concern. Consider for example, the application of model-based
compression. With the trilinear functions we need
17 parameters to represent a view as a function of two reference
views in full correspondence (recall, 27 coefficients
were used in order to reduce the number of corresponding
points from nine to seven). Assume both the sender
and the receiver have the two reference views and apply
the same algorithm for obtaining correspondences between
the two views. To send a third view (ignoring problems
of self occlusions that may be dealt with separately) the
sender can solve for the 17 parameters using many points,
but eventually send only the 17 parameters. The receiver
then simply combines the two reference views in a "trilin-
way" given the received parameters. This is clearly a
domain where the number of points is not a major concern,
whereas simplicity, and robustness (as shown above) due to
the short-cut in the computations, is of great importance.
Related to image coding, an approach of image decomposition
into "layers" was recently proposed by [1, 2]. In this
approach, a sequence of views is divided up into regions,
whose motion of each is described approximately by a 2D
affine transformation. The sender sends the first image followed
only by the six affine parameters for each region for
each subsequent frame. The use of algebraic functions of
views can potentially make this approach more powerful
because instead of dividing up the scene into planes one
can attempt to divide the scene into objects, each carries
the 17 parameters describing its displacement onto the subsequent
frame.
Another area of application may be in computer graph-
ics. Re-projection techniques provide a short-cut for image
rendering. Given two fully rendered views of some 3D ob-
ject, other views (again ignoring self-occlusions) can be rendered
by simply "combining" the reference views. Again,
the number of corresponding points is less of a concern
here.

Acknowledgments

I acknowledge ONR grants N00014-92-J-1879 and
N00014-93-1-0385, NSF grant ASC-9217041, and ARPA
grant N00014-91-J-4038 as a source of funding for the Artificial
Intelligence laboratory and for the Center for Biological
Computational Learning. Also acknowledged is the
McDonnell-Pew postdoctoral fellowship that has been my
direct source of funding for the duration of this work. I
thank T. Luong an L. Quan for providing their implementation
for recovering fundamental matrices and epipoles.
Thanks to N. Navab and A. Azarbayejani for assistance in
capturing the image sequence (equipment courtesy of MIT
Media Laboratory).



--R

Layered representations for image coding.
Layered representation for motion analysis.
Inherent ambiguities in recovering 3D motion and structure from a noisy flow field.
A unified perspective on computational techniques for the measurement of visual motion.
Contour matching using local affine transformations.
Invariant linear methods in photogrammetry and model-matching
Hierarchical motion-based frame rate conversion
Affine and projective structure from motion.
Robustness of correspondence based structure from motion.
What can be seen in three dimensions with an uncalibrated stereo rig?
What can two images tell us about a third one?
Why stereo vision is not always about 3D reconstruction.
Stereo from uncalibrated cameras.
Relative orientation.
Relative orientation revisited.
Recognizing solid objects by alignment with an image.
Affine structure from motion.
A computer algorithm for reconstructing a scene from two projections.
the reconstruction of a scene from two projections - configurations that defeat the 8-point algorithm
On determining the fundamental matrix: Analysis of different methods and experimental results.
Canonical representations for the geometries of multiple projective views.
The projective geometry of ambiguous surfaces.


Correspondence and affine shape from two orthographic views: Motion and Recognition.
Geometry and Photometry in 3D visual recogni- tion
Illumination and view position in 3D visual recog- nition
On geometric and algebraic aspects of 3D affine and projective structures from perspective 2D views.
Projective re-construction from two perspective/orthographic views and for visual recognition
Projective structure from uncalibrated images: structure from motion and recognition.
Trilinearity in visual recognition by alignment.
Relative affine structure: Theory and application to 3d reconstruction from perspective views.
The quadric reference surface: Applications in registering views of complex 3d objects.
Factoring image sequences into shape and motion.
Uniqueness and estimation of three-dimensional motion parameters of rigid objects with curved sur- face
The Interpretation of Visual Motion.
Aligning pictorial descriptions: an approach to object recognition.
Recognition by linear combination of models.
Model based invariants for 3-D vision
--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
Shai Avidan , Amnon Shashua, Threading Fundamental Matrices, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.1, p.73-77, January 2001
D. Ortn , J. M. M. Montiel, Indoor robot motion based on monocular images, Robotica, v.19 n.3, p.331-342, May 2001
Gideon P. Stein , Amnon Shashua, On Degeneracy of Linear Reconstruction From Three Views: Linear Line Complex and Applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.3, p.244-251, March 1999
Harpreet S. Sawhney , Yanlin Guo , Rakesh Kumar, Independent Motion Detection in 3D Scenes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.10, p.1191-1199, October 2000
Atsushi Marugame , Jiro Katto , Mutsumi Ohta, Structure Recovery with Multiple Cameras from Scaled Orthographic and Perspective Views, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.7, p.628-633, July 1999
Jianbo Su , Ronald Chung , Liang Jin, Homography-based partitioning of curved surface for stereo correspondence establishment, Pattern Recognition Letters, v.28 n.12, p.1459-1471, September, 2007
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
Kalle strm , Magnus Oskarsson, Solutions and Ambiguities of the Structure and Motion Problem for 1DRetinal Vision, Journal of Mathematical Imaging and Vision, v.12 n.2, p.121-135, April 2000
Ronald Chung , Hau-San Wong, Polyhedral Object Localization in an Image by Referencing to a Single Model View, International Journal of Computer Vision, v.51 n.2, p.139-163, February
Akihiro Sugimoto, A Linear Algorithm for Computing the Homography from Conics in Correspondence, Journal of Mathematical Imaging and Vision, v.13 n.2, p.115-130, Oct. 2000
S. Avidan , T. Evgeniou , A. Shashua , T. Poggio, Image-based view synthesis by combining trilinear tensors and learning techniques, Proceedings of the ACM symposium on Virtual reality software and technology, p.103-110, September 1997, Lausanne, Switzerland
Richard I. Hartley, Lines and Points in Three Views and the Trifocal Tensor, International Journal of Computer Vision, v.22 n.2, p.125-140, March 1997
Nassir Navab , Mirko Appel, Canonical Representation and Multi-View Geometry of Cylinders, International Journal of Computer Vision, v.70 n.2, p.133-149, November  2006
Olivier Faugeras , Long Quan , Peter Strum, Self-Calibration of a 1D Projective Camera and Its Application to the Self-Calibration of a 2D Projective Camera, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.10, p.1179-1185, October 2000
Anders Heyden, Reduced Multilinear Constraints: Theory and Experiments, International Journal of Computer Vision, v.30 n.1, p.5-26, Oct. 1998
Stefan Carlsson , Daphna Weinshall, Dual Computation of Projective Shape and Camera Positions  from Multiple Images, International Journal of Computer Vision, v.27 n.3, p.227-241, May 1, 1998
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
Gideon P. Stein , Amnon Shashua, Model-Based Brightness Constraints: On Direct Estimation of Structure and Motion, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.9, p.992-1015, September 2000
Cristian Sminchisescu , Dimitris Metaxas , Sven Dickinson, Incremental Model-Based Estimation Using Geometric Constraints, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.5, p.727-738, May 2005
Amnon Shashua , Nassir Navab, Relative Affine Structure: Canonical Model for 3D From 2D Geometry and Applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.9, p.873-883, September 1996
Shai Avidan , Amnon Shashua, Novel View Synthesis by Cascading Trilinear Tensors, IEEE Transactions on Visualization and Computer Graphics, v.4 n.4, p.293-306, October 1998
John Oliensis, A Multi-Frame Structure-from-Motion Algorithm under Perspective Projection, International Journal of Computer Vision, v.34 n.2-3, p.163-192, Nov. 1999
Amnon Shashua, On Photometric Issues in 3D Visual Recognition from aSingle 2D Image, International Journal of Computer Vision, v.21 n.1-2, p.99-122, January. 1997
Hayman , Torfi Thrhallsson , David Murray, Tracking While Zooming Using Affine Transfer and Multifocal Tensors, International Journal of Computer Vision, v.51 n.1, p.37-62, January
visual recognition;algebraic and geometric invariants;reprojection;projective geometry;alignment