PIXELBANKv8.2.1
Menu
Sign In

Non-Maximum Suppression (NMS)

EasyFeature Detection and Matching

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

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

Algorithm:

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

The Euclidean distance between two points (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2) is: d=(x1−x2)2+(y1−y2)2d = \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][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]][[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][10, 10, 0.9] is kept as it's the first one.
    • The detection [12,12,0.8][12, 12, 0.8] is within distance d=5.0d = 5.0 of [10,10,0.9][10, 10, 0.9] since d=(12−10)2+(12−10)2=8≈2.83<5.0d = \sqrt{(12 - 10)^2 + (12 - 10)^2} = \sqrt{8} \approx 2.83 < 5.0, so it's suppressed.
    • The detection [11,11,0.6][11, 11, 0.6] is also within distance d=5.0d = 5.0 of [10,10,0.9][10, 10, 0.9] since d=(11−10)2+(11−10)2=2≈1.41<5.0d = \sqrt{(11 - 10)^2 + (11 - 10)^2} = \sqrt{2} \approx 1.41 < 5.0, so it's suppressed.
    • The detection [50,50,0.7][50, 50, 0.7] is kept as it's not within distance d=5.0d = 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]][[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
Editor

Test Results

0/0
Run code to see test results.