Shape-Based Trajectory Clustering

Automatic trajectory classification has countless applications, ranging from the natural sciences, such as zoology and meteorology, to urban planning and sports analysis, and has generated great interest and investigation. The purpose of this work is to propose and test new methods for trajectory clustering, based on shape, rather than spatial position, as is the case with previous methods. The proposed approach starts by uniformly resampling the trajectories using splines, and then characterizes them using the angles of the tangents at the resampled points. Angular data introduces some challenges for analysis, due to its periodic nature, therefore preventing the direct application of common clustering techniques. To overcome this problem, three methods are proposed/adapted: a variant of the k-means algorithm, a mixture model using multivariate Von Mises distributions, which is fitted using the EM algorithm, and sparse nonnegative matrix factorization. Since the number of clusters is seldom known a priori, methods for automatic model selection are also introduced. Finally, these techniques are tested on both real and synthetic data, and the viability of this approach is demonstrated.