Implement Prewitt Edge Detector

hardFREEBrief HistoryEdge DetectionCV: Introduction to Computer Vision

Implement the Prewitt edge detector, one of the earliest edge detection methods (1970).

The Prewitt operator uses two 3×3 kernels to compute horizontal and vertical gradients:

$G_x = \begin{pmatrix} -1 & 0 & 1 \\ -1 & 0 & 1 \\ -1 & 0 & 1 \end{pmatrix} * I, \quad G_y = \begin{pmatrix} -1 & -1 & -1 \\ 0 & 0 & 0 \\ 1 & 1 & 1 \end{pmatrix} * I$

The edge magnitude and direction are: $G = \sqrt{G_x^2 + G_y^2}, \quad \theta = \arctan\left(\frac{G_y}{G_x}\right)$

Here $*$ means centring the kernel on each pixel and summing the element-wise products, without flipping the kernel (so $G_x > 0$ when the column to the right is brighter than the column to the left, and $G_y > 0$ when the row below is brighter than the row above). Pixels outside the image count as 0.

The direction $\theta$ is the full-circle angle of the vector $(G_x, G_y)$ : the signs of both components decide the quadrant, so e.g. $G_x = G_y = -255$ gives $225°$ , not $45°$ . A pixel with $G_x = G_y = 0$ gets direction $0°$ .

Return both the magnitude map and the edge direction map (in degrees, in $[0, 360)$ ).

Example

Input

image = [[0, 0, 0],
         [0, 255, 0],
         [0, 0, 0]]

Output

{'magnitude': [[360.62, 255.0, 360.62], [255.0, 0.0, 255.0], [360.62, 255.0, 360.62]], 'direction': [[45.0, 90.0, 135.0], [0.0, 0.0, 180.0], [315.0, 270.0, 225.0]]}

Reasoning

Input: image is a $3 \times 3$ grayscale grid, all zeros except one bright pixel of 255 at the centre; everything outside the border counts as 0.
Centre (1,1): its window holds 255 only in the middle cell, where both kernels are 0, so $G_x = G_y = 0$ : magnitude 0.0, and the undefined angle is reported as 0.0.
Left neighbour (1,0): the 255 lands in its window's right column, middle row: $G_x = (+1)(255) = 255$ , $G_y = 0$ , so $G = 255$ and $\theta = 0°$ .
Top-left corner (0,0): the 255 is in the bottom-right window cell, weighted $+1$ by both kernels: $G = \sqrt{255^2 + 255^2} = 255\sqrt{2} \approx 360.62$ , $\theta = 45°$ .
Bottom-right corner (2,2): both components are $-255$ , the third quadrant, so $\theta = 225°$ , not the $45°$ that $\arctan(G_y/G_x) = \arctan(1)$ alone would give.
Notice the ring of directions $0°, 45°, \dots, 315°$ : every neighbour's gradient points toward the bright pixel (rows count downward).

Constraints

image: 2D grayscale array
Return: Dict with 'magnitude' and 'direction' arrays
Use zero-padding for borders
Direction in degrees [0, 360), rounded to 1 decimal
Magnitude rounded to 2 decimals

More from CV: Introduction to Computer Vision

Sparse Matrix Operations for Imagesmedium Multi-Scale Feature Pyramidhard Connected Components Labelinghard K-Means Color Quantizationmedium Image Histogram Equalizationmedium

Concept primer

Prewitt Edge Detector: Background & Implementation Guide

Background Knowledge

Edge Detection Fundamentals

Edge detection is a foundational technique in computer vision that identifies boundaries between regions of different intensities in an image. Edges represent significant changes in pixel values and are crucial for object recognition, feature extraction, and image segmentation. The Prewitt operator, developed in 1970, is one of the earliest and most influential edge detection methods. It works by computing spatial gradients—the rate of change of pixel intensity in different directions—using discrete convolution with predefined kernels.

The Gradient-Based Approach

The Prewitt method operates on the principle that edges correspond to regions where the image gradient (rate of change) is large. By applying two separate 3×3 kernels to an image, the algorithm computes the gradient in the horizontal direction ( $G_x$ ) and vertical direction ( $G_y$ ). These kernels are designed to emphasize changes in intensity: the $G_x$ kernel detects vertical edges (changes across columns), while the $G_y$ kernel detects horizontal edges (changes across rows). The magnitude of the gradient at each pixel indicates edge strength, while the direction indicates the orientation of the edge.

Convolution and Kernel Operations

The asterisk (*) in the equations represents 2D convolution, a core operation in image processing. For each pixel, you center the kernel over it, multiply corresponding elements between the kernel and the image patch, sum the results, and store the output. This operation must be applied carefully at image boundaries, where the kernel extends beyond the image—common strategies include zero-padding, reflection, or ignoring boundary pixels.

Algorithm/Approach

The Prewitt edge detector follows a straightforward pipeline:

Convolve the input image with the $G_x$ kernel to compute horizontal gradients
Convolve the input image with the $G_y$ kernel to compute vertical gradients
Compute the magnitude at each pixel using the Euclidean norm: $G = \sqrt{G_x^2 + G_y^2}$
Compute the direction at each pixel using the arctangent: $\theta = \arctan2(G_y, G_x)$
Convert direction to degrees in the range [0, 360)

Step-by-Step Strategy

Step 1: Implement 2D Convolution Create a helper function that performs 2D convolution between an image and a kernel. Handle boundary conditions (typically zero-padding is simplest). For each output pixel, extract the corresponding 3×3 neighborhood, element-wise multiply with the kernel, and sum.

Step 2: Apply Prewitt Kernels Define the $G_x$ and $G_y$ kernels as 2D arrays. Convolve the input image with each kernel separately to produce two gradient maps of the same shape as the input.

Step 3: Compute Magnitude Element-wise compute $G = \sqrt{G_x^2 + G_y^2}$ for all pixels. This represents edge strength; stronger edges have larger magnitude values.

Step 4: Compute Direction Use atan2(G_y, G_x) (not regular atan) to compute the angle in radians. The atan2 function correctly handles all four quadrants and avoids division-by-zero issues. Convert from radians to degrees by multiplying by 180/π.

Step 5: Normalize Direction to [0, 360) Since atan2 returns values in [-π, π], convert to [0, 360) by adding 360 to any negative angles.

Common Pitfalls

Using atan instead of atan2: The two-argument arctangent function (atan2) correctly handles all angle quadrants; regular atan does not and will produce incorrect directions.
Forgetting to convert radians to degrees: Ensure you multiply by 180/π when converting from radians.
Incorrect boundary handling: Decide how to handle pixels near image edges where the 3×3 kernel extends beyond the image. Zero-padding is common but may introduce artifacts; document your choice.
Data type overflow: Gradient values can exceed the original image's range (e.g., if the input is uint8, gradients can exceed 255). Use floating-point arithmetic or larger integer types to avoid overflow.
Magnitude normalization: Depending on your application, you may need to normalize the magnitude map to a specific range (e.g., [0, 255] for visualization).
Direction ambiguity at zero gradient: When both $G_x$ and $G_y$ are zero (no edge), the direction is undefined. Handle this case explicitly (e.g., set direction to 0 or NaN).

Time & Space Complexity

Time Complexity: $O(H \times W)$ where $H$ and $W$ are the height and width of the input image. Each pixel requires a constant number of operations (convolution with a 3×3 kernel, magnitude, and direction computation).

Space Complexity: $O(H \times W)$ for storing the output magnitude and direction maps. If you store intermediate $G_x$ and $G_y$ maps, the space requirement remains $O(H \times W)$ since these are the same size as the input.

solution.py

Python 3.13

Test results