Rigid Body Segmentation and Shape Description from Dense Optical Flow Under Weak Perspective.
AbstractWe present an algorithm for identifying and tracking independently moving rigid objects from optical flow. Some previous attempts at segmentation via optical flow have focused on finding discontinuities in the flow field. While discontinuities do indicate a change in scene depth, they do not in general signal a boundary between two separate objects. The proposed method uses the fact that each independently moving object has a unique epipolar constraint associated with its motion. Thus motion discontinuities based on self-occlusion can be distinguished from those due to separate objects. The use of epipolar geometry allows for the determination of individual motion parameters for each object as well as the recovery of relative depth for each point on the object. The algorithm assumes an affine camera where perspective effects are limited to changes in overall scale. No camera calibration parameters are required. A Kalman filter based approach is used for tracking motion parameters with time.
Introduction
Visual motion can provide us with two vital pieces of information: the segmentation of the
visual scene into distinct moving objects and shape information about those objects. In this
paper we will examine how the use of epipolar geometry under the assumption of rigidly moving
objects can be used to provide both the segmentation of the visual scene and the recovery of
the structure of the objects within it.
Epipolar geometry tells us that a constraint exists between corresponding points from
different views of a rigidly moving object (or camera). This epipolar constraint is unique to that
object. Optical flow provides a dense set of correspondences between frames. Therefore the
unique epipolar constraint can be used to find separate rigidly moving objects in the scene given
the optical flow. An algorithm will be developed for segmenting the scene while simultaneously
recovering the motion of each object in the scene. This algorithm makes the assumption that
the scene consists of connected piecewise-rigid objects. The image then consists of connected
regions, each associated with a single rigid object.
Once the motion of rigidly moving objects has been determined, scene structure can be
obtained via the same epipolar constraint. The scene structure problem becomes analogous to
stereopsis in that object depth is a function of distance along the epipolar constraint. Dense
correspondences such as those in optical flow can lead to rich descriptions of the scene geometry.
Recent work [TM94, SP93] has used the uniqueness of the epipolar constraint to attempt
a partition of sparse correspondences. These approaches can only deal with small sets of
correspondences and thus will result in sparse recovery of shape information. In this paper we
examine the use of the dense set of correspondences found from optical flow to partition the
scene into rigidly moving objects.
The epipolar geometry will be examined in the context of an affine camera where perspective
effects are limited to uniform changes in scale. Under weak perspective, the epipolar constraint
equation becomes linear in the image coordinates, thus allowing a least-squares solution for
the parameters of the constraint. Different regions of the image representing independently
moving rigid objects can then be segmented by the fact that they possess different linear
epipolar constraints on their motion in the image plane. Once the parameters of the constraint
equation have been recovered, they can be used to describe the three dimensional rigid motion
that each object in the scene has undergone.
In the next section we look at previous work using dense flow for scene segmentation. A
review of the affine camera, and how under a rigid transformation it leads to a special form
of the Fundamental Matrix [LF94] (which expresses the epipolar constraint in matrix form),
can be found in Section 3. Under the affine camera model the epipolar constraint is linear in
image coordinates, allowing for a standard least squares solution which is outlined in Section 4.
It is then shown how the least squares solution for the combination of two separate regions
of the image can be found easily from the combined measurements. Section 6 outlines the
statistic-based region-growing algorithm which estimates both the motion parameters and the
segmentation of the scene into distinct motion regions. Section 7 examines how once the
epipolar geometry has been estimated, the relative depth of each point in the scene can be
calculated. Section 8 describes how the motion parameters for each object can be dynamically
updated with time by using a modified Kalman Filter approach. In Section 9 the results of
the algorithm applied to a set of both real and synthetic motion sequences are examined and
finally a look at future improvements to the algorithm is discussed in Section 10.
2 Review of Past Work
Previous work on using optical flow to segment a visual scene can be divided into two general
classes. The first class looks for clues in the two dimensional optical flow field to find potential
boundaries between different three dimensional objects. The second class uses the unique
epipolar constraint relating points on rigidly moving objects in different views. Since only a
subset of discontinuities in the two dimensional flow field actually correspond to boundaries
between rigid objects, the first class can not distinguish between independently moving objects
and depth boundaries. Also, the optical flow near discontinuities is often difficult to recover.
As a result, the first class of algorithms are operating in regions of the image where the optical
flow is least accurate.
2.1 Motion Field Segmentation
Early work on segmentation via motion looked for discontinuities in one or both components
of the displacement field [SU87, TMB85, BA90, Bla92]. Since under general perspective projections
the motion field is continuous as long as the depth of the viewed surface is continuous,
discontinuities in the flow field signal depth discontinuities. Unfortunately, the flow field at
discontinuities is difficult to recover. For example, optical flow techniques based on derivatives
of the image function assume continuous or affine flow and thus fail at these regions. At locations
of depth edges, motion will introduce regions of occlusion and disocclusion which are
often not explicitly modeled in optical flow routines.
Some algorithms attempt to locate regions near a flow boundary before computing the
flow [BR87, Sch89, BJ94]. The first two papers look at the gradient constraint within a local
region. Schunck [Sch89] performs a cluster analysis on the constraint lines while Bouthemy
and Rivero [BR87] use a statistical test to find separate motions. Black and Jepson [BJ94]
first find regions of uniform brightness and calculate flow within these regions.
In a number of segmentation algorithms, the assumption that the optical flow field was
locally affine in image coordinates was used [Adi85, MW86, NSKO94, RCV92, WA94]. This
assumes that the scene is piecewise-continuous in depth.
ffl Adiv [Adi85] groups optical flow vectors that have similar affine coordinates using a
Hough transform. Assuming each cluster represents the motion of a planar object, the
object's motion is recovered. Clusters with similar motions are then merged. Wang and
Adelson perform a split-and-merge algorithm on the same parameterization.
ffl Under the assumption of planar objects, the motion and shape can be computed in a
least-squares fashion from a collection of measurements. Murray and Williams [MW86]
begin by computing these parameters for small patches of the image. Patches are merged
if they have similar parameters. A boundary is detected when residuals from the fit to
the parameters are high.
ffl Nagel et al. [NSKO94] fit the derivatives of the intensity function directly to affine flow
parameters. Assuming that the deviations from affine flow are normally distributed
random variables, they detect boundaries via a statistical test.
ffl Rognone et al. [RCV92] fit local patches of flow to five different flow templates. Each of
the templates consisted of first order flow (subsets of full affine). The results of these fits
are clustered into possible labels. A relaxation labeling is then performed to assign these
labels to the image patches.
All of these methods make the assumption of piecewise first order flow which implies piecewise
planar scene structure. However for objects of general shape, many depth variations can occur,
even self occlusion of a rigid object. Thus the piecewise planar assumption about the scene is
often invalid.
2.2 Segmentation via the Epipolar Constraint
Epipolar geometry tells us that a linear constraint exists between the projected points of a
rigid body as it undergoes an arbitrary rigid transformation. This constraint is unique to each
rigid transformation and can be used to identify independently moving objects. The epipolar
constraint has been used in a number of structure from motion algorithms [LH81, TH84, TK92].
The epipolar constraint can be used even in the case of uncalibrated cameras [LF94, LDFP93].
This allows for segmentation without any priors on shape or scene structure. In addition, the
constraint holds for each point on an object, not just at the boundaries. The optical flow can
therefore be sparse at the object boundaries.
As pointed out by Koenderink and van Doorn [KvD91], and implemented by Shapiro et
al. and Cernuschi-Frias et al. [SZB94, SZB93, CFCHB89], under weak perspective projection
motion parameters and shape descriptions can be obtained (modulo a relief transformation such
as depth scaling) from just two views. Thus even under the restrictions of scaled orthography,
important motion information can be obtained.
The use of the epipolar constraint to associate correspondences to distinct rigid objects has
been used by Torr [Tor93, TM94], Nishimura et al. [NXT93] and Soatto and Perona [SP93].
Each of these papers form many subsets of the measurements and use a statistical test to
determine which subsets are possible correct partitions. This would lead to a combinatorial
explosion in hypothesis tests for dense correspondences. Our work uses the assumption that
the independent objects in the scene form continuous regions on the image plane. Thus initial
sets can be constrained to nearest neighbors and avoid the combinatorial explosion.
In stereopsis, the epipolar constraint is used in conjunction with priors on the scene structure
to help constrain the problem. The violation of the prior can then also be used to detect
boundaries [Bel93]. These priors usually take the form of a penalty for high depth gradients,
biasing the solution toward a piecewise continuous depth map [MS85]. One work making use
of a prior on the structure in the context of motion is [CFCHB89]. We have not used a prior
on the scene structure for two reasons. First, most common priors try to limit some derivative
of the depth as a function of image coordinates. This biases the result toward fronto-parallel
solutions. One would like to incorporate the concept of piecewise smoothness into a prior
instead of a low depth gradient. Secondly, a prior would destroy the simple direct solution to
the problem as found in Section 4 due to the coupling of motion and structure estimation. We
believe strongly that a coupling between the two problems can lead to more robust estimation
of both structure and motion, but that the proper prior has not been investigated.
2.3 Scene Partitioning Problem
In Section 6 we will see that we can formulate the segmentation of the optical flow field
into a scene partitioning problem [Lec89]. In such problems, a partition of the image into
distinct regions according to an assumed model or descriptive language is desired. The problem
is formulated in terms of a cost functional which attempts to balance a number of model
constraints. These constraints include terms for fitting a smooth model to the data while
simultaneously minimizing the number of distinct regions. The cost functional is often modeled
as the probability of a given solution assuming gaussian departures from the model. Leclerc
[Lec89] showed that the minimal solution could also be interpretated as the minimal length
encoding describing the scene in terms of a given descriptive language.
There are stochastic [GG84], region-growing [BF70, HP74], and continuation [Lec89, BZ87,
GY91] methods for finding solutions to the scene partitioning problem when it is described in
terms of a cost functional. Stochastic methods use simulated annealing programs in which a
gradient descent method is perturbed by a stochastic process which decreases in magnitude
as the global minimum is approached. Continuation methods start from some variation of
the cost functional where a solution can be easily found. The modified cost functional is
then continuously deformed back to its original form and the solution is tracked during the
deformation. If the deformation is slow enough, the solution will track to the global minimum
of the original cost functional. This is the basis of the Graduated Non-Convexity Algorithm of
Blake and Zisserman [BZ87] and the mean field theory approach of Geiger and Girosi [GG91].
Our solution will use the region-growing method described in [Web94] to solve for the
partition. This method uses a statistic-based region growing algorithm which assumes the
solution is piecewise continuous in image coordinates.
3 Projections and Rigid Motions
This section will describe the weak perspective camera. The linear constraint introduced by
a rigid motion leads to a special form of the Fundamental Matrix. We will also introduce
the representation for rotations used by Koenderink and van Doorn [KvD91] and show how
the components of the Fundamental Matrix can be used to obtain the rotation and scale
parameters.
3.1 The Weak Perspective Camera
The weak perspective camera is a projection from 3D world coordinates to 2D scene coordi-
nates. The projection is scaled orthographic and preserves parallelism. The projection can be
as:
where X is the 3D world coordinate point and x its 2D image projection. The 2x3 matrix M
rotates the 3D world point into the camera's reference frame, scales the axes and projects onto
the image plane. The vector t is the image plane projection of the translation aligning the two
frames. The simplest form of the matrix M occurs when the world and camera coordinates
are aligned and the camera's aspect ratio is unity. In this case M can be written
where Z ave is the average depth of the scene. This transformation is a valid approximation to
a real camera only if the variance of the depth in the viewed scene is small compared to Z ave .
We will assume that in the first frame the camera and world coordinates are aligned such that
M takes the form above.
A rigid transformation of the world points that takes the point X to X 0 can be written as
where R is a rotation matrix with unit determinant. The projection of the point x after
undergoing this transformation is
which is another weak perspective projection. Under the assumption above, M 0 is simply
All perspective effects have been incorporated into the change in average depth Z 0
ave \Gamma Z ave .
Introducing the scale factor ave =Z 0
ave we can relate the two frames by
where the translation component t 0
is sMT. We can write the rotation matrix R as being
composed of a 2 \Theta 2 sub-matrix, B, and two vectors, d and f .
f
where the matrix B and vector d are
R
R 23A (8)
R i;j are the elements of the rotation matrix R. Because the matrix M removes the third
component of its right multiplying vector, the values of the vector f do not enter into the
elements of x 0 . From equation (1) we can write x 0 in terms of the first projected point x,
Z i is the scaled depth [SZB93] at point x, -
ave with Z i
being the true depth.
We can eliminate the depth component -
Z i to get a linear constraint relating x and x 0 . By
multiplying equation (9) by the vector orthogonal to d we obtain the linear constraint
In terms of image coordinates this linear constraint is
where
This constraint can be written in terms of a special form of the Fundamental Matrix.
z
x
y
f

