Sobel Edge Detection

1. 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)$.

---

2. 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.

---

3. Step-by-Step Strategy

4. 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).

2. 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]]

3. 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.

4. 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

5. 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])

6. (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

---

4. 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.

---

5. 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)$.