Non-Maximum Suppression for Edge Thinning

mediumPROEdge DetectionComputer Vision 2

Given gradient magnitude and direction matrices (same size), thin edges by keeping only local maxima along the gradient direction.

Algorithm:

For each interior pixel (skip border pixels, set them to 0):
Quantize the gradient direction to one of 4 angles: $0°$ , $45°$ , $90°$ , $135°$ (using modulo 180)
Check the two neighbors along that direction:
- $0°$ : left and right neighbors $(i, j-1)$ and $(i, j+1)$
- $45°$ : diagonal neighbors $(i-1, j+1)$ and $(i+1, j-1)$
- $90°$ : top and bottom $(i-1, j)$ and $(i+1, j)$
- $135°$ : diagonal $(i-1, j-1)$ and $(i+1, j+1)$
If the pixel's magnitude is $\geq$ both neighbors, keep it; otherwise suppress to 0.

Quantization ranges (using angle mod 180):

$[0, 22.5)$ or $[157.5, 180)$ → $0°$
$[22.5, 67.5)$ → $45°$
$[67.5, 112.5)$ → $90°$
$[112.5, 157.5)$ → $135°$

Example

Input

magnitude = [[5, 5, 5], [5, 10, 5], [5, 5, 5]]
direction = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

Output

[[0, 0, 0], [0, 10, 0], [0, 0, 0]]

Reasoning

The gradient direction is $0°$ for all pixels, so we compare each pixel's magnitude with its left and right neighbors.
For the middle pixel in the second row, its magnitude ( $10$ ) is greater than or equal to both its left and right neighbors ( $5$ ), so it is kept as is.
For all other interior pixels, their magnitudes are not greater than or equal to both their neighbors (e.g., the top-middle pixel has a magnitude of $5$ , which is not greater than its right neighbor, also $5$ , but since they are equal and the pixel is not a local maximum along the $0°$ direction in this specific comparison context, it gets suppressed), so they are suppressed to $0$ .
Border pixels are set to $0$ as per the algorithm, resulting in the final output: [[0, 0, 0], [0, 10, 0], [0, 0, 0]]

Constraints

magnitude and direction are 2D lists of the same size (at least 3x3)
direction values are in degrees
Border pixels are always set to 0
Return the thinned magnitude matrix

More from Computer Vision 2

1D Bilateral Filterhard Image Sharpening with Unsharp Maskmedium Gaussian Blurmedium Gaussian Kernel Generationeasy 2D Image Convolutioneasy

Concept primerPREVIEW

Background Knowledge

Edge detection is a fundamental concept in computer vision, which involves identifying and locating edges within an image. Edges are areas of significant change in intensity, which can indicate the presence of an object or a boundary. The gradient magnitude and direction matrices are essential components in edge detection, as they represent the rate of change of intensity in different directions. The gradient magnitude represents the strength of the edge, while the direction represents the orientation of the edge.

The concept of non-maximum suppression is used to thin edges by eliminating pixels that are not local maxima. This is done by comparing the gradient magnitude of each pixel with its neighbors along the gradient direction. If the pixel's magnitude is not greater than or equal to its neighbors, it is suppressed to 0. This process helps to refine the edges and remove noise. The quantization of gradient direction to one of four angles (0°, 45°, 90°, 135°) is a common technique used to simplify the comparison process.

The use of modulo 180 to quantize the gradient direction is based on the fact that the gradient direction is periodic, with 0° and 180° representing the same direction. By using modulo 180, we can ensure that the quantized direction falls within the range of 0° to 180°, making it easier to compare with the predefined ranges. The predefined ranges for quantization are based on the fact that the gradient direction is typically measured in degrees, with 0° representing the horizontal direction and 90° representing the vertical direction.

Algorithm/Approach

The general approach to solve this problem involves iterating over each interior pixel in the image, quantizing the gradient direction, and comparing the gradient magnitude with its neighbors along the quantized direction. The algorithm pattern can be broken down into the following steps:

Iterate over each interior pixel
Quantize the gradient direction
Compare the gradient magnitude with its neighbors
Suppress pixels that are not local maxima

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.

PRO

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