Loading problem...
Edge detection is one of the most fundamental and powerful techniques in computer vision, enabling systems to identify and locate meaningful boundaries within images. Edges represent significant local changes in pixel intensity—marking transitions between objects, textures, shadows, and background regions.
In this problem, you will implement a gradient-based edge detection algorithm that uses directional derivative operators to compute how rapidly pixel intensities change across an image. The algorithm employs two 3×3 convolution kernels—one tuned to detect horizontal intensity gradients and another for vertical intensity gradients:
Horizontal Gradient Kernel (Gx): $$G_x = \begin{bmatrix} -1 & 0 & +1 \ -2 & 0 & +2 \ -1 & 0 & +1 \end{bmatrix}$$
Vertical Gradient Kernel (Gy): $$G_y = \begin{bmatrix} -1 & -2 & -1 \ 0 & 0 & 0 \ +1 & +2 & +1 \end{bmatrix}$$
For each pixel position in the image, the kernels are applied through convolution to compute the gradient components in both directions. The edge magnitude at each position is then calculated using the Euclidean norm:
$$\text{Magnitude} = \sqrt{G_x^2 + G_y^2}$$
The final step involves normalizing the magnitude values to fit within the standard grayscale intensity range of [0, 255], where 0 represents no edge and 255 represents the strongest detected edge.
Your Task: Implement a function that takes a grayscale image and returns an edge magnitude map. Due to the 3×3 kernel size and valid convolution (no padding), the output dimensions will be (H-2, W-2) where H and W are the input image height and width respectively.
Edge Cases to Handle:
image = [[0, 0, 255], [0, 0, 255], [0, 0, 255]][[255]]This 3×3 image contains a sharp vertical edge—the left side is pure black (0) and the right column is pure white (255). When the gradient kernels are applied at the center pixel:
• Gx (horizontal gradient): The weighted sum detects a strong transition from dark to bright moving left-to-right, yielding Gx = 1020 • Gy (vertical gradient): No vertical change exists since each row is identical, yielding Gy = 0
The magnitude = √(1020² + 0²) = 1020. Since this is the maximum magnitude in the output, it gets normalized to 255.
The output is a 1×1 array because valid convolution on a 3×3 image with a 3×3 kernel produces a single pixel output.
image = [[0, 85, 170, 255], [0, 85, 170, 255], [0, 85, 170, 255]][[255, 255]]This 3×4 image displays a smooth horizontal gradient from black (0) on the left to white (255) on the right. Each column increases by 85 intensity units.
Applying the gradient kernels at the two valid positions (center of each 3×3 window): • Both positions detect consistent horizontal gradients with Gx = 680 • No vertical changes exist, so Gy = 0 for both
Both magnitudes equal √(680² + 0²) = 680. After normalization relative to the maximum value, both output pixels are set to 255.
The output dimensions are 1×2 (height = 3-2 = 1, width = 4-2 = 2).
image = [[0, 255, 0, 255], [255, 0, 255, 0], [0, 255, 0, 255], [255, 0, 255, 0]][[0, 0], [0, 0]]This 4×4 image shows a perfect checkerboard pattern where adjacent pixels alternate between black (0) and white (255).
Despite the high local contrast, the checkerboard's symmetric nature causes the gradient kernels to produce zero response at all valid positions: • The positive and negative contributions in both Gx and Gy kernels cancel out perfectly due to the alternating pattern • Every 3×3 window centered on the interior pixels yields Gx = 0 and Gy = 0
The magnitude at all positions is 0, resulting in a 2×2 output of zeros—indicating no directional edge structure despite the high-contrast pattern.
This demonstrates an important property: gradient-based edge detectors respond to directional intensity changes, not just overall contrast.
Constraints