Finding nodes in the trajectory

We extract pathlets from the trajectory in the appearance parameter space by selecting points on that trajectory that split the trajectory into pathlets. We call those points ``nodes''. Figure 5.2 illustrates this process. Two consecutive nodes are the beginning and the end of a pathlet.

Since each point on the trajectory represents a frame from the original video sequence, the nodes represent particular frames.

Figure 5.2: Overview of the pathlet groups extraction process. First nodes are extracted from the trajectory which split the trajectory into pathlets. Similar pathlets are then grouped together.

We have tried several algorithms to select those nodes, including:

• Selecting a node every $N$ timeframes (algorithm A1).
• Selecting a node every $N$ points or if the current point we are considering to be a node candidate is close to another node previously selected (algorithm A2).
• Selecting a node if the direction of the speed changes (algorithm A3).
• Selecting a node if it is close to a maximum number of other nodes (algorithm A4).

There are no good a priori reasons to choose one over the other.

Table 5.1 shows the nodes found on some trajectories. Its columns represent different trajectories. The first and second columns represent two hand drawn trajectories while the last column represents the trajectory given by the appearance parameters from video V1. The first row shows the points the trajectories are composed of. The remaining rows show the results of algorithms A1, A2, A3 and A4. For each algorithm and each trajectory, the trajectory points have been drawn in grey while the selected nodes have been highlighted with bigger black dots.

Table 5.1: Comparison of the different algorithms of the node extraction process. Trajectory T2 has been drawn by hand so that it looks similar to the data used in [96] for direct visual comparison of the node selection results. Trajectory T1 is hand drawn while trajectory T3 is generated from the video sequence V1 (see section 4.3.1).

	Trajectory T1	Trajectory T2	Trajectory T3

Algorithm A1 is the simplest approach: selecting pathlets of fixed length. For instance, [40] or [74] use fixed length segments of trajectory for their behaviour model. As you can see in Table 5.1, this strategy leads to unstructured pattern of nodes selected from the original trajectory. Although it might be valid for some behaviour models, it leads to sets of pathlets that are unlikely to be easily clustered.

Ideally we would like to split the trajectory into pathlets which can be effectively grouped and modelled. This suggests that the nodes (the ends of the pathlets) should form tight clusters where possible. Algorithm A1 does not achieve this.

A simple modification is to select every $N^{th}$ point unless one of the next $N$ points is close to an existing node, in which case it gets selected. Figure 5.4 illustrates this algorithm. In detail, algorithm A2 is given in figure 5.3.

Figure 5.3: Algorithm A2

Figure 5.4: Selection of nodes using algorithm A2. The circles and black dots represent the points from the original trajectory. The nodes selected by the algorithm are represented by the black dots. The algorithm selects nodes every $N$ points unless it passes close to a already selected node with a distance less than $d$. In that case, the next selected node is the point on the trajectory that is closest to the already selected node. This figure has been drawn with $N=3$.

In Table 5.1 we can see that algorithm A2 gives a more structured segmentation than algorithm A1. Nodes are grouped together, but we can still see some remaining unstructured sets of nodes. Those unstructured sets of nodes often split the trajectory into small pathlets of one or two points long that are unlike the other pathlets. Such pathlets are outliers and are hard to group with others, since they are usually located further apart in the appearance parameter space.

In [95], Walter et al. propose a temporal segmentation of a gesture trajectory in two steps:

• detection of rest positions, where the velocity drops below a threshold
• detection of discontinuities in orientation to recover strokes

Following the same approach, algorithm A3 segments the trajectory by thresholding the scalar product of two consecutive unitary speed vectors. In order to avoid selecting consecutive points as nodes, we only select the lowest scalar product for each set of consecutive points with low scalar products, in a similar way as for low distances in algorithm A2. The resulting selected nodes on trajectories T1, T2 and T3 are shown in Table 5.1. Trajectory T2 is a hand draw reproduction of the data shown in [95], representing hand positions during gestures. Algorithm A3 performs well on this trajectory but is sometimes disturbed by the noise in the data. Algorithm A3 does not perform well with the other two trajectories, due to noise, the small sampling rate of trajectory T3 and the behaviour of trajectory T1. Since no sudden change of velocity appears in trajectory T1, only changes of directions due to noise are selected.

The attempts at clustering the trajectory highlight the following:

• the nodes should be chosen so that they are close to other chosen nodes to ease the grouping of pathlets.
• the smaller the number of clusters of nodes, the smaller the number of pathlet groups, and the easier it will be to learn their temporal relationship.

Those remarks lead us to consider algorithm A4. We select points that are close to other trajectory points in the appearance parameter space. In order to find those points, algorithm A4 is based on the mean shift algorithm.