Hungarian Algorithm

The Hungarian algorithm is an exact optimization method that finds the lowest-cost one-to-one matching that pairs every item in the smaller of two sets. It optimizes the total cost across all selected pairs. In computer vision, it connects detections with tracked objects or predictions with training targets.

Harold W. Kuhn introduced it in 1955 in The Hungarian Method for the Assignment Problem. Hungarian method and Kuhn–Munkres algorithm are alternative names for the same algorithm family. Its name honors Hungarian mathematicians Dénes Kőnig and Jenő Egerváry, whose work underpins the method.

How the Hungarian Algorithm Works#

The input is a cost matrix: each row represents an item from one set, each column represents an item from the other, and each entry measures the cost of pairing them. For a square matrix, the solution selects exactly one entry per row and column. A greedy strategy commits to attractive individual pairs; Hungarian matching finds the globally minimum total.

In the classic matrix reduction procedure, subtract each row's minimum from that row, then each column's minimum from that column. These reductions preserve the best complete assignment because every assignment uses every row and column once. Cover all zeros with the fewest horizontal and vertical lines. If n lines are needed for an n x n matrix, select n zeros with no shared row or column. Otherwise, subtract the smallest uncovered value from uncovered entries, add it at intersections of covering lines, and repeat the covering test. Calculate the assignment's cost using the original matrix.

Efficient Hungarian implementations run in O(n³) time for square matrices, compared with n! possible complete assignments.

Applications in Computer Vision#

Multi-object tracking. The original SORT design combines Hungarian assignment with a Kalman filter, which predicts each track's position. Intersection over union measures overlap between predicted and detected bounding boxes. SORT's reference implementation solves assignment using LAPJV or SciPy, rejects low-overlap associations, and creates identities for unmatched detections.

Object detection training. DETR uses Hungarian matching to pair unordered predictions with labeled objects. Its transformer produces prediction slots, and matching combines classification and box-location costs. With enough slots, each target receives one prediction, making the loss function independent of annotation order; unmatched slots learn the "no object" class. Ultralytics applies this assignment formulation in RT-DETR: its HungarianMatcher combines classification, L1 coordinate distance, and generalized IoU costs. Its linear assignment backend uses a modified Jonker–Volgenant solver to select training pairs.

Hungarian Matching in Python#

The munkres Python package implements the Hungarian method. Install it with pip install munkres, then solve its sample cost matrix:

from munkres import Munkres

costs = [
    [5, 9, 1],
    [10, 3, 2],
    [8, 7, 4],
]
solver = Munkres()
assignments = solver.compute(costs)
# Read costs from the original matrix.
minimum_cost = sum(costs[row][col] for row, col in assignments)
print(f"Minimum total cost: {minimum_cost}")

The output is Minimum total cost: 12, the smallest sum attainable while selecting one entry per row and column.

Related Methods and Unmatched Objects#

The assignment problem is the task; the Hungarian algorithm is one solver. Non-maximum suppression removes competing detections within an image. Object re-identification supplies appearance information for association, often through embeddings compared using cosine similarity. Such scores can become matching costs.

Unequal group sizes produce rectangular matrices. Tracking also needs rejection rules or dummy entries with defined unmatched costs to accommodate missing detections and newly appearing objects. A wrong association causes an identity switch: a track ID transfers to another object.

SciPy's linear assignment solver solves the same optimization problem using a modified Jonker–Volgenant algorithm. For an r x c rectangular matrix, it returns exactly min(r, c) pairs when a feasible full assignment exists.