Figure

1: Koenderink and van Doorn representation for rotations: a rotation about the viewing
direction followed by a rotation about an axis in the image plane, ~!.
This form has 5 non-zero terms which can be determined only up to a scale factor since any
scalar multiplying equation (14) does not change the result. The form of F is
c d eC C C A (15)
3.2 Koenderink and van Doorn Rotation Representation
A rotation in space can be expressed in a number of representations: Euler angles, axis/angle
quarternions etc. A particularly useful representation for vision was introduced by Koenderink
and van Doorn [KvD91]. In this representation, the rotation matrix is the composition
of two specific rotations: the first about the viewing direction (cyclorotation) and the second
about an axis perpendicular to the viewing direction at a given angle from the horizontal (see

Figure

1.) Assuming that the viewing direction is along the z axis, the rotation matrix for a
rotation of ' about z, and of ae about ~! is
where ~! is an axis in the image plane at an angle of OE from the horizontal. The rotation about
the viewing direction provides no depth information. All information about structure must
come from the rotation about an axis in the image plane. This representation separates the
rotation into an information containing component and a superfluous additive component.
Using the notation above the total rotation matrix can be written
Using these values in the formation of the Fundamental Matrix as in equations (11,15) we
find that
The motion parameters of interest can be obtain from the matrix elements:
Equations (18) and (19) are identical to the ones used in Shapiro et al. [SZB93]. In their
application, they require a test to see if the angle ' from the arctan function is correct or
is too large by a factor of -. Since we are dealing with small motions which occur between
consecutive frames, we can assume that the angle ' is less than - and thus subtract - if the
arctan function returns a ' with magnitude larger than -.
We have shown that given the elements of the Fundamental Matrix in (15), one can obtain
the motion parameters s; OE; and '. The angle ae in (17) can not be obtained under weak
perspective from just two views because of an unknown scaling factor, as proved by Huang
and Lee [HL89]. Koenderink and van Doorn [KvD91] solve for ae from three views using a
non-linear algorithm.
4 Solving for the Fundamental Matrix
In the previous section we saw how under the assumptions of an affine camera model, the
displacement field for a rigidly moving object satisfies an affine epipolar constraint (11). This
Measured
d
Constraint line for point x
Uncertainty Ellipsoid

Figure

2: Epipolar geometry constrains the displacement vector to lie on a line in velocity space.
The perpendicular distance between this line and the measured displacement is minimized to find
the parameters of the Fundamental Matrix.
constraint says that a point (x; y) in the first frame will be projected to a point somewhere on
a line in the second frame. The location of this line is dictated by the Fundamental Matrix.
In our scenario, the location of the point in the second frame is given by the optical flow,
v). The constraint can be written in terms of the optical flow,
where the Fundamental Matrix elements are related to the primed values by c
d+ b. The affine epipolar constraint equation forces the optical flow to lie on a line in velocity
space. Since optical flow is a measured quantity sensitive to noise, the flow may not lie on the
lines dictated by the Fundamental Matrix constraint. We can use weighted least squares to
solve for the parameters (a; b; c by minimizing the weighted distance in velocity space
between the measured optical flow and the constraint line (see Figure 2).
min
The weighting factor, w i , comes from the error covariance of the measured optical flow,
=\Omega ~v . Instead of minimizing the distances in velocity space between the epipolar
constraint line and the measured optical flow (21), one could minimize the distance in
image coordinates between the point in both frames and the respective epipolar constraint
lines. (The rigid transformation from frame 1 to frame 2 implies an epipolar constraint on
points in frame 2. By symmetry, the reverse motion implies an epipolar constraint on points
in frame 1.) This is the standard minimization when instead of optical flow, the measurements
consist of feature points tracked from frame to frame. When using feature correspondences the
point positions in both frames are subject to error. By using optical flow, we are assuming the
flow is associated with a particular point in the first frame. The flow itself is subject to error,
but not the image location. Therefore it is more appropriate to minimize in velocity space.
Equation (21) is similar to the cost function E 2 in Shapiro et al. [SZB94]. Adopting their
terminology, we write ~ The minimization is performed
by using a Lagrange multiplier, -, on the constraint a We introduce the diagonal
matrix Q which is zero except for ones at entries Q 1;1 and Q 2;2 . The constraint then becomes
which is equivalent to setting a
min
(~ n;e)
The minimization over e can be done immediately by setting
is the weighted centroid of the 4D points ~ x i . Substituting e into equation (22)
we have
min
where the measurement matrix
Differentiating with respect to ~ n and using the fact that Q T we obtain the matrix
equation
Since Q has only two non-zero entries, finding the value of - which causes (W \Gamma -Q) to drop
rank involves only a quadratic equation in -. In addition, W is real-symmetric so we also
know that - will be real. As will be shown in the next paragraph, the smaller of the quadratic
equation's two solutions is the one desired. The solution ~ n is now the vector which spans the
null space of (W \Gamma -Q). We normalize the solution by setting jjQ~ njj which results from
differentiating (23) with respect to -.
The sum in equation (21) can be found by substituting the solution for ~ n into (21). Using
the fact that W~ summation is simply -. Thus the sum of squared distances in
velocity space for the minimal fit can be found by solving the cubic equation implied by (24).
The solution ~ n minimizes the weighted sum squared distances in velocity space between the
epipolar constraint line and the measured displacements.
The correct weighting factor w i to use in the weighted least squares solution would be the
reciprocal of the variance in the direction perpendicular to the epipolar line, F~x. Using the
fact that ~ n is normalized this value is
Since we do not know ~ n before minimizing the cost functional (22), we can not know the values
of the w i . We therefore use the value of
trace(\Omega ~v ) as an initial value of w i and update once
we find ~ n. Weng et al. [WAH93] also calculated weighting factors in this fashion for their
non-linear minimization. At each iteration of their algorithm they recalculated the weights.
We will see in Section 7 that the variance of the optical flow measurement in the direction
parallel to the epipolar constraint line determines the uncertainty in the value of the depth
recovered. This is in contrast to the uncertainty perpendicular to the epipolar line which is
used here.
The fact that the total contribution to the cost functional for a particular choice of Fundamental
Matrix can be found from the elements of the matrix W and centroids of the measurements
makes it easy to calculate the least-squares solution for any combination of subsets
of the measurement data. Suppose we calculate the measurement matrices W 1
separate regions of the image, R 1 If we wish to know the change to the cost functional if
we assign a single ~ n to the combination of the image regions, we need to compute the combined
measurement matrix W which is a simple function of the elements of the separate matrices
and the centroids -
. The result is that only a simple calculation need be
performed to determine whether it would be advantageous in terms of cost for two regions to
combine their measurements into a single region. This fact is the basis for the simultaneous
segmentation and epipolar geometry calculation algorithm outlined in Section 6.
5 The Case of Affine Flow
The solution for the Fundamental Matrix elements in equation (24) requires that the matrix
three, i.e. the null space has dimension one. Otherwise, more than one
solution can exist. One case where this occurs is when the optical flow is affine in image
coordinates. That is, when@ u
vA =@ a b
c dA@ x
In this case, a linear relationship exists between (u; v) and (x; y) and thus W drops rank. The
Fundamental Matrix cannot be uniquely determined in these cases. This is a consequence of
that fact that a family of motions and scene structures can give rise to the same affine flow.
This observation was also made by Ullman [Ull79], but without reference to the Fundamental
Matrix. The non-trivial causes of affine flow are either a special arrangement of the points
observed (co-planarity) or special motions. The causes are enumerated below.
Case 1: Co-planar points. When the observed points are co-planar, a constraint exists
on their three dimensional coordinates of the form Ax
perspective, the depth of the projected point at image coordinates x is then a linear
function of x, i.e. Z From equation (9) we see that x 0 , the coordinates of
that point in the second view, is a linear function of x and thus the optical flow is affine
in image coordinates.
ffl Case 2: No rotation in depth. If there is no rotation in depth (the rotation ae in the
Koenderink and van Doorn representation, Figure 1) then the vector d in equation
is zero. As above, this causes x 0 to be a linear function of x and thus the optical flow is
affine.
If there is rotation in depth, multiple observations can be used to resolve Case 1. Under
the assumption that the rigid motion of each independently moving object does not vary
significantly from frame to frame, the individual Fundamental Matrices can be viewed as
being constant. We can therefore use more than one optical flow field in order to determine
them. The measurement matrix W formed from multiple frames will regain full rank. This
comes from the fact that we are viewing the plane from different views, and as a result, it
gains depth, as illustrated in Figure 3. In fact under orthographic projection, 4 non-coplanar
point correspondences through 3 frames are sufficient to determine both motion and structure
in this case [Ull79].
Motions consisting of pure translational motion and/or rotation about an axis parallel to the
optical axis (Case 2) will always result in affine flow under weak-perspective and orthographic
projections. The measurement matrix will not gain rank with multiple frames. When a region

Figure

3: A planar object rotating about an axis perpendicular to the optical axis gains depth over
time. The use of multiple frames allows for the recovery of the motion which is ambiguous from
only two frames.
has been detected as containing affine flow, the motion can be recovered directly from the affine
parameters and objects can be segmented based on these parameters. Thus objects undergoing
pure translation can be segmented, even though the Fundamental Matrix for the motions is not
uniquely defined. Other motion segmentation algorithms based on the Fundamental Matrix
do not handle this case.
Since the optical flow is corrupted by noise, a criterion must be developed for deciding if a
region contains affine flow. A region is designated as containing affine flow via a ratio of the
singular values of the measurement matrix. The symmetric matrix W \Gamma -Q should have rank
three and therefore have three positive, non-zero singular values. If the singular values, oe i , are
numbered in increasing order, the following ratio is used to test for rank less than three:
oe 4
If this ratio is less than a given threshold, the matrix is assumed to have rank less than three.
For example, if a rank 2 matrix is perturbed with a small amount of noise, the singular values
oe 1 and oe 2 will be of order ffl, where ffl is small, while oe 3 and oe 4 will be of order ?? ffl. The
ratio (27) will then be very small. For the experiments, the threshold for the ratio was set to
calculations were done in double precision.
6 Segmenting via a Region-Growing Method
We wish to partition the scene into distinct regions, each region being labeled by a unique
Fundamental Matrix. We define a cost functional which balances the cost of labeling each pixel
with a penalty for having too many different labelings. We define as a total cost functional
E(~ n;
where the summation i is over all pixels in the image and N i is the set of nearest neighbor pixels
to i. The delta function ffi(\Delta) is equal to one when its argument is zero, and zero otherwise.
The vector ~ n i is the estimate of the Fundamental Matrix at pixel i. In terms of the standard
form of a cost functional [BZ87], D(~ n) represents a goodness of fit term which attempts to keep
the estimate close to the data, and P (~ n; ff) is a discontinuity penalty term which tries to limit
the frequency of discontinuities. The D(~ n) term is the weighted sums of squared distances in
velocity space with a Lagrange multiplier as defined in the Section 4. The penalty term attaches
a fixed cost ff for each pixel bordering a discontinuity since the value of
unity unless ~
Our model assumes that the scene can be segmented in a discrete way: there are a finite
number of regions with particular motion parameters attached to each. Thus the field ~ n is
piecewise constant, being constant within each region and changing abruptly between regions.
This problem is an example of the scene partitioning problem [Lec89] in which the scene is to
be partitioned into distinct regions according to an assumed model or descriptive language.
The minimum of the cost functional E(~ n; ff) can be seen as a maximum apriori probability
(MAP) estimate if we model the deviations from the fit as coming from a stochastic process
with certain priors.
To solve this partitioning problem we will use the region-growing method described in
[Web94]. We outline the method below.
From the previous section we saw that computing the cost (in terms of deviation of fit from
data) of combining information from different regions involves only simple operations. The fit
cost for combining two regions, DR 1 +R 2
can be compared to the fit cost of the two regions
separately, DR 1
. The algorithm decides whether these two regions should be merged
via the statistic
which can be shown to be similar to an F -test statistic. The factor \Delta is the tolerated difference
between regions that can be considered similar.
The algorithm begins by forming small initial patches of size 4 \Theta 4 pixels. Each of these
patches then computes its solution, ~ n, and error, DR . For a small value of \Delta, all regions which
can be combined when the statistic F 0 is below a fixed confidence level are merged. Newly
formed regions are tested for affine flow solutions. The value of \Delta is increased and all possible
mergings are checked again. This continues until we reach the final value of \Delta. See [Web94]
for details and application of the algorithm on a range of scene segmentation problems.
The use of a statistical test for flow-based segmentation can also be found in [NSKO94,
BR87]. In these cases however, the deviation of the optical flow from affine parameters is
tested instead.
The statistical test can not be used to compare an affine region with a non-affine region
because there exists a subspace of solutions for the Fundamental Matrix in the affine case.
The same test however can be used between two affine regions. In this case, the cost term D
in equation (29) is the sum of squared errors between the measurements and the least-squares
affine motion fit. The same statistical test is used for both affine and non-affine regions in the
region growing algorithm, but with different data terms D in the statistic F 0 .
7 Recovering Depth
Once we have recovered the elements of the Fundamental Matrix for a region of the image
plane, we can attempt to recover the depth of each image point. From Section 3.1 we saw that
the projected point x in the second frame is
From the elements of F we know the direction of the vector d. Taking the dot product of
equation (31) with d and rearranging we obtain
We can not solve directly for the d T t 00
term since we do not have enough information to recover
the full translation. However the d T t 00
term is a constant throughout the object's projection.
The remaining terms are known (up to a scale factor). Solving for -
Z i we find
ay
is a constant for each object. Therefore, up to an additive constant
Z c , the scaled depth of each imaged point can be computed given the elements of the matrix
F .
The recovered depth map from (33) is a direct function of the optical flow measurements
and therefore noisy. The first term of equation (33) is the distance in velocity space along the
line Fx. If we know the error covariance of our measured optical flow, var(~v T ~v)
then the uncertainty of the measurement in the direction parallel to the epipolar line Fx is
equal to the uncertainty in the depth estimate. Thus from our solution to the fundamental
matrix, the relative weighting factor, q i , which represents the inverse of this uncertainty should
be
i\Omega ~v
~
n 0 is the unit vector perpendicular to ~ n. This is in contrast to
the weighting factor w i used in Section 4 for the deviation of the estimate in the direction
perpendicular to the epipolar constraint. This separation of depth and motion parameters
estimation was also pointed out by Weng et al. [WAH93].
The final depth estimate -
Z i is found using a weighted sum of local estimates.
where the
region\Omega is the intersection of a local region about the point x i and the rigid motion
region associated with that point. We are not including depth values from separate regions,
but we are making the assumption that local points on the object have similar depths.
In the case of affine flow, we know that the object is either undergoing pure translation or
is rotating about an axis parallel to the optical axis. In either case, no depth information can
be obtained under orthographic or weak-perspective projection. Consequently depth recovery
would have to rely on other cues.
In the formalism presented here, the determination of structure is separate from that of
motion. Once the motion is found, the depth comes directly from equations (33) and (34).
One of the strengths of the epipolar constraint is that it places no limit on the scene structure.
The scene could consist of a cloud of randomly placed points. One could however introduce
priors on the scene structure to regularize the estimate, as is done in stereopsis. This work
has not examined the use of structure priors beyond the local smoothness implied by equation
Object Two
Object One
Prediction Time t+1
Unassigned
Segmentation Time t

Figure

4: Illustration of the calculation of the predicted segmentation based on the current segmentation
and optical flow. The unassigned regions which have associated flow vectors will be filled in
by the segmentation algorithm which begins with the prediction image.
8 Object Tracking
Once the separate objects have been segmented, we would like to track them with time.
Beginning with the initial segmentation formed from the first three flow fields, the algorithm
proceeds by taking the present segmentation and forming a prediction of the segmentation for
the next flow field.
The prediction is formed by taking the current pixel assignment and translating it along
that pixels' optical flow vector. The assignment is rounded to the nearest integral pixel value.
Disoccluded regions are left unassigned. The segmentation algorithm is run on this prediction
image to fill in the unassigned regions. This is repeated for each new optical flow field. New
objects can be introduced if, after filling in the unassigned regions, a new region is formed
which does not merge with any of the existing regions. Figure 4 illustrates the prediction
method.
The proposed scheme avoids having to run the entire segmentation algorithm from scratch
at each new frame since it uses the previous segmentation as a prediction. Also, it avoids the
problem of matching regions in the new frame with those of the previous frame. However, this
method requires a correct initial segmentation. If two objects are labeled as a single object in
the initial segmentation they may remain so in subsequent frames.
Once we have correctly labeled the optical flow vectors in a frame according to which
rigid object they correspond to, we can use the information in each new frame to increase the
accuracy of both the shape and motion of each independently moving object. At this point
we can relax the assumption that the rigid motion parameters are constant from frame to
frame which was used to form the initial segmentation. We adopt a Kalman filter approach in
which the motion parameters are modeled as a process with a small amount of noise. In this
way the motion parameters can change with time. Each new optical flow field provides a new
measurement for estimating this varying state.
The work by Soatto et al. [SFP94] addresses the case of estimating the elements of the
Fundamental Matrix in a Kalman Filter framework. Although their work was for the full
Fundamental Matrix, it is easily adapted to the simpler affine form. The difficult part of using
a Kalman Filter approach to tracking the motion parameters is that the relation between
measurements, the optical flow, and state variables is not linear. Instead there exists the
epipolar constraint, equation (11), relating the product of the two. One can linearize this
implicit constraint about the predicted state to produce a linear update equation. Details can
be found in [SFP94]. We will simply state the results for the affine case below.
In what Soatto et al. call the Essential Estimator, the state consists of the 5 non-zero
elements of the affine Fundamental Matrix, ~ n(t). The vector ~ n(t) lies on the subspace of IR 5
corresponding to jjQ~ They model the dynamics of this state as simply being a random
walk in IR 5 which has been projected onto the jjQ~ As new measurements come
in, the value of ~ n(t) as well as an estimate of the error covariance, P (t), are updated. Borrowing
their notation, where represents the prediction at time t
to time t, and (t represents the estimate given measurements up to time t + 1, the
filter equations are:
Update:
Gain Matrices:
The matrix X is an n \Theta 5 matrix whose rows are made up of the n measurement vectors,
1). The measurement error covariance matrix R x (t) is a diagonal matrix consisting
of the weighting terms w
i\Omega ~v ~ n) \Gamma1 defined in Section 4. The operation \Phi is addition plus
a projection back onto the jjQ~ As a result, the gain matrix applies a change
to ~ n which is then normalized back to jjQ~
9 Experimental Results
The algorithm was tested on a number of synthetic and real image sequences. The optical
flow was computed using the multi-scale differential method of Weber and Malik [WM95].
The algorithm also produced the expected error
covariance,\Omega ~v , associated with each flow
estimate.
For each sequence, the segmentation of the scene into distinct objects, the tracked motion
of these objects, and the scaled scene structure are recovered. We begin with a synthetic
sequence in order to compare ground truth data with the tracked motion parameters.
9.1 Sequence I
Two texture-mapped cubes rotating in space were imaged on a Silicon Graphics computer
using its texture-mapping hardware. The still frames were used as input to the optical flow
algorithm. The magnitude of the optical flow ranged from zero to about 5 pixels/frame. For
the first 10 frames of the sequence, the cubes were rotating about fixed but different rotation
axes. For the second 10 frames these axes were switched. In this way we could examine the
recovery of the motion parameters when they are not constant with time. The rotation axes
used, as well as a sample image and optical flow field are shown in Figure 5. At the edges of
the foreground cube, the assumptions of a differential method for optical flow are invalid. As
a result the optical flow is noisy and confidence is low. If we were to attempt to find shape
boundaries by differentiating the flow field components, we would have difficulty in the very
regions which we are trying to find since the flow is not defined there.
The segmentation algorithm found two separate moving objects for each frame. The initial
segmentation along with the initial depth recovered for the smaller cube is shown in Figure 6.
The estimated angle OE as a function of frame number for each cube is shown in Figure 7.
The original estimate is good because of the density of the optical flow. Subsequent frames do
not show much improvement. The Kalman Filter successively tracks the change in rotation
axis which occurs at frame 10. Within a few frames the estimate is locked onto the new
directions. The response time of the tracker can be changed by increasing or decreasing R n ,
the expected variance in motion parameters in equation (36).
9.2 Sequence II
The algorithm was run on a real sequence consisting of a cube placed on a rotating platen.
(This sequence was produced by Richard Szeliski at DEC and obtained from John Barron). The
background was stationary. The displacements between frames are very small in this sequence,
with the largest displacement on the cube itself being only 0:5 pixel. The background had zero
flow and was labeled as affine. An image from the sequence, the computed optical flow and
recovered depth map are shown in Figure 8.
In this case, the rotation axis of the cube makes an angle of 90 degrees in the image plane.
The recovered value of this angle as a function of frame number is shown in Figure 9. Again the
large number of measurements from the initial segmentation produced an accurate estimate.
9.3 Sequence III
The next image sequence consists of textured patterns translating in the background while a
toy train moves in the foreground. The planar background produces uniform flow. A frame
from the sequence, an example optical flow recovered and the segmentation are shown in

Figure

10. The planar background regions were correctly recognized as consisting of affine
flow.
This sequence demonstrates the algorithm's ability to identify regions of affine flow. The
boundaries appear irregular because no priors on the segmentation are used. Priors favoring

Figure

5: Two independently rotating texture-mapped cubes were created on a Silicon Graphics
workstation. A single frame from the sequence and a sample optical flow field is shown on the
top row. For the first 10 frames, the cubes rotated with rotation axes indicated in the bottom left
figure. For the second 10 frames, the rotation axes were as indicated in the bottom right figure.

Figure

The boundary between the two independently moving objects found by the segmentation
algorithm and the pixel depths of the smaller cube.
Frame Number
-20.020.0Degrees
Rotation Axis Angle
Foreground Cube
True
Estimate
Frame Number
-20.020.0Degrees
Rotation Axis Angle
Background Cube
True
Estimate

Figure

7: The recovered value of the angle the rotation axis of each cube makes in the image plane
as a function of frame number. After 10 frames, the rotation directions were switched.

Figure

8: A single frame of a Rubik's Cube on a rotating platen. The optical flow and recovered
depth map as seen from a side view are shown below.
Frame Number85.095.0Degrees
Rotation Axis Angle
Rubik Cube

Figure

9: A single frame of a Rubik's Cube on a rotating platen. The optical flow and recovered
depth map are shown below.
straight over jagged boundaries could be introduced as well as combining information from
intensity and texture boundaries [BJ94].
Discussion and Future Work
We have shown that even with just the optical flow of an image sequence, it is possible to
segment the image into regions with a consistent rigid motion and determine the motion
parameters for that rigid motion. Furthermore, the relative depth of points within the separate
regions can be recovered for each point displacement between the images.
The recovery requires no camera calibration but does make the assumptions of an affine
camera: i.e. perspective effects are small. The special form of epipolar geometry for the case
considered here has its epipoles at infinity. Perspective dominant motions can not be fit by the
motion parameters. The region-growing algorithm used for the simultaneous region formation
and motion parameter estimation was not dependent on this particular form of the geometry.
If a recovery of the full perspective case was required, the same algorithm could be used.
However, the calculation of the Fundamental Matrix from small displacements such as found
in optical flow is not stable [WAH93, LDFP93].

Figure

10: A single frame of the "mobile" sequence from RPI. The background consists of translating
patterns while a toy train traverses the foreground. An example optical flow recovered is also
shown. The labeled image is shown below. The background parts (colored grey) were identified as
undergoing pure translational motion by the singular value ratio test. The black and white colored
regions (corresponding to the train, rotating ball and transition regions) were not labeled as affine.
Another method of motion segmentation based on the Fundamental Matrix can be found
in [Tor93, TM94]. In this paper, the displacement vectors are segregated by finding outliers in
a robust estimation of the Fundamental Matrix. Clusters of displacements are found through
an iterative method. The combinatorial explosion of dense displacement fields would make
this method difficult to implement. We take advantage of the gross number of estimates to
gain robustness as opposed to finding specific outliers. However, the eigenvector perturbation
method discussed in [Tor93] would make an easy test for outliers and could be implemented
in our framework to detect and remove outliers.

Acknowledgements

This research was partially supported by the PATH project MOU 83. The authors wish to
thank Paul Debevec for creating the synthetic image sequence.



--R

Determining three-dimensional motion and structure from optical flow generated by several moving objects
Constraints for the early detection of discontinuity from motion.
A Baysian Approach to the Stereo Correspondence Problem.
Scene analysis using regions.
Estimating optical flow in segmented images using variable-order parametric models with local deformations
Combining intensity and motion for incremental segmentation and tracking over long image sequences.
A hierarchical likelihood approach for region segmentation according to motion-based criteria
Visual reconstruction.
Toward a model-based bayesian theory for estimating and recognizing parameterized 3-d objects using two or more images taken from different positions
Stochastic relaxation
Parallel and deterministic algorithms from mrf's: Surface reconstruction.
A common framework for image segmentation.
Motion and structure from orthographic pro- jections
Picture segmentation by a directed split-and- merge procedure
Affine structure from motion.
On determining the Fundamental matrix: analysis of different methods and experimental results.
Constructing simple stable descriptions for image partitioning.
The Fundamental matrix: theory
A Computer Algorithm for Reconstructing a Scene from Two Projections.
Boundary detection by minimizing functionals.
Detecting the image boundaries between optical flow fields from several moving planar facets.
Motion boundary detection in image sequences by local stochastic tests.
Motion segmentation and correspondence using epipolar constraint.
multiple motions from optical flow.
Image flow segmentation and estimation by constraint line clustering.
Recursive motion estimation on the essential manifold.
Three dimensional transparent structure segmentation and multiple 3d motion estimation from monocular perspective image sequences.
The early detection of motion boundaries.
Motion from point matches using affine epipolar geometry.
Motion from point matches using affine epipolar geometry.
Uniqueness and estimation of three-dimensional motion parameters of rigid objects wirth curved surfaces
Shape and motion from image streams under or- thography: a factorization method
Stochastic motion clustering.
Dynamic occlusion analysis in optical flow fields.
Outlier detection and motion segmentation.
The Interpretation of Visual Motion.
Representing moving images with layers.
Optimal motion and structure estimation.
Scene partitioning via statistic-based region growing
Robust computation of optical flow in a multi-scale differential framework
--TR

--CTR
M. M. Y. Chang, Motion segmentation using inertial sensors, Proceedings of the 2006 ACM international conference on Virtual reality continuum and its applications, June 14-April 17, 2006, Hong Kong, China
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
Alireza Bab-Hadiashar , David Suter, Robust segmentation of visual data using ranked unbiased scale estimate, Robotica, v.17 n.6, p.649-660, November 1999
A. Mitiche, Joint optical flow estimation, segmentation, and 3D interpretation with level sets, Computer Vision and Image Understanding, v.103 n.2, p.89-100, August 2006
Niloofar Gheissari , Alireza Bab-Hadiashar , David Suter, Parametric model-based motion segmentation using surface selection criterion, Computer Vision and Image Understanding, v.102 n.2, p.214-226, May 2006
shape from motion;fundamental matrix;epipolar constraint;scene partitioning problem;motion segmentation;optical flow