In the world of object detection, the final "cleanup" step is often the most overlooked. After a neural network proposes thousands of potential bounding boxes, a simple algorithm called Non-Maximum Suppression (NMS) steps in to discard the redundant ones. While effective, standard NMS is a blunt instrument. In a new paper, researchers from IIT Kanpur, Microsoft, and the University of Bath propose a more sophisticated alternative: Determinantal Point Processes (DPP).
TL;DR
This paper replaces the standard greedy Non-Maximum Suppression (NMS) in object detection with a Determinantal Point Process (DPP) framework. By treating NMS as a diverse subset selection problem, the authors achieve consistent performance gains on standard benchmarks without requiring additional neural network training.
What Problem Does This Paper Address?
Modern object detectors like Faster R-CNN work in stages. First, a Region Proposal Network (RPN) generates thousands of candidate windows. Then, these windows are scored and refined. Finally, NMS is used to ensure that each object in the image is represented by only one bounding box.
The standard "GreedyNMS" algorithm works by picking the highest-scoring box and deleting all other boxes that overlap with it above a certain threshold (e.g., 30% IoU). This creates a fundamental tension:
- High Recall: If you set a narrow suppression window, you might keep too many redundant boxes.
- High Precision: If you set a wide suppression window, you might accidentally delete a high-scoring box that actually belongs to a different object nearby (common in crowded scenes like a group of people).
The authors argue that GreedyNMS is too simplistic because it relies on a single, manually tuned threshold and doesn't explicitly optimize for the "diversity" of the selected boxes.
Methods
The researchers propose framing NMS as a subset selection problem using Determinantal Point Processes (DPPs). DPPs are probabilistic models that are mathematically designed to encourage diversity. In physics, they describe the Pauli exclusion principle; in computer vision, they can be used to pick a set of items that are both high-quality and distinct from one another.
The L-Ensemble Approach
The authors construct a similarity matrix $L$ (an $L$-ensemble) where each entry $L_{ij}$ represents the relationship between two candidate boxes $i$ and $j$. This matrix is built using two features:
- Scores ($s_i$): The confidence score from the RPN.
- IoU ($IoU_{ij}$): The spatial overlap between boxes.
The final formulation is: $$L = \alpha [e^s e^{s^T}] \odot \text{IoU}$$
Here, $\alpha$ is a scaling parameter that biases the system toward selecting larger subsets, counteracting the natural tendency of the algorithm to pick very few items.
Optimization
Finding the absolute best subset is NP-hard. However, the authors leverage the fact that the log-determinant of this matrix is a submodular function. This allows them to use a fast, greedy algorithm with a heap-based implementation to select the best boxes one by one, ensuring each new box adds the most "marginal gain" in terms of both confidence and spatial diversity.
Datasets
The method was evaluated on two heavyweights of the object detection world:
- MS-COCO: A large-scale dataset with 80 object categories, known for its challenging small objects and crowded scenes.
- PASCAL VOC 2007: A classic benchmark for object detection.
The authors specifically looked at the "Persons" class in COCO to test how the algorithm handles highly overlapping objects.
Key Insights and Ideas
- Diversity as a First-Class Citizen: Instead of just "deleting overlaps," the DPP approach treats the final set of boxes as a team that needs to cover the image effectively without redundancy.
- Plug-and-Play Integration: Unlike other recent NMS improvements that require training a separate neural network (like Neural-NMS), this DPP approach is a post-processing step. It works with the same inputs as standard NMS, making it easy to drop into existing pipelines.
- Efficiency through Diversity: One of the most striking findings is that a diverse set of just 200 windows selected via DPP can outperform 300 windows selected by standard GreedyNMS.
Key Results
The DPP-based NMS consistently outperformed GreedyNMS across both datasets:
- MS-COCO: The method achieved higher Average Precision (AP), particularly in the "Persons" category, where it reached an $AP_{0.5}$ of 70.2 compared to 69.8 for GreedyNMS.
- PASCAL VOC: The average performance across all classes was 70.17, beating GreedyNMS (69.81) and significantly outperforming other complex alternatives like MP-NMS and LDDP.
- Better Localization: The authors found that their method is especially superior when high precision is required (IoU > 0.7), suggesting that DPP chooses better-fitting bounding boxes.
Limitations and Future Work
The primary drawback is computational cost. While standard NMS is extremely fast, the greedy DPP optimization has a complexity of approximately $O(k^4)$, where $k$ is the number of selected proposals. While the authors achieved comparable runtimes for up to 100 selections (0.5s vs 0.3s per image), the algorithm scales poorly as the number of desired boxes increases.
Future work could involve exploring faster approximation methods for the MAP inference or integrating the DPP cost function directly into the neural network's training phase to further bridge the gap between detection and suppression.
Summary updated