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

5. If mod ( iter/λ )=0and n<mxnodes ,where λ is a predefined value, a new
node r is inserted. To this end, the node with maximum error is found,

q =max
i ω i ∈Ω

E ( i ) . (5)

and also the node with maximum error among the neighbors of q ,

l =max
i ω i ∈ N q

E ( i ) . (6)

The new node is inserted by breaking the connection between nodes q and
l , C ( q, l )= C ( l, q ) = 0 and adding the new connection C ( r, q )= C ( r, q )=
C ( l, r )= C ( r, l ) = 1. The weight of the new node is:

ω r =( ω l + ω q ) / 2

Ω = Ω ω r
E ( r )=( E l + E q ) / 2

(7)

Increase the number n of active nodes.
6. Decrease the error in all the nodes ΔE ( i )=

βE ( i )where β is a predefined
constant. If iter < mxiter repeat the process from point 3. Else stop the
algorithm and return the matrix

−

.
7. Find those nodes that are enough close each other,

Ω

ω i − ω j <μ ,where μ

is a predefined constant and group them into a unique node.

2.3 Prototype Trajectories

The GNG algorithm provides a set of n nodes, each one representing a subtra-
jectory prototype. In this stage the algorithm searches for common sequences of
sub-trajectories in order to build a set of prototype trajectories. These common
sequences are extracted from the set of observed trajectories. As it has been
highlighted in the previous section, there was a lack of information in the GNG
algorithm about what trajectory produce each segment. Now, we have recovered
the information obtained in the first step, so instead of considering initial trajec-
tories the sequences of linear segments are studied. Each segment is associated
to its nearest node:

s 1 , s 2 , .., s d

T i → S i =

(8)

φ j s j − ω z =max

z

j =1 , 2 , ..d i z =1 , 2 , .., n

From this assigment, we have mapped each trajectory into a set of indexes
associated to prototype sub-trajectories, Φ i = { φ 1 ,φ 2 , ...φ d i } .Asearchisnow

made to obtain those Φ i that are repeated more than a given number of times.

In our work we have considered a sequence of sub-trajectories to be a prototype
if it is repeated more than four times.