Sobel Edge Detection

#241 · Computer Vision · Medium

Problem

Implement the Sobel edge detection operator. Apply Sobel kernels in the x and y directions to a grayscale image, then compute the gradient magnitude.

Solution

import math

def sobel_edge_detection(image: list[list[float]]) -> list[list[float]]:
    """
    image: [H, W] grayscale image
    Returns: [H, W] edge magnitude image
    """
    H = len(image)
    W = len(image[0])

    # Sobel kernels
    Gx = [[-1, 0, 1],
           [-2, 0, 2],
           [-1, 0, 1]]

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

    # Pad image with zeros
    padded = [[0.0] * (W + 2) for _ in range(H + 2)]
    for h in range(H):
        for w in range(W):
            padded[h + 1][w + 1] = image[h][w]

    result = [[0.0] * W for _ in range(H)]

    for h in range(H):
        for w in range(W):
            sx = 0.0
            sy = 0.0
            for kh in range(3):
                for kw in range(3):
                    pixel = padded[h + kh][w + kw]
                    sx += pixel * Gx[kh][kw]
                    sy += pixel * Gy[kh][kw]
            result[h][w] = round(math.sqrt(sx * sx + sy * sy), 4)

    return result

Explanation

Define the 3x3 Sobel kernels for horizontal (Gx) and vertical (Gy) gradients.
Pad the image with zeros to handle border pixels.
For each pixel, convolve with both Gx and Gy to get gradient components.
Compute the gradient magnitude: sqrt(Gx^2 + Gy^2).
High magnitude values indicate strong edges in the image.

Complexity

Time: O(H W 9) = O(H * W) for the 3x3 convolution
Space: O(H * W) for the output and padded image

← #240 #242 →