Results of clustering based on the greedy algorithm

This section presents the pathlet groups extracted from the original trajectory using the greedy algorithm. Nodes are extracted from the trajectory using the mean shift based algorithm (A4) as in the previous section.

Table 5.7 shows the pathlet groups extracted from trajectory T1. As in the previous section, for each cell of the table, the figure at the top represents the pathlets used to create the pathlet group along with the nodes extracted from the original trajectory, while at the bottom one hundred pathlets have been generated using the pathlet model. Most types of pathlet model can be found.

Table 5.7: Pathlet groups for trajectory T1 (groups 1 to 12) based on the greedy algorithm. For each group, the nodes are drawn in the upper figure with the pathlets forming that group. Using the pathlet model learnt from that group, one hundred generated pathlets are drawn in the lower figure.

pathlet groups of trajectory T1
Group 1	Group 2	Group 3	Group 4	Group 5
Group 6	Group 7	Group 8	Group 9	Group 10
Group 11	Group 12

For instance, sets of pathlets have been correctly grouped (group 4 or group 11). A group containing a single pathlet can also be seen (group 12). Some groups contain outliers (group 1 contains two pathlets that end in different locations to the other pathlets in the group). However, the associated pathlet model seems to model the original data quite faithfully. No pathlet that looks impossible has been generated from the pathlet model learnt from group 1.

Pathlet groups 2 or 8 are also amongst those that contain an outlier. The corresponding model sometimes generates pathlets with negative timings. As in the previous section, this is due the fact that very short pathlets have been included in the model. However, we can see that this only happens if the other pathlets in the group are short themselves. After discarding a pathlet with negative timings, the new sampled pathlet is likely to be reasonable.

We can argue that group 6 in table 5.7 contains pathlets that do not look like each other, but once again the model represents the original pathlets rather well.

Table 5.8: Pathlet groups for trajectory T2 (groups 1 to 15) based on the greedy algorithm. For each group, the nodes are drawn in the upper figure with the pathlets forming that group. Using the corresponding pathlet model, one hundred generated pathlets are drawn in the lower figure.

pathlet groups of trajectory T2
Group 1	Group 2	Group 3	Group 4	Group 5
Group 6	Group 7	Group 8	Group 9	Group 10
Group 11	Group 12	Group 13	Group 14	Group 15

Table 5.9: Pathlet groups for trajectory T2 (groups 16 to 23) based on the greedy algorithm. For each group, the nodes are drawn in the upper figure with the pathlets forming that group. Using the corresponding pathlet model, one hundred generated pathlets are drawn in the lower figure.

pathlet groups of trajectory T2
Group 16	Group 17	Group 18	Group 19	Group 20
Group 21	Group 22	Group 23

Table 5.10: Pathlet groups for trajectory T3 (groups 1 to 7) based on the greedy algorithm. For each group, the nodes are drawn in the upper figure with the pathlets forming that group. Using the corresponding pathlet model, one hundred generated pathlets are drawn in the lower figure.

pathlet groups of trajectory T3
Group 1	Group 2	Group 3	Group 4	Group 5
Group 6	Group 7

We can see on tables 5.8 and 5.9 that the pathlet models encode the same structures as the original pathlets used to build the models. Only similar pathlets are grouped together. The groups that have been created with only one pathlet only contains the outliers. Indeed, pathlet groups like group 20, 21, 22 or 23 contain pathlets that are not common. This is mainly due to errors in the selection of the nodes in the original trajectory. For instance the pathlet in group 21 should have been split into 3 pathlets.

The greedy algorithm is able to cope with imperfections in the node selection process. This quality of the greedy algorithm is useful since the node selection algorithm is not always perfect. The normalised cut algorithm, along with the similarity measure based on the dynamic time warping algorithm, is not always able to recover proper pathlet groups in the case of a failure to select good nodes in the original trajectory. For instance, the pathlets in the group 19 on table 5.9 have been clustered has a part of the group 2 in table 5.4. The pathlets in group 19 on table 5.9 should have been split into two pathlets each with extra nodes. The wrong clustering in table 5.4 is due to the fact that the dynamic time warping tends to match those pathlets with one of the two pathlets that would have been used instead. It compares badly extracted pathlets with pathlets that are similar to parts of those badly extracted pathlets.

This is a general problem of the dynamic time warping algorithm: it matches parts of pathlets and shrinks the time of the reminder of the pathlets to zero for the comparison, thus forcing wrong matchings.

Table 5.10 shows that the greedy algorithm performs correctly on data extracted from a video of a face (trajectory T3 corresponding to the video sequence V1 described in section 4.3.1).

We can also note that, for each trajectory (T1, T2 or T3), the greedy algorithm requires fewer pathlet groups than the algorithm based on the normalised cuts and the dynamic time warping algorithms for visually similar pathlet quality.

Finally, we can note that, with the greedy algorithm, some pathlet groups appears very similar. Two corresponding models generate pathlets in opposite directions. Similar pathlets with two different directions cannot be modelled properly by the same pathlet model. Examples of such corresponding pathlet groups include the pathlet groups 1 and 10 and the pathlet groups 6 and 12 in figure 5.8. Pathlet groups extracted from real video sequences also show such correspondences as we can see on figure 5.10: the pathlet group 1 corresponds to the pathlet group 2 and the pathlet group 3 corresponds to the pathlet group 4.