Bipartite Matching and Hungarian Algorithm
You'll learn: How DETR solves the critical problem of matching predicted objects to ground truth labels during training using optimal bipartite matching.
The Assignment Problem in Object Detection
In DETR's architecture, the model produces a fixed set of predictions (say, 100 object proposals) per image, but your ground truth might only contain 3 actual objects. How do you decide which predictions should match which ground truth objects for calculating loss?
This is where bipartite matching comes in. Think of it like assigning students to projects: you have N students (predictions) and M projects (ground truth objects, where M ≤ N). Each student-project pair has a "cost" based on how well they match (combining bounding box overlap and class prediction confidence). You want to find the assignment that minimizes total cost.
The Hungarian Algorithm
The Hungarian algorithm (also called the Kuhn-Munkres algorithm) solves this optimal assignment problem in polynomial time. DETR uses it to:
- Calculate a cost matrix between all predictions and ground truth objects
- Find the one-to-one matching that minimizes total cost
- Assign each ground truth to exactly one prediction
The unmatched predictions are assigned to a special "no object" class (∅). This eliminates the need for non-maximum suppression and anchor boxes—each prediction specializes in detecting specific positions through this training signal.
The matching happens once per training step before computing the loss, ensuring each ground truth object has a unique, optimal prediction responsible for detecting it.
Key Takeaway: DETR uses the Hungarian algorithm to find optimal one-to-one assignments between predictions and ground truth objects, enabling direct set prediction without post-processing heuristics.