Euclidean Reconstruction and Reprojection Up to Subgroups.
The necessary and sufficient conditions for being able to estimate scene structure, motion and camera calibration from a sequence of images are very rarely satisfied in practice. What exactly can be estimated in sequences of practical importance, when such conditions are not satisfied? In this paper we give a complete answer to this question. For every camera motion that fails to meet the conditions, we give explicit formulas for the ambiguities in the reconstructed scene, motion and calibration. Such a characterization is crucial both for designing robust estimation algorithms (that do not try to recover parameters that cannot be recovered), and for generating novel views of the scene by controlling the vantage point. To this end, we characterize explicitly all the vantage points that give rise to a valid Euclidean reprojection regardless of the ambiguity in the reconstruction. We also characterize vantage points that generate views that are altogether invariant to the ambiguity. All the results are presented using simple notation that involves no tensors nor complex projective geometry, and should be accessible with basic background in linear algebra.
Introduction
Reconstructing spatial properties of a scene from a number
of images taken by an uncalibrated camera is a classical
problem in computer vision. It is particularly important
when the camera used to acquire the images is not available
for calibration, as for instance in video post-processing,
or when the calibration changes in time, as in vision-based
navigation. If we represent the scene by a number of isolated
points in three-dimensional space and the imaging process
by an ideal perspective projection, the problem can be
reduced to a purely geometric one, which has been subject
to the intense scrutiny of a number of researchers during
the past ten years. Their efforts have led to several important
and useful results. The problem is that conditions for
a unique Euclidean reconstruction are almost never satisfied
in sequence of images of practical interest. In fact, they
require as a necessary condition that the camera undergoes
rotation about at least two independent axes, which is rarely
the case both in video processing and in autonomous navigation
[14].
In this paper we address the question of what exactly can
be done when the necessary and sufficient conditions for
unique reconstruction are not satisfied. In particular:
(i) For all the motions that do not satisfy the conditions, to
what extent can we reconstruct structure, motion and
calibration?
(ii) If the goal of the reconstruction is to produce a new view
of the scene from a different vantage point, how can we
make sure that the image generated portrays a "valid"
Euclidean scene?
On our way to answering these questions, we pause to reflect
on the nature of multilinear constraints. While constraints
involvingtwo images at a time (fundamental constraints) are
well understood and involve clean notation and geometric
interpretation, muti-linear constraints are more difficult to
work with and to interpret. It seems therefore natural to ask
the following question
(iii) Do multilinear constraints carry geometric information
on the camera system that is not contained in bilinear
ones?
1.1. Relation to previous work
The study of ambiguities in Euclidean reconstruction (i)
arises naturally in the problem of motion and structure recovery
and self-calibration from multiple cameras. There is
a vast body of literature on this topic, which cannot be reviewed
in the limited space allowed. Here we only comment
on some of the work that is most closely related to this
paper, while we refer the reader to the literature for more
details, references and appropriate credits (see for instance
[4, 8, 10, 13, 19, 20, 21] and references therein).
It has long been known that in the absence of any a priori
information about motion, calibration and scene struc-
ture, reconstruction can be performed at least up to a projective
transformation [6]. Utilizing additional knowledge
about the relationship between geometric entities in the image
(e.g., parallelism) one can stratify the different levels
of reconstructions from projective all the way to Euclidean
[3, 5, 6, 18]. At such a level of generality, the conditions on
the uniqueness and existence of solutions are restrictive and
the algorithms are computationally costly, often exhibiting
local minima [12].
The nature of the constraints among images of the same
point in different cameras has been studied extensively, and
is known to be multilinear (see for instance [7, 10, 20]). The
algebraic dependency among constraints (iii) has been established
by means of elimination [21] or other algebraic
geometric tools [9]. However, an explicit characterization
of how the information is encoded in different constraints
- which is crucial in the design of robust estimation algorithms
- is hard to derive by such means.
Recently, Sturm [19] has proposed a taxonomy of critical
motions, that is motions which do not allow a unique recon-
struction. However, not only the given taxonomy is by no
means intrinsic to Euclidean reconstruction (see [14]), but
also no explicit characterization of the ambiguities in the re-constructed
shape, motion and calibration has been given. A
natural continuation of these efforts involved the analysis of
cases where the motion and/or calibration were restricted either
to planar or linear motion [2, 18] and techniques were
proposed for affine reconstruction or up to one parameter
family.
Several techniques have been proposed to synthesize
novel views of a reconstructed scene (ii): in [1], trilinear
constraints have been exploited to help generate reprojected
images for a calibrated camera. In the case of a partially
uncalibrated camera, such a method has to face the issues
of whether the reprojected image portrays a valid Euclidean
scene.
1.2. Outline of this paper and its contributions
As we anticipated in the previous section, the answer
to question (iii) has been established before on an algebraic
footing - the algebraic ideals generated by trilinear
and quadrilinear constraints (as polynomials of image coor-
dinates) are necessarily contained in that generated by bi-linear
ones [9]. However, in order to give a complete account
of ambiguities in 3D Euclidean reconstruction (espe-
cially for self-calibration and motion recovery), it is crucial
to know how the information on the Euclidean configuration
of a camera system is encoded in the multilinear con-
straints. In section 2 we give a novel, complete and rigorous
proof that unveils how the information encoded in trilinear
and quadrilinear constraints depends on that in bilinear ones.
There we also discuss the role of multilinear constraints with
regards to singular configurations of points.
The well-known - but conservative - answer to question
(i) is that structure can at least be recovered up to a global
projective transformation of the three-dimensional space.
However, there is more to be said, as we do in section 3
for the case of constant calibration. 1 There, we give explicit
formulas of exact ambiguities in the reconstruction of
scene structure, camera motion and calibration with respect
to all subgroups of the Euclidean motion. In principle, one
should study ambiguities corresponding to all critical configurations
as given in [14]. However, it is only the ambiguities
that exhibita group structure that are of practical importance
in the design of estimation algorithms. In such a case,
not only can the analysis be considerably simplified but also
clean formulas for all generic ambiguities can be derived.
Such formulas are important for 3D reconstruction as well
as for synthesizing novel 2D views.
Question (ii) is then answered in section 4, where we
characterize the complete set of vantage points that generate
"valid" images of the scene regardless of generic ambiguities
in 3D reconstruction.
These results have great practical significance, because
they quantify precisely to what extent scene structure, camera
motion and calibration can be estimated in sequences for
which many of the techniques available todate do not apply.
Furthermore, the analysis clarifies the process of 2D view
synthesis from novel viewpoints. In addition to that, we give
a novel account of known results on the role of multilinear
constraints and their relationship to bilinear ones.
Granted the potential impact on applications, this paper is
mainly concerned with theory. We address neither algorithmic
issues, nor do we perform experiments of any sort: the
validation of our statements is in the proofs. We have tried
to keep our notation as terse as possible. Our tools are borrowed
from linear algebra and some differential geometry,
although all the results should be accessible without background
in the latter. We use the language of (Lie) groups
because that allows us to give an explicit characterization of
all the ambiguities in a concise and intuitive fashion. Traditional
tools involved in the analysis of self-calibration involved
complex loci in projective spaces (e.g., the "absolute
conic"), which can be hard to grasp for someone not proficient
in algebraic geometry.
2. Dependency of multilinear constraints revis-
ited
We model the world as a collection of points in a three-dimensional
Euclidean space, which we represent in homogeneous
coordinates as . The
perspective projection of the generic point onto the two-dimensional
image plane is represented by homogeneous
coordinates x 2 R 3 that satisfy
where -(t) 2 R is a scalar parameter related to the distance
of the pointq from the center of projection and the non-
In fact, even in the case of time-varying calibration, in principle, the
best one can do is an affine reconstruction, not just a projective one!
singular matrix A(t) - called "calibration matrix" - describes
the intrinsic parameters of the camera. Without loss of generality
we will re-scale the above equation so that the determinant
of A is 1. The set of 3 \Theta 3 matrices with determinant
one is called Special Linear group denoted by SL(3). The
rigid motion of the camera g(t) is represented by a translation
vector p(t) 2 R 3 and a rotation matrix R(t), that is an
orthogonal matrix with determinant equal to one. Such matrices
form a group called Special Orthogonal group and indicated
by belongs to SE(3),
the special Euclidean group of rigid motion in R 3 . The action
of g(t) on the point q is given by
In equation (1) we will assume that x(t) is measured, while
everything else is unknown.
When we consider measurements at n different times, we
organize the above equations by defining
which we will assume to be full-rank, that is rank(M
C A
C A
which we re-write in a more compact notation as X ~
Mq. We call M 2 R 3n\Theta4 the motion matrix and X the image
matrix.
2.1. Constraints on multiple images
Let ~
denote the four columns of
the matrix M and ~
be the n columns
of the matrix X. Then the coordinates x(t
same point seen from different views only if they satisfy the
following wedge product equation:
~
This constraint, which is multilinear in the measurements
simply expresses the fact that the columns of M and
are linearly dependent. Constraintsinvolvingfour images
are call quadrilinear, constraints involving three images are
called trilinear, and those involving two images are called
bilinear or fundamental. In general, the coefficients of all
the multilinear constraints are minors of the motion matrix
M . As it has been shown (see, for instance, Triggs in [20]),
constraints involving more than four frames are necessarily
dependent on quadrilinear, trilinear and bilinear ones. In this
section we go one step further to discuss how trilinear and
quadrilinear constraints are dependent on bilinear ones.
When studying the dependency among constraints, one
must distinguish between algebraic and geometric depen-
dency. Roughly speaking, algebraic dependency concerns
the conditions that a point in an image must satisfy in order
to be the correspondent of a point in another image. Vice
versa, geometric dependency is concerned with the information
that correspondingpoints give on the operator that maps
one to the other. The two notions are related but not equiva-
lent, and the latter bears important consequences when one
is to use the constraints in optimization algorithms to recover
structure and calibration. While the geometric dependency
of multilinear constraints has been established before
under the assumption of constant calibration [10], we give a
novel, simple and rigorous proof that is valid under the more
general assumption of time-varying calibration.
2.2. Algebraic vs. geometric dependency
To clarify the relation between algebraic and geometric
dependency note that in general we can express a multi-linear
constraint in the form:
ff j are some polynomials of entries of M and fi j polynomials
of entries of the image coordinates, with M and X defined
as before. ff j 's are called the coefficients of multilinear
constraints. Studyingthe algebraic dependency between
constraints then corresponds to fixing the coefficients ff j and
asking whether there are some additional constraints among
the image coordinates X generated by three and four views 3 .
This problem has been studied many researchers and an elegant
answer can be found in [9] by explicitly characterizing
the primary decomposition of the ideal (in the polynomial
ring of image coordinates x i 's) generated by the bilinear
constraints in terms of that generated by trilinear ones or
quadrilinear ones.
Geometric dependency, on the other hand, investigates
whether, given the image coordinates X, the coefficients ff j
corresponding to motion parameters in additional views can
give additional information about M . These two different
types of dependencies were previously pointed out (see for
instance the work of Heyden [10]). For both types of depen-
dencies, the answer is negative, i.e., trilinear and quadrilinear
constraints in general are dependent of bilinear ones. We
here give a simple but rigorous study of the geometric de-
pendency. The results will also validate the ambiguity analysis
given in following sections.
Consider the case for the moment, disregard
the internal structure of the motion matrix M 2
R 9\Theta4 . Its columns can be interpreted as a basis of a
four-dimensional subspace of the nine-dimensional space.
The set of k-dimensional subspaces of an m-dimensional
space is called a Grassmannian manifold and denoted by
G(m; k). Therefore, M is an element of G(9; 4). By just
This subsection is for the benefit of the reader already familiar with
existing work on the algebraic dependency among multilinear constraints.
The reader who is not at ease with algebraic geometry or unfamiliar with
the existing literature can skip this subsection without loss of continuity
3 In other words, it addresses the dependencyamong algebraic ideals associated
with the three types of multilinear constraints.
re-arranging the three blocks
OE between G(9; 4) and three copies of G(6;
The question of whether trilinear constraints are independent
of bilinear ones is tightly related to whether these
two representations of the motion matrix M are equivalent.
Since the coefficients in the multilinear constraints are homogeneous
in the entries of each block M i , the motion matrix
M is only determined up to the equivalence relation:
f0g. Thus for multilinear constraints the
motion matrix is only well-defined as an element of the quotient
space G(3n; 4)= - which is of dimension (11n \Gamma 15),
4 as was already noted by Triggs [20].
We are now ready to prove that coefficients ff j 's in trilinear
and quadrilinear constraints depend on those in bilinear
ones.
Theorem 1 (Geometric dependency) Given three (or
four) views, the coefficients of all bilinear constraints
or equivalently the corresponding fundamental matrices
uniquely determine the motion matrix M as an element in
(or G(12; 4)= -) given that Ker(M i )'s are
linearly independent.
Proof: It is known that between any pair of images (i;
the motion matrix:
determined by the
corresponding fundamental matrix F ij up to two scalars
Hence for the three view
case all we need to prove is that the map:
~
is injective. To this end, assume ~
then we have
that, after re-scaling,
M3
G3 for some- i 2 R
3. This yields M1
there exist U i 2 R 4\Theta4 with each column of U i is in
4 The Grassmannian G(3n; 4) has dimension (3n \Gamma
The dimension of the quotient space is smaller since the equivalence
relation has scales.
5 GL(4) is the general linear group of all non-degenerate4 \Theta 4 real matrices

Combining these three equations, we obtain:
The matrix on the right hand side of the equation
has a non-trivial null-space since its columns are in
spanfKer(M1 ); Ker(M2);Ker(M3)g which has dimension
three. However, G1 is non-singular, and therefore
it must be
That is, the columns of
are linear combinations of columns of -2G2 \Gamma G1 and
are linearly independent.
Thus we have
A =@
which means that M 0 and M are the same, up to the equivalence
relation defined in equation (4). Therefore, they represent the same
element in G(9; 4)= -, which means that the map ~
OE is injective.
In the case of four views, in order to show that coefficients
in quadrilinear constraints also depend on bilinear ones, one only
needs to check that the obvious map from G(12; 4)= - to
(G(9; 4)= -) 4 is injective. This directly follows from the above
proof of the three frame case.
Comment 1 As a consequence of the theorem, coefficients ff j 's
in trilinear and quadrilinear constraints are functions of those in
bilinear ones. While the above proof shows that the map ~
OE can be
it does not provide an explicit characterization of the in-
verse. Such an inverse can in principle be highly non-linear and
conditioning issues need to be taken into account in the design of
estimation algorithms. We emphasize that the geometric dependency
does not imply that two views are sufficient for reconstruc-
tion! It claims that given n views, their geometry is characterized
by considering only combinations of pairs of them through bilinear
constraints, while trilinear constraints are of help only in the
case of singular configurationsof points and camera (see comment
2). For four views, the condition that Ker(M i are
linearly independent is not necessary. A less conservative condition
is that there exist two groups of three frames which satisfy the
condition for the three view case.
Theorem 1 requires that the one-dimensional kernels of the
matrices or are linearly indepen-
dent. Note that the kernels of M i for are given
by (\Gammap T
the vector R T
exactly
the position of the i th camera center. Hence the condition
of the theorem is satisfied if and only if the centers of projection
of the cameras generate a hyper-plane of dimension
In particular, when the three camera centers
form a triangle, and when 4, the four camera centers
form a tetrahedron.
Comment 2 (Critical surfaces and motions) Although we
have shown that the coefficients of multilinear constraints depend
on those of bilinear ones, we have assumed that the latter (or the
corresponding fundamental matrices) are uniquely determined by
the epipolar geometry. However, this is not true when all the points
lie on critical surfaces. In this case, as arguedby Maybank in [15],
we may obtain up to three ambiguous solutions from the bilinear
constraints. This is one of the cases when trilinear and quadrilinear
constraints provide useful information. On this topic, see also
[16]. Also, when the camera is undergoing a rectilinear motion
(i.e., all optical centers are aligned), trilinear constraints provide
independent information in addition to bilinear ones. This fact has
been pointed out before; see for instance Heyden in [11].
3. Reconstruction under motion subgroups
The goal of this section is to study all "critical" motion
groups that do not allow unique reconstruction of structure,
motion and calibration. While a classification of such critical
motions has been presented before (see [14]), we here
go well beyond by giving an explicit characterization of
the ambiguity in the reconstruction for each critical motion.
Such an explicit characterization is crucial in deriving the
ambiguity in the generation of novel views of a scene, which
we study in section 4.
In this section, we characterize the generic ambiguity in
the recovery of (a) structure, (b) motion and (c) calibration
corresponding to each possible critical motion. A subgroup
of SE(3) is called critical if the reconstruction is not unique
when the motion of the camera is restricted to it. For the purpose
of this section, we assume that the calibration matrix A
is constant.
3.1. Some preliminaries
So far the only restriction we have imposed on the constant
calibration matrix A is that it is non-singular and is
normalized as to have However, A can only
be determined up to an equivalence class of rotations, that
is A 2 SL(3)=SO(3). 6 For more detail, please see [14].
The unrecoverable rotation in our choice of A simply corresponds
to a rotation of the entire camera system. We borrow
the following statement directly from [14]:
Theorem 2 (Necessary and sufficient condition for
a unique calibration) Given a set of camera motion
none of the rotation component
R i is of the form e b
then the
camera calibration A as an element in SL(3)=SO(3) is
uniquely determined if and only if at least two of the axes
are linearly independent.
6 Here take left cosets as elements in the quotient space. A representation
of this quotient space is given, for instance, by upper-triangular matri-
ces; such a representation is commonly used in modeling calibration matrices
by means of physical parameters of cameras such as focal length, principal
point and pixel skew.
Although the necessity of the independence of the rotation
axes has been long known in the literature (see e.g. [13]), the
sufficiency is not proven till recent [14]. This theorem states
a very important and useful fact: the condition for a unique
calibration has nothing to do with translation (as opposed to
the results given in [19])! See [14] for the detail. Due to this
theorem, all proper continuous subgroups of SE(3) except
are critical for self-calibration. So the first step in our
analysis consists in classifying all continuous Lie subgroups
of SE(3). It is a well known fact that a complete list of these
groups (up to conjugation) is given by 7 :
Translational Motion: (R 3 ; +) and its subgroups
Rotational Motion: (SO(3); \Delta) and its subgroups
Planar Motion: SE(2)
Screw Motion: (SO(2); \Delta) \Theta (R; +)
We are now ready to explore to what extent scene structure,
camera motion and calibration can be reconstructed when
motion is constrained onto one of the above subgroups. In
other words, we will study the generic ambiguities of the
reconstruction problem. In what follows, we use
3 to denote the 3D coordinates of
the point respect to the camera
frame at time t: To simplify nota-
tion, for any u 2 R 3 we define b u to be a 3 skew-symmetric
matrix such that 8v 2 R 3 the cross product u \Theta
3.2. Generic ambiguities in structure, motion and
calibration
Translational motion (R 3 and its subgroups). The co-ordinate
transformation between different views is given by
According to Theorem
2, the calibration A 2 SL(3) cannot be recovered from
pure translational motion, and therefore the corresponding
structure q and translational motion p can be recovered only
up to the unknown transformation A. We therefore have the
following
Theorem 3 (Ambiguity under R 3 ) Consider an un-calibrated
camera described by the calibration matrix
undergoing purely translational motion R 3 (or
any of its nontrivial subgroups) and let B be an arbitrary
matrix in SL(3). If the camera motion p 2 R 3 and the
scene structure q 2 R 4 are unknown, then B, B \Gamma1 Ap and
are the only generic ambiguous solutions for the
camera calibration, camera motion and the scene structure
respectively.
Note that this ambiguity corresponds exactly to an affine re-construction
[18].
7 The completeness of this list can be shown by classifying all Lie subalgebras
of the Lie algebra se(3) of SE(3) and then exponentiate them.
Rotational motion (SO(3)). The action of SO(3) transforms
the coordinates in different cameras by
According to Theorem 2, the
calibration A can be recovered uniquely, and so can the rotational
motion R(t) 2 SO(3). However, it is well known
that the depth information of the structure cannot be recovered
at all. We summarize these facts into the following:
Theorem 4 (Ambiguity under SO(3)) Consider an un-calibrated
camera with calibration matrix A 2 SL(3)
undergoing purely rotational motion SO(3) and let - be
an arbitrary (positive) scalar. If both the camera motion
and the scene structure q 2 R 3 are unknown,
then A, R and - \Delta q are the only generic ambiguous solutions
for the camera calibration, camera motion and the scene
structure respectively.
Planar motion (SE(2)). While the previous two cases
were of somewhat academic interest and the theorems portray
well-known facts, planar motion arises very often in ap-
plications. We will therefore study this case in some more
detail.
R 3 be the standard basis of R 3 . Without loss of generality,
we may assume the camera motion is on the plane normal to
e 3 and is represented by the subgroup SE(2).
Let A be the unknown calibration matrix of the cam-
era. As described in section 3.1 we consider A as an element
of the quotient space SL(3)=SO(3). According to
[14], any possible calibration matrix A 0 2 SL(3)=SO(3)
is such that the matrix
0 is in the symmetric
real kernel (SRKer) of the Lyapunov map for all
A \GammaT R T A T
By the choice of e 1 the real eigenvector of R is e 3 .
Imposing S 2 SL(3), we obtain
3\Theta3 is a matrix function of s:
Geometrically, this reveals that only metric information
within the plane can be recovered while the relative scale
between the plane and its normal direction cannot be deter-
mined. If we choose an erroneous matrix A 0 from the set
of possible solutions for calibration, then A
some matrix B 2 SL(3). Since A \GammaT
0 is necessarily in
SRKer(L), we further have that, for some s 2 R,
A \GammaT
A solution of (7) is of the form
us define a one-parameter Lie group
G SE(2) as:
Then the solution space of (7) is given by SO(3)G SE(2) .
The group G SE(2) can be viewed as a natural representation
of ambiguous solutions in the space SL(3)=SO(3).
Once we have a calibration matrix, say A 0 , we can extract
motion from the fundamental matrix
R 3\Theta3 as follows: we know that
. Then we define
and note that, for we have that D(s) commutes
with R i.e., is an essential
matrix since
HD(s)p: The motion recovered from E is therefore
is the true motion. Note that (HRH T ; HD(s)p) is actually
a planar motion (in a plane rotated by H from the original
one). The coordinate transformation in the uncalibrated
camera frame is given by
instead, the matrix A 0 is chosen to justify the camera cali-
bration, the coordinate transformation becomes:
Therefore, any point q viewed with an uncalibrated camera
A undergoing a motion (R; p) 2 SE(2) is not distinguishable
from the point HD(s)q viewed with an uncalibrated
camera A undergoing a motion
We have therefore proven
the following
Theorem 5 (Ambiguity under SE(2)) Consider a camera
with unknown calibration matrix A 2 SL(3) undergoing
planar motion SE(2) and let
. If both the camera motion
(R; p) 2 SE(2) and the scene structure q 2 R 3 are
unknown, then AB
SE(2) and B(s)q 2 R 3 are the only generic ambiguous solutions
for the camera calibration, camera motion and scene
structure respectively.
Comment 3 Note that the role of the matrix H 2 SO(3) is just
to rotate the overall configuration. Therefore, the only generic ambiguity
of the reconstruction is characterizedby the one parameter
Lie group G SE(2) .
Subgroups SO(2), SO(2) \Theta R and SE(2) \Theta R. We
conclude our discussion on subgroups of SE(3) by studying
SO(2), SO(2) \Theta Rand SE(2) \Theta Rtogether. This is because
their generic ambiguities are similar to the case of SE(2),
which we have just studied. Notice that in the discussion of
the ambiguity G SE(2) , we did not use the fact that the translation
p has to satisfy Therefore, the generic re-construction
ambiguities of SO(2) \Theta Rand SE(2) \Theta Rare
exactly the same as that of SE(2). The only different case is
SO(2). It is readily seen that the ambiguity of SO(2) is the
"product" of that of SE(2) and that of SO(3) due to the fact
As a consequence of Theorem
4 and Theorem 5 we have:
Corollary 1 (Ambiguity under SO(2)) Consider an un-calibrated
camera with calibration matrix A 2 SL(3) undergoing
a motion in SO(2) and let
\Delta). If both the
camera motion R 2 SO(3) and the scene structure q 2 R 3
are unknown, then AB
are the only generic ambiguous solutions
for the camera calibration, camera motion and scene
structure respectively.
From the above discussion of subgroups of SE(3) we
have seen that generic ambiguities exist for any proper sub-group
of SE(3). Therefore all subgroups of SE(3) are critical
with respect to reconstruction of scene structure, motion
and camera calibration. Furthermore, such ambiguities
which have been derived above based only on bilinear con-
straints, are not resolved by multilinear constraints according
to Theorem 1.
4. Reprojection under partial reconstruction
In the previous section we have seen that, in general, it
is possible to reconstruct the calibration matrix A and the
scene's structure q only up to a subgroup - which we call K ,
the ambiguity subgroup. For instance, in the case of planar
motion, an element in K has the form D(s) given by equation
(6). Therefore, after reconstruction we have
~
suppose one wants to generate a novel view of the
scene, ~ x from a new vantage point, which is specified
by a motion ~
must satisfy ~
~
In general, the reprojection ~
depends
both on the ambiguity subgroup K and on the vantage point
~ g and there is no guarantee that it is an image of the original
Euclidean scene.
It is only natural, then, to ask what is the set of vantage
points that generate a valid reprojection, that is an image of
the original scene q taken as if the camera A was placed at
some vantage point g(K). We discuss this issue in section
4.1. A stronger condition to require is that the reprojection
be independent (invariant) of the ambiguity K , so that we
have regardless of K; we discuss this issue in
section 4.2.
4.1. Valid Euclidean reprojection
In order to characterize the vantage points - specified
by motions ~ g - that produce a valid reprojection we must
find ~ g such that: ~
the reprojected image ~
x is ~
~
Ag(K)q, the characterization of all such
motions ~ g is given by the following Lie group:
We call R(K) the reprojection group for a given ambiguity
group K . For each of the generic ambiguities we studied in
section 3, the corresponding reprojection group is given by
the following
Theorem 6 The reprojection groups corresponding to each
of the ambiguity groups K studied in section 3 are given by:
1. (ambiguity of
(R
2. (R
of SO(2)).
3. (ambiguity of
4. (ambiguity of SE(3)).
Even though the reprojected image is, in general, not unique,
the family of all such images are still parameterized by the
same ambiguity group K . For a motion outside of the group
i.e., for a ~
the action of the
ambiguity group K on a reprojected image cannot simply
be represented as moving the camera: it will have to be a
more general non-Euclidean transformation of the shape of
the scene. However, the family of all such non-Euclidean
shapes are minimally parameterized by the quotient space
SE(3)=R(K).
Comment 4 [Choice of a "basis" for reprojection] Note that
in order to specify the viewpoint it is not just sufficient to choose
the motion ~ g for, in general, g(K) 6= ~ g. Therefore, an imaginary
"visual-effect operator" will have to adjust the viewpoint
g(K) acting on the parameters in K . The ambiguity subgroups
derived in section 3 areone-parametergroups(for the most important
cases) and therefore the choice is restricted to one parameter.
In a projective framework (such as [6]), the user has to specify a
projective basis of three-dimensional space, that is 15 parameters.
This is usually done by specifying the three-dimensional position
of 5 points in space.
4.2. Invariant reprojection
In order for the view taken from ~ g to be unique, we must
have
independent of K . Equivalentlywe must have K
where K is the ambiguity generated by the motion on a sub-group
G of SE(3). The set of ~ g that satisfy this condition
is a group N (K), the so called normalizer of K in SE(3).
Therefore, all we have to do is to characterize the normaliz-
ers for the ambiguity subgroups studied in section 3.
Theorem 7 The set of viewpoints that are invariant to re-projection
is given by the normalizer of the ambiguity sub-
group. For each of the motion subgroups analyzed in section
3 the corresponding normalizer of the ambiguity group
is given by:
1. N (R 3 ; +)).
2. N (R
of SO(2)).
3. N (ambiguity of
4. N (ambiguity of SE(3)).
For motions in every subgroup, the reprojection performed
under any viewpoint determined by the groups above is
unique.
5. Conclusions
When the necessary and sufficient conditions for a unique
reconstruction of scene structure, camera motion and calibration
are not satisfied, it is still possible to retrieve a reconstruction
up to a global subgroup action (on the entire configuration
of the camera system). We characterize such sub-groups
explicitly for all possible motion groups of the cam-
era. The reconstructed structure can then be re-projected to
generate novel views of the scene. We characterize the "ba-
sis" of the reprojection corresponding to each subgroup, and
also the motions that generate a unique reprojection. We
achieve the goal by using results from two view analysis
[14]. This is possible because the coefficients of multilinear
constraints are geometrically dependent of those of bi-linear
constraints. Therefore, the only advantage in considering
multilinear constraints is in the presence of singular
surfaces and rectilinear motions. Our future research agenda
involves the design of optimal algorithms to recover all (and
only!) the parameters that can be estimated from the data
based upon their generic ambiguities. The reconstruction
and reprojection problem studied in this paper is for a constant
calibration matrix. We will present generalized results
for the time-varying case in future work.

Acknowledgment

This work is supported by ARO under the MURI grant
DAAH04-96-1-0341.



--R

Novel view synthesis in tensor space.
Affine calibration of mobile vehicles.
Euclidean constraints for uncalibrated reconstruction.
Multiple image invariance using the double algebra.
Euclidean shape and motion from multiple perspective views via affine iterations.
What can be seen in three dimensions with an uncalibrated stereo rig?

Lines and points in three views


Reduced multilinear constraints - theory and ex- periments

Canonical representations for the geometries of multiple projective views.

Theory of Reconstruction from Image Motion.
Ambiguity in reconstruction from images of six points.
A theory of self-calibration of a moving camera
Affine reconstruction from perspective pairs obtained by a translating camera.
Critical motion sequences for monocular self-calibration and uncalibrated Euclidean reconstruction
The geometry of projective reconstruction I: Matching constraints and the joint image.
The study of 3D-from-2D using elimination
--TR

--CTR
Fredrik Kahl , Anders Heyden , Long Quan, Minimal Projective Reconstruction Including Missing Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.4, p.418-424, April 2001
Pr Hammarstedt , Fredrik Kahl , Anders Heyden, Affine Reconstruction from Translational Motion under Various Autocalibration Constraints, Journal of Mathematical Imaging and Vision, v.24 n.2, p.245-257, March     2006
reprojection;multilinear constraints;reconstruction ambiguity;camera self-calibration