📘

Non-Maximum Suppression (NMS)

EasyFeature Detection and Matching 📚 Computer 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:

First, sort the detections by score in descending order: $[[10, 10, 0.9], [12, 12, 0.8], [50, 50, 0.7], [11, 11, 0.6]]$
Then, iterate through the sorted detections and apply NMS:
- The detection $[10, 10, 0.9]$ is kept as it's the first one.
- The detection $[12, 12, 0.8]$ is within distance $d = 5.0$ of $[10, 10, 0.9]$ since $d = \sqrt{(12 - 10)^2 + (12 - 10)^2} = \sqrt{8} \approx 2.83 < 5.0$ , so it's suppressed.
- The detection $[11, 11, 0.6]$ is also within distance $d = 5.0$ of $[10, 10, 0.9]$ since $d = \sqrt{(11 - 10)^2 + (11 - 10)^2} = \sqrt{2} \approx 1.41 < 5.0$ , so it's suppressed.
- The detection $[50, 50, 0.7]$ is kept as it's not within distance $d = 5.0$ of any already kept detection.
The final output is the kept detections sorted by score in descending order: $[[10, 10, 0.9], [50, 50, 0.7]]$

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

More from Computer Vision 1

Semi-Global Matching Cost AggregationHard Compute Depth Map from DisparityMedium Stereo Rectification CheckEasy Oriented BRIEF DescriptorHard Gaussian Scale SpaceMedium

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.

👑

Continue the full explanation

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

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.