Critical Motions for Auto-Calibration When Some Intrinsic Parameters Can Vary.
Auto-calibration is the recovery of the full camera geometry and Euclidean scene structure from several images of an unknown 3D scene, using rigidity constraints and partial knowledge of the camera intrinsic parameters. It fails for certain special classes of camera motion. This paper derives necessary and sufficient conditions for unique auto-calibration, for several practically important cases where some of the intrinsic parameters are known (e.g. skew, aspect ratio) and others can vary (e.g. focal length). We introduce a novel subgroup condition on the camera calibration matrix, which helps to systematize this sort of auto-calibration problem. We show that for subgroup constraints, criticality is independent of the exact values of the intrinsic parameters and depends only on the camera motion. We study such critical motions for arbitrary numbers of images under the following constraints: vanishing skew, known aspect ratio and full internal calibration modulo unknown focal lengths. We give explicit, geometric descriptions for most of the singular cases. For example, in the case of unknown focal lengths, the only critical motions are: (i) arbitrary rotations about the optical axis and translations, (ii) arbitrary rotations about at most two centres, (iii) forward-looking motions along an ellipse and/or a corresponding hyperbola in an orthogonal plane. Some practically important special cases are also analyzed in more detail.
Introduction
One of the core problems in computer vision is the recovery of 3D scene
structure and camera motion from a set of images. However, for certain
con-gurations there are inherent ambiguities. This kind of problem
was already studied in optics in the early 19th century, for example,
by Vieth in 1818 and Muller in 1826. Pioneering work on the subject
was also done by Helmholtz. See [13] for references. One well-studied
ambiguity is when the visible features lie on a special surface, called
a critical surface, and the cameras have a certain position relative
to the surface. Critical surfaces or igef#hrlicher Ortj were studied by
Krames [21] based on a monograph from 1880 on quadrics [32]. See also
the book by Maybank [24] for a more recent treatment. Another well-known
ambiguity is that when using projective image measurements, it
is only possible to recover the scene up to an unknown projective transformation
[8, 10, 35]. Additional scene, motion or calibration constraints
are required for a (scaled) Euclidean reconstruction. Auto-calibration
uses qualitative constraints on the camera calibration, e.g. vanishing
skew or unit aspect ratio, to reduce the projective ambiguity to a sim-
ilarity. Unfortunately, there are situations when the auto-calibration
constraints may lead to several possible Euclidean reconstructions. In
this paper, such degeneracies are studied under various auto-calibration
constraints.
In general it is possible to recover Euclidean scene information from
images by assuming constant but unknown intrinsic parameters
of a moving projective camera [26, 7]. Several practical algorithms have
been developed [39, 2, 30]. Some of the intrinsic parameters may even
vary, e.g. the focal length [31], or the focal length and the principal
point [14]. In [29, 15] it was shown that vanishing skew suOEces for a
Euclidean reconstruction. Finally in, [16] it was shown that given at
least 8 images it is suOEcient if just one of the intrinsic parameters is
known to be constant (but otherwise unknown).
However, for certain camera motions, these auto-calibration constraints
are not suOEcient [42, 1, 40]. A complete categorization of these
critical motions in the case of constant intrinsic parameters was given
by Sturm [36, 37]. The uniformity of the constant-intrinsic constraints
makes this case relatively simple to analyze. But it is also somewhat
unrealistic: It is often reasonable to assume that the skew actually vanishes
whereas focal length often varies between images. While the case of
constant parameters is practically solved, much less is known for other
auto-calibration constraints. In [43], additional scene and calibration
constraints are used to resolve ambiguous reconstructions, caused by a
-xed axis rotation. The case of two cameras with unknown focal lengths
is studied in [12, 28, 4, 20]. For the general unknown focal length case,
Sturm [38] has independently derived results similar to those presented
here and in [20, 19].
In this paper, we generalise the work of Sturm [37] by relaxing the
constraint constancy on the intrinsic parameters. We show that for a
large class of auto-calibration constraints, the degeneracies are independent
of the speci-c values of the intrinsic parameters. Therefore, it
makes sense to speak of critical motions rather than critical con-gura-
tions. We then derive the critical motions for various auto-calibration
constraints. The problem is formulated in terms of projective geometry
and the absolute conic. We start with fully calibrated cameras, and then
continue with cameras with unknown and possibly varying focal length,
principal point, and -nally aspect ratio. Once the general description of
the degenerate motions has been completed, some particular motions
frequently occurring in practice are examined in more detail.
This paper is organized as follows. In Section 2 some background
on projective geometry for vision is presented. Section 3 gives a formal
problem statement and reformulates the problem in terms of the absolute
conic. In Section 4, our general approach to solving the problem is
presented, and Section 5 derives the actual critical motions under various
auto-calibration constraints. Some particular motions are analyzed
in Section 6. In order to give some practical insight of critical and near-
critical motions, some experiments are presented in Section 7. Finally,
Section 8 concludes.
2. Background
In this section, we give a brief summary of the modern projective formulation
of visual geometry. Also, some basic concepts in projective and
algebraic geometry are introduced. For further reading, see [6, 24, 33].
A perspective (pinhole) camera is modeled in homogeneous co-ordinates
by the projection equation
world point,
image, P is the 3 \Theta 4 camera projection matrix and ' denotes
equality up to scale. Homogeneous coordinates are used for both image
and object coordinates. In a Euclidean frame, P can be factored, using
a QR-decomposition, cf. [9], as
Here the extrinsic parameters (R; t) denote a 3 \Theta 3 rotation matrix
and a 3 \Theta 1 translation vector, which encode the pose of the camera. The
columns of de-ne an orthogonal base. The standard base is
de-ned by e . The intrinsic
parameters in the calibration matrix K encode the camera's internal
geometry: f denotes the focal length, fl the aspect ratio, s the skew
and the principal point.
A camera for which K is unknown is said to be uncalibrated.
It is well-known that for uncalibrated cameras, it is only possible to
recover the 3D scene and the camera poses up to unknown projective
transformation [8, 10, 35]. This follows directly from the projection
equation (1): Given one set of camera matrices and 3D points that
satis-es (1), another reconstruction can be obtained from
where T is a non-singular 4 \Theta 4 matrix corresponding to a projective
transformation of P 3 .
A quadric in P n is de-ned by the quadratic form
where Q denotes a (n
homogeneous point coordinates. The dual is a quadric envelope, given
by
where \Pi denotes homogeneous coordinates for hyper-planes of dimension
are tangent to the quadric. For non-singular matrices, it
can be shown that Q ' (Q   ) \Gamma1 (see [33] for a proof). A quadric with a
non-singular matrix is said to be proper. Quadrics with no real points
are called virtual. In the plane, are called conics. We
will use C for the 3 \Theta 3 matrix that de-nes the conic points x T
and C   for its dual that de-nes the envelope of tangent lines l T C
(where C   ' C \Gamma1 ). The image of a quadric in 3D-space is a conic, i.e.
the silhouette of a 3D quadric is projected to a conic curve. This can
be expressed in envelope forms as
Projective geometry encodes only cross ratios and incidences. Properties
like parallelism and angles are not invariant under dioeerent projective
coordinate systems. An aOEne space, where properties like parallelism
and ratios of lengths are preserved, can be embedded in a
projective space by singling out a plane at in-nity \Pi 1 . The points on
\Pi 1 are called points at in-nity and be interpreted as direction vectors.
In P 3 , Euclidean properties, like angles and lengths, are encoded by singling
out a proper, virtual conic on \Pi 1 . This absolute
scalar products between direction vectors. Its dual, the dual absolute
quadric\Omega
products between plane
normals.\Omega
1 is a 4 \Theta 4
symmetric rank 3 positive semide-nite matrix, where the coordinate
system is normally chosen such
is\Omega   1 's
unique null
vector:\Omega   1 The similarities or scaled Euclidean
transformations in projective space are exactly those transformations
that
invariant. The transformations that leave \Pi 1 invariant
are the aOEne transformations. The dioeerent forms of the absolute
conic will be abbreviated to (D)AC for (Dual) Absolute C onic.
Given image conics in several images, there may or may not be a
3D quadric having them as image projections. The constraints which
guarantee this in two images are called the Kruppa constraints [22].
In the two-image case, these constraints have been successfully applied
in order to derive the critical sets, e.g. [28]. For the more general case
of multiple images, the projection equation given by (4) can be used for
each image separately.
3. Problem Formulation
The problem of auto-calibration is to -nd the intrinsic camera parameters
denotes the number of camera positions.
In general, auto-calibration algorithms proceed from a projective re-construction
of the camera motion. In order to auto-calibrate, some
constraints have to be enforced on the intrinsic parameters, e.g. vanishing
skew and/or unit aspect ratio. Thus, we require that the calibration
matrices should belong to some proper subset G of the group K of 3 \Theta 3
upper triangular matrices. Once the projective reconstruction and the
intrinsic parameters are known, Euclidean structure and motion are
easily computed.
For a general set of scene points seen in two or more images, there
is a unique projective reconstruction. However, certain special con-g-
urations, known as critical surfaces, give rise to additional ambiguous
solutions. For two cameras, the critical con-gurations occur only if both
camera centres and all scene points lie on a ruled quadric surface [24].
Furthermore, when an alternative reconstruction exists, then there will
always exist a third distinct reconstruction. For more than two cameras,
the situation is less clear. In [25], it is proven that when six scene points
and any number of camera centres lie on a ruled quadric, then there
are three distinct reconstructions. If there are other critical surfaces is
an open problem.
We will avoid critical surfaces by assuming unambiguous recovery
of projective scene structure and camera motion. In other words, the
camera matrices and the 3D scene are considered to be known up to an
unknown projective transformation. We formulate the auto-calibration
problem as follows: If all that is known about the camera motions
and calibrations is that each calibration matrix K i lies in some given
constraint set G ae K, when is a unique auto-calibration possible? More
Problem 3.1. Let G ae K. Then, given the true camera projections
G, is there any projective
transformation T (not a similarity) such that ~
~
calibration matrices ~
lying in
G?
Without constraints on the intrinsic parameters T can be chosen
arbitrarily, so auto-calibration is impossible. Also, T is only de-ned
modulo a similarity,
as such transformations leave K in the decomposition
invariant. Based on the above problem formulation, we can de-ne precisely
what is meant by a motion being critical.
De-nition 3.1. Let G ae K and let (P
denote two projectively
related motions, with calibration matrices (K
respectively. If the two motions are not related by a Euclidean transformation
and
are said to be critical with respect to G.
A motion is critical if there exists an alternative projective motion
satisfying the auto-calibration constraints. Without any additional as-
sumptions, it is not possible to tell which motion is the true one. One
natural additional constraint is that the reconstructed 3D structure
should lie in front of all cameras. In many (but by no means all) cases
this reduces the ambiguity, but it depends on which 3D points are
observed.
According to (4) the image of the absolute
i\Omega
I 0
Thus, knowing the calibration of a camera is equivalent to knowing its
image
Also, if there is a projectively related motion ( ~
the false image of the true absolute conic is the true image of a ifalsej
absolute conic:
i\Omega  ~
T\Omega
i\Omega
T\Omega
virtual quadric of rank 3. This
observation allows us to eliminate the ifalsej motion ( ~
i=1 from the
problem and work only with the true Euclidean motion, but with a false
absolute dual
quadric\Omega
f .
Problem 3.2. Let G ae K. Then, given the true motion
G, is there any other proper, virtual conic
\Omega
f , dioeerent
1 , such that P
i\Omega
Given only a 3D projective reconstruction derived from uncalibrated
images, the
true\Omega 1 is not distinguished in any way from any other
proper, virtual planar conic in projective space. In fact, given any such
potential
conic\Omega
f , it is easy to -nd a 'rectifying' projective transformation
that converts it to the Euclidean DAC
and hence de-nes a false Euclidean structure. To recover the true struc-
ture, we need constraints that single out the
true\Omega 1 and \Pi 1 from all
possible false ones. Thus, ambiguity arises whenever the images of some
non-absolute conic satisfy the auto-calibration constraints. We call such
conics potential absolute conics or false absolute conics. They are
in one-to-one correspondence with possible false Euclidean structures
for the scene.
A natural question is whether the problem is dependent on the actual
values of the intrinsic parameters. We will show that this is not the
case whenever the set G is a proper subgroup of K. Fortunately, according
to the following easy lemma, most of the relevant auto-calibration
constraints are subgroup conditions.
Lemma 3.1. The following constrained camera matrices form proper
subgroups of the 3 \Theta 3 upper triangular matrices K:
(i) Zero skew, i.e.
(ii) Unit aspect ratio, i.e.
(iii) Vanishing principal point, i.e.
(iv) Unit focal length, i.e.
(v) Combinations of the above conditions.
Independence of the values of the intrinsic camera parameters is
shown as follows:
Lemma 3.2. Let G i 2 G for m, where G is a proper subgroup
of K. Then, the motion (P
is critical w.r.t. G if and only if the
motion
is critical w.r.t. G.
Proof. If
is critical with the alternative motion ( ~
calibrations
are also
critical, because G i K
by the closure of G under multipli-
cation. The converse also holds with G \Gamma1
, by the closure of G under
inversion.
Camera matrices with prescribed parameters do not in general form
a subgroup of K, but it suOEces for them to be of the more general form
known matrix and K belongs to a proper subgroup of
K. For example, the set of all camera matrices with known focal length
f has the form 2f 0 0
The invariance with respect to calibration parameters simpli-es things,
especially if one chooses G
m. With this in mind,
we restrict our attention to proper subgroups of K and formulate the
problem as follows.
Problem 3.3. Let G ae K be a proper subgroup. Then, given the true
motion
for calibrated cameras, where
any other false absolute
conic\Omega
f , dioeerent
i]\Omega
~
where ~
4. Approach
We want to explicitly characterize the critical motions (relative camera
placements) for which particular auto-calibration constraints are insuf-
-cient to uniquely determine Euclidean 3D structure. We assume that
projective structure is available. Alternative Euclidean structures correspond
one-to-one with possible locations for a potential absolute conic
in P 3 . Initially, any proper virtual projective plane conic is potentially
absolute, so we look for such
conics\Omega   whose images also satisfy the
given auto-calibration constraints. Ambiguity arises if and only if more
than one such conic exists. We work with the true camera motion in
a Euclidean frame where the true absolute
conic\Omega 1 has its standard
coordinates.
Several general invariance properties help to simplify the problem:
Calibration invariance: As shown in the previous section, if the auto-calibration
constraints are subgroup conditions, the speci-c parameter
values are irrelevant. Hence, for the purpose of deriving critical motions,
we are free to assume that the cameras are in fact secretly calibrated,
even though we do not assume that we know this. (All that
we actually know is K which does not allow some image conics
I to be excluded outright).
Rotation invariance: For known-calibrated cameras, K i can be set to
identity, and thus the image !
I of any false AC must be identical
to the image of the true one. Since
i\Omega
i\Omega
hold for any rotation R, the image !
i is invariant to camera rota-
tions. Hence, criticality depends only on the camera centres, not on
their orientations. More generally, any camera rotation that leaves the
auto-calibration constraints intact is irrelevant. For example, arbitrary
rotations about the optical axis and 180 ffi AEips about any axis in the
optical plane are irrelevant if (a; s) is either (1; 0) or unconstrained,
and
Translation invariance: For true or false absolute conics on the plane
at in-nity, translations are irrelevant so criticality depends only on
camera orientation.
In essence, Euclidean structure recovery in projective space is a matter
of parameterizing all of the possible proper virtual plane conics, then
using the auto-calibration constraints on their images to algebraically
eliminate parameters until only the unique true absolute conic remains.
More abstractly, if C parameterizes the possible conics and X the camera
geometries, the constraints cut out some algebraic variety in (C; X)
space. A constraint set is useful for Euclidean structure from motion
recovery only if this variety generically intersects the subspaces
in one (or at most a few) points (C; X 0 ), as each such intersection represents
an alternative Euclidean structure for the reconstruction from
that camera geometry. A set of camera poses X is critical for the
constraints if it has exceptionally (e.g. in-nitely) many intersections.
Potential absolute conics can be represented in several ways. The
following parameterizations have all proven relatively tractable:
(i) Choose a Euclidean frame in
which\Omega
f is diagonal, and express
all camera poses relative this frame [36, 37]. This is symmetrical with
respect to all the images and usually gives the simplest equations. How-
ever, in order to -nd explicit inter-image critical motions, one must
revert to camera-based coordinates which is sometimes delicate. The
cases of a -nite false absolute conic and a false conic on the plane at
in-nity must also be treated separately,
e.g.\Omega
with either d 3 or d 4 zero.
(ii) Work in the -rst camera frame,
encoding\Omega
f by its -rst image !  and supporting plane (n T ; 1). Subsequent images !
are
given by the inter-image homographies H
is the i th camera pose. The output is in the -rst camera frame and
remains well-de-ned even if the conic tends to in-nity, but the algebra
required is signi-cantly heavier.
Parameterize\Omega
f implicitly by two images !
2 subject to the
Kruppa constraints. In the two-image case this approach is both relatively
simple and rigorous - two proper virtual dual image conics
satisfy the Kruppa constraints if and only if they de-ne a (pair of)
corresponding 3D potential absolute conics - but it does not extend
so easily to multiple images.
The derivations below are mainly based on method (i) .
5. Critical Motions
In this section, the varieties of critical motions are derived. In most
situations, the problem is solved in two separate cases. One is when
there are potential absolute conics on the plane at in-nity, \Pi 1 , and the
other one is conics outside \Pi 1 . If the potential conics are all on \Pi 1 , it is
still possible to recover \Pi 1 and thereby obtain an aOEne reconstruction.
Otherwise, the recovery of aOEne structure is ambiguous, and we say that
the motion is critical with respect to aOEne reconstruction.
The following constraints on the camera calibration are considered:
(i) known intrinsic parameters,
(ii) unknown focal lengths, but the other intrinsic parameters known,
(iii) known skew and aspect ratio.
These constraints form a natural hierarchy and they are perhaps the
most interesting ones from a practical point of view. In Section 3, it
was shown in that it is suOEcient to study the normalized versions of
the auto-calibration constraints, since critical motions are independent
of the speci-c values of the intrinsic parameters. That is, when some of
the intrinsic parameters are known, e.g. the principal point is (10; 20),
we may equivalently analyze the case of principal point set to (0; 0).
The corresponding camera matrices give rise to subgroup conditions
according to Lemma 3.1.
5.1. Known intrinsic parameters
We start with fully calibrated perspective cameras. The results may not
come as a surprise, but it is important to know that there are no other
possible degenerate con-gurations.
Proposition 5.1. Given projective structure and calibrated perspective
cameras at m - 3 distinct -nite camera centres, Euclidean structure
can always be recovered uniquely. With distinct camera centres,
there is always exactly a twofold ambiguity.
Proof. Assuming that the cameras have does not change the
critical motions. The camera orientations are irrelevant because any
false absolute conic must have the same (rotation invariant) images as
the true one. Calibrated cameras never admit false absolute conics on
as the (known) visual cone of each image conic can intersect \Pi 1
in only one conic, which is the true absolute conic. Therefore, consider
a -nite absolute
conic\Omega
f , with supporting plane outside \Pi 1 . As all
potential absolute conics are proper, virtual and positive semi-de-nite
[34, 37], a Euclidean coordinate system can be chosen such
f has
supporting plane z = 0, and matrix coordinates
\Omega
Since the cameras are calibrated, their orientations are
the conic projection (4) in each camera becomes
\Gammat]\Omega
y
x
z
z
x
y
x
y
x
z
z y1
optical centre

Figure

1. A twisted pair of reconstructions.
As the conic should be proper, both d 4 6= 0 and t 3 6= 0, which gives
Thus the only solutions are t
and\Omega
implies that there
are at most two camera centres, and the false conic is a circle of imaginary
radius i z, centred in the plane bisecting the two camera centres

In the two-image case, the improper self-inverse projective transfor-
mation
interchanges the
true\Omega
1 and the
f , according to
T\Omega
'\Omega  and takes the two projection matrices P to
While the -rst camera remains -xed, the other has rotated 180 ffi about
the axis joining the two centres. This twofold ambiguity corresponds exactly
to the well-known twisted pair duality [23, 18, 27]. The geometry
of the duality is illustrated in Figure 1.
The 'twist' T represents a very strong projective deformation that
cuts the scene in half, moving the plane between the cameras to in-nity,
see

Figure

2. By considering twisted vs. non-twisted optical ray intersec-
tions, one can also show that it reverses the relative signs of the depths,
so for one of the solutions the structure will appear to be behind one
visual
optical centre
supporting
planes
potential
conics
cone

Figure

2. Intersecting the visual cones of two image conics satisfying the Kruppa
constraints generates a pair of 3D conics, corresponding to the two solutions of the
twisted pair duality.
camera, cf. [17]. To conclude, Proposition 5.1 states that any two-view
geometry has a 'twisted pair' projective involution symmetry and any
camera con-guration with three or more camera centres has a unique
projective-to-Euclidean upgrade.
5.2. Unknown focal lengths
In the case of two images and internally calibrated cameras modulo
unknown focal lengths, it is in general possible to recover Euclidean
structure. Since we know that the solutions always occur in twisted pairs
(which can be disambiguated using the positive depth constraint), it is
more relevant to characterize the motions for which there are solutions
other than the twisted pair duality. Therefore, the two-camera case will
be dealt with separately, after having derived the critical motions for
arbitrary many images.
5.2.1. Many images
If all intrinsic parameters are known except for the focal lengths, the
camera matrix can be assumed to be which in turn
implies that the image of a potential absolute conic satis-es
We start with potential absolute conics on \Pi 1 .
Potential absolute conics on \Pi 1
Let C f denote a 3 \Theta 3 matrix corresponding to a false absolute conic
(in locus form) on the plane at in-nity. Since C f is not the true one,
I. The image of C f is according to (4)
Notice that criticality is independent of translation of the camera.
Two cameras are said to have the same viewing direction if their
optical axes are parallel or anti-parallel.
Proposition 5.2. Given \Pi 1 and known skew, aspect ratio and principal
point, then a motion is critical if and only if there is only one
viewing direction.
Proof. Choose coordinates in which camera 1 has orientation R
Suppose a motion is critical. According to (6) and (7), this implies that
3 for some - ? \Gamma1. For camera 2, let
apply (7),
I
This implies that r in turn, R
which is equivalent
to a -xed viewing direction of the camera. Conversely, suppose the
viewing direction is -xed, which means that R
Then, it is not possible to disambiguate between any of the potential
absolute conics in the pencil C f (-) ' I
3 , since R i C f R T
Potential absolute conics outside \Pi 1
Assume we have a critical motion (R
with the false dual absolute
conic\Omega
f . If the supporting plane
f is \Pi 1 , the critical motion is
described by Proposition 5.2, so assume
f is outside \Pi 1 . As in
the proof of Proposition 5.1, one can assume without loss generality
that a Euclidean coordinate system has been chosen such
f has
supporting plane z = 0, and matrix coordinates
\Omega
The image
of\Omega
f is according to (4),
i\Omega
d 2i
optical centres
critical ellipse
critical hyperbola

Figure

3. Two orthogonal planes, where one plane contains an ellipse and the other
contains a hyperbola.
A necessary condition for degeneracy is that R i should diagonalize C f to
the form (6), i.e. the matrix C f must have two equal eigenvalues. As it
is always possible to -nd an orthogonal matrix that diagonalizes a real,
symmetric matrix [5], all we need to do is to -nd out precisely when C f
has two equal eigenvalues. Lemma A.1 in the Appendix characterizes
matrices of this form.
Applying the lemma to C f in (8), with oe
results in the following cases:
(i) If d 1 6= d 2 , then
a.
b.
These equations describe a motion on two planar conics for which
the supporting planes are orthogonal. On the -rst plane, the conic
is an ellipse, while on the other the conic is a hyperbola (depending
on whether d 1 ? d 2 or vice versa), see Figure 3.
(ii) If d arbitrary.
Notice that the second alternative in case (ii) of Lemma A.1 does
not occur, since it implies t T e making C f rank-de-cient. Also,
case (iii) is impossible, since oe
It remains to -nd the rotations that diagonalize C f . Since rotations
around the optical axis are irrelevant, only the direction of the optical
axis is signi-cant. Suppose the optical axis is parameterized by the
camera centre t and a direction d, i.e. Rg. Any point on
the axis projects to the principal point,
The direction d should equal the third row of R, which corresponds
to the eigenvector of the single eigenvalue of C f . Regarding the proof
of Lemma A.1, it is not hard to see that the eigenvectors are v '
in the two sub-cases
in (i) above. Geometrically, this means that the optical axis must
be tangent to the conic at each position, as illustrated in Figure 4(b).
Similarly in (ii), it is easy to derive that which means
that the optical axis should be tangent to the translation direction, cf.

Figure

4(c). An exceptional case is when C f has a triple eigenvalue,
because then any rotation is possible. However, according to Proposition
5.1, it occurs only for twisted pairs. To summarize, we have proven
the following.
Proposition 5.3. Given known intrinsic parameters except for focal
lengths, a motion is critical w.r.t. aOEne reconstruction if and only if
the motion consists of (i) rotations with at most two distinct centres
(twisted pair ambiguity), or (ii) motion on two conics 1 (one ellipse and
one hyperbola) whose supporting planes are orthogonal and where the
optical axis is tangent to the conic at each position, or (iii) translation
along the optical axis, with arbitrary rotations around the optical axis.
The motions are illustrated in Figure 4. In case (i) and (ii), the
ambiguity of the reconstruction is twofold, as there is only one false
absolute conic, whereas in case (iii) there is a one-parameter family of
potential planes at in-nity (all planes z=constant). Case (iii) can be
seen as a special case of the critical motion in Proposition 5.2, which
also has a single viewing direction, but arbitrary translations.
5.2.2. Two images
For two cameras, projective geometry is encapsulated in the 7 degrees
of freedom in the fundamental matrix, and Euclidean geometry in the
5 degrees of freedom in the essential matrix. Hence, from two projective
images we might hope to estimate Euclidean structure plus two
additional calibration parameters. Hartley [10, 11] gave a method for
the case where the only unknown calibration parameters are the focal
lengths of the two cameras. This was later elaborated by Newsam et. al.
1 The actual critical motion is the conics minus the two points where the ellipse
intersects the plane z = 0, since the image !   is non-proper at these points.
potential
conic
absolute
optical centre
(b)
conic
potential
absolute
optical centres
critical ellipse
critical hyperbola
(c)
conic
potential
optical centres
absolute

Figure

4. Critical motions for unknown focal lengths: (a) A motion with two -xed
centres. (b) A planar motion on an ellipse and a hyperbola. (c) Translation along
the optical axis. See Proposition 5.3.
y
x
x
z z y
(b)
x
x
y

Figure

5. Critical con-gurations for two cameras: (a) Intersecting optical axes. (b)
Orthogonal optical axis planes. See Proposition 5.4.
[28], Zeller and Faugeras [41] and Bougnoux [4]. All of these methods
are Kruppa-based. We will derive the critical motions for this case based
on the results of the previous sections.
Proposition 5.4. Given zero skew, unit aspect ratio, principal point
at the origin, but unknown focal lengths for two cameras, then a motion
(in addition to twisted pair) is critical if and only if (i) the optical axes
of the two cameras intersect or (ii) the plane containing the optical axis
of camera 1 and camera centre 2, is orthogonal to the plane containing
optical axis of camera 2 and camera centre 1.
Proof. Cf. [28]. Suppose a motion is critical. Regarding Proposition 5.2,
we see that if there is only one viewing direction, the optical axes are
parallel and intersect at in-nity, leading to (i) above. Examining the
three possibilities in Proposition 5.3, we see that the -rst one is the
twisted pair solution. The second one, either both cameras lie on the
same conic (and hence their axes are coplanar and intersect) or one lies
on the hyperbola, the other on the ellipse (in which case their optical
axes lie in orthogonal planes) leading to (ii). Conversely, given any two
cameras with intersecting or orthogonal-plane optical axes, it is possible
to -t (a one-parameter family of) conics through the camera centres,
tangential to the optical axes.
The two critical camera con-gurations are shown in Figure 5.
5.3. Known skew and aspect ratio
Consider the image !
of\Omega
1 . Inserting the parameterization
of K in (2) into its dual !, it turns out that !
. Since f and fl
never vanish, requiring that the skew vanishes is equivalent to !
The constraint can also be expressed in envelope form using !
dually !
If in addition to zero skew, unit aspect ratio is required in K, it is
equivalent to ! 22 . This follows from the fact that !
and
. The constraint can also be transfered to !   ,
dually !
Analyzing the above constraints on ! in locus form, results in the
following proposition when the plane at in-nity \Pi 1 is known.
Proposition 5.5. Given \Pi 1 , a motion is critical with respect to zero
skew and unit aspect ratio if and only if there are at most two viewing
directions.
Proof. For each image we have the two auto-calibration constraints (9),
given by (7). Choose 3D coordinates in which the -rst
camera has orientation R I. The image 1 constraints become simply
so we can parameterize C f with C 11 , C 12 and C 13 .
Given a subsequent image 2, represent its orientation R 2 by a quaternion
its two auto-calibration constraints, and
eliminate C 11 between them to give:
One of the 3 factors must vanish. If the -rst vanishes the motion is an
optical axis rotation, q 2
If the second vanishes it is a 180 ffi AEip
about an axis orthogonal to the optical one, q 2
In both cases
the viewing direction remains unchanged and no additional constraint
is enforced on C f . Finally, if the third factor vanishes, solving for C f in
terms of q gives a linear family of solutions of the form
(the third row of R 2 (q)) are the two
viewing directions and (ff; fi) are arbitrary parameters. Conversely, given
any potential AC C f 6' I, there is always exactly one pair of real
viewing directions that make C f critical under (11). The linear
family ff contains three rank 2 members, one for each eigenvalue
- of C f (with fi 0 =ff calculation shows that each
member can be decomposed uniquely (up to sign) into a pair
of viewing direction vectors supporting (11), but only the pair
corresponding to the middle eigenvalue is real. (Coincident eigenvalues
correspond to coincident viewing directions and can be ignored). Hence,
no potential AC C f can be critical for three or more real directions
simultaneously.

Table

I. Summary of critical motions in auto-calibration.
Auto-calibration Critical motions Reconstruction
constraint ambiguity
Known calibration twisted pair duality projective
Unknown focal length (i) optical axis rotation aOEne
but otherwise known (ii) motion on two planar conics projective
calibration (iii) optical axis translation projective
Unknown focal length (i) intersecting optical axes projective
(two images only) (ii) orthogonal optical axis planes projective
Zero skew and (i) two viewing directions aOEne
unit aspect ratio (ii) complicated algebraic variety projective
For potential absolute conics outside \Pi 1 things are more compli-
cated. For each image, there are two auto-calibration constraints. So
in order to single out the true absolute conic (which has 8 degrees of
freedom), at least 4 images are necessary. For a
f the polynomial
constraints in (9) and (10) determine a variety in the space of rigid
motions. We currently know of no easy geometrical interpretation of
this manifold.
It is easy to see that given a critical camera motion, the ambiguity
is not resolved by rotation around the camera's optical axis.
5.4.

Summary

A summary of the critical motions for auto-calibration under the auto-calibration
constraints studied is given in Table I. The reconstruction
ambiguity is classi-ed as projective if the plane at in-nity cannot be
uniquely recovered, and aOEne if it is possible. As mentioned earlier, the
twisted pair duality is not a true critical motion, since the positive-depth
constraint can always resolve the ambiguity.
6. Particular Motions
Some critical motions occur frequently in practice. In this section, a
selection of them is analyzed in more detail.
6.1. Pure rotation
In the case of a stationary camera performing arbitrary rotations, no 3D
reconstruction is possible. There always exist many potential absolute
conics outside \Pi 1 .
However, it is still possible to recover the internal camera calibration,
provided there are no potential absolute conics on \Pi 1 , cf. [37]. Proposition
5.2 and Proposition 5.5, regarding critical motions and potential
ACs on \Pi 1 tells us when such auto-calibration is possible for a purely
rotating camera.
6.2. Pure translation
If a sequence of movements only consists of arbitrary translations and
no rotations, all proper, virtual conics on \Pi 1 are potential absolute
conics. Still, one could hope to recover the plane at in-nity correctly,
and thus get an aOEne reconstruction.
Proposition 6.1. Let (t
be a general sequence of translations,
where m is suOEciently large. Then, the motion is
(i) always critical w.r.t. aOEne reconstruction under the constraints zero
skew and unit aspect ratio.
(ii) not critical w.r.t. aOEne reconstruction under the constraints zero
skew, unit aspect ratio and vanishing principal point.
Proof. (i) We need to show that there exists a potential
DAC\Omega
f outside
which is valid for all
. Choose a coordinate system such that
\Theta
I

. Then for
instance\Omega
is a potential DAC
(multiply P
i\Omega
i to get !   and check that it ful-lls (9) and (10)). (ii)
follows directly from Proposition 5.3.
Note that translating only along the optical axis in case (ii) above results
in a critical motion.
6.3. Parallel axis rotations
Sequences of rotations around parallel axes with arbitrary translations
are interesting in several aspects. They occur frequently in practice and
are one of the major degeneracies for auto-calibration with constant
intrinsic parameters [36, 43]. See Figure 6.
It follows directly from Proposition 5.5 that given zero skew, unit
aspect ratio and general rotation angles, the -xed-axis motion is not
critical unless it is around the optical axis. If we further add the vanishing
principal point constraint, the optical axis remains critical according

Figure

6. Rotations around the vertical axes with arbitrary translations.
to Proposition 5.2. If we know only that the skew vanishes, we have the
following proposition.
Proposition 6.2. Let (R
be a general motion whose rotations
are all about parallel axes, where R suOEciently large.
Given \Pi 1 , the motion is critical w.r.t. zero skew if and only if the
rotation is around one of the following axes:
or (1; \Gamma1; 0),
where each   denotes an arbitrary real number.
Proof. Let C f denote a false AC on \Pi 1 . The zero skew constraint in
using the parameterization in (7) gives C
arbitrary rotation around a -xed axis (q can be parameterized
by R. Inserting this into the zero skew constraint in
yields a polynomial in R[-]. Since - can be arbitrary all coeOEcients of
the polynomial must vanish. The solutions to the system of vanishing
coeOEcients are the ones given above.
Some of these critical axes may be resolved by requiring that the
camera calibration should be constant. In [37], it is shown that parallel
axis rotations under constant intrinsic parameters are always critical
and give rise to the following pencil of potential absolute conics:
Combining constant intrinsic parameters, and some a priori known
values of the intrinsic parameters, some of the critical axes are still
critical.
Corollary 6.1. Let (R
be a general motion with parallel axis
rotations, where R suOEciently large. Given \Pi 1 , and
constant intrinsic parameters, the following axes are the only ones still
critical:
(ii) (0; 0; 1) w.r.t. zero skew and unit aspect ratio,
w.r.t. an internally calibrated camera except for focal length.
Proof. (i) Using the potential ACs in (12) in the proof of Proposition
6.2, one -nds that the only critical axes remaining under the
zero skew constraint are (0;  ;  ) and ( ; 0;  ). (ii) and (iii) are proved
analogously.
7. Experiments
In practice, a motion is never exactly degenerate due to measurement
noise and modeling discrepancies. However, if the motion is close to
a critical manifold it is likely that the reconstructed parameters will
be inaccurately estimated. To illustrate the typical eoeects of critical
motions, we have included some simple synthetic experiments for case
of two cameras with unknown focal lengths but other intrinsic parameters
known. We focus on the question of how far from critical the two
cameras must be to give reasonable estimates of focal length and 3D
Euclidean structure [20]. The experimental setup is as follows: two unit
focal length perspective cameras view 25 points distributed uniformly
within the unit sphere. The camera centres are placed at (\Gamma2; \Gamma2;
and (2; \Gamma2; 0) and their optical axes intersect at the origin, similar to
the setup in Figure 5(a). Independent Gaussian noise of 1 pixel standard
deviation is added to each image point in the 512 \Theta 512 images.
In the experiment, the elevation angles are varied, upwards for the
left camera and downwards for the right one, so that their optical axes
are skewed and no longer meet. For each pose, the projective structure
Unknown focal bundle: -
Focal
Length
Elevation Angle (degrees)
Unknown focal bundle: -
Calibrated bundle: -x-
Point
Elevation Angle (degrees)

Figure

7. Relative errors vs. camera elevation for two cameras.
and the fundamental matrix are estimated by a projective bundle adjustment
that minimises the image distance between the measured and
reprojected points [3]. Then, the focal lengths are computed analytically
with Bougnoux' method [4]. For comparison, a calibrated bundle
adjustment with known focal lengths is also applied to the same data.
The resulting 3D error is calculated by Euclidean alignment of the true
and reconstructed point sets.

Figure

7 shows the resulting root mean square errors over 100 trials
as a function of elevation angle. At zero elevation, the two optical
axes intersect at the origin. This is a critical con-guration according
to Proposition 5.4. A second critical con-guration occurs when the
epipolar planes of the optical axes become orthogonal at around 35 ffi
elevation. Both of these criticalities are clearly visible in both graphs.
For geometries more than about 5-10 ffi from criticality, the focal lengths
can be recovered quite accurately and the resulting Euclidean 3D structure
is very similar to the optimal 3D structure obtained with known
calibration.
8. Conclusion
In this paper, the critical motions in auto-calibration under several auto-calibration
constraints have been derived. The various constraints on
the intrinsic parameters have been expressed as subgroup conditions on
the 3 \Theta 3 upper triangular camera matrices. With this type of condition,
we showed that the critical motions are independent of the speci-c
values of the intrinsic parameters.
It is important to be aware of the critical motions when trying to
auto-calibrate a camera. Additional scene or motion constraints may
help to resolve the ambiguity, but clearly the best way to avoid degeneracies
is to use motions that are ifarj from critical. Some synthetic
experiments have been performed that give some practical insight to the
numerical conditioning of near-critical and critical stereo con-gurations.

Acknowledgments

This work was supported by the European Union under Esprit project
LTR-21914 Cumuli. We would like to thank Sven Spanne for constructing
the proof of Lemma A.1.


Appendix


Lemma A.1. Let A be a real, symmetric 3 \Theta 3 matrix of the form
real
3 vector and ae a non-zero real scalar. Let oe 1 ,oe 2 and oe 3 be given real
scalars. Then, necessary and suOEcient conditions on (t,ae) for A to have
two equal eigenvalues can be divided into three cases:
for at least one i (where
or 3). Furthermore, ae can take the values:
for any i for which t T e
(ii) If oe
a. t T e
b. t T e
(iii) If oe arbitrary.
Proof. It follows from the Spectral Theorem [5] that if A is real and
symmetric with two equal eigenvalues -, then there is a third eigenvector
v and a scalar - such that
corresponding to v is -). This gives
Multiplying this matrix equation with e 1 , e 2 and e 3 , results in three
vector equations,
To prove (i), assume oe 1 6= oe 2 6= oe 3 . The orthogonal bases e 1 , e 2 and
e 3 are linearly independent and cannot all be linear combinations of t
and v, so one of oe must vanish, and thereby exactly one. Suppose
If one of the coeOEcients is non-zero, then t and v would be linearly
dependent. However, this is impossible because e 2 and e 3 are linearly
independent and oe Analogously, ae 6= 0 because
otherwise e 2 and e 3 would be linearly dependent according to (13).
Therefore t T e
If t is orthogonal to e 1 and calculations yield that
ae must be chosen as
which is also suOEcient.
When two or three of oe i are equal, similar arguments
can be used to deduce (ii) and (iii).



--R



Close Range Photogrammetry and Machine Vision.

Matrices and Linear Transformations.



Matrix Computation.



Handbuch der Physiologischen Optik.










Theory of Reconstruction from Image Motion.








Algebraic Projective Geometry.
Analytical Quadrics.


'Vision 3D Non Calibr#e: Contributions # la Reconstruction Projective et #tude des Mouvements Critiques pour l'Auto-Calibrage'






--TR
Multiple Interpretations of the Shape and Motion of Objects from Two Perspective Images
A theory of self-calibration of a moving camera
Three-dimensional computer vision
Reconstruction from Calibrated CamerasMYAMPERSANDmdash;A New Proof of the Kruppa-Demazure Theorem
Estimation of Relative Camera Positions for Uncalibrated Cameras
Camera Self-Calibration
What can be seen in three dimensions with an uncalibrated stereo rig
Self-Calibration from Image Triplets
Euclidean 3D Reconstruction from Image Sequences with Variable Focal Lenghts
Minimal Conditions on Intrinsic Parameters for Euclidean Reconstruction
Autocalibration and the absolute quadric
Euclidean Reconstruction from Image Sequences with Varying and Unknown Focal Length and Principal Point
Critical Motion Sequences for Monocular Self-Calibration and Uncalibrated Euclidean Reconstruction
Metric calibration of a stereo rig
The Modulus Constraint
Euclidean Reconstruction from Constant Intrinsic Parameters
Ambiguity in Reconstruction From Images of Six Points
From Projective to Euclidean Space Under any Practical Situation, a Criticism of Self-Calibration
Self-Calibration and Metric Reconstruction in spite of Varying and Unknown Internal Camera Parameters

--CTR
Antonio Valds , Jos Ignacio Ronda, Camera Autocalibration and the Calibration Pencil, Journal of Mathematical Imaging and Vision, v.23 n.2, p.167-174, September 2005
Gang Qian , Rama Chellappa, Bayesian self-calibration of a moving camera, Computer Vision and Image Understanding, v.95 n.3, p.287-316, September 2004
P. Sturm , Z. L. Cheng , P. C. Y. Chen , A. N. Poo, Focal length calibration from two views: method and analysis of singular cases, Computer Vision and Image Understanding, v.99 n.1, p.58-95, July 2005
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
Toms Svoboda , Daniel Martinec , Toms Pajdla, A convenient multicamera self-calibration for virtual environments, Presence: Teleoperators and Virtual Environments, v.14 n.4, p.407-422, August 2005
Kalle strm , Fredrik Kahl, Ambiguous Configurations for the 1D Structure and Motion Problem, Journal of Mathematical Imaging and Vision, v.18 n.2, p.191-203, March
Lourdes Agapito , E. Hayman , I. Reid, Self-Calibration of Rotating and Zooming Cameras, International Journal of Computer Vision, v.45 n.2, p.107-127, November 2001
Loong-Fah Cheong , Chin-Hwee Peh, Depth distortion under calibration uncertainty, Computer Vision and Image Understanding, v.93 n.3, p.221-244, March 2004
Xiaochun Cao , Jiangjian Xiao , Hassan Foroosh , Mubarak Shah, Self-calibration from turn-table sequences in presence of zoom and focus, Computer Vision and Image Understanding, v.102 n.3, p.227-237, June 2006
Han , Takeo Kanade, Multiple Motion Scene Reconstruction with Uncalibrated Cameras, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.7, p.884-894, July
Marta Wilczkowiak , Peter Sturm , Edmond Boyer, Using Geometric Constraints through Parallelepipeds for Calibration and 3D Modeling, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.2, p.194-207, February 2005
critical motions;absolute conic;calibration;structure and motion;projective geometry;auto-calibration;3D reconstruction