📘

Feature NMS (Non-Maximum Suppression)

MediumFeatures 📚 CV: Feature Detection and Matching

You are given a response map from a corner detector and need to apply non-maximum suppression to keep only local maxima as feature points.

Non-maximum suppression ensures that detected features are well-distributed and don't cluster together. A pixel is kept as a feature only if it's the strict maximum in its local neighborhood.

The algorithm:

For each pixel in the response map
Compare it to all neighbors within a window of size window_size × window_size
If the pixel's value is strictly greater than ALL neighbors, it's a local maximum
Return coordinates of all local maxima

A strict maximum means: pixel_value > all_neighbor_values (not ≥)

Example:

Input:

response_map = [[1, 2, 1],
                [2, 5, 2],
                [1, 2, 1]]
window_size = 3

Output:

[(1, 1)]

Reasoning:

Checking each pixel against its neighbors (3×3 window):

(0,0)=1: neighbors include 2,2,5 → not a max
(0,1)=2: neighbors include 5 → not a max
(0,2)=1: neighbors include 2,5,2 → not a max
(1,0)=2: neighbors include 5 → not a max
(1,1)=5: neighbors are [1,2,1,2,2,1,2,1] → max is 2 < 5 ✓ LOCAL MAX
(1,2)=2: neighbors include 5 → not a max
(2,0)=1: neighbors include 2,5,2 → not a max
(2,1)=2: neighbors include 5 → not a max
(2,2)=1: neighbors include 2,5,2 → not a max

Only (1,1) is a local maximum.

Constraints:

response_map is a 2D array of corner responses
window_size is an odd number (3, 5, 7, etc.)
Return list of (row, col) tuples for all local maxima
Order: top-to-bottom, left-to-right

More from CV: Feature Detection and Matching

Circle Hough TransformHard Canny Edge Detection PipelineHard Hamming Distance MatcherHard Simple BRIEF DescriptorMedium Point to Hough SpaceEasy

You want to understand local non-maximum suppression on a 2D response map (not bounding boxes), and how to implement it robustly.

1. Background Knowledge

In corner/interest point detection (e.g., Harris, Shi-Tomasi), you first compute a response map: a 2D array where each pixel stores a “corner strength” (how likely it is to be a good feature). This map often has many nearby high responses around the same structure.

Non-maximum suppression (NMS) on a response map is a post-processing step that thins these responses so that only isolated, strong peaks remain. A pixel is considered a valid feature only if it is a strict local maximum in its neighborhood: its value is strictly greater than all pixels in a surrounding window. This avoids clusters of points on the same corner and ensures features are better distributed spatially.

The window size controls how aggressively you thin the features: a larger window keeps fewer, more separated points; a smaller window allows more dense features. The “strictly greater than” condition (not ≥) ensures you don’t keep flat plateaus or ties as multiple features.

2. Algorithm / Approach

High-level pattern for this problem:

Treat the response map as a 2D array.
For each pixel, consider a local neighborhood window centered at that pixel.
Check whether the center pixel is the strict (>) maximum over that window.
If yes, record its coordinates as a feature point; otherwise, discard it.
Handle boundaries by shrinking the window or skipping border pixels.

This is a straightforward sliding window + argmax pattern over a 2D grid.

3. Step-by-Step Strategy

Inputs and parameters

Given:
response as a 2D array of shape (H, W).
window_size (odd recommended, e.g. 3, 5, 7).
Compute:
r = window_size // 2 (radius in each direction).

Decide how to handle borders Two common choices:

Only process pixels with a full window around them:
Loop i from r to H - r - 1
Loop j from r to W - r - 1
Or, allow smaller windows near borders (a bit more logic, but similar idea).

For each candidate center pixel

Extract its local window:

window = response[i-r : i+r+1, j-r : j+r+1]
center_val = response[i, j]

Find the maximum in the window:

local_max = window.max()

Check strict maximum:
center_val == local_max and
center_val appears only once in the window (or equivalently center_val > all other values).
If conditions satisfied, add (i, j) to the list of feature coordinates.

A typical robust check (conceptually):

if center_val == local_max and np.count_nonzero(window == center_val) == 1:
keep (i, j)

Collect results

Store all kept coordinates in a list (or array) and return them as the output.

4. Common Pitfalls

Using ≥ instead of > If you use >=, you will keep multiple points in flat regions or where two neighbors have exactly equal response. The problem explicitly requires a strict maximum.
Not enforcing uniqueness of the maximum center_val == window.max() alone is not enough when multiple pixels share the same maximum value. Ensure the center is the only max in that window.
Incorrect window indexing
Off-by-one errors when slicing windows.
Forgetting that response[i-r : i+r+1] is inclusive of i-r and exclusive of i+r+1.
Border handling
Accessing indices outside the array.
Forgetting to adjust loop bounds when you require a full window.
Even window sizes
A window with even size (e.g., 4×4) has no single central pixel. It’s simpler and more standard to require odd window_size.

5. Time & Space Complexity

Let:

$H$ = height, $W$ = width of the response map,
$k = \text{window_size}$ .
Time complexity
For each of the $H \times W$ pixels, you examine a $k \times k$ neighborhood.
Complexity:

O(H \times W \times k^2)

For small, fixed $k$ (e.g., 3, 5, 7), this is effectively $O(H \times W)$ .
Space complexity
If you store only the list of coordinates and use a sliding window directly on the input array, extra space is:
$O(F)$ for the output list, where $F$ is the number of detected features.
$O(1)$ auxiliary space (not counting input/output).
Overall: O(HW) for input + O(F) for output, with O(1) extra working memory.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.