Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces an incremental assignment algorithm for multi-object tracking in dense crowds, addressing the computational bottleneck of the classical Hungarian algorithm, which operates in \(O(N^3)\) time. By leveraging the block-sparse structure of crowd tracking cost matrices, the proposed method achieves optimal assignments more efficiently by processing one person at a time and maintaining exact optimal dual potentials. The algorithm demonstrates a significant speedup of 3.7 to 6.5 times over the Hungarian method on large-scale benchmarks, particularly beneficial for scenarios with thousands of individuals.
Achieving up to 6.5 times faster optimal assignments for crowd tracking could revolutionize real-time applications in dense environments.
Multi-object tracking in dense crowds requires solving a bipartite assignment problem between detections and trajectories at every video frame. The classical Hungarian algorithm solves this in $O(N^3)$ time, which becomes a bottleneck for large scenes with hundreds of people. We propose an \emph{incremental} assignment algorithm that exploits the block-sparse structure of crowd tracking cost matrices --- dense within each crowd cluster, near-zero between clusters. We compute the exact same optimal $N \times N$ assignment as the Hungarian algorithm, but via an incremental strategy: we add one person at a time, exploiting the fact that after step $n-1$ the dual potentials are \emph{exactly optimal} for the $(n-1)\times(n-1)$ subproblem --- a strictly stronger condition than the intermediate feasibility maintained by the Hungarian algorithm during its $N$ outer iterations. Each new step therefore requires only a single augmenting path search from a certified optimal starting point. This avoids repeated full-matrix scans while guaranteeing an identical globally optimal result. A diagonal-reordering invariant keeps the data structure compact and cache-friendly. On realistic crowd benchmarks with $N \in [200, 5000]$ people organised into dense clusters, our algorithm achieves \textbf{3.7--6.5$\times$ speedup} over the Hungarian baseline while producing provably optimal matchings identical to those of Hungarian. The speedup grows with $N$ and remains stable beyond $N=3000$, making the method especially attractive for large-scale crowd scenes such as stadium exits and mass public events.