Feature NMS (Non-Maximum Suppression)

mediumFREEFeature DetectorsFeaturesCV: 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 ≥)

At the borders, window positions that fall outside the map are ignored: only neighbors that actually exist are compared, so edge and corner pixels can also be local maxima.

Example

Input

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

Output

[(1, 1)]

Reasoning

response_map is a $3 \times 3$ grid of corner strengths and window_size is $3$ , so each pixel's neighbourhood is the $3 \times 3$ block centred on it: everything within $\lfloor 3/2 \rfloor = 1$ row and column.
The centre (1, 1) holds $5$ . Its eight neighbours are $1, 2, 1, 2, 2, 1, 2, 1$ , at most $2$ . Since $5 > 2$ , it is a local maximum.
Every edge pixel, such as (0, 1) with value $2$ , has the $5$ inside its window. It fails to beat that neighbour, so it is suppressed.
Near the border the window hangs off the map, and those missing cells simply are not neighbours. Corner (0, 0) has only three real neighbours, $2, 2, 5$ , and loses.
Only one pixel survives, so the answer is [(1, 1)], written as (row, column).
Notice the comparison is strict: a map of all $1$ s returns an empty list because no pixel beats its equal neighbours, while a map with $5$ in each corner and $0$ elsewhere keeps all four corners.

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

Learn this in

Feature Detection and MatchingCV Study Plan

More from CV: Feature Detection and Matching

Circle Hough Transformhard Canny Edge Detection Pipelinehard Hamming Distance Matcherhard Simple BRIEF Descriptormedium Point to Hough Spaceeasy

Concept primer

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