Observability of 3D Motion.
This paper examines the inherent difficulties in observing 3D rigid motion from image sequences. It does so without considering a particular estimator. Instead, it presents a statistical analysis of all the possible computational models which can be used for estimating 3D motion from an image sequence. These computational models are classified according to the mathematical constraints that they employ and the characteristics of the imaging sensor (restricted field of view and full field of view). Regarding the mathematical constraints, there exist two principles relating a sequence of images taken by a moving camera. One is the epipolar constraint, applied to motion fields, and the other the positive depth constraint, applied to normal flow fields. 3D motion estimation amounts to optimizing these constraints over the image. A statistical modeling of these constraints leads to functions which are studied with regard to their topographic structure, specifically as regards the errors in the 3D motion parameters at the places representing the minima of the functions. For conventional video cameras possessing a restricted field of view, the analysis shows that for algorithms in both classes which estimate all motion parameters simultaneously, the obtained solution has an error such that the projections of the translational and rotational errors on the image plane are perpendicular to each other. Furthermore, the estimated projection of the translation on the image lies on a line through the origin and the projection of the real translation. The situation is different for a camera with a full (360 degree) field of view (achieved by a panoramic sensor or by a system of conventional cameras). In this case, at the locations of the minima of the above two functions, either the translational or the rotational error becomes zero, while in the case of a restricted field of view both errors are non-zero. Although some ambiguities still remain in the full field of view case, the implication is that visual navigation tasks, such as visual servoing, involving 3D motion estimation are easier to solve by employing panoramic vision. Also, the analysis makes it possible to compare properties of algorithms that first estimate the translation and on the basis of the translational result estimate the rotation, algorithms that do the opposite, and algorithms that estimate all motion parameters simultaneously, thus providing a sound framework for the observability of 3D motion. Finally, the introduced framework points to new avenues for studying the stability of image-based servoing schemes.
Introduction
Visual Servoing and Motion Estimation
A broad definition of visual servoing amounts to the control of motion on the basis of image analysis. Thus,
a driver adjusting the turning of the wheel by monitoring some features in the scene, a system attempting to
insert a peg through a hole, a controller at some control panel perceiving a number of screens and adjusting a
number of levers, a navigating system trying to find its home, all perform visual servoing tasks. Such systems
must respond "appropriately" to changes in their environment; thus, on a high level, they can be described as
evolving or dynamical systems, which can be represented as a function from states and control signals to new
states; both the states and the control variables may be functions of time. One approach to controlling such a
system is to design an observer or state estimator to obtain an estimate of the state; for example, this estimator
might implement a partial visual recovery process. This estimate is used by a controller or state regulator to
compute a control signal to drive the dynamical system. Ideally, observation and control are separable in the sense
that if we have an optimal controller and an optimal observer then the control system that results from coupling
the two is guaranteed to be optimal [13]. Different agents, i.e., dynamical systems, have different capabilities and
different amounts of memory, with simple reactive systems at one end of the spectrum and highly sophisticated
and flexible systems, making use of scene descriptions and reasoning processes, at the other end.
In the first studies on visual control, efforts concentrated on the upper echelon of this spectrum, trying to
equip systems with the capability of estimating accurate 3D motion and the shape of the environment. Assuming
that this information could be acquired exactly, sensory feedback robotics was concerned with the planning and
execution of the robot's activities. This was characterized as the ``look and move'' approach and the servoing
approaches were "position-or-scene-based." The problem with such separation of perception from action was
that both computational goals turned out to be very difficult. On the one hand, the reconstruction of 3D
motion and shape is hard to achieve accurately and, in addition, many difficult calibration problems had to be
addressed. On the other hand, spatial planning and motion control are very sensitive to errors in the description
of the spatiotemporal environment. After this realization and with the emergence of active vision [3-6], attention
turned to the lower part of the spectrum, minimizing visual processing and placing emphasis on the regulator,
as opposed to the estimator. One of the main lessons learned from research on the static look and move control
strategy was that there ought to be easier things to do with images than using them to compute 3D motion and
shape. This led to formulations of visual servoing tasks which were such that the controller had to act on the
image, i.e., to move the manipulator's joints in such a way that the scene ends up looking a particular way. In
technical terms, the controller had to act in such a way that specific coordinate systems (hand, eye, scene, etc.)
were put in a particular relationship with each other. Furthermore, this relationship could be realized by using
directly available image measurements as feedback for the control loop. This approach is known as image-based
robot servoing [16, 18, 21], and in recent years it has given very interesting research results [14, 23, 24, 28]. Most
of these results deal with the computation of the image Jacobian (i.e., the differential relationship between the
camera frame and the scene frame), along with the camera's intrinsic and extrinsic parameters.
Regardless of the philosophical approach one adopts in visual servoing (scene-based or image-based), the
essential aspects of the problem amount to the recovery of the relationship between different coordinate systems
(such as the ones between camera, gripper, robot, scene, object, etc. This could be the relationship itself or a
representation of the change of the relationship. Since a servoing system is in general moving (or observing moving
parts), a fundamental problem is the recovery of 3D motion from an image sequence. Whether this recovery is
explicit or implicit, without it the relationships between different coordinate frames cannot be maintained, and
servoing tasks cannot be achieved. Thus, it is important to understand how accurately 3D motion can be observed,
in order to understand how successfully servoing can be accomplished. Experience has shown that in practice
3D motion is very difficult to accurately observe, involving many ambiguities and sensitivities. Are there any
regularities in which the ambiguity in 3D motion expresses itself? In trying to estimate 3D motion, do the
introduced errors satisfy any constraints? As 3D rigid motion consists of the sum of a translation and a rotation,
are there differences in the inherent ambiguities governing the recovery of the different components of 3D motion?
In addition, we need to study this question independently of specific optimization algorithms. This is the problem
studied in this paper.
2 The Approach
There is a veritable cornucopia of techniques for estimating 3D motion but our approach should be algorithm
independent, in order for the results to be of general use. Equivalently, our approach should encompass all the
possible computational models that can be used to estimate 3D motion from image sequences. To do so, we need
to classify all possible approaches to 3D motion on the basis of the input used and the mathematical constraints
that are employed.
As a system moves in some environment, every point in the scene has a velocity with regard to the system.
The projection of these velocity vectors on the system's eye constitutes the so-called motion field. An estimate
of the motion field, called optical flow, starts by first estimating the spatiotemporal derivatives of the image
intensity function. These derivatives comprise the so-called normal flow which is the component of the flow along
the local image gradient, i.e., normal to the local edge. A system could start 3D motion estimation using normal
flow as input or it could first attempt to estimate the optical flow, though that is a very difficult problem, and
subsequently 3D motion. This means that an analysis of the difficulty of 3D motion estimation must consider
both inputs, optic flow fields and normal flow fields, and algorithms in the literature use one or the other input.
Regarding the mathematical constraints through which 3D motion is encoded in the input image motion,
extensive work in this area has established that there exist only two such constraints if no information about the
scene is available. The first is the "epipolar constraint" and the second, the "positive depth constraint." The
epipolar constraint ensures that corresponding points in the sequence are the projection of the same point in the
scene. The positive depth constraint requires that the depth of every scene point be positive, since the scene is
in front of the camera. Since knowledge of normal flow does not imply knowledge of corresponding points in the
sequence, the epipolar constraint cannot be used when normal flow is available.
The epipolar constraint has attracted most work. It can only be used when optic flow is available. Since many
measurements are present, one develops a function that represents deviation from the epipolar constraint all over
the image. A variety of approaches can be found in the literature using different metrics in representing epipolar
deviation and using different techniques to seek the optimization of the resulting functions. Furthermore, there
exist techniques that first estimate rotation and, on the basis of the result subsequently estimate translation
[9, 36, 37]; techniques that do the opposite [1, 22, 26, 31, 33, 38, 40]; and techniques that estimate all motion
parameters simultaneously [7, 8, 17, 35, 43]. The positive depth constraint, which has been used for normal flow
fields, is relatively new and is employed in the so-called direct algorithms [8, 20, 27]. One has to search for the 3D
motion that is consistent with the input and produces the minimum amount of negative depth. Put differently,
in these approaches the function representing the amount of negative depth must be minimized. Finally, one may
be able to use the "positive depth constraint" when optic flow is available, but there exist no algorithms yet in
the literature implementing this principle.
Looking at nature we observe that there exists a great variety of eye designs in organisms with vision. An
important characteristic is the field of view. There exist systems whose vision has a restricted field of view. This
is achieved by the corneal eyes of land vertebrates. Human eyes and common video cameras fall in that category
and they are geometrically modeled through central projection on a plane. We refer to these eyes as planar or
camera-type eyes. There exist also systems whose vision has a full 360 degree field of view. This is achieved by
the compound eyes of insects or by placing camera-type eyes on opposite sides of the head, as in birds and fish.
Panoramic vision is adequately modeled geometrically by projecting on a sphere using the sphere's center as the
center of projection. In studying the observability of 3D motion, we investigate both restricted field of view and
panoramic vision. It turns out that they have different properties regarding 3D motion estimation.
In our approach we employ a statistical model to represent the constraints to derive functions representing
deviation from epipolar geometry or the amount of negative depth, for both a camera-type eye and a spherical eye.
All possible, meaningful algorithms for 3D motion estimation can be understood from the minimization of these
functions. Thus, we perform a topographic analysis of these functions and study their global and local minima.
Specifically, we are interested in the relationships between the errors in 3D motion at the points representing
the minima of these surfaces. The idea behind this is that in practical situations any estimation procedure is
hampered by errors and usually local minima of the functions to be minimized are found as solutions.
3 Problem Statement
3.1 Prerequisites
We use the standard conventions for expressing image motion measurements for a monocular observer moving
rigidly in a static environment. We describe the motion of the observer by its translational velocity
and its rotational velocity with respect to a coordinate system OXY Z fixed to the nodal point of
the camera. Each scene point P with coordinates has a velocity -
R relative to the
camera. Projecting -
R onto a retina of a given shape gives the image motion field. If the image is formed on
a plane (Figure 1a) orthogonal to the Z axis at distance f (focal length) from the nodal point, then an image
point f) and its corresponding scene point R are related by
R, where z 0 is a unit vector in the
direction of the Z axis. The motion field becomes
(R
f z 0 \Theta (r \Theta (! \Theta
Z
R
r
Y
Z
x
y
f
O
z 0
r
R
f r
O
r
(a) (b)

Figure

1: Image formation on the plane (a) and on the sphere (b). The system moves with a rigid motion with
translational velocity t and rotational velocity !. Scene points R project onto image points r and the 3D velocity
R of a scene point is observed in the image as image velocity -
r.
with representing the depth. If the image is formed on a sphere of radius f (Figure 1b) having the
center of projection as its origin, the image r of any point R is
jRj , with R being the norm of R (the range),
and the image motion is
R u tr (t)
The motion field is the sum of two components, one, u tr , due to translation and the other, u rot , due to rotation.
The depth Z or range R of a scene point is inversely proportional to the translational flow, while the rotational
flow is independent of the scene in view. As can be seen from (1) and (2), the effects of translation and scene
depth cannot be separated, so only the direction of translation, t=jtj, can be computed. We can thus choose the
length of t; throughout the following analysis f is set to 1, and the length of t is assumed to be 1 on the sphere
and the Z-component of t to be 1 on the plane. The problem of 3D motion estimation then amounts to finding
the scaled vector t and the vector ! from a representation of the motion field. In the following, to make the
analysis easier, for the camera-type eye we will employ a non-vector notation. Then, the first two coordinates of
r denote the image point in the Cartesian system oxy, with oxkOX, oykOY and o the intersection of OZ with
the image plane. Denote by the image point representing the direction of the translation
vector t (referred to as the Focus of Expansion (FOE) or Focus of Contraction (FOC) depending on whether W
is positive or negative). Equations (1) become then the well known equations expressing the flow measurement
fly
where v tr (x;y)
are the translational and rotational flow
components, respectively.
Regarding the value of the normal flow, if n is a unit vector at an image point denoting the orientation of the
gradient at that point, the normal flow v n satisfies
r
Finally, the following convention is employed throughout the paper. We use letters with hat signs to represent
estimated quantities, unmarked letters to represent the actual quantities and the subscript "ffl" to denote errors,
where the error quantity is defined as the actual quantity minus the estimated one. For example, u rot (!) represents
actual rotational flow, u rot ( -
estimated rotational flow, t ffl the translational error vector, x
ff,
etc.
3.2 The model
The classic approach to 3D motion estimation is to minimize the deviation from the epipolar constraint. This
constraint is obtained by eliminating depth (or range) from equation (1) (or (2)). For both planar and spherical
eyes it is
r +! \Theta r) = 0: (5)
Equating image motion with optic flow, this constraint allows for the derivation of 3D rigid motion on the basis
of optic flow measurements. One is interested in the estimates of translation - t and rotation -
which best satisfy
the epipolar constraint at every point r according to some criterion of deviation. The Euclidean norm is usually
used, leading to the minimization [25, 34] of the function 1
Z Z
image
\Theta r)dr: (6)
On the other hand, if normal flow is given, the vector equations (1) and (2) cannot be used directly. The only
constraint is scalar equation (4), along with the inequality Z ? 0 which states that since the surface in view is in
front of the eye its depth must be positive. Substituting (1) or (2) into (4) and solving for the estimated depth
Z or range -
R, we obtain for a given estimate - t; -
! at each point r:
Z(or -
If the numerator and denominator of (7) have opposite signs, negative depth is computed. Thus, to utilize the
positivity constraint one must search for the motion - t; -
that produces a minimum number of negative depth
estimates. Formally, if r is an image point, define the indicator function
I nd
ae
Then estimation of 3D motion from normal flow amounts to minimizing [19, 20, 27] the function
Z Z
image
I nd (r)dr: (8)
Expressing -
r in terms of the real motion from (1) and (2), functions (6) and (8) can be expressed in terms of
the actual and estimated motion parameters t, !, - t and -
(or, equivalently, the actual motion parameters t; !
and the errors t
!) and the depth Z (or range R) of the viewed scene. To conduct any analysis,
a model for the scene is needed. We are interested in the statistically expected values of the motion estimates
resulting from all possible scenes. Thus, as our probabilistic model we assume that the depth values of the scene
are uniformly distributed between two arbitrary values Z min (or R min ) and Zmax (or Rmax
For the minimization of negative depth values, we further assume that the directions in which flow measurements
Because t \Theta r introduces the sine of the angle between t and r, the minimization prefers vectors t close to the center of gravity of
the points r. This bias has been recognized [40] and alternatives have been proposed that reduce this bias, but without eliminating
the confusion between rotation and translation.
are made are uniformly distributed in every direction for every depth. Parameterizing n by /, the angle between
n and the x axis, we thus obtain the following two functions:
Z=Zmin
Z
Z=Zmin
nd dZ d/; (10)
measuring deviation from the epipolar constraint and the amount of negative depth, respectively. Functions
and (10) are five-dimensional surfaces in t ffl the errors in the motion parameters. Finally, since for the scene
in view we employ a probabilistic model, the results are of a statistical nature, that is, the geometric constraints
between ffl at the minima of (9) and (10) that we shall uncover should be interpreted as being likely to occur.
3.3 Negative depth and depth distortion
This section contains a few technical prerequisites needed for the study of negative depth minimization and a
geometric observation that show the relationship of epipolar minimization to minimization of negative depth.
Equation (7) shows the estimated depth -
Z (or range -
R) given normal flow -
r \Delta n and estimates - t; -
! of the
motion. It can be further written as:
Z(or -
with D in the case of noiseless motion measurements (that is, -
of the form
Equation (11) shows how wrong depth estimates are produced due to inaccurate 3D motion values. The distortion
D, multiplies the real depth value to produce the estimate. Equation (12), for a fixed value of D and
describes a surface in (r; Z) (or (r; R)) space which is called an iso-distortion surface. Any such surface is to
be understood as the locus of points in space which are distorted in depth by the same multiplicative factor if
the image measurements are in direction n. If we fix n and vary D, the iso-distortion surfaces of the resulting
family change continuously as D varies. Thus all scene points giving rise to negative depth estimates lie between
the 0 and \Gamma1 distortion surfaces. The integral over all points (for all directions) giving rise to negative depth
estimates we call the negative depth volume. In Section 5 we will make use of the iso-distortion surfaces and
the negative depth volume to study in a geometric way function (10) resulting from minimization of the negative
depth values.
Let us now examine the two different minimizations from a geometric perspective. When deriving the deviation
from the epipolar constraint we consider integration over all points and depth values of the expression
or, equivalently,
denotes the vector perpendicular to u tr ( - t) in the plane of the image coordinates. When deriving the
number of negative depth values we consider integration over all points and depth values of the angle ff between
the two vectors
An illustration is given in Figure 2. The two measures considered in the two different minimizations are clearly
related to each other. In the case of negative depth we consider the angle ff, whereas in the case of the epipolar
constraint we consider the squared distance a 2 , which amounts to (sin ffku tr ( - t)k
The major difference in using the two measures arises for angles ff ? 90 ffi . The measure for negative depth
is monotonic in ff, but the measure for the deviation from the epipolar constraint is not, because it does not
differentiate between depth estimates of positive and negative value.
The fact that the computed depth has to be positive has not been considered in past approaches employing
minimization of the epipolar constraint. As this fact provides an additional constraint which could be utilized in
a
negative depth
a
a

Figure

2: Different measures used in minimization constraints. (a)
6 ff in the minimization of negative depth
values from projections of motion fields. (b) a 2 in the epipolar constraint.
the future, maybe in conjunction with the epipolar constraint, we are interested in the influence of this constraint
on 3D motion estimation as well. Thus, in addition to minimization of the functions (9) and (10) discussed
above, we study the minimization of a third function. This function amounts to the number of values giving
rise to negative depth when full flow measurements (optical flow) are assumed and the analysis is presented in


Appendix

B.
3.4 A model for the noise in the flow
In the analysis on the plane we will also consider noise in the image measurements, that is, we will consider the
flow values of the form (u
The choice of the noise model is
motivated by the following considerations: First, the noise should be such that no specific directions are favored.
Second, assuming that noise is both additive and multiplicative, there should be a dependence between noise and
depth, because the translational flow component is proportional to the inverse depth. Therefore we define noise
using two stochastic variables
Z
with the first and second moments being
and all stochastic variables being independent of each other, independent of image position, and independent of
the depth.
3.5 Overview of the paper, summary of results and related work
Our approach expresses functions (9) and (10) in terms of t, !, t ffl and ! ffl and finds the conditions that t ffl
ffl satisfy at local minima which represent solutions of the different estimation algorithms. Procedures for
estimating 3D motion can be classified into those estimating either the translation or rotation as a first step and the
remaining component (that is, the rotation or translation) as a second step, and those estimating all components
simultaneously. Procedures of the former kind result when systems utilize inertial sensors which provide them
with estimates of one of the components of the motion, or when two-step motion estimation algorithms are used.
Thus, three cases need to be studied: the case were no prior information about 3D motion is available and
the cases where an estimate of translation or rotation is available with some error. Imagine that somehow the
rotation has been estimated, with an error ! ffl . Then our functions become two-dimensional in the variables t ffl and
represent the space of translational error parameters corresponding to a fixed rotational error. Similarly, given
a translational error t ffl , the functions become three-dimensional in the variables ! ffl and represent the space of
rotational errors corresponding to a fixed translational error. To study the general case, one needs to consider the
lowest valleys of the functions in 2D subspaces which pass through 0. In the image processing literature, such local
are often referred to as ravine lines or courses. Each of the three cases is studied for four optimizations:
epipolar minimization for the sphere and the plane (full field of view and restricted field of view vision) and
minimization of negative depth for the sphere and the plane. Thus, there are twelve (four times three) cases, but
since the effects of rotation on the image are independent of depth, it makes no sense to perform minimization of
negative depth assuming an estimate of translation is available. Thus, we are left with ten different cases which
are studied below. These ten cases represent all the possible, meaningful motion estimation procedures.
The analysis shows that:
1. In the case of a camera-type eye (restricted field of view) for algorithms in both classes which estimate all
motion parameters simultaneously (i.e., there is no prior information), the obtained solution will have an
error in the translation and (ff ffl ; in the rotation such that x0 ffl
and
means that the projections of the translational and rotational errors on the image are perpendicular to each
other and that the rotation around the Z axis has the least ambiguity. We refer to this constraint as the
"orthogonality constraint." In addition, the estimated translation (-x lie on a line passing from the
origin of the image and the real translation
. We refer to this second constraint
as the "line constraint." Similar results are achieved for the case where translation is estimated first and on
that basis rotation is subsequently found, while the case where rotation is first estimated and subsequently
translation provides different results. The work is performed both in the absence of error in the image
measurements-in which case it becomes a geometric analysis of the inherent confusion between rotation
and translation-and in the case where the image measurements are corrupted by noise that satisfies the
model from Section 3.4. In this case, we derive the expected values of the local and global minima. As will
be shown, the noise does not alter the local minima, and the global minima fall within the valleys of the
function without noise. Thus, the noise does not alter the functions' overall structure.
2. In the case of panoramic vision, for algorithms in both classes which estimate all motion parameters si-
multaneously, the obtained solution will have no error in the translation and the rotational error
will be perpendicular to the translation. In addition, for the case of epipolar minimization from optic flow,
given a translational error t ffl , the obtained solution will have no error in the rotation (! while for the
case of negative depth minimization from normal flow, given a rotational error the obtained solution will
have no error in the translation. In other cases ambiguities remain. In the spherical eye case the analysis is
simply performed for noiseless flow.
A large number of error analyses have been carried out [2, 11, 12, 15, 29, 39, 41, 42] in the past for a
camera-type eye, while there is no published research of this kind for the full field of view case. None of the
existing studies, however, has attempted a topographic characterization of the function to be minimized for
the purpose of analyzing different motion techniques. All the studies consider optical flow or correspondence
as image measurements and investigate minimizations based on the epipolar constraint. Often, restrictive
assumptions about the structure of the scene or the estimator have been made, but the main results obtained
are in accordance with our findings. In particular, the following two results already occur in the literature.
(a) Translation along the x axis can be easily confounded with rotation around the y axis, and translation
along the y axis can be easily confounded with rotation around the x axis, for small fields of view and
insufficient depth variation. This fact has long been known from experimental observation, and has been
proved for planar scene structures and unbiased estimators [10]. The orthogonality constraint found
here confirms these findings, and imposes even more restrictive constraints. It shows, in addition, that
the x-translation and y-rotation, and y-translation and x-rotation, are not decoupled. Furthermore,
we have found that rotation around the Z axis can be most easily distinguished from the other motion
components.
(b) Maybank [32, 33] and Jepson and Heeger [29] established before the line constraint, but under much
more restrictive assumptions. In particular, they showed that for a small field of view, a translation
far away from the image center and an irregular surface, the function in (9) has its minima along a
line in the space of translation directions which passes through the true translation and the viewing
direction. Under fixation the viewing direction becomes the image center.
4 Epipolar Minimization: Camera-type Eye
the field of view is small, the quadratic terms in the image coordinates
are very small relative to the linear and constant terms, and are therefore ignored. All the computations are
carried out with the symbolic algebraic computation software Maple, and, for abbreviation, intermediate results
are not given. First the case of noise-free flow is studied.
Considering a circular aperture of radius e, setting the focal length
the function
in
Z=Zmin
e
Z
Z
Z
r
oe
dr dOE dZ
where (r; OE) are polar coordinates sin OE). Performing the integration, one obtains
y
'Z min
(a) Assume that the translation has been estimated with a certain error t 0). Then the relationship
among the errors in 3D motion at the minima of (14) is obtained from the first-order conditions @E1
= 0, which yield
It follows that ff ffl =fi
(b) Assuming that rotation has been estimated with an error (ff among the errors is
obtained from @E1
In this case, the relationship is very elaborate and the translational error depends
on all the other parameters-that is, the rotational error, the actual translation, the image size and the depth
interval. See Appendix A.
(c) In the general case, we need to study the subspaces in which E 1 changes least at its absolute minimum;
that is, we are interested in the direction of the smallest second derivative at 0, the point where the motion errors
are zero. To find this direction, we compute the Hessian at 0, that is the matrix of the second derivatives of
respect to the five motion error parameters, and compute the eigenvector corresponding to the smallest
eigenvalue. The scaled components of this vector amount to
As can be seen, for points defined by this direction, the translational and rotational errors are characterized by
the "orthogonality constraint" ff ffl =fi
and by the "line constraint" x 0 =y
Next we consider noise in the flow measurements. We model the noise (N x ; N y ) as defined in Section 3.4 and
derive E(E ep ), the expected value of E ep , which amounts to
Z=Zmin
Z
e
Z
ae'
r
oe
dr dOE dZ (16)
and thus
'Z min
(a) If we fix x
and y 0 ffl
and solve for
we obtain the same relationship as for noiseless flow described in (15).
This shows that the noise does not alter the expected behavior of techniques which in a first step minimize the
translation.
(b) If we fix ff ffl , fi ffl , and fl ffl , and solve for
@y
we obtain as before a complicated relationship between the translational error, the actual translation, and the
rotational error.
(c) To analyze the behavior of techniques which minimize for all 3D motion parameters, we study the global minimum
of E(E). From minimization with regard to the rotational parameters, we obtained (15) (the orthogonality
constraint and Substituting (15) into (16) and solving for
@y
we get, in addition,
\GammaZ
Thus the absolute minimum of E(E ep ) is to be found in the direction of smallest increase in E 1 , and is described
by the constraint by the orthogonality constraint, and by the line constraint.
5 Minimization of Negative Depth Volume: Camera-type Eye
In the following analysis we study the function describing the negative depth values geometrically, by means of the
negative depth volumes, that is, the points corresponding to negative depth distortion as defined in Section 3.3.
This allows us to incrementally derive properties of the function without considering it with respect to all its
parameters at once. For simplicity, we assume that the FOE and the estimated FOE are inside the image, and
we do not consider the exact effects resulting from volumes of negative depth in different directions being outside
the field of view. We first concentrate on the noiseless case. If, as before, we ignore terms quadratic in the image
coordinates, the 0 distortion surface (from equation (11)) becomes
and the \Gamma1 distortion surface takes the form
The flow directions (n x alternatively be written as (cos /; sin /), with / 2 [0; -] denoting the angle
between and the x axis. To simplify the visualization of the volumes of negative depth in different
directions, we perform the following coordinate transformation to align the flow direction with the x axis: for
every / we rotate the coordinate system by angle /, to obtain the new coordinates [x
cos / sin /
sin / cos /
Equations (17) and (18) thus become
(a) To investigate techniques which, as a first step, estimate the rotation, we first study the case of fl
then extend the analysis to the general case of fl ffl 6= 0.
If the volume of negative depth values for every direction / lies between the surfaces
The equation
describes a plane parallel to the y 0 Z plane at distance - x 0
0 from the origin, and
describes a plane parallel to the y 0 axis of slope 1
, which intersects the x 0 y 0 plane in the
. Thus we obtain a wedge-shaped volume parallel to the y 0 axis. Figure 3 illustrates the volume
through a slice parallel to the x 0 Z plane.
The scene in view extends between the depth values Z min and Zmax . We denote by A/ the area of the cross
section parallel to the x 0 Z plane through the negative depth volume in direction /.
As can be seen from Figure 3, to obtain the minimum, -
0 has to lie between x
then
Z=Zmin
which amounts to
If we fix fi 0
ffl and solve for x
0, we obtain
-that is, the 0 distortion surface has to intersect the \Gamma1 distortion surface in the middle of the depth interval
in the plane
.
depends only on the depth interval, and thus is independent of the direction, /. Therefore, the negative
depth volume is minimized if (20) holds for every direction. Since fi ffl
sin /y 0 ffl , we obtain x0 ffl
If the \Gamma1 distortion surface becomes
This surface can be most easily understood by slicing it with planes parallel to the x 0 y 0 plane. At every depth
value Z, we obtain a line of slope \Gamma1
which intersects the x 0 axis at x Figure 4a). For any
given Z the slopes of the lines in different directions are the same. An illustration of the volume of negative depth
is given in Figure 4b.
Z min
Z

Figure

3: Slice parallel to the x 0 Z plane through the volume of negative estimated depth for a single direction.
z4002000
volume
volume
(a) (b)

Figure

4: (a) Slices parallel to the x 0 y 0 plane through the 0 distortion surface (C 0 ) and the \Gamma1 distortion surface
at depth values
0: volume of negative depth values
between the 0 and \Gamma1 distortion surfaces.
Let us express the value found for - x 0
0 in the case of fl
I . In order to derive the position
of -
0 that minimizes the negative depth volume for the general case of fl ffl 6= 0, we study the change of volume as
0 changes from x
Referring to Figure 5, it can be seen that for any depth value Z, a change in the position of -
0 to -
assuming Z 6= 0, causes the area of negative depth values to change by A c , where A
and y 0
1 and y 0
2 denote the y 0 coordinates of the intersection point of the \Gamma1 distortion contour at depth Z with
the 0 distortion contours x I and x d. These coordinates are
and y 0
Therefore
Z
The change V c in negative depth volume for any direction is given by
Zmin
A c dZ
which amounts to
Substituting for Z I = Zmin+Zmax
, it can be verified that in order for V c to be negative, we must have
\Gammasgn(d).
We are interested in the d which minimizes V c . By solving
@d
we obtain
Thus
depends only on the depth interval, the total negative depth volume is obtained if the volume in
every direction is minimized. Therefore, for any rotational error (ff independent of fl ffl , we have the
orthogonality constraint:
A comment on the finiteness of the image is necessary here. The values A c and V c have been derived for an
infinitely large image. If fl ffl is very small or some of the depth values Z in the interval [Z min are small, the
coordinates of the intersections y 0
1 and y 0
2 do not lie inside the image. The value of A c can be at most the length
of the image times d. Since the slope of the \Gamma1 distortion contour for a given Z is the same for all directions, this
will have very little effect on the relationship between the directions of the translational and rotational motion
errors. It has an effect, however, on the relative values of the motion errors. Only if the intersections are inside
the image can (22) be used to describe the value of x 0
as a function of fi 0
ffl and the interval of depth values of the
scene in view.
(b) Next we investigate techniques which minimize both the translation and rotation at once. First consider a
certain translational error and change the value of fl ffl . An increase in fl ffl decreases the slope of the \Gamma1 distortion
surfaces, and thus, as can be inferred from Figure 4a, the area of negative depth values for every direction /
and every depth Z increases. Thus In addition, from above, we know that x0 ffl
. The exact
relationship of fi 0
ffl to x 0
is characterized by the locations of local minima of the function A/ , which in the image
processing literature are often referred to as "courses." (These are not the courses in the topographical sense
[30].) To be more precise, we are interested in the local minima of A/ in the direction corresponding to the
largest second derivative. We compute the largest eigenvalue, - 1 , of the Hessian, H, of A/ , that is the matrix of
the second derivatives of A/ with respect to x 0
and fi 0
ffl , which amounts to
and obtain
. The corresponding eigenvector, e 1 , is (fi 0
Solving for
we obtain
Last in an analysis of the noiseless case, we consider the effects due to the finiteness of the aperture. As before,
we consider a circular aperture. We assume a certain amount of translational error
, and we seek the
direction of translational error that results in the smallest negative depth volume.
Independent of the direction of translation, (23) describes the relationship of x
and fi ffl for the smallest negative
depth volume. Substituting (23) into (19), we obtain the cross-sections through the negative depth volume as a
function of x
0 and the depth interval. The negative depth volume for every direction / amounts to A/ l / , where
l / denotes the average extent of the wedge-shaped negative depth volume in direction /. The total negative depth
volume is minimized if
Considering a circular aperture, this minimization is achieved
if the largest A/ corresponds to the smallest extent l / and the smallest A/ corresponds to the largest l / . This
happens when the line constraint holds, that is, x0
y0 (see

Figure

6).
It remains to be shown that noise in the flow measurements does not alter the qualitative characteristics of
the negative depth volume and thus the results obtained.
First we analyze the orthogonality constraint. The analysis is carried out without considering the size of the
aperture; as will be shown, this analysis leads to the orthogonality constraint.
First, let Ignoring the image size, we are interested in E(V ), the expected value of the integral of the
cross sections A/ , which amounts to
Z=Zmin
Z
or
Z=Zmin
dZA
We approximate the expectation of the integrand by performing a Taylor expansion at 0 up to second order,
which gives
x
y

Figure

5: A change of - x 0
0 to -
causes the area
of negative depth values A c to increase by A 1 and to
decrease by A 2 . This change amounts to A
OE
A y 2
l y 1
l y 2

Figure

Cross-sectional view of the wedge-shaped negative
depth volumes in a circular aperture. The minimization
of the negative depth volume for a given
amount of translational error occurs when x0
y0 .
and l / i
denote the areas of the cross sections and
average extents respectively, for two angles / 1 and / 2 .
The two circles bounding A/ i are given by the equations
ffl Z min and x
ffl Zmax .
We are interested in the angle - between the translational and rotational error which minimizes the negative
depth volume. If we align the translational error with the x axis, that is, y
0, and if we express the rotational
error as sin -), we obtain
Z=Zmin
\Delta0
Solving for @E(V )
) to be perpendicular to (ff ffl ; fi ffl ), if
minimizations considered.
Next, we allow fl ffl to be different from zero. For the case of a fixed translational error, again, the volume
increases as fl ffl increases, and thus the smallest negative depth volume occurs for For the case of a
fixed rotational error we have to extend the previous analysis (studying the change of volume when changing the
estimated translation) to noisy motion fields: The \Gamma1 distortion surface becomes x
and the 0 distortion surfaces remain the same. Therefore, VC becomes
\Gammasgn
and E(VC ) takes the same form as VC in (21). We thus obtain the orthogonality constraint for
Finally, we take into account the limited extent of a circular aperture for the case of global minimization.
As noise does not change the structure of the iso-distortion surfaces, as shown in Figure 6, in the presence of
noise, too, the smallest negative depth volume is obtained if the FOE and the estimated FOE lie on a line passing
through the image center. This proves the orthogonality constraint for the full model as well as the line constraint.
The global minimum of the negative depth volume is thus described by the constraint the orthogonality
constraint and the line constraint.
6 Epipolar Minimization: Spherical Eye
The function representing deviation from the epipolar constraint on the sphere takes the simple form
Rmin
Z Z
sphere
ae'
r \Theta (r \Theta t)
dAdR
where A refers to a surface element. Due to the sphere's symmetry, for each point r on the sphere, there exists
a point with coordinates \Gammar. Since u tr when the integrand is expanded
the product terms integrated over the sphere vanish. Thus
Rmin
Z Z
sphere
t \Theta - t
dAdR
(a) Assuming that translation - t has been estimated, the ! ffl that minimizes E ep is since the resulting
function is non-negative quadratic in ! ffl (minimum at zero). The difference between sphere and plane is already
clear. In the spherical case, as shown here, if an error in the translation is made we do not need to compensate
for it by making an error in the rotation (! while in the planar case we need to compensate to ensure that
the orthogonality constraint is satisfied!
(b) Assuming that rotation has been estimated with an error ! ffl , what is the translation - t that minimizes
Since R is uniformly distributed, integrating over R does not alter the form of the error in the optimization.
consists of the sum of two terms:
Z Z
sphere
t \Theta - t
dA and
Z Z
sphere
are multiplicative factors depending only on R min and Rmax . For angles between t; - t and - t; ! ffl in
the range of 0 to -=2, K and L are monotonic functions. K attains its minimum when
Fix the distance between t and - t leading to a certain value K, and change the position of - t. L takes its minimum
as follows from the cosine theorem. Thus E ep achieves its minimum when - t lies on the
great circle passing through t and ! ffl , with the exact position depending on j! ffl j and the scene in view.
(c) For the general case where no information about rotation or translation is available, we study the subspaces
changes the least at its absolute minimum, i.e., we are again interested in the direction of the smallest
second derivative at 0. For points defined by this direction we calculate, using Maple, t.
7 Minimizing Negative Depth Volume on the Sphere
(a) Assuming that the rotation has been estimated with an error ! ffl , what is the optimal translation - t that
minimizes the negative depth volume?
Since the motion field along different orientations n is considered, a parameterization is needed to express all
possible orientations on the sphere. This is achieved by selecting an arbitrary vector s; then, at each point r of
the sphere, s\Thetar
ks\Thetark defines a direction in the tangent plane. As s moves along half a circle, s\Thetar
ks\Thetark takes on every
possible orientation (with the exception of the points r lying on the great circle of s). Let us pick ! ffl perpendicular
to s (s
We are interested in the points in space with estimated negative range values -
R.
ks\Thetark and s
the estimated range -
R amounts to -
. -
where sgn(x) provides the sign of x. This constraint divides the surface of the sphere into four areas, I to IV,
whose locations are defined by the signs of the functions ( - t \Theta s) \Delta r, (t \Theta s) \Delta r and (! ffl \Delta r)(s \Delta r), as shown in

Figure

7.
s
I 0
IV
III I
II IV
s
IIV
I
II
IV
III
area location constraint on R
I sgn(t \Theta s) \Delta

Figure

7: Classification of image points according to constraints on R. The four areas are marked by different
colors. The textured parts (parallel lines) in areas I and III denote the image points for which negative depth
values exist if the scene is bounded. The two hemispheres correspond to the front of the sphere and the back of
the sphere, both as seen from the front of the sphere.
For any direction n a volume of negative range values is obtained consisting of the volumes above areas I, II
and III. Areas II and III cover the same amount of area between the great circles (t \Theta s) \Delta
and area I covers a hemisphere minus the area between (t \Theta s) \Delta If the scene in view
is unbounded, that is, R 2 [0; +1], there is for every r a range of values above areas I and III which result in
negative depth estimates; in area I the volume at each point r is bounded from below by
(! ffl \Deltar)(s\Deltar) , and in
area III it is bounded from above by
. If there exist lower and upper bounds R min and Rmax in
the scene, we obtain two additional curves C min and Cmax with C
and we obtain negative depth values in area I only between Cmax
in area III only between C min and (! ffl \Theta r)(s \Theta r) = 0. We are given ! ffl and t, and we
are interested in the - t which minimizes the negative range volume. For any s the corresponding negative range
volume becomes smallest if - t is on the great circle through t and s, that is, (t \Theta s) \Delta - as will be shown next.
Let us consider a - t such that (t \Theta s) \Delta - t 6= 0 and let us change - t so that (t \Theta s) \Delta - changes, the area
of type II becomes an area of type IV and the area of type III becomes an area of type I. The negative depth
volume is changed as follows: It is decreased by the spaces above area II and area III, and it is increased by
the space above area I (which changed from type III to type I). Clearly, the decrease is larger than the increase,
which implies that the smallest volume is obtained for s; t; - t lying on a great circle. Since this is true for any s,
the minimum negative depth volume is attained for t. 2
(b) Next, assume that no prior knowledge about the 3D motion is available. We want to know for which
configurations of - t and ! ffl the negative depth values change the least in the neighborhood of the absolute minimum,
that is, at From the analysis above, it is known that for any ! ffl 6= 0, t. Next, we show that ! ffl
is indeed different from zero: Take t 6= - t on the great circle of s and let ! ffl , as before, be perpendicular to s.
the curves Cmax and C min can be expressed as C
6 (t;s)
0, where sin
denotes the angle between vectors t and s. These curves consist of the great circle
and the circle sin
6 (t;s)
parallel to the great circle (s Figure 8). If sin
6 (t;s)
this circle disappears.
s
I
IV

Figure

8: Configuration for t and - t on the great circle of s and ! ffl perpendicular to s. The textured part of area I
denotes image points for which negative depth values exist if the scene is bounded.
Consider next two flow directions defined by vectors s 1 and s 2 with
and - t.
For every point r 1 in area III defined by s 1 there exists a point r 2 in area I defined by s 2 such that the negative
estimated ranges above r 1 and r 2 add up to Rmax \Gamma R min . Thus the volume of negative range obtained from s 1
and s 2 amounts to the area of the sphere times (Rmax \Gamma R min ) (area II of s 1 contributes a hemisphere; area III of
area I of s 2 together contribute a hemisphere). The total negative range volume can be decomposed into
A word of caution about the parameterization used for directions
ks\Thetark is needed. It does not treat all orientations equally
(as s varies along a great circle with constant speed, s \Theta r accelerates and decelerates). Thus to obtain a uniform distribution,
normalization is necessary. The normalization factors, however, do not affect the previous proof, due to symmetry.
three components: a component V 1 originating from the set of s between t and - t, a component V 2 originating
from the set of s symmetric in t to the set in V 1 , and a component V 3 corresponding to the remaining s, which
consists of range values above areas of type I only. If for all s in V 3 , sin
6 (t;s)
zero. Thus for
all
Rmax , the negative range volume is equally large and amounts to the area on the sphere
times (Rmax \Gamma R min ) times
takes on values different from zero.
This shows that for any t ffl 6= 0, there exist vectors ! ffl 6= 0 which give rise to the same negative depth volume
as However, for any such ! ffl 6= 0 this volume is larger than the volume obtained by setting
follows that t. From Figure 7, it can furthermore be deduced that for a given ! ffl the negative depth volume,
which for only lies above areas of type I, decreases as t moves along a great circle away from ! ffl , as the
areas between C min and Cmax and between C min and (t \Theta s) \Delta decrease. This proves that in addition to
Conclusions
The preceding results constitute a geometric statistical investigation of the observability of 3D motion from
images. On their basis, a number of striking conclusions can be achieved. First, they clearly demonstrate the
advantages of panoramic vision in the process of 3D motion estimation. Table 1 lists the eight out of ten cases
which lead to clearly defined error configurations. It shows that 3D motion can be estimated more accurately
with spherical eyes. Depending on the estimation procedure used-and systems might use different procedures
for different tasks-either the translation or the rotation can be estimated very accurately. For planar eyes, this is
not the case, as for all possible procedures there exists confusion between the translation and rotation. The error
configurations also allow systems with inertial sensors to use more efficient estimation procedures. If a system
utilizes a gyrosensor which provides an approximate estimate of its rotation, it can employ a simple algorithm
based on the positive depth constraint for only translational motion fields to derive its translation and obtain a
very accurate estimate. Such algorithms are much easier to implement than algorithms designed for completely
unknown rigid motions, as they amount to searches in 2D as opposed to 5D spaces [19]. Similarly, there exist
computational advantages for systems with translational inertial sensors in estimating the remaining unknown
rotation.
Since the positive depth constraint turns out to be very powerful and since epipolar minimization does not
consider depth positivity, an interesting research question that arises for the future is how to couple the epipolar
constraint with the positive depth constraint. We attempted a first investigation into this problem through a
study of negative depth on the basis of optic flow for the plane in Appendix B, which gave very interesting results.
Specifically, we found that estimating all motion parameters simultaneously by minimizing negative depth from
optic flow provides a solution with no error in the translation. However, the rotation cannot be decoupled from the
translation, which makes it clear that for cameras with restricted fields of view the problem of rotation/translation
confusion cannot be escaped.
Camera-type eyes are found in nature in systems that walk and perform sophisticated manipulation because
such systems have a need for very accurate segmentation and shape estimation and thus high resolution in a
limited field of view. Panoramic vision, either through compound eyes or a pair of camera-type eyes positioned
on opposite sides of the head is usually found in flying systems which have the obvious need for a larger field of
view but also rely on accurate 3D motion estimation as they always move in an unconstrained way. When we
face the task of equipping robots with visual sensors, we do not have to necessarily copy nature, and we also do
not have to necessarily use what is commercially available. Instead, we could construct new, powerful eyes by
taking advantage of both the panoramic vision of flying systems and the high-resolution vision of primates. An
eye like the one in Figure 9, assembled from a few video cameras arranged on the surface of a sphere, can easily
estimate 3D motion since, while it is moving, it is sampling a spherical motion field!
Such an eye not only has panoramic properties, allowing very accurate determination of the transformations
relating multiple views, but it has the unexpected benefit of making it easy to estimate image motion with high
accuracy. Any two cameras with overlapping fields of view also provide high-resolution stereo vision, and this
collection of stereo systems makes it possible to locate a large number of depth discontinuities. Given scene
discontinuities, image motion can be estimated very accurately. As a consequence, having accurate 3D motion

Table

1: Summary of results
I II
Spherical Eye Camera-type Eye
Epipolar minimization,
given optic flow
(a) Given a translational error
ffl , the rotational error
(b) Without any prior infor-
mation,
(a) For a fixed translational
error
), the rotational
error
the form
(b) Without any a priori information
about the mo-
tion, the errors satisfy
Minimization of negative
depth volume, given
normal flow
(a) Given a rotational error
ffl , the translational error
(b) Without any prior infor-
mation,
(a) Given a rotational error,
the translational error is of
the form \Gammax
(b) Without any error infor-
mation, the errors satisfy
and image motion, the eye in Figure 9 is very well suited to developing accurate models of the world necessary
for many robotic/servoing applications.

Figure

9: A compound-like eye composed of conventional video cameras, arranged on a sphere and looking
outward.



--R

Determining 3D motion and structure from optical flow generated by several moving objects.
Inherent ambiguities in recovering 3-D motion and structure from a noisy flow field
Active vision.

Active perception.
Principles of animate vision.
Rigid body motion from depth and optical flow.
A Computational Approach to Visual Motion Perception.
Estimating 3-D egomotion from perspective image sequences
On the Error Sensitivity in the Recovery of Object Descriptions.
Analytical results on error sensitivity of motion estimation from two views.
Understanding noise sensitivity in structure from motion.
Planning and Control.
Simultaneous robot-world and hand-eye calibration
Robustness of correspondence-based structure from motion
A new approach to visual servoing in robotics.
Motion and structure from motion from point and line matches.

Direct perception of three-dimensional motion from patterns of visual motion
Qualitative egomotion.

Subspace methods for recovering rigid motion I: Algorithm and implemen- tation

Visual guided object grasping.
Robot Vision.
Relative orientation.

A tutorial on visual servo control.
Subspace methods for recovering rigid motion II: Theory.

The interpretation of a moving retinal image.
Algorithm for analysing optical flow based on the least-squares method
A Theoretical Study of Optical Flow.
Theory of Reconstruction from Image Motion.
Estimation of three-dimensional motion of rigid objects from noisy observations
Egomotion and relative depth map from optical flow.
Determining instantaneous direction of motion from optical flow generated by a curvilinear moving observer.
Processing differential image motion.
Optimal computing of structure from motion using point correspondence.
Optimal motion estimation.
Understanding noise: The critical role of motion error in scene reconstruction.
Statistical analysis of inherent ambiguities in recovering 3-D motion from a noisy flow field

--TR
Algorithm for analysing optical flow based on the least-squares method
Inherent Ambiguities in Recovering 3-D Motion and Structure from a Noisy Flow Field
Estimating 3D Egomotion from Perspective Image Sequence
Relative orientation
Estimation Three-Dimensional Motion of Rigid Objects from Noisy Observations
Analytical results on error sensitivity of motion estimation from two views
Planning and control
Subspace methods for recovering rigid motion I
Statistical Analysis of Inherent Ambiguities in Recovering 3-D Motion from a Noisy Flow Field
Principles of animate vision
Two-plus-one-dimensional differential geometry
Qualitative egomotion
Robot Vision

--CTR
John Oliensis, The least-squares error for structure from infinitesimal motion, International Journal of Computer Vision, v.61 n.3, p.259-299, February/March 2005
Tao Xiang , Loong-Fah Cheong, Understanding the Behavior of SFM Algorithms: A Geometric Approach, International Journal of Computer Vision, v.51 n.2, p.111-137, February
Jan Neumann , Cornelia Fermller , Yiannis Aloimonos, A hierarchy of cameras for 3D photography, Computer Vision and Image Understanding, v.96 n.3, p.274-293, December 2004
Abhijit S. Ogale , Cornelia Fermuller , Yiannis Aloimonos, Motion Segmentation Using Occlusions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.6, p.988-992, June 2005
positive depth constraint;error analysis;epipolar constraint;3D motion estimation