CES 
)plications 
f distance 
plied. The 
[lowed for 
ining. Our 
cessary to 
ion allows 
low-level 
; a critical 
election of 
ena for an 
1formation 
'sholds by 
0]. 
mentation 
À “shot” 
ith similar 
xample is 
derground 
rveillance, 
temporal 
out mobile 
analysis of 
shots that 
the same, 
Jence, the 
. including 
objects in 
tatic in an 
tween ego- 
esults in all 
results for 
d a fast but 
he on-line 
otions and 
.g.). In this 
ing metric 
y generated 
segmented 
is possible 
  
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004 
  
thanks to a simple propagation model. Nevertheless, it is 
commonly believed that to improve the management of 
complex video scenes are, it is not possible to reduce ourselves 
to a fully automatic segmentation tools. Hence, it is necessary 
the development of relations between automatic and interactive 
tools for video processing. Thus, the current work intends to 
contribute to the development of such relations by means the 
computer implementation of some semi-automatic processing 
tools. 
2. REGIONS-BASED FAST SEGMENTATION AND 
DYNAMIC MATCHING 
Fast segmentation is usually based on the extraction of regions 
with “similar” properties. Main issues concern to the 
specification of similarity notions involving to low-level 
patterns for image processing (histograms, colour and textures) 
and high-level patterns for identification and comparison of 
shapes. Sensitivity to brightness variations and the lack of 
localization (position and orientation) information are two 
neckbottles of a strictly colour segmentation approach. Another 
said, low-level patterns by themselves are difficult to manage 
without adding spatial information relative to their eventually 
mobile localization. This fact justifies our hybrid (colour- 
position) approach. On the other hand, the high computational 
complexity of kinematic models linked to simple shapes, 
suggests adapting some kind of symbolic representation able of 
supporting low- and high-level patterns. 
Some advantages of symbolic representations given by 
adjacency graphs are: simplicity, easy updating and absorption 
of small changes relative to image features and shapes. Video 
segmentation requires to identify topological changes in a 
sequence of adjacency graphs. Shots are defined as 
discontinuities of graphs for the temporal axis, i.e., some nodes 
representing regions are unfolded or deleted, following birth 
and death usual models. 
Our choice for mobile segmentation is based on an extended 
colour segmentation. Traditional colour segmentation identifies 
a typical colour for regions R;. Furthermore, we consider the 
mass m; and a typical shape S; for region A; extracted as its 
boundary OR ;. The mass m; corresponds to the number of 
pixels contained in R;. The boundary is the conflict locus for 
propagation algorithms. Typical colour arises from a 
homogenisation above a threshold following usual competitive 
propagation algorithms. We have implemented two versions of 
competitive — propagation — algorithms, which play a 
complementary role, which are labelled as “overflow” and 
expansion algorithms (see the next section for details). The 
extraction of contours O R; is performed to an iconic level, 
only, ie. without assigning any kind of mathematical 
primitives to each component. Anyway, we can suppose that 
the boundary OR; is piecewise smooth. So, we have a 
reasonable framework for some duality questions related with 
the symbolic management of meaningful information. 
Our symbolic approach for regions segmentation of each view 
is based on a graph I. Nodes nj of the graph are supported on 
centroids C; of regions R; arising from a color segmentation. 
Two nodes n; and n; of the graph I” are connected by means of 
an edge e; if and only if the regions A; and R; have a common 
component in their boundary. Our algorithm design excludes 
the existence of quadruple points in contours segmentation. 
Another said, corners can belong to two or three regions, giving 
us double or triple points. Each corner separates the boundary 
Ô R; in two components. À T-junction generates a subdivision 
in the oriented component of R; where the T-confluence is 
generated. Hence, the eventually increased list of corners 
heritates also an orientation. So, a doubly connected list (d.c.1.) 
is automatically generated for the management of regions, 
contours and corners data contained in each view, in the same 
way as for the linear case with a similar design of pointers. In 
particular, for each pair of adjacent regions R; and R; we count 
twice the common component of boundary. each one with the 
orientation induced by that of R;. In the same way, each corner 
has an oriented weight, Le. it appears with so many 
orientations as the oriented edges incident at the corner. 
Centroids Cj of regions A; are the sites of a Voronoi diagram, 
with the corresponding dual representation which supports a 
standard combinatorial information (Delaunay triangulation). 
Symbolic attributes for segmented regions R; correspond to 
constant functions defined on the positively oriented region A; 
(it suffices to evaluate at the centroid C;). Matching between 
different regions is easier, reliable and fast thanks to the 
existence of common boundaries with opposite orientations. 
The boundary operator assigns to each region R; its boundary 
OR; in a piecewise smooth way. Breaking points for 
smoothness correspond to oriented corners, i.e. the incidence 
locus of at least two different colour components. The existence 
of a natural orientation corresponding to all elements appearing 
in the d.c.L, allow to verify usual properties of boundary 
operators (such that O ? — 0). Hence, we can define homology 
groups, which provide us information about holes, or more 
advanced topological properties of oriented components with 
homogenous properties for colour and/or textures. 
If incidence conditions are preserved, nevertheless some shape 
changes in apparent contours, then the number of meaningful 
connected components is constant. Elementary topological 
events along a video sequence are characterized in terms of 
elementary transformations (grouping or splitting) of regions 
previously existent. For a fixed camera (with a fixed 
background), an elementary shot is linked to the (dis)apparition 
of a multibody, where a multibody is characterized as a 
connected tree of regions with proper motion (car, animal, 
human body, typically). If the camera is mobile, the 
discrimination between egomotion and external motion can be 
performed with the motion analysis of background and 
foreground. If the common background to several views is 
fixed, then there is no egomotion, and it suffices to evaluate 
absolute motion of mobile objects foreground. Otherwise, a 
finer analysis is required, and relative motion of foreground is 
obtained from a subtraction of the observed motion of 
background. 
3. SPATIO-TEMPORAL PROPAGATION 
ALGORITHMS FOR MOBILE DATA 
Each region is described as a collection of contiguous pixels 
with a homogenous colour. Competitive propagation algorithms 
provide a local homogeneity with respect to the colour. We 
have implemented two spatial propagation algorithms that are 
labelled as “overflow” and expansion, in correspondence with 
linear and rotational sweep-out techniques for each image. 
Competitive propagation algorithms follow simple comparison 
criteria for pixels linked to position and colour attributes.