Edge Non-Maximum Suppression

1. Background Knowledge

Edge detection in images is typically based on the image gradient, which measures how quickly intensity changes in different directions. After smoothing (e.g., with a Gaussian) and applying a gradient operator (e.g., Sobel), you get:

• a gradient magnitude image $G(x,y)$, showing how strong the edge is at each pixel
• a gradient direction image $\theta(x,y)$, showing the direction of maximum change (perpendicular to the edge).

Raw gradient magnitudes often produce thick edges (several pixels wide), since many neighboring pixels along the gradient direction can have similar large magnitudes. Non-maximum suppression (NMS) is used to thin these responses so that edges become one-pixel wide ridges: it keeps only local maxima of the gradient magnitude along the gradient direction and suppresses others to zero.

To do this efficiently, we quantize the continuous gradient direction $\theta$ into a small set of directions (here 4: 0°, 45°, 90°, 135°). For each pixel, we look at the two neighbors in the quantized direction of the gradient and keep the pixel only if its magnitude is greater than or equal to both neighbors; otherwise, we set it to zero. This is the core of NMS in edge detection (as used, for example, in the Canny edge detector).

2. Algorithm / Approach

General pattern for edge non-maximum suppression:

• For each pixel $(i,j)$:
• Read its gradient magnitude $M(i,j)$ and direction $\theta(i,j)$.
• Quantize $\theta(i,j)$ to one of a small set of canonical directions (0°, 45°, 90°, 135°).
• Based on that quantized direction, choose the two neighboring pixels that lie along the gradient direction (i.e., on both sides of $(i,j)$ along that line).
• Compare $M(i,j)$ with the magnitudes at those two neighbors.
• If $M(i,j)$ is a local maximum (≥ both neighbors), keep it; otherwise, set its output to 0.

This is a single pass over the image, using local comparisons (3 pixels per direction), so it is inherently $O(H \times W)$ where $H, W$ are the image dimensions.

3. Step-by-Step Strategy

Here’s a clear implementation plan:

1. Inputs and outputs

• Input:
• mag[h][w]: gradient magnitudes (floats or doubles).
• dir[h][w]: gradient directions in radians or degrees (often from atan2).
• Output:
• nms[h][w]: result after non-maximum suppression (same shape as mag).

2. Normalize / interpret angles

• Make sure directions are in a consistent range, e.g.:
• Degrees: $-180^\circ$ to $180^\circ$ or $0^\circ$ to $360^\circ$.
• You may convert radians to degrees if easier:

angle_deg = dir[i][j] * 180.0 / math.pi

3. Bring angles into [0°, 180°) or [0°, 360°)

• Often we only need 0–180°, because gradient direction is symmetric:

if angle_deg < 0:
angle_deg += 180.0

4. Quantize direction into 4 bins Common mapping (angles in degrees, example for [0°,180°)):