2D Convolution

1. Background Knowledge

In image processing, a 2D convolution takes an input image $I(x,y)$ and a small kernel/filter $K(i,j)$, and produces an output image where each output pixel is a weighted sum of nearby input pixels. The weights come from the kernel, which can be designed to blur, sharpen, detect edges, etc. Mathematically, for discrete images, convolution is defined as $(I * K)(x,y) = \sum_i \sum_j I(x-i, y-j)\, K(i,j).$ Notice the indices: $I$ is sampled at $(x-i, y-j)$, so the kernel is effectively flipped in both directions compared to correlation.

Because the kernel extends beyond the image boundaries near the edges, you must decide what to assume “outside” the image. This problem specifies zero-padding, meaning any pixel access outside valid indices is treated as 0. This leads to a full output image of the same size as the input, but with boundary effects (e.g., darker borders for some filters).

2. Algorithm/Approach

The general pattern is:

• Treat the image as a 2D array I[h][w] and kernel as K[kh][kw].
• For each output pixel $(x,y)$, compute a double sum over all kernel positions $(i,j)$.
• Map kernel coordinates to image coordinates: $(ix, iy) = (x - i, y - j)$ according to the given formula (or an equivalent but consistent indexing scheme).
• If $(ix, iy)$ is outside the image, use 0 (zero-padding); otherwise, use I[iy][ix].
• Multiply and accumulate: sum += I[iy][ix] * K[i][j].
• Store sum into the output image at $(x,y)$.

This is a straightforward nested-loop algorithm: two loops over output pixels, and two inner loops over kernel entries.

3. Step-by-Step Strategy

4. Get dimensions

• Let image size be H x W.
• Let kernel size be KH x KW.

2. Option A (explicit padding array)

• Compute padding sizes, e.g.
• pad_h = KH - 1, pad_w = KW - 1 if following the exact formula with full flip, or
• often pad_h = KH // 2, pad_w = KW // 2 if using the common centered form.
• Create a new array P of size (H + 2pad_h) x (W + 2pad_w) initialized to 0.
• Copy I into the center of P.

3. Option B (on-the-fly bounds checks)

• Skip creating a padded array and, whenever you compute an index into I, check if it is within [0, H) and [0, W); if not, treat as 0.

4. Main convolution loop (conceptual form) Pseudocode (on-the-fly bounds check version):

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

for y in range(H):
for x in range(W):
s = 0.0
for i in range(KH):
for j in range(KW):
ix = x - i
iy = y - j
if 0 <= ix < W and 0 <= iy < H:
s += I[iy][ix] * K[i][j]
# else: add 0
out[y][x] = s

This matches the given formula directly. You can also re-index to center the kernel differently as long as you’re consistent.

5. Return / output

• Return the out image with the same size H x W.

4. Common Pitfalls

• Confusing convolution with correlation: Convolution flips the kernel; correlation does not. Check your indexing carefully against the provided formula.
• Wrong center / offset: Misaligning how kernel indices map to image coordinates can shift the whole output or produce rotated results.
• Boundary handling mistakes:
• Forgetting zero-padding and reading garbage/out-of-bounds memory.
• Accidentally using “valid” (smaller output) instead of “same” (same size) behavior.
• Integer overflow / precision: If the image is integer and kernel has large values, sums can overflow smaller integer types; often you should accumulate in a larger or floating type.
• Kernel orientation: If you visually designed a kernel (e.g., Sobel), but you implement correlation instead of convolution, you may get edges in the opposite direction.

5. Time & Space Complexity

• Time complexity: For each of the $H \times W$ output pixels, you compute a sum over all $KH \times KW$ kernel elements. $T = O(H \cdot W \cdot KH \cdot KW).$

• Space complexity:

• Output image of size $H \times W$: $O(HW)$.

• Optional padded image adds $O((H + 2\cdot pad_h)(W + 2\cdot pad_w))$, still $O(HW)$ asymptotically. Overall: $S = O(HW).$