Sobel Edge Magnitude and Direction

mediumFREEEdge DetectionComputer Vision 2

Given a 2D grayscale image, compute both the X and Y Sobel gradients, then derive the gradient magnitude and direction at each pixel.

The Sobel kernels are: $G_x = \begin{bmatrix} -1 & 0 & 1 \\ -2 & 0 & 2 \\ -1 & 0 & 1 \end{bmatrix}, \quad G_y = \begin{bmatrix} -1 & -2 & -1 \\ 0 & 0 & 0 \\ 1 & 2 & 1 \end{bmatrix}$

For each valid position compute:

Magnitude: $M = \sqrt{G_x^2 + G_y^2}$
Direction: $\theta = \text{atan2}(G_y, G_x)$ in degrees

Return a tuple (magnitude_matrix, direction_matrix), both rounded to 2 decimal places.

Example

Input

image = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Output

([[25.3]], [[71.57]])

Reasoning

image is a $3 \times 3$ grid of intensities that rise by 1 left to right and by 3 top to bottom. A $3 \times 3$ kernel fits fully inside it at exactly one spot (centred on the 5), so both output grids are $1 \times 1$ ; an $H \times W$ image gives $(H-2) \times (W-2)$ .
Overlay $G_x$ on the whole window: it weights the right column minus the left column, rows weighted $1, 2, 1$ : $G_x = (3-1) + 2(6-4) + (9-7) = 8$ .
Overlay $G_y$ : bottom row minus top row, columns weighted $1, 2, 1$ : $G_y = (7 + 16 + 9) - (1 + 4 + 3) = 24$ .
Magnitude: $M = \sqrt{8^2 + 24^2} = \sqrt{640} \approx 25.298$ , rounded to 2 decimal places: 25.3.
Direction: $\theta = \text{atan2}(24, 8)$ (tangent $3$ ) is about $71.565^\circ$ , giving 71.57.
Notice the vertical gradient is three times the horizontal one, matching the image rising 3 per row versus 1 per column. A flat image gives 0.0 for both.

Constraints

Input image is a 2D list (at least 3x3)
Use math.sqrt and math.atan2, math.degrees
Return tuple of two 2D lists, each rounded to 2 decimal places

Learn this in

Feature Detection and MatchingCV Study Plan

More from Computer Vision 2

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

Concept primer

Background Knowledge

The problem revolves around edge detection in computer vision, specifically using the Sobel operator. The Sobel operator is a discrete differential operator that computes the gradient of an image intensity function. It's widely used for edge detection because it highlights areas with high spatial frequency, which typically correspond to edges. The Sobel operator uses two kernels, $G_x$ and $G_y$ , to compute the gradients in the horizontal and vertical directions, respectively.

The gradient of an image at a point can be thought of as a vector with two components: the rate of change in the x-direction ( $G_x$ ) and the rate of change in the y-direction ( $G_y$ ). The magnitude of this gradient vector, $M = \sqrt{G_x^2 + G_y^2}$ , represents the strength of the edge at that point, while the direction, $\theta =$ \text{atan2} $(G_y, G_x)$ , gives the orientation of the edge. Understanding these concepts is crucial for implementing edge detection algorithms.

In the context of this problem, the task is to apply the Sobel kernels to a given grayscale image to compute the $G_x$ and $G_y$ gradients at each pixel, then calculate the magnitude and direction of these gradients. The result will be two matrices: one for the magnitude of the edges and another for their direction. This process involves convolution operations, where the Sobel kernels are slid over the image, performing a dot product at each position to compute the gradient values.

Algorithm/Approach

The general approach to solving this type of problem involves the following steps:

Convolution: Apply the Sobel kernels ( $G_x$ and $G_y$ ) to the input image through convolution to obtain the $G_x$ and $G_y$ gradient images.
Gradient Calculation: Compute the magnitude ( $M$ ) and direction ( $\theta$ ) of the gradient at each pixel using the $G_x$ and $G_y$ values.
Post-processing: Round the calculated magnitude and direction values to 2 decimal places as required.

Step-by-Step Strategy

Load the Image: Start by loading the given grayscale image.
Apply Sobel Kernels: Convolve the Sobel kernels ( $G_x$ and $G_y$ ) with the image to obtain the $G_x$ and $G_y$ gradient images.
Compute Gradient Magnitude: For each pixel, calculate the magnitude $M = \sqrt{G_x^2 + G_y^2}$ .
Compute Gradient Direction: For each pixel, calculate the direction $\theta =$ \text{atan2} $(G_y, G_x)$ and convert it to degrees.
Round Values: Round the magnitude and direction matrices to 2 decimal places.
Return Result: Return the magnitude and direction matrices as a tuple.

Common Pitfalls

Kernel Application: Ensure that the Sobel kernels are applied correctly, considering the boundaries of the image.
Data Types: Be mindful of the data types used for calculations to avoid overflow or underflow, especially when computing the square root for the magnitude.
atan2 Usage: Understand that $\text{atan2}(G_y, G_x)$ gives the angle in radians; it needs to be converted to degrees for the direction matrix.

Time & Space Complexity

Time Complexity: The time complexity is dominated by the convolution operation, which is $O(n \cdot m \cdot k^2)$ , where $n$ and $m$ are the dimensions of the image, and $k$ is the size of the kernel (in this case, $k=3$ ). The subsequent calculations for magnitude and direction are $O(n \cdot m)$ .
Space Complexity: The space complexity is $O(n \cdot m)$ , as we need to store the gradient images ( $G_x$ and $G_y$ ), the magnitude matrix, and the direction matrix, all of which are of the same size as the input image.

solution.py

Python 3.13

Test results