Optimizing short-term data association for multiple object tracking

Multiple object tracking plays a vital role in computer vision, supporting applications ranging from surveillance, autonomous systems, target tracking, urban traffic monitoring in the geospatial domain. Building upon the three-level framework proposed in the M2Track multi-object tracking algorithm, this paper concentrates on optimizing Level 1, also known as the linear sum assignment problem (LSAP). The objective is to reduce run time for performing detection-to-track associations across consecutive frames using a modified Jonker-Volgenant (MJV) algorithm. To address the computational challenges of large-scale multi-object tracking, we propose two methods (coordinate ordering and priority search trees) for efficiently computing Intersection over Union (IoU) values as an alternative to the brute force approach of computing the full cost matrix for all possible pairwise associations between detections and predictions. We use adjacency lists to optimize the mapping process instead of relying on a full cost matrix in the MJV algorithm. These methods efficiently identify overlapping pairs of bounding boxes, significantly reducing computational overhead by limiting IoU calculations to a subset of relevant pairs of detections and predictions. Additionally, we modified the LSAP algorithm to use adjacency lists and incorporated optimized data structures like min-heaps and unordered sequential lists, which significantly improved performance on geospatial aerial drone tracking datasets with up to 438 times speed up for the LSAP portion with 10K objects and 77% speed up over the full Level 1 M2Track algorithm.