Sobel Edge Detection

Apply the Sobel operator in the X direction to a 2D grayscale image (matrix).

The Sobel $G_x$ kernel is: $G_x = \begin{bmatrix} -1 & 0 & 1 \\ -2 & 0 & 2 \\ -1 & 0 & 1 \end{bmatrix}$

Perform valid convolution (no padding) by sliding the kernel over the image. For each position, compute the sum of element-wise products between the kernel and the overlapping image region. Return the absolute value of each result, rounded to 4 decimal places.

The output matrix will have dimensions $(H-2) \times (W-2)$ where $H$ and $W$ are the input dimensions.

Example

Input

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

Output

[[8]]

Reasoning

image is a $3 \times 3$ grid of grayscale intensities: rows [1, 2, 3], [4, 5, 6], [7, 8, 9]. Brightness rises by 1 per step to the right and by 3 per step down.
With no padding, the $3 \times 3$ kernel fits in exactly one position, so the output is $(3-2) \times (3-2) = 1 \times 1$ .
Multiply each pixel by the kernel weight in the same spot and add: $(-1)(1) + 0(2) + 1(3) + (-2)(4) + 0(5) + 2(6) + (-1)(7) + 0(8) + 1(9) = 8$ .
Read it column-wise: the middle column has weight 0, so the kernel measures right column minus left column, with the centre row counted twice: $1(3-1) + 2(6-4) + 1(9-7) = 2 + 4 + 2 = 8$ .
The absolute value of $8$ is $8$ , giving [[8]]. Integer pixels give an integer sum, so no decimals appear.
Notice the vertical change of 3 per row contributes nothing: $G_x$ only responds to horizontal change. A left-right mirror would give $-8$ , which the absolute value turns back into $8$ .

Constraints

Input image is a 2D list of numbers (at least 3x3)
Return a 2D list of absolute gradient values
Round each value to 4 decimal places

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 Sobel Edge Detection problem involves applying a kernel to a 2D grayscale image to detect edges. The key concept here is convolution, which is a fundamental operation in image processing. Convolution involves sliding a small matrix (kernel) over a larger matrix (image), performing element-wise multiplication and summing the results at each position. This process can be used to apply various effects to an image, such as blurring, sharpening, or edge detection.

In the context of edge detection, the Sobel operator is used to compute the gradient of the image intensity function. The $G_x$ kernel is designed to detect horizontal edges, while a similar $G_y$ kernel can be used to detect vertical edges. The valid convolution approach, which is specified in the problem, means that the kernel will only be applied to positions where it fully overlaps with the image, resulting in an output matrix that is smaller than the input.

The mathematical representation of the convolution operation can be expressed as: $(f \ast g)(x, y) = \sum_{i=-\infty}^{\infty} \sum_{j=-\infty}^{\infty} f(x-i, y-j) \cdot g(i, j)$ where $f$ is the image, $g$ is the kernel, and $(x, y)$ is the position of the output pixel. However, in this problem, we will be using a simplified version of this equation, since the kernel is small and the convolution is valid.

Algorithm/Approach

The general approach to solving this problem involves iterating over each position in the image where the kernel can be applied, performing the element-wise multiplication and summing the results. This process can be broken down into several steps, including initializing the output matrix, iterating over the image, applying the kernel, and storing the results.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize an output matrix with dimensions $(H-2) \times (W-2)$ , where $H$ and $W$ are the input dimensions.
Iterate over each position $(x, y)$ in the image where the kernel can be applied (i.e., $x = 1$ to $H-2$ and $y = 1$ to $W-2$ ).
At each position, extract the $3 \times 3$ sub-matrix of the image that overlaps with the kernel.
Perform element-wise multiplication between the sub-matrix and the kernel, and sum the results.
Take the absolute value of the result and round it to 4 decimal places.
Store the result in the corresponding position in the output matrix.

Common Pitfalls

Some common pitfalls to watch out for when implementing this solution include:

Incorrectly indexing the image or kernel matrices.
Failing to initialize the output matrix with the correct dimensions.
Not taking the absolute value of the result or rounding it to the correct number of decimal places.
Applying the kernel to positions where it does not fully overlap with the image.

Time & Space Complexity

The time complexity of this solution is $O(H \cdot W)$ , where $H$ and $W$ are the dimensions of the input image. This is because we are iterating over each position in the image where the kernel can be applied, and performing a constant amount of work at each position. The space complexity is also $O(H \cdot W)$ , since we need to store the output matrix, which has dimensions $(H-2) \times (W-2)$ .

solution.py

Python 3.13

Test results