Non-Maximum Suppression (NMS)

easyPROFeature Detection and MatchingComputer Vision 1

Implement Non-Maximum Suppression (NMS) for 2D point detections.

Given a list of detections, each represented as $[x, y, score]$ , and a distance threshold $d$ , suppress detections that are within distance $d$ of a higher-scoring detection.

Algorithm:

Sort detections by score in descending order
Initialize an empty list of kept detections
For each detection (in score order):
- If it is within Euclidean distance $d$ of any already-kept detection, suppress it (skip)
- Otherwise, keep it

The Euclidean distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is: $d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$

Return the surviving detections sorted by score in descending order. Each detection should be returned as $[x, y, score]$ with values rounded to 4 decimal places.

Example

Input

detections = [[10, 10, 0.9], [12, 12, 0.8], [50, 50, 0.7], [11, 11, 0.6]]
dist_threshold = 5.0

Output

[[10, 10, 0.9], [50, 50, 0.7]]

Reasoning

Inputs: four point detections, each a location $(x, y)$ plus a confidence score, and a radius $d = 5.0$ . Detections within $d$ of a stronger one are treated as duplicates of the same object.
Ranked by score the order is $0.9, 0.8, 0.7, 0.6$ . The strongest, [10, 10, 0.9], has nothing above it, so it survives.
[12, 12, 0.8]: distance to $(10, 10)$ is $\sqrt{2^2 + 2^2} = \sqrt{8} \approx 2.83 \le 5$ , so it is suppressed.
[50, 50, 0.7]: distance to $(10, 10)$ is $\sqrt{40^2 + 40^2} \approx 56.57 > 5$ , so it survives. It is only compared against survivors, never against the suppressed $(12, 12)$ .
[11, 11, 0.6]: distance to $(10, 10)$ is $\sqrt{2} \approx 1.41 \le 5$ , so it is suppressed even though it lies closer than $(12, 12)$ did.
Output: [[10, 10, 0.9], [50, 50, 0.7]], one peak per cluster, highest score first. Notice that a point at exactly distance $d$ also counts as "within" and is suppressed.

Constraints

detections: List of [x, y, score]
dist_threshold: float (distance threshold for suppression)
Return: List of surviving detections sorted by score descending
Round values to 4 decimal places
Use pure Python + math

Learn this in

Visual SLAM & Localization3D Computer Vision

More from Computer Vision 1

Semi-Global Matching Cost Aggregationhard Compute Depth Map from Disparitymedium Stereo Rectification Checkeasy Oriented BRIEF Descriptorhard Gaussian Scale Spacemedium

Concept primerPREVIEW

Background Knowledge

Non-Maximum Suppression (NMS) is a technique used in computer vision to filter out duplicate or redundant detections. It's commonly applied in object detection tasks where multiple detections may overlap or be nearby. The goal of NMS is to select the most confident detection (i.e., the one with the highest score) and suppress the others within a certain distance threshold. This helps to reduce the number of false positives and improve the overall accuracy of the detection system.

The key concept in NMS is the Euclidean distance, which measures the straight-line distance between two points in a 2D space. The Euclidean distance $d$ between two points $(x_1, y_1)$ and $(x_2, y_2)$ is calculated using the formula: $d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$ . This distance metric is used to determine whether two detections are close enough to be considered redundant.

In the context of feature detection and matching, NMS is essential for refining the detection results and removing noise or duplicate detections. By applying NMS, you can improve the robustness and accuracy of your computer vision system. Understanding the underlying principles of NMS, including the sorting and iteration process, is crucial for implementing an efficient and effective solution.

Algorithm/Approach

The general approach to solving this problem involves sorting the detections by their scores, followed by an iterative process to filter out redundant detections. The algorithm pattern can be summarized as:

Sorting: Arrange the detections in descending order based on their scores.
Iteration: Iterate through the sorted detections, applying the distance threshold to determine whether each detection should be kept or suppressed.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.