EP09_04 — 🟡 Intersection over Union (IoU) and Non-Maximum Suppression (NMS)

9.10.4 EP09_04 🟡 Intersection over Union (IoU) and Non-Maximum Suppression (NMS)

Object detection models can produce multiple candidate bounding boxes for the same object, with different positions and confidence scores. The post-processing step responsible for eliminating these redundant detections is Non-Maximum Suppression (NMS), whose fundamental operation uses the Intersection over Union (IoU) metric.

NMS uses this measure to decide which boxes should be kept. In general, the box with the highest confidence is selected first; then, boxes that have an IoU above a given threshold with the selected box are considered redundant and removed. The process is repeated until no candidate boxes remain.

In this exercise, you must implement the NMS algorithm from scratch, calculating the IoU between boxes and successively applying the selection and suppression criteria to produce the final set of detections.

9.10.4.1 📋 Implementation Guidelines

Input: Read the integer \(N\) (number of candidate boxes) and the real threshold \(\tau\) (IoU threshold for suppression), on the same line.
Boxes: Read \(N\) lines, each with five real values:

x1 y1 x2 y2 score

where \((x_1,y_1)\) represents the top-left corner, \((x_2,y_2)\) the bottom-right corner, and score the confidence score.
Intersection over Union: For two boxes \(A\) and \(B\),

\[ IoU(A,B)= \frac{\operatorname{Area}(A\cap B)} {\operatorname{Area}(A\cup B)}. \]

The intersection area must be computed from the overlap of the intervals in \(x\) and \(y\). If there is no overlap, the intersection area is zero.
Greedy NMS algorithm:
1. Sort the boxes by score in descending order. In case of ties, maintain the original reading order.
2. Select the box with the highest score among the remaining boxes and add it to the output set.
3. Compute the IoU between the selected box and all remaining boxes. Suppress those boxes for which
\[ \text{IoU} > \tau. \]
1. Repeat steps (b) and (c) until no boxes remain.
Output: For each kept box, in the order it was selected, print its original index (reading position, starting at \(0\)) and its score, formatted with 4 decimal places. At the end, print:

Total kept: X

9.10.4.2 📌 Computational Constraints

Strict suppression: only boxes with \(\text{IoU} > \tau\) are suppressed. Boxes with \(\text{IoU}=\tau\) are kept.
Original indices: the output refers to the position in which each box was read from the input (starting at \(0\)), not its position after sorting.
Stable sorting: in case of equal score values, the original reading order must be preserved.
Axis-aligned rectangles: all boxes are specified by two corners, with \(x_1 < x_2\) and \(y_1 < y_2\) guaranteed in the input.
Coordinates and scores: real values may be positive or negative, according to the limits defined by the input, but the box dimensions are always positive.

9.10.4.3 🧠 Theoretical Background

Element	Role in detection post-processing
IoU	Quantifies the spatial overlap between two boxes; \(\text{IoU}=1\) for identical boxes and \(\text{IoU}=0\) for boxes with no overlap
Confidence-based sorting	Ensures that the box with the highest `score` is analyzed first
Threshold \(\tau\)	Defines the amount of overlap required for a box to be considered redundant
Suppression	Removes boxes that exhibit large overlap with an already selected box
Distant boxes	Have IoU close to zero and, in general, are not suppressed by this rule

9.10.4.4 🧩 Methods from `morph.py` that may help

mm.IoU(boxA, boxB) — computes the IoU metric, but expects boxes in the format \((x,y,w,h)\), i.e., top-left corner, width, and height. The input of this exercise uses the format \((x_1,y_1,x_2,y_2)\). The conversion is straightforward:

\[ w=x_2-x_1,\qquad h=y_2-y_1. \]

Using this function is optional. The main goal of the exercise is to correctly implement the NMS selection and suppression process.

9.10.4.5 📦 Input and Output Specification (VPL)

Input:

Line 1: integer \(N\) and real \(\tau\).
Next \(N\) lines: \(x_1\ y_1\ x_2\ y_2\ \text{score}\).

Output:

One line per kept box, in selection order: index score.
Last line: Total kept: X.

🎮 Simulator: IoU and Non-Maximum Suppression 🟡 NMS

Selected box Kept box Suppressed box Candidate box

Number of boxes 5

Threshold τ (IoU) 0.50

Example Default

🎯 Box Visualization

📋 NMS Step by Step

Figure 9.46: EP09_04 Simulator: IoU and Non-Maximum Suppression (NMS)

%%writefile EP09_04.py
# Python code

Overwriting EP09_04.py

TestSuite("EP09_04.py").run()

✔️ EP09_04.cases already exists in casos/
📋 3 case(s) loaded from casos/EP09_04.cases

🔍 Testing Python: EP09_04.py
⚠️ EP09_04.py: Empty file (fewer than 3 lines). Tests skipped.