Motion-based segmentation and contour-based classification of video objects.
The segmentation of objects in video sequences constitutes a prerequisite for numerous applications ranging from computer vision tasks to second-generation video coding.We propose an approach for segmenting video objects based on motion cues. To estimate motion we employ the 3D structure tensor, an operator that provides reliable results by integrating information from a number of consecutive video frames. We present a new hierarchical algorithm, embedding the structure tensor into a multiresolution framework to allow the estimation of large velocities.The motion estimates are included as an external force into a geodesic active contour model, thus stopping the evolving curve at the moving object's boundary. A level set-based implementation allows the simultaneous segmentation of several objects.As an application based on our object segmentation approach we provide a video object classification system. Curvature features of the object contour are matched by means of a curvature scale space technique to a database containing preprocessed views of prototypical objects.We provide encouraging experimental results calculated on synthetic and real-world video sequences to demonstrate the performance of our algorithms.
INTRODUCTION
Video object segmentation is required by numerous applications
ranging from high-level vision tasks to second-generation
video coding [25]. The MPEG-4 video coding
standard [10] provides functionality for object-based video
coding. Video information can be encoded in a number of
arbitrarily shaped video object planes.
Automatic content analysis and indexing methods can
benet from object segmentation algorithms. For instance,
it is possible to summarize videos based on the occurrence
and activities of video objects [14].
Algorithms for high-level vision tasks such as shape-based
object recognition [26, 19, 2] depend on information with
regard to object outlines.
We propose an approach to segmenting video object based
on motion cues. Motion estimation is performed by estimating
local orientations in a spatio-temporal neighborhood
with the 3D structure tensor. Thus, information from a
number of consecutive frames is exploited. We present a new
hierarchical algorithm that embeds the tensor-based motion
estimation into a multiresolution framework to allow the calculation
of large displacements. The nal segmentation is
performed by a geodesic active contour model, enabling the
simultaneous detection of multiple objects.
Furthermore, we provide a video object classication system
that categorizes the segmented video objects into several
object classes (e.g. cars, people). This classication
system matches curvature features of the object contour to
a database containing preprocessed views of prototypical objects

The remainder of the paper is organized as follows: After
summarizing related work, Section 3 describes our segmentation
approach. Section 4 introduces the video object clas-
sication system. Section 5 presents experimental results.
Finally, Section 6 oers concluding remarks.
2. RELATED WORK
Various approaches have been proposed in the eld of motion
estimation and segmentation. A number of optical
ow
techniques are reviewed in [3, 4, 18].
Mech and Wollborn [16] estimate a change detection mask
by employing a local thresholding relaxation technique. Regions
of uncovered background are removed from this mask
by using a displacement vector eld.
In [13] an edge map is calculated from the inter-frame dif-
Figure

1: From left to right: (a) Frame 10 from the taxi sequence, (b) optical
ow with Lucas Kanade
ow with 3D structure tensor.
ference image using the Canny edge detector [6]. The edge
map|containing edge pixels from both frames|is compared
to the edge map of the current frame and to a background
reference frame. The nal segmentation is achieved by morphological
operators and an additional lling algorithm.
Meier and Ngan [17] propose two approaches. First, they
combine an optical
ow eld with a morphological operator.
Second, they employ a connected component analysis on the
observed inter-frame dierence in conjunction with a lling
procedure.
Paragios and Deriche [21] propose a statistical framework
based on Gaussian and Laplacian law to detect the moving
object's boundary in combination with boundaries obtained
from the current frame. They integrate the motion detection
and the tracking problems into a geodesic active contour
model.
In object classication, contour-based techniques have been
under study for a long time. Overviews can be found in [22,
15, 8].
One of the more promising contour analysis techniques
is the curvature scale space method (CSS) introduced by
Mokhtarian [20, 19] for still images. Here, the contour of an
already segmented object is compared to a database containing
representations of preprocessed objects. The technique
does not depend on size or rotation angle and is robust to
noise. In [2] a modied CSS technique can be found. Re-
cently, Richter et al. [23] extended the CSS technique to
include the classication of video objects.
3. VIDEO OBJECT SEGMENTATION
In addition to the color and texture information already
available in still images, a video sequence provides temporal
information. While it is hard to extract semantically
meaningful objects based on color and texture cues only,
motion cues facilitate the segregation of objects from the
background.
Consequently, the rst step in our approach is to choose
an appropriate motion detector. Various methods have been
proposed to estimate motion [3, 4, 18]. However, most of
them determine motion parameters on the basis of only
two consecutive frames. Hence, these techniques are sensitive
to noise and require appropriate compensation methods

Figure

1 illustrates this observation for the classical
Lucas Kanade algorithm. We calculated the optical
ow for
frame 10 of the taxi sequence with the Lucas Kanade implementation
used in [3]. The parameters were set to
and 2 > 5 (see [3] for details), motion vectors shorter than
pixel/frame are suppressed in the gure. The taxi sequence
contains four moving objects: the taxi in the mid-
dle, a car on the left, a van on the right and a pedestrian
in the upper left corner. While the motion for the three
main objects is calculated reliably, several misclassications
occur due to noise in the background. Note that the result
can be improved signicantly by preprocessing the sequence
with a 3D Gaussian smoothing lter. However, a drawback
to pre-smoothing is the elimination of small structures, e.g.
the pedestrian in the upper left corner of the taxi sequence
cannot be detected.
In our approach, we employ the 3D structure tensor to
analyze motion [5]. Here, motion vectors are calculated by
estimating local orientations in the spatio-temporal domain.

Figure

1(c) depicts the result for the structure tensor. Here,
background noise is eliminated without pre-ltering and reliable
motion detection is possible. Even small structures
like the pedestrian are identied.
In the following section we describe the structure tensor
technique. Then we present a new algorithm that embeds
the approach into a multiresoultion framework to allow the
detection of large velocities.
3.1 Tensor-based Motion Estimation
Within consecutive frames stacked on top of each other,
a video sequence can be represented as a three-dimensional
volume with one temporal (z) and two spatial (x; y) coor-
dinates. From this perspective, motion can be estimated
by analyzing orientations of local gray value structures [5].
Assuming that illumination does not vary, gray values remain
constant in the direction of motion. Thus, stationary
parts of a scene result in lines of equal gray values in parallel
to the time axis. Moving objects, however, cause iso-gray-
value lines of dierent orientations. Figure 2 illustrates this
observation.
Consequently, moving and static parts on the image plane
can be determined from the direction of minimal gray value
change in the spatio-temporal volume. This direction can be
calculated as the direction n being as much perpendicular
to all gray value gradients in a 3D local neighborhood
Thus, for each pixel at position (x;
Z
where r3 := (@x ; @y ; @z ) denotes the spatio-temporal gradi-
9zxFigure

2: Local orientation of image structures.
Left: Frame 169 (top) and frame 39 (bottom) of
the \hall and monitor" sequence. Right: Slice of
the corresponding spatio-temporal volume taken at
the horizontal line marked by the white lines in the
single frames.
ent, I the three-dimensional volume
and
a 3D neighborhood
around the pixel at position (x;
As described in [5, 9], minimizing Equation 1 is equivalent
to determining the eigenvector to the minimum eigenvalue
of the 3D structure tensor
J =4 Jxx Jxy Jxz
Jxy Jyy Jyz
Jxz Jyz Jzz5 (2)
are calculated within a local neigh-
borhood
from
Z
By analyzing the three eigenvalues 1  2  3  0
of the 3  3 symmetric matrix, we can classify the local
neighborhood's motion. In general, an eigenvalue  i  0
indicates that the gray values change in the direction of the
corresponding eigenvector e i . Figure 3 illustrates the relationship
between local structures, eigenvalues, and eigen-vectors
in the two-dimensional case. Consider, for instance,
case 1, where the local
neighborhood
is centered over a
horizontal structure. The gray values within this neighborhood
change in one direction. Consequently, 1  0;
and the eigenvector e1 gives the direction of the gray value
change.
Within the context of a three-dimensional neighborhood
the following observations can be made. All three eigen-values
equal to zero indicate an area of constant gray val-
ues, therefore no motion can be detected. If 1 > 0 and
only in one direction. This
corresponds to a horizontal (or vertical) structure moving
with constant velocity. Consequently, due to the correspondence
problem we can only calculate normal velocity.
Real motion can be calculated if gray values remain constant
in only one direction, hence, 1 > 0; 2 > 0 and
occurs when a structure containing gray value
changes in two directions moves at constant speed.
Finally, if all three eigenvalues are greater than zero, we
y

Figure

3: Local structures, eigenvalues, and eigen-vectors
in two dimensions. Case 1 (case 3): horizontal
(vertical) structure, gray values change in
one direction, i.e., 1  0, case 2: corner,
gray values change in more than one direction, i.e.,
cannot determine the optical
ow due to noise.
In real-world video sequences, however, it is impractical
to compare the eigenvalues to zero, since due to noise in
the sequence small gray value changes always occur. Thus,
we introduce normalized coherence measures c t and cs that
quantify the certainty of the calculations. The coherence
measure c t indicates whether a reliable motion calculation
is possible and is dened by
exp
C
else (4)
where C > 0 denotes a contrast parameter. Areas with
(j1 3 are regarded as almost constant local neighborhoods
[27]. A value of c t near 1.0 indicates that 1  3 ,
therefore, a reliable motion calculation can be performed.
The opposite is true if the c t value approaches zero.
The coherence measure cs ,
exp
C
else
provides information whether normal or real motion can be
determined. Values near 1.0 allow the calculation of real
motion. Otherwise only normal velocities can be specied.
As depicted in Figure 1(c), the structure tensor allows reliable
motion calculations and suppresses background noise
due to the integration of several consecutive frames. The
number of frames used in the motion calculation is determined
by the size of the neighborhood
Setting
for instance, means that the motion calculation for each
pixel is performed within a spatio-temporal area of 777
pixels.
3.2 Multiscale Motion Estimation
The motion detection approach described so far exhibits
problems with sequences containing large velocities. This
results from the xed size of the local neighborhood
Con-
sider an image feature that moves at high velocity. Conse-
quently, it changes its position by a large displacement from
one frame to the next. If the displacement exceeds the size
of the local neighborhood, the motion of the feature cannot
be detected.
To overcome this limitation we developed a new hierarchical
algorithm that embeds the structure tensor technique
in a linear scale-space framework. Hence, the calculations
are performed in a coarse-to-ne manner.
First, a Gaussian pyramid of L levels is constructed from
the video sequence. Let I 1 (x; denote the original sequence
of size (n 1
Then, the coarser levels are constructed
recursively, i.e., for I l is calculated
from I l 1 by spatial smoothing and spatial downsampling
by a factor of two.
Then, for each position
the optical
ow vector is calculated. The calculations
start at the coarsest level L. The position p L within this
level is determined as
within a local
neighborhood
centered at the position p L
the structure tensor J is calculated and the corresponding
eigenvalues are evaluated as described in Section 3.1. If motion
calculation is feasible, a motion vector v
y ) is
determined at this position. Note that due to the subsampling
procedure large displacements are reduced appropriately
and therefore can be captured within the local neighborhood

The motion vector v L determined at the coarsest pyramid
level L serves now as an initial guess g L 1 at the next pyramid
level L 1. Since the spatial dimensions double from
one level to the next, we adapt the initial guess accordingly,
i.e.,
y ). Thus, at this state we know that
at position p L an image feature
moves roughly according to g L 1 .
The goal at level L 1 is now to rene the initial guess.
This is done by (1) compensating for the motion vector
within the local neighborhood around p L 1 and (2)
by calculating a displacement vector d L 1 on the modied
neighborhood. Hence, the motion vector at this level, v L 1 ,
emerges from a combination of initial guess and displace-
ment,
The motion vector v L 1 is used as initial guess for the
consecutive pyramid level and the algorithm repeats until
the highest resolution is reached.
A crucial part of the algorithm is the motion compensation
that must be performed on each level in order to allow
the displacement calculation. Remember the calculations of
the structure tensor elements, e.g. the element Jxx :
Here, spatial derivations are calculated within a spatio-temporal
neighborhood around the position (x; z). If we
consider
patches from three frames of the
video sequence, namely, z 1, z, z+1, are involved in the cal-
culations. Consider now, that an initial guess
for this local neighborhood is available from the previous
pyramid level. Thus, to determine the additional displacement
d, it is rst necessary to compensate for this guess.
Consequently, Equation 6 changes to
i.e., from frame z patch around position
+gy ), from frame z 1 a patch around
and from frame z a patch around (x; y) is used. Obviously,
gx and gy need not be integer values. Thus, bilinear interpolation
is used to determine image values at the subpixel
level. Accordingly, the other elements of the tensor J are
calculated under motion compensation.
The need for motion compensation and the use of bilinear
interpolation techniques in the hierarchical algorithm clearly
aect the performance of the whole method. In order to
improve the eciency it is useful to eliminate those positions
in [0; n 1
y advance where presumably a
reliable motion calculation is not possible.
Again, the structure tensor, used here in the spatial domain

xy
xy J 0
yy
is a reliable indicator for this task. Remember that in the
two-dimensional case (see Figure 3) the eigenvalues 1 and
provide information about the texturedness of the local
neighborhood. Both eigenvalues larger zero indicate a
textured region. With respect to motion estimation it is
probable that this region can be identied in the consecutive
frame, too. Consequently, a full motion vector can
be calculated. If only one eigenvalue is greater than zero,
the area in question contains a horizontal or vertical struc-
ture. Therefore only motion in the direction of the gradient
(normal motion) can be determined. On the other hand,
a uniform region, i.e., no estimation of motion is possible,
results in 1  2  0.
Thus, Shi and Tomasi [24] propose the following reliability
measure:
i.e., a position (x; y) in the image contains a good feature to
track, if the lesser eigenvalue exceeds a predened threshold
T .
However, our purpose is slightly dierent because we want
to calculate any kind of motion occurring in the video se-
quence. Therefore, we modify the reliability measure (Equa-
tion to exclude only uniform regions from the motion
calculation:
exp
C
else.
A small sum of 1 and 2 result in values near zero, while
in all other cases the reliability measure adopts values near
one.
3.3 Motion-based Segmentation
As depicted in Figure 1(c), the motion estimation approach
is able to reliably identify regions of interest, though
some parts of the van are left out due to low contrast. How-
ever, tensor-based motion detection only is not sucient to
provide an accurate segmentation of the objects in question.
We observe two shortcomings that are inherent to this
approach. First, due to areas of constant gray values within
the moving objects we do not receive dense motion vector
elds. In these areas all three eigenvalues are close to zero
and therefore motion cannot be calculated. However, it is
likely that motion can be estimated at the spatial edges of
the moving objects.
Second, the tensor fails to provide the true object boundaries
accurately since the calculations within the neighbor-
hood
blur motion information across spatial edges.
Consequently, we need (1) a grouping step that will integrate
neighboring regions into objects while closing gaps

Figure

4: Tensor-driven geodesic active contour. From left to right: contour after 3000, 6000, 9000, 12000,
iterations. Constant force
and holes and (2) contour renement based on spatial edge
information.
Widely used within this context are active contour mod-
els. Basically, a planar parametric curve C(s) placed around
image parts of interest evolves under smoothness control (in-
ternal energy) and the in
uence of an image force (external
energy).
In the classical explicit snake model [11] the following
functional is minimized
I
ds (11)
where the rst two terms control the smoothness of the planar
curve, while the third attracts the contour to high gradients
of the image.
To obtain a topological
exibility that will allow the simultaneous
detection of multiple objects, we employ geodesic
active contours [12, 7]. The basic idea is to embed the initial
curve as a zero level set into a function
C is represented by the set of points x i with u(x i
to evolve this function under a partial dierential equation.
Using a modied energy term this results in the image
evolution equation [12, 7]
@t
where  denotes the curvature of a level set, r := (@x ; @y )
is the spatial gradient, c adds a constant force for faster
convergence, and g represents the external image-dependent
force or stopping function.
By dening an appropriate stopping function g, we can
integrate the tensor-based motion detection into the model.
Choosing
smoothed version of
stops the curve evolution positions are reached
that coincide with \motion pixels". Note that
denotes the 2D velocity available from the motion estimation
step. is a predened velocity threshold compared against
the norm of the motion vector. Hence, our segmentation
scheme assumes|in the current state |a static camera.
In the event of a moving camera, a global camera motion
estimation has to be performed rst. It should then be possible
to compare the motion vectors determined from the
structure tensor to the vectors resulting from the the global
camera parameters [17].

Figure

4 depicts the evolution of the tensor-driven geodesic
active contour. The contour succeeds in splitting up
and detecting the four dierent moving objects.
In order to improve the segmentation results, we employ a
renement procedure based not on motion information but

Figure

5: Contour renement. Left: motion-based
segmentation, right: motion-based segmentation
with contour renement (445 iterations, ~
on the gradient values within a single frame. As can be seen
in

Figure

5 (left), the motion-based segmentation detects
regions that are slightly larger than the moving objects.
Thus, we restart the image evolution process using the
result from the motion-based segmentation as the zero level
set. However, this time a stopping function ~ g based on the
spatial gradient is used:
~
Here, ~
C is a contrast parameter that diminishes the inuence
of low gradient values. Figure 5 depicts the performance
of the renement procedure.
4. VIDEO OBJECT CLASSIFICATION
Our system for object classication consists of two major
parts, a database containing contour-based representations
of prototypical video objects, and an algorithm to match
extracted objects with the database. In the following we
summarize the classication approach, for details see [23].
4.1 Curvature Scale Space Representation
The curvature scale space (CSS) technique [1, 20, 23] is
based on the idea of curve evolution, i.e., basically the deformation
of a curve over time. A CSS image provides a
multi-scale representation of the curvature zero crossings of
a closed planar contour.
Consider a closed planar curve (u),
with the normalized arc length parameter u. The curve
is smoothed by a one-dimensional Gaussian kernel g(u; )
of width . The deformation of the closed planar curve is
represented by
where X(u; ) and Y (u; ) denote the components x(u) and
after convolution with g(u; ).
(a) (b)
(c) (d)

Figure

Construction of the CSS image. Left: (a)-
(f) Object view and smoothed contour after 10, 30,
100, 200 and 300 iterations. The small dots on the
contour mark the curvature zero crossings. Right:
Resulting CSS image.
The curvature (u; ) of an evolved curve can be computed
using the derivatives Xu(u; ), Xuu(u;
and Yuu(u;
A CSS image I(u; ) is dened by
It shows the zero crossings with respect to their position
on the contour and the width of the Gaussian kernel (or the
number of iterations, see Figure 6). During the deformation
process, zero crossings merge as transitions between contour
segments of dierent curvature are equalized. Consequently,
after a certain number of iterations, in
ection points cease to
exist and the shape of the closed curve is convex. Note that
due to the dependence on curvature zero crossings, convex
object views cannot be distinguished by the CSS technique.
Signicant contour properties that are visible for a large
number of iterations result in high peaks in the CSS image.
However, areas with rapidly changing curvatures caused by
noise produce only small local maxima.
In many cases the peaks in the CSS image provide a robust
and compact representation of an object view's contour[19,
20]. Note that a rotation of an object view on the image
plane can be accomplished by shifting the CSS image left
or right in a horizontal direction. Furthermore, a mirrored
object view can be represented by mirroring the CSS image.
A main drawback to the basic CSS technique|where only
the two values (position, height) represent a peak in an CSS
image|is the occurrence of ambiguities. Certain contours
diering signicantly in their visual appearance nevertheless
have similar images. This is due to the fact that shallow
and deep concavities on a contour may result in peaks of
the same height in the CSS image.
presents several approaches to avoiding these
ambiguities, raising the computational costs signicantly.
In our extension [23] we extract the width at the bottom
of the arc-shaped contour corresponding to the peak. The
width species the normalized arc length distance of the two
curvature zero crossings enframing the contour segment represented
by the peak in the CSS image. For each peak in
the CSS image three values have to be stored: the position
of the maximum, its value (iteration or width of the Gaussian
kernel), and the width at the bottom of the arc-shaped
contour. It is sucient to extract the signicant maxima
(above a certain noise level) from the CSS image. For in-
stance, in the example depicted in Figure 6, and assuming
a noise level of only four data triples have to
be stored.
The matching algorithm described in the following section
utilizes the information in the peaks to compare automatically
segmented video objects with prototypical video
objects in the database.
4.2 Object Matching
The objects are matched in two steps. In the rst, each
automatically segmented object in a sequence is compared
to all objects in the database. A list of the best matches
is built for further processing. In the second step, the results
are accumulated and a condence value is calculated.
Based on it, the object class of the object in the sequence is
determined.
In order to nd the most similar object in the database
compared to a query object from a sequence, a matching
algorithm is needed. The general idea is to compare the
peaks in the CSS images of the two objects, based on the
characterization by the triples (height, position, width).
In a rst step, the best position to compare the two
images has to be determined. It might be necessary to
rotate or mirror one of the images so that the peaks are
aligned best. As mentioned before, shifting the CSS
image corresponds to rotation of the original object.
One of the CSS images is shifted so that the highest
peaks in both CSS images are aligned.
A matching peak is determined for each peak in the
rst object. Two peaks may match, if their position
and width are within a certain range. Only for the
highest peaks, does the height also need to be within
a certain range.
If a matching peak is found, the Euclidean distance
of the height and position of the peaks is calculated
and added to the dierence between the images. If
no matching peak can be determined, the height of
the peak in the rst query object is multiplied by a
penalty factor and added to the total dierence.
The matching algorithm might return 1, e.g. if no adequate
rotation could be found or if the highest maxima in
the CSS images do not match within a given tolerance range.
If this is the case, the two objects are signicantly dierent.
All top matches which were recognized are used for accu-
mulation. The object class with a percentage above 75 % is
considered to be the class of the sequence.
5. EXPERIMENTAL RESULTS
We subdivide the experimental results achieved with our
algorithms into three sections. First, we demonstrate the

Figure

7: Left: frame from the synthetic sequence,
right: motion eld calculated by the hierarchical
structure tensor approach (for better visibility the
ow image is subsampled by a factor of 4).
performance of the multiscale structure tensor approach on
a synthetic sequence containing large displacements. Sec-
ond, we provide segmentation results obtained by the tensor-
driven geodesic active contour with respect to two real-world
sequences. Finally, results calculated by the object classi-
cation algorithm are presented.
5.1 Multiscale Motion Estimation Results
To measure the performance of the hierarchical approach
described in Section 3.2, we created a simple synthetic video
sequence for which the displacements from one frame to the
next are known. Figure 7 (left) shows a frame in this sequence
that contains two moving squares. While the upper
square (square 1) moves at a constant velocity of 10 pixels
per frame from the right to the left, the other square (square
moves diagonally upwards at velocity of

Figure

7 (right) depicts the result obtained by our multiresolution
algorithm using 4 pyramid levels. A closer look
at the motion vectors calculated by the algorithm reveals
the following observations:
1. At the corners of the squares the velocity could be
estimated exactly (square 1: 2:
Remember that at a corner moving with
constant speed enough texture is available to allow the
calculation of the full image motion.
2. On account of the pyramidal structure the velocities
at horizontal and vertical structures approximate the
real image motion. In general, full motion calculation
is possible for points near the corners. At the coarsest
pyramid level each point on a horizontal or vertical
structure is near the corner (in our specic example).
Therefore, an initial full motion guess for these points
can be calculated. However, for consecutive pyramid
levels full motion calculation is no longer possible since
the distance to the corners increases. Consequently,
the displacements added to the initial guess rene the
motion estimation only in the normal direction.
3. For pixels in the interior of the squares it is not possible
to calculate image motion. The reliability measure
described in Equation 10 eliminates these points from
the calculations.
The results for the synthetic sequence indicate that|
under specic circumstances|the proposed approach is able
to estimate motion exactly even given the existence of large
displacements.
Object Frame FP FN FP FN
car 7 156 61 9.12 3.73
car
car 9 208
car
van 7 135 448 10.77 28.61
van 8 176 663 15.04 40.01
van 9 288 522 22.15 34.03
van 11 246 800 19.54 44.13

Table

1: Region-based distance for the taxi se-
quence. Columns 3, 4: false positives, false nega-
tives. Columns 5, percentage of mismatched pixels
in comparison to the entire number of pixels of
the manual segmentation.
Object Frame avg.
car 7 1.27 38.12 35.15 14.36 12.38
car 8 1.41 27.27 35.23 18.18 19.32
car 9 1.54 33.82 29.90 8.82 27.45
car 11 1.39 34.98 29.06 13.30 22.66
taxi 9 1.44 44.21 28.95 6.84 20.00
van 7 4.21 20.59 18.24 10.00 51.18
van 8 6.20 11.36 17.05 11.36 60.23
van 9 6.05 11.18 11.18 7.65 70.00
van 11 7.43 9.95 9.42 7.85 72.77

Table

2: Edge-based distance for the taxi sequence.
Column 3: average edge pixel distance. Colums 4-7:
percentages of the distances 0,1,2,3.n.
5.2 Segmentation Results
We applied the segmentation algorithm described above to
two real-world sequences. The rst one is the Hamburg taxi
sequence widely used within the computer vision community

Figure

8 illustrates the performance of our segmentation
approach on this sequence. We employed the standard
structure tensor described in Section 3.1. The parameters
were set as follows: (1) The size of the local neighborhood
was set to 7  7  7. (2) The contrast parameter for the
coherence measures was set to 5. For all positions with a
coherence c t > 0:75 we performed motion estimation, positions
with c t below this value were rejected. Full motion
vectors were calculated for positions with cs > 0:9.
The motion estimates were integrated as an external force
into the geodesic active contour model (see Section 3.3). For
faster convergence we set the external force
that a value for c greater than zero forces the curve to shrink,
while a value smaller zero causes an expansion. Finally, we
employed the contour renement step described in Section
3.3.
In addition to the visual results we provide quantitative
measures in Tables 1 and 2. First, we used the region-based
distance measures FP and FN to compare the automatic segmentation
results to those of a manual segmentation. While
FP contains the number of pixels incorrectly marked as object
pixels by the automatic segmentation (false positives),
FN sums up object pixels missed by the process (false neg-
atives). Second, we employed an edge-based distance mea-
sure. For each contour pixel in the manual segmentation
the distance to the closest contour pixel in the automatic
segmentation was determined.
The following conclusions can be drawn from the mea-
sures: The segmentations of the car and the taxi are accept-
able. While the number of pixels detected by the automatic
segmentation is rather high, the miss rate is fairly low. Fur-
thermore, the edge-based measure indicates that edges of the
automatic and the manual segmentation coincide. However,
the van could not be segmented accurately. Both region-based
and edge-based distance measures return high error
rates.
The second video sequence is a typical \head and shoul-
der" sequence. However, due to the low sampling rate the
displacements of the moving person are large. Hence, we
employed the multiresolution motion estimation with four
pyramid levels and a local neighborhood of size 3  3  3.
To speed up the motion detection we employed the reliability
measure provided in Section 3.2, i.e., positions with a
reliability below 0.9 were rejected. The nal segmentation
was performed by the geodesic active contour model.

Figure

9 depicts the results of the motion estimation and
segmentation for the second sequence. Our segmentation
approach identies the region of interest correctly. How-
ever, the accuracy is less than that for the taxi sequence.
Especially, in areas containing strong but static edges, results
from the hierarchical motion estimation blur across the
moving edges, thus enlarging the segmented region. Tables
3 and 4 underline these observations. Especially the percentages
of exactly matching edges are rather small.
5.3 Classification Results
Our test database [23] consists of ve object classes containing
animals, birds, cars, people, and miscellaneous ob-
jects. For each object class we collected 25 { 102 images from
a clip art library. The clip arts are typical representatives of
their object class with easily recognizable perspectives. The
object class people contains the most objects (102 images).
The contours of humans dier greatly in image sequences,
e. g. the position of the arms and legs makes a great impact
on the contour.
We applied the extended object matching algorithm on
the automatically segmented cars in the Hamburg taxi sequence
(see Figure 8) and in the person sequence (see Figure
9). The CSS matching was performed with the triples
Frame FP FN FP FN
34 336 77 6.55 1.58

Table

3: Region-based distance for the person se-
quence. Columns 2, 3: false positives, false nega-
tives. Columns 4, 5: percentage of mismatched pixels
in comparison to the entire number of pixels of
the manual segmentation.
Frame avg. distance
34 1.20 25.40 41.98 23.53 9.10
38 2.04 12.61 38.71 24.93 23.75

Table

4: Edge-based distance for the person se-
quence. Column 2: average edge pixel distance.
Colums 3-6: percentages of the distances 0,1,2,3.n.
Good Bad Rejected
sequence matches matches frames
car (left) Cars 92% 0% 8%
taxi (center) Cars 68% Misc 8% 24%
van (right) Cars 29% Animals 39% 0%
People 32%

Table

5: Results of the automatically segmented objects
in the Taxi sequence matched to the objects in
the database.
(position, height, width) for each peak in the CSS image.

Table

5 shows the result of the Hamburg taxi sequence.
The perspective and segmentation of the car (left object) is
best suited for recognition. At only 68% the taxi (center
object) cannot be recognized reliably. The van cannot be
recognized by the application.
The last row in Figure 8 shows the four best matches of
the car (left object) in frame 12. The perspective of the
car does not change, so the other frames show similar results

Figure

9 depicts classication results for the person
sequence. The best matches for the frames 25, 33, 34, and
38 are displayed in the last row.
6. CONCLUSIONS
We presented an approach to the segmentation and clas-
sication of video objects. In the motion segmentation step
we integrated the 3D structure tensor into a geodesic active
contour model. While the structure tensor is able to estimate
motion reliably in the presence of background noise,
the active contour groups neighboring regions and closes
holes and gaps. The level set-based implementation allows
the simultaneous detection of multiple objects. To account
for large displacements that cannot be handled by the standard
structure tensor, we developed a new multiresolution
tensor-based algorithm.
A contour-based video object classication system was
presented as an application. The robustness of the curvature
scale space method allows correct classication even in the
presence of segmentation errors. We provided various experimental
results. While the results for the segmentation
algorithm driven by the standard tensor are very encour-
aging, the segmentation obtained in conjunction with the
multiresolution algorithm are less accurate. Nevertheless,
the classication algorithm was able to calculate reasonable
categorizations.
There are, however, several areas that require further de-
velopment. First, the segmentation performance of the multiresolution
approach has to be improved. Second, to provide
a complete segmentation module, it is necessary to integrate
a tracking component.
7.

ACKNOWLEDGMENTS

The authors would like to thank Changick Kim, University
of Washington, for the provision of the \person se-
quence" on his website.
8.



--R

Shape similarity retrieval under a
Enhancing css-based shape retrieval for objects with shallow concavities
Performance of optical ow techniques.
The computation of optical ow.

A computational approach to edge detection.
Geodesic active contours.


ISO/IEC 14496-2
Active contour models.
Conformal curvature ows: from phase transitions to active vision.
A fast and robust moving object segmentation in video sequences.
An integrated scheme for object-based video abstraction
A survey of shape analysis techniques.
A noise robust method for segmentation of moving objects in video sequences.
Extraction of moving objects for content-based video coding
Computation and analysis of image motion: A synopsis of current problems and methods.

Robust and e
Geodesic active contours and level sets for the detection and tracking of moving objects.
Review of algorithms for shape analysis.

Good features to track.
New trends in image and video compression.


--TR
A computational approach to edge detection
Multidimensional Orientation Estimation with Applications to Texture Analysis and Optical Flow
Performance of optical flow techniques
The computation of optical flow
Computation and analysis of image motion
Geodesic Active Contours
Geodesic Active Contours and Level Sets for the Detection and Tracking of Moving Objects
An integrated scheme for object-based video abstraction
Shape Analysis and Classification
A Tensor Approach for Precise Computation of Dense Displacement Vector Fields
A Noise Robust Method for Segmentation of Moving Objects in Video Sequences

--CTR
Xinguo Yu , Changsheng Xu , Hon Wai Leong , Qi Tian , Qing Tang , Kong Wah Wan, Trajectory-based ball detection and tracking with applications to semantic analysis of broadcast soccer video, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA
Mayur D. Jain , S. Nalin Pradeep, A video surveillance system under varying environmental conditions, Proceedings of the 24th IASTED international conference on Signal processing, pattern recognition, and applications, p.32-37, February 15-17, 2006, Innsbruck, Austria
space;structure tensor;curvature scale;object classification;motion segmentation