g problem 
ns around 
)rganizing 
- character 
geometric 
movie-file 
ates some 
) captures 
cture with 
this gaol, 
d to: the 
geometric 
ın optimal 
jerties of 
2921); but 
re. 
er regions 
ature, and 
ion can be 
olor. This 
(position- 
n color in 
| particular 
o different 
is given by 
to obtain 
the image. 
model can 
y to have a 
pearing at 
ly, we can 
z a contour 
)ecause we 
ithematical 
the second 
boundaries 
crimination 
(to identify 
labelling) 
procedure, which is propagated for adjacent pixels following a 
like WTA algorithm. The recursive procedure is 
computationally expensive O(e") where exponential depends on 
the recursive order. We avoid it, by making only one sweep. To 
get labels for regions in a image context, we have adapted some 
basic ideas to the Kohonen’s Self-Organizing-Map (SOM). An 
iteration around image pixels (horizontal scanline p.e.), 
compares vector labels for each vector pixel (position and 
color), and evaluates a weigthed distance between them. 
Weigthing up the color, rather than the position, gives 
uniformity. Inversely, weigthing up the position, rather than 
color, gives consistence (connected regions). For each iteration 
in the pixel level, the region that minimizes the distance is the 
provisonal winner. In a fixed number of regions scheme, the 
vector of that region is brought near to the pixel’s vector. In a 
non-fixed number of regions scheme, if the value of the distance 
goes up to a thresholding value, a new region is created, else the 
winner’s region vector is modified. 
Transitions between adjacent regions vector are given by means 
of a linear averaged approach between two vectors, whose 
weights depend on the ‘size’ factor. Another said, if the region 
is small (‘has’ few pixels), the aproximation is more huge than 
if it ‘has’ much pixels. This algorithm allow us to define each 
region over an image surface with a linear cost. If we take a 
fixed number of regions, O(n) is always the same on two images 
equally sized, independent of the image complexity. By varying 
the threshold in the non-fixed number of regions version, the 
value of the color uniformity in a region is modified. In both 
cases, the time dedicated to the segmentation and merging 
process is smaller, than the contour segmentation. 
3. A clustering technique based in Computational 
Geometry 
Our proposal for clustering uses an adaptation of 3D Voronoi 
diagram linked to typical mean values for each region. Such 
typical mean value is given by a median which is locally 
computed following a winner-takes-all (WTA) criteria. In this 
way, we reduce the number of typical values for colors inside 
each view, and we generate convex regions with homogeneous 
color following a competitive propagation algorithm with centre 
each median. We have developed a computer implementation 
inspired by the behaviour of human retina. An example is given 
by the following iterative algorithm: 
INITIATE depending on the threshold (fixed by the user) 
FOR every pixel of the original image, DO. 
SELECT a representative element by a WTA typical 
competition scheme 
GENERATE a map of color classes with a 
representative pixel by region 
COMPUTE the smallest distance in a color map to 
the representative pixel 
IF this value is higher tham a maximal 
threhold, THEN 
CREATE a new region 
END IF 
UPDATE the map of classes 
END FOR 
FOR every pixel of the original image DO 
COMPUTE the smallest distance between the current 
pixel and the characteristic class of existing regions 
LABEL the region corresponding to the pixel as a new 
region in the map of representative or characteristic 
colors. 
END FOR 
Mean color intensities and their variances give us the regional 
distribution of color, and each region arising from this process 
is consequently labelled. By taking the dual construction of 3D 
Voronoi decomposition, we obtain a Delaunay simplicial 
decomposition, allowing us to generate a 3D skeleton. The 
resulting 3D Delaunay skeleton give us a symbolic 
representation for any vector representation of color. 
So, vertices of the Delaunay simplicial decomposition give us 
some kind of virtual attractors for the valley regions where one 
can find a predominant color, whereas edges of Voronoi 
diagrams represent conflict or peak values. In the same way, 
Voronoi vertices represent in fact repulsors for a dynamics 
based on proximity relations between median values. At peak 
values, we reinforce the discontinuity by using a weighted sum 
linked to a vector representation of color (preferably the IHS). 
The Delaunay decomposition does present optimal properties 
relative to the regularity (maximization of the minimal angle is 
proved in [Law77] ). Such optimal properties are inheritated by 
the regional decomposition ([Ede93]). Statistical stability of our 
model is an immediate consequence of optimality properties of 
Delaunay simplicial decompositions. Abrupt changes in 
illumination conditions appear as foldings or unfoldings of 
previously detected regions, but these changes can be managed 
in terms of similar operations linked to the chosen symbolic 
representation in terms of Delaunay simplicial decompositions. 
So, we obtain a robust model with strongly correlated variations 
even under abrupt changes of illumination. 
4. Mobile segmentation for sequences of images 
In the dynamical case, we apply the above algorithm for a 
spatio-temporal segmentation, merging and tracking of a movie- 
file. The choice of a Delaunay simplicial representation as a 3D 
skeleton allows us an easy update in terms of elementary 
transformations involving to folding and unfolding processes. 
We determine the deformation of merged images which is lower 
when the frames are taken near in time, 20 per second we 
compare the centroid movement for each merged region to 
determine the movement features, and we determine 
illuminance variations from the color differences between 
consecutive images. In this way, we extract qualitative 
properties of the relative motion, allowing us to discriminate 
between the motion camera and the motion of different agents 
in the scene, independently of the complexity of the scene and 
motion. 
If we adopt again a normalized RGB representation for the 
color, we may introduce a superimposed linear model, where 
the homogenous color regions are connected between them by 
edges of Delaunay simplices. The sites of the dual Voronoi 
configuration are the centers of influence regions or color 
organisers associated to minimum energy and maximal volume. 
The minimum energy represents the square of the typical 
deviation. By adapting some arguments of a dynamical 
interpretation ([Per90]), the volume can be interpreted as the 
temporal evolution of the anisotropic diffusion given by a 
partial differential equation. This partial differential equation 
gives the temporal evolution of the complex chromacity as the 
product of the divergence of normalized color by by the 
gradient of the complex chromacity. Hence, the superimposed 
Delaunay model is optimal, as it could be expected from general 
properties of Delaunay simplicial decompositions ([Ede93]). 
—153—