Clustering of Trajectories in Video Surveillance Using Growing Neural Gas - Foundations on Natural and Artificial Computation - page 462

of the trajectories observed in a video scene. The obtained weights indicate
prototype sub-trajectories that are useful to generate prototype trajectories to
feed the model. To this end, an algorithm that studies sequences of prototype
trajectories was designed. This algorithm studies the observed trajectories and
associates them to one of the clusters provided by the GNG algorithm.

2 Proposed Algorithm

2.1 Trajectory Segmentation

Let's suppose that a trajectory T i is defined by a set of n i 2D-points, correspond-
ing to consecutive positions of a tracked object of interest, observed at equally
spaced intervals of time, T i

. As mentioned,
the number of points n i of each trajectory can change from one trajectory to
other, and depends on several factors such as the path followed by the object,
the velocity or a truncation in the trajectory due to some occlusions. As it was
described in the preivous section, it is more complex to define a distance measure
when the whole trajectory is considered. In this paper we propose to divide each
trajectory in linear segments by using a fast realization of the Douglas-Peucker
(DP) algorithm [11]. This algorithm was already used in trajectory compression
[10] but in this case, we propose to use these segments as the inputs of the
GNG network. As it is shown in Figure (1) after the DP algorithm has been
applied to trajectories, these are transformed into T i →

= { ( x 1 ,y 1 ) , ( x 2 ,y 2 ) , ..., ( x n i ,y n i ) }

s 1 , s 2 , .., s d

S i = ,being

4
is composed by the coordinates of the starting point ( x s ,y s ) and the end point
( x f ,y f ) concatenated. Segments are then treated as vectors, all of them with the
same dimension, and then the clustering algorithm is expected to find prototype
segments.

the number of segments extracted, and each of the elements s j ∈ R

d i << n i

0

10

20

30

40

50

60

70

80

90

100

0 20 40 60 80 100

Fig. 1. Douglas-Peucker algorithm applied to extract linear segments from trajectories