Clustering for Multi-Target Tracking

Abstract: This thesis presents a clustering-based approach to decrease the computational cost of data association in multi-target tracking. This is achieved by clustering the sensor tracks using approximate distance functions, thereby decreasing the number of possible associations and the need to calculate expensive statistical distances between tracks. The studied tracking problem includes passive and active sensors with built-in filters. Statistical and non-statistical distance functions were designed to account for the characteristics of the different combinations of sensors. The computational cost and accuracy of these distance functions were evaluated and compared. Analysis is done in a simulated environment with randomly positioned targets and sensors. Simulations show that there are approximate distances with a cost of calculation ten times cheaper than the true statistical distance, with only minor drops in accuracy. Spectral clustering is used on these distances to divide complex association problems into sub-problems. This algorithm is evaluated on a large number of random scenarios. The mean size of the largest sub-problem is 40 % of the original, and the mean number of errors in the clustering is 5 %.