Understanding the Hungarian Algorithm and Its Role in Computer Vision

Introduction

Multi‑object tracking (MOT) requires matching detections across consecutive video frames. The core difficulty lies in designing a frame‑to‑frame matching strategy that considers detection box positions, occlusions, motion trajectories, and appearance similarity.

Hungarian Algorithm Overview

The Hungarian method is a polynomial‑time combinatorial optimization algorithm for solving assignment problems. It was proposed by Harold W. Kuhn in 1955 and builds on earlier work by Hungarian mathematicians Konig and Egervary.

Problem Modeling

The classic “worker‑task” assignment problem is used as a concrete example. Given n workers and n tasks with known salary costs, the goal is to assign each worker exactly one task, ensure every task is performed, and minimize total salary.

Each worker is assigned a unique task.

All tasks must be assigned.

Total cost is minimized.

A 4 × 4 cost matrix is presented as the running example.

Algorithm Steps

Row Reduction

For each row, subtract the smallest element from every entry, guaranteeing at least one zero per row.

Column Reduction

Similarly, subtract the smallest element of each column from all entries in that column.

Covering Zeros

Draw the minimum number k of horizontal and vertical lines needed to cover all zeros. If k = n , an optimal assignment can be read directly from the uncovered zeros.

Adjustment Step

If k < n , find the smallest uncovered element, subtract it from all uncovered elements, and add it to every element that lies at the intersection of two covering lines (the “corner” elements). This preserves optimality while creating additional zeros.

Repeat the covering and adjustment steps until k = n . Then select one zero in each row and column to obtain the final assignment.

Result Extraction

After the final covering, choose zeros starting from rows/columns with the fewest zeros. Map the selected zeros back to the original matrix to retrieve the optimal worker‑task pairing.

Complexity

The Hungarian algorithm runs in O(n³) time, where n is the matrix dimension. For small‑scale matching problems, this cubic cost is acceptable.

Application to Computer Vision

Beyond the textbook assignment problem, the algorithm is widely used in computer‑vision tasks such as MOT. Detections from a frame (e.g., YOLO boxes) are paired with detections from the next frame by constructing a cost matrix whose entries are the Euclidean distances between box centers.

Running the Hungarian algorithm on this matrix yields the optimal matching, e.g., (A₁, C₂), (B₁, A₂), (C₁, B₂) with total cost 14, which is the minimal possible sum.

Real‑world MOT systems augment this simple distance metric with additional cues such as motion trajectory, speed, direction, and appearance similarity, but the Hungarian algorithm remains the backbone for finding the globally optimal assignment.

Conclusion

The article demonstrated how the Hungarian algorithm solves the classic assignment problem through systematic matrix transformations and how the same procedure can be applied to multi‑object tracking in computer vision, offering an exact, polynomial‑time solution for moderate‑size problems.