We now have a similarity measure to compare two pathlets. We wish to cluster the pathlets using this similarity measure. Clustering algorithms have been used in a wide range of applications. However, our similarity measure does not verify the triangular inequality. So clustering algorithms like the k-means algorithm [70] cannot be used.
We require clustering algorithm based on a similarity measure and not a distance measure. We also need the algorithm to be efficient as the number of pathlets might be large for long training video sequences. We use the normalised cut algorithm from Shi and Malik [88], described in appendix B.
The normalised cut algorithm returns a set of groups of pathlets. Each resulting group of pathlets is modelled by a pathlet model.