Sobel Edge Detection

mediumFREELinear FilteringImage ProcessingCV: Image Processing

Implement a Sobel Edge Detection algorithm to identify edges in an image by applying linear filtering techniques. This task involves using Sobel operators to compute the gradient of an image intensity function.

The Sobel operator is a discrete differential operator that computes the gradient of an image intensity function, which is a measure of the rate of change of the intensity in the x and y directions. This is represented by the gradient magnitude, $G = \sqrt{G_x^2 + G_y^2}$ , where $G_x$ and $G_y$ are the x and y components of the gradient.

Here are the steps to detect edges:

Apply the x-direction Sobel kernel, $G_x$ , to the image.
Apply the y-direction Sobel kernel, $G_y$ , to the image.
Compute the gradient magnitude.

G_x = \begin{pmatrix} -1 & 0 & 1 \\ -2 & 0 & 2 \\ -1 & 0 & 1 \end{pmatrix}, \quad G_y = \begin{pmatrix} -1 & -2 & -1 \\ 0 & 0 & 0 \\ 1 & 2 & 1 \end{pmatrix}

This technique is widely used in image processing and computer vision applications.

Example

Input

sobel([[0,0,255],[0,0,255],[0,0,255]])

Output

[[0, 0, 0], [0, 255, 0], [0, 0, 0]]

Reasoning

Only the centre pixel $(1, 1)$ has a full 3×3 neighbourhood, so the 1-pixel border stays 0.
The centre's neighbourhood is the whole image: left and middle columns 0, right column 255.
$G_x = (-1 - 2 - 1) \cdot 0 + (1 + 2 + 1) \cdot 255 = 1020$ .
$G_y = -(0 + 0 + 255) + (0 + 0 + 255) = 0$ , since the top and bottom rows are identical.
Magnitude: $\sqrt{1020^2 + 0^2} = 1020$ , clamped to $255$ .
Output: $[[0, 0, 0], [0, 255, 0], [0, 0, 0]]$ , a strong vertical edge at the centre.

Constraints

Return edge magnitude image
Round to nearest integer
Clamp to [0, 255]
Border pixels (no full 3×3 neighbourhood) stay 0

More from CV: Image Processing

Frequency Domain Filteringhard Separable Filter Optimizationhard Contrast Limited Adaptive Histogram Equalizationmedium Frequency Component Energyeasy Low-Pass Filter (Frequency)medium

Concept primer

Background Knowledge

Sobel edge detection is a classic gradient-based method to find edges in images. An edge is a location where intensity changes sharply; mathematically, this corresponds to a large gradient of the image function. If we treat a grayscale image as a 2D function $I(x, y)$ , then edges are where the derivatives $\partial I /$ \partial $x$ and $\partial I /$ \partial $y$ are large.

Direct derivatives are noisy, so Sobel uses 3×3 convolution kernels that both approximate the derivative and apply slight smoothing (the central row/column is weighted more). Convolving the image with $G_x$ approximates the horizontal derivative (change along x, detecting vertical edges), and convolving with $G_y$ approximates the vertical derivative (change along y, detecting horizontal edges). From these two components, you can compute an edge magnitude $G = \sqrt{G_x^2 + G_y^2}$ and optionally a direction $\theta = \arctan2(G_y, G_x)$ .

Algorithm / General Approach

At a high level, the pattern is:

Interpret Sobel operators as convolution filters.
For each pixel, apply the 3×3 Sobel kernels to a 3×3 neighborhood to get:
$g_x(x, y)$ : horizontal gradient component.
$g_y(x, y)$ : vertical gradient component.
Combine $g_x$ and $g_y$ to get:
Magnitude: $G(x, y) = \sqrt{g_x^2 + g_y^2}$ .
Optionally apply a threshold to get a binary edge map.

So the problem is essentially: implement 2D convolution with given kernels, then compute per-pixel gradient magnitude.

Step-by-Step Strategy
Input preparation

Ensure you have a grayscale image (2D array).
If you start with RGB, convert to grayscale first (e.g., weighted sum of channels).

Define Sobel kernels

Hard-code the 3×3 kernels:

Gx = [[-1, 0, 1],
[-2, 0, 2],
[-1, 0, 1]]

Gy = [[-1, -2, -1],
[ 0, 0, 0],
[ 1, 2, 1]]

Handle image borders

Choose a strategy:
Ignore 1-pixel border (output smaller image), or
Pad the input (e.g., with zeros or edge replication) and produce same-sized output.

Compute $G_x$ and $G_y$ via convolution

For each pixel $(i, j)$ (excluding borders if not padded):
Take its 3×3 neighborhood.
Multiply element-wise with $G_x$ and sum → $g_x(i, j)$ .
Multiply element-wise with $G_y$ and sum → $g_y(i, j)$ .

Example (pseudo-code):

for i in range(1, H-1):
for j in range(1, W-1):
gx = 0
gy = 0
for u in range(-1, 2):
for v in range(-1, 2):
val = img[i+u][j+v]
gx += val * Gx[u+1][v+1]
gy += val * Gy[u+1][v+1]
Gx_img[i][j] = gx
Gy_img[i][j] = gy

Compute gradient magnitude

For each pixel:

G[i][j] = sqrt(Gx_img[i][j]**2 + Gy_img[i][j]**2)
# or faster approximation:
# G[i][j] = abs(Gx_img[i][j]) + abs(Gy_img[i][j])

(Optional) Normalize / threshold

If required by the problem:
Normalize $G$ to a valid image range (e.g., 0–255).
Optionally apply a threshold:

edge[i][j] = 255 if G[i][j] > T else 0

Common Pitfalls

Border handling: Accessing out-of-bounds indices when computing 3×3 neighborhoods. Decide clearly how to treat the outermost pixels.
Integer overflow / type issues:
Intermediate gradient values can exceed 255; use a larger integer or float type during computation, then clamp or normalize at the end.
Mixing up $G_x$ and $G_y$ :
Remember: the provided $G_x$ detects vertical edges (changes along x), and $G_y$ detects horizontal edges.
Using squared magnitude but calling it magnitude:
If you skip the square root for speed, be explicit whether you’re returning $G^2$ or $G$ , and be consistent with any thresholding.
Not converting to grayscale:
Applying Sobel separately to each color channel without a defined combination can give unexpected results unless the problem explicitly wants that.

Time & Space Complexity

Let the image size be $H \times W$ .
Time complexity:
Convolution with each 3×3 kernel is $O(1)$ per pixel.
Two convolutions (for $G_x$ and $G_y$ ) plus magnitude → overall $O(H \times W)$ .
Space complexity:
Storing the output gradient magnitude (and optionally $G_x$ , $G_y$ ) takes $O(H \times W)$ .
So total extra space is $O(H \times W)$ .

solution.py

Python 3.13

Test results