Hungarian Algorithm for MOT

hardPROObject TrackingCVCV: Motion Estimation

Implement the Hungarian Algorithm for solving the Multi-Object Tracking (MOT) association problem. The goal is to find the optimal assignment between detections and tracks, given a cost matrix representing the association costs between them.

The Hungarian Algorithm is a combinatorial optimization technique used to solve the Assignment Problem, which is a fundamental problem in computer science and operations research. In the context of MOT, the assignment problem involves finding the optimal mapping between a set of detections and a set of tracks, such that the total association cost is minimized. This is crucial in object tracking, as it enables the accurate association of detections across frames.

To solve this problem, the following steps are involved:

Construct a cost matrix, where each entry $c_{ij}$ represents the cost of assigning the $i^{th}$ detection to the $j^{th}$ track.
Apply the Hungarian Algorithm to find the optimal assignment. The key formula for the assignment problem is:

\min_{\mathbf{x}} \sum_{i=1}^{n} \sum_{j=1}^{m} c_{ij}x_{ij}

where $x_{ij} = 1$ if detection $i$ is assigned to track $j$ and $0$ otherwise, with each detection and each track used at most once.

Return the $\min(n, m)$ assigned pairs as a list of (detection_index, track_index) tuples, ordered by detection index; when $n \neq m$ the extra detections or tracks are left unassigned. An empty matrix returns an empty list.

This technique is widely used in object tracking applications, such as surveillance and autonomous vehicles.

Example

Input

Cost matrix

Output

Assignment pairs

Reasoning

cost_matrix is an $n \times m$ grid of non-negative costs: row $i$ is a detection, column $j$ a track, and $c_{ij}$ is how poorly detection $i$ fits track $j$ .
Take the test matrix $C = \begin{bmatrix} 1 & 2 \\ 3 & 1 \end{bmatrix}$ . Each detection needs a different track, so only two complete matchings exist.
Straight: $c_{00} + c_{11} = 1 + 1 = 2$ . Crossed: $c_{01} + c_{10} = 2 + 3 = 5$ .
The minimum is $2$ , so the assignment pairs are $(0, 0)$ and $(1, 1)$ : two pairs, matching the test's expected 2.
Notice that taking each row's cheapest entry can fail: for $\begin{bmatrix} 1 & 2 \\ 2 & 10 \end{bmatrix}$ it gives $1 + 10 = 11$ , while the crossed matching costs $2 + 2 = 4$ . The objective is the whole sum.
With 2 detections and 3 tracks you still get $\min(n, m) = 2$ pairs; one track stays unmatched.

Constraints

Input cost matrix: 2D numpy array of shape (n, m) where n is the number of detections and m is the number of tracks, with float values in [0, inf) representing association costs
Valid ranges: n and m are positive integers, cost matrix values are non-negative
Output format: List of tuples, where each tuple contains a detection index and a track index, representing the optimal assignment pairs
Special conditions: The input cost matrix is not necessarily square (i.e., n may not equal m), and the algorithm should handle empty input matrices
Input validation: The input cost matrix should not contain NaN or infinity values, except for the special case where the matrix is empty

Learn this in

Motion EstimationCV Study Plan

More from CV: Motion Estimation

Rolling Shutter Correctionhard Horn-Schunck Global Optical Flowmedium Intersection over Union (IoU) for Trackingmedium Bilinear Flow Warpinghard Trajectory Smoothing Filtermedium

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results