Information Technology Reference
In-Depth Information
In order to define the model of the surveillance system it is of high interest to
associate objects with common observed trajectories. As the number of trajec-
tories grows it becomes impractical to group and identify them manually, so it
is necessary to use a clustering algorithm that can also provide prototypes of
trajectories and detect outliers.
Trajectory matching involves the measure of the similarity respect to some
kind of distance metric between two or more trajectories. The most trivial dis-
tance measure is the Euclidean one, but it should be noted that two different tra-
jectories can have different number of points. In [9] trajectories are re-sampled so
that all of them have the same number of points, allowing the use of the Euclidean
distance as a metric of similarity. Nevertheless, this measure is suboptimal when
comparing sub-trajectories obtained as a result of some kind of occlusion in the
tracking stage. This fact makes necessary the research on other measures that do
not require the two trajectories to have the same number of points. One of the
measures in this second group, widely used in trajectory comparison, is Dynamic
Time Warping (DTW) [19], [18]. Another measure that do not need the same
number of points is the Longest Common SubSequence (LCSS) used in [5] or [7].
The modified Hausdorff distance introduced in [2] adapts the Hausdorff distance
to compare trajectories keeping the order of the points in the sequences. In [14]
the distance used was called Trajectory Directional Histogram and it is based
on the histogram of the angles obtained from the sequence.
Previous works have explored clustering methods in order to group trajecto-
ries. The most extended is K-means and its soft version fuzzy K-means, used in
[12] or [9]. Agglomerative techniques have also been used as described in [1] or
[5]. A common problem with these approaches is that it is necessary to know a
priori the number of centroids or classes of the problem and make some assump-
tions about the distribution of the data. Spectral clustering is another method
found in the literature, that do not make any assumption on the distribution of
data points and approximates an optimal graph partition [16]. Its use in trajec-
tory clustering is described in [3]. However, this last approach does not provide
prototype trajectories, which can be one of the targets if we are interested in a
model of the video scene. A deeper review of the state of the art in trajectory
classification and clustering can be found in [15]. More recently, several works
indicate that the problem of trajectory classification and clustering can be eas-
ily solved by dividing it into sub-trajectories. This solution is based on the way
humans recognize trajectories by dividing them into atomic units of actions that
are of substantial value for perception [4], [17].
Growing neural gas [8] (GNG) is a bioinspired algorithm for finding optimal
representation of feature vectors. Its name comes from the behaviour of the
vectors during the adaptation process that distributes them like a gas in space.
It is based on growing self organizing maps and has been used for clustering
analysis [6]. The advantage as a clustering algorithm is that, with enough training
time, it can adapt to clusters with very different nature, keeping more neurons
in those clusters that are more complex to be represented. This paper proposes
to adapt this algorithm to the problem of trajectory clustering using segments
Search WWH ::
Custom Search