Non-Maximum Suppression Variants

After an object detector proposes potential bounding boxes, it often generates multiple, highly overlapping boxes around the same object, each with a different confidence score. The role of Non-Maximum Suppression (NMS) is to clean up these redundant detections, leaving only the most confident, distinct boxes. While the standard greedy NMS algorithm is widely used, it can be suboptimal, especially in scenes with densely packed objects. Variants of NMS designed to address these limitations are analyzed.

The Standard NMS Algorithm and Its Limitations

Recall the standard greedy NMS procedure:

1. Sort all detection boxes by their confidence scores in descending order.
2. Select the box $B_{max}$ with the highest confidence score and add it to the final list of detections.
3. Remove $B_{max}$ from the list of boxes.
4. For all remaining boxes $B_i$, calculate their Intersection over Union (IoU) with $B_{max}$.
5. Remove all boxes $B_i$ where $IoU(B_{max}, B_i)$ is greater than a predefined threshold $N_{threshold}$.
6. Repeat steps 2-5 until the list of boxes is empty.

This approach is simple and computationally efficient. However, its main drawback lies in step 5. If a correct detection box $B_j$ has a significant overlap with $B_{max}$ (e.g., two distinct objects very close to each other), it might be removed entirely if its IoU exceeds $N_{threshold}$, even if it represents a different object instance. This can lead to lower recall, particularly in crowded images.

Comparison between Standard NMS and Soft-NMS when processing two overlapping boxes (A and B), where A has a higher initial score. Standard NMS removes Box B, while Soft-NMS retains Box B but reduces its confidence score.

Soft-NMS

Instead of eliminating overlapping boxes entirely, Soft-NMS proposes reducing their confidence scores based on the degree of overlap with a higher-scoring selected box. The intuition is that if a box has a high overlap with a very confident detection, it's less likely to be a correct detection itself, but it shouldn't necessarily be discarded completely, especially if it might represent a distinct, nearby object.

The score $s_i$ of a box $B_i$ is updated based on its IoU with the selected highest-scoring box $B_{max}$:

$$s_i = s_i \times f(IoU(B_{max}, B_i))$$

The function $f(\cdot)$ is a penalty function that decreases as the IoU increases. Two common forms are:

1. Linear Penalty: $$f(iou) = \begin{cases} 1 & \text{if } iou < N_{threshold} \\ 1 - iou & \text{if } iou \ge N_{threshold} \end{cases}$$
2. Gaussian Penalty: $$f(iou) = e^{-\frac{iou^2}{\sigma}}$$

Here, $N_{threshold}$ is the standard NMS threshold (used to decide when to start applying the penalty in the linear case), and $\sigma$ is a parameter controlling the steepness of the Gaussian decay.

By decaying scores instead of eliminating boxes, Soft-NMS often improves Average Precision (AP), especially for datasets with significant object occlusion or density. The trade-off is a slight increase in computational cost compared to standard NMS and the introduction of a new parameter ($\sigma$ for the Gaussian variant) that might need tuning.

DIoU-NMS (Distance-IoU NMS)

Standard NMS and Soft-NMS rely solely on the IoU metric. However, IoU doesn't consider the distance between the centers of the bounding boxes. Consider two scenarios: two boxes with high IoU because they tightly surround the same object, versus two boxes with the same high IoU but representing two distinct, adjacent objects whose boxes happen to overlap significantly. Standard NMS treats both cases identically.

DIoU-NMS incorporates the normalized distance between the central points of the two boxes into the suppression criterion. The core idea is that when suppressing a box $B_i$ based on $B_{max}$, not only the IoU but also the distance between their centers should be considered. If the centers are far apart, $B_i$ is less likely to be a redundant detection of the same object as $B_{max}$, even if their IoU is high.

The DIoU metric itself penalizes the distance between centers. In DIoU-NMS, the suppression condition is modified. Instead of just checking $IoU(B_{max}, B_i) > N_{threshold}$, DIoU-NMS might use a criterion involving the DIoU value, which is defined as:

$$DIoU = IoU - \frac{\rho^2(b, b_{gt})}{c^2}$$

where $\rho(\cdot)$ is the Euclidean distance, $b$ and $b_{gt}$ are the center points of the two boxes, and $c$ is the diagonal length of the smallest enclosing box covering both boxes. When used in NMS, the penalty term $\frac{\rho^2(b, b_{gt})}{c^2}$ is added to the IoU calculation during suppression. Boxes with high IoU but distant centers are penalized less and are less likely to be suppressed.

This makes DIoU-NMS particularly effective at preserving correct detections for distinct but nearby objects, leading to better performance in crowded scenes compared to standard NMS.

Other Variants

• Matrix NMS: Used in some real-time instance segmentation models like YOLACT, Matrix NMS parallelizes the suppression process. Instead of iterating sequentially, it computes pairwise IoUs and decays scores in parallel based on overlaps, making it very fast on GPUs. Its formulation is often tailored to the specific architecture it's used within.
• Adaptive NMS: Used in methods like Point RCNN for point cloud object detection, Adaptive NMS adjusts the suppression threshold based on the density of objects or detection scores, becoming stricter in sparse regions and more lenient in dense regions.

Choosing and Tuning NMS

The choice between standard NMS and its variants depends on the specific application and dataset characteristics:

• Standard NMS: Fastest and often sufficient for simple scenes with well-separated objects. It's the default choice unless specific problems (like missed detections in crowded areas) are observed.
• Soft-NMS: A good choice when maximizing recall is important and objects often appear close together or occluded. Requires minimal changes to standard NMS implementations.
• DIoU-NMS: Recommended when standard NMS incorrectly suppresses distinct nearby objects due to high bounding box overlap. Offers a more refined criterion than IoU alone.

Regardless of the variant, the IoU threshold ($N_{threshold}$) remains a critical hyperparameter. A lower threshold leads to more aggressive suppression (fewer, more distinct boxes), while a higher threshold is more permissive (potentially more overlapping boxes and false positives). Similarly, the initial confidence score threshold used to filter boxes before NMS significantly impacts the input to the NMS algorithm. Optimal values for these thresholds are typically determined empirically by evaluating performance on a validation dataset.

In summary, while greedy NMS provides a fundamental mechanism for refining object detections, variants like Soft-NMS and DIoU-NMS offer refined strategies to handle the complexities of overlapping objects, often leading to measurable improvements in detection accuracy, particularly in challenging, dense scenarios. Understanding these alternatives allows for better tailoring of the post-processing stage to the specific needs of your object detection task.