2D Convolution

mediumFREELinear FilteringImage ProcessingCV: Image Processing

Implement a 2D convolution operation to filter an image using a given kernel. This process is fundamental in Linear Filtering for image processing, where the goal is to modify or enhance the image by applying a kernel that slides over the entire image, performing an element-wise multiplication at each position.

The concept of 2D convolution is crucial in image processing as it allows for the application of various filters to achieve desired effects such as blurring, sharpening, or edge detection. Mathematically, the 2D convolution operation can be represented as a double summation over the kernel's dimensions.

Initialize the output image with zeros.
Slide the kernel over the input image, calculating the element-wise product at each position.
Sum the products to obtain the output value at each position.

\text{out}(y, x) = \sum_{m=0}^{k_H-1} \sum_{n=0}^{k_W-1} I\big(y + m - \lfloor k_H/2 \rfloor,\ x + n - \lfloor k_W/2 \rfloor\big) \cdot K(m, n)

Here $y$ is the row and $x$ the column. The kernel is not flipped, its anchor is cell $(\lfloor k_H/2 \rfloor, \lfloor k_W/2 \rfloor)$ , and any image position outside the image counts as 0 (zero padding).

This technique is widely used in image processing applications.

Example

Input

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

Output

[[-1, -2, -3], [-4, -4, -4], [-7, -4, -4]]

Reasoning

Inputs: image is a $3 \times 3$ intensity grid; kernel holds the weights $K = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$ . Since $\lfloor 2/2 \rfloor = 1$ , the anchor is the kernel's bottom-right cell: $K(0,0)$ lands on the pixel up-and-left of the target, $K(1,1)$ on the target itself.
Math: plugging into the formula gives $\text{out}(y,x) = I(y-1, x-1) - I(y, x)$ , where anything outside the image is 0.
Top row and left column: the up-left neighbour is padding, so only $-I(y,x)$ survives. Row 0 becomes $-1, -2, -3$ ; cells $(1,0)$ and $(2,0)$ become $-4$ and $-7$ .
Interior: $(1,1)$ : $1 - 5 = -4$ ; $(1,2)$ : $2 - 6 = -4$ ; $(2,1)$ : $4 - 8 = -4$ ; $(2,2)$ : $5 - 9 = -4$ .
Output: a $3 \times 3$ grid, same size as the input: [[-1, -2, -3], [-4, -4, -4], [-7, -4, -4]].
Notice every interior value is $-4$ : the image rises by exactly 4 along each down-right diagonal ( $1 \to 5 \to 9$ ), which is what this diagonal-difference kernel measures. Flipping the kernel would change these numbers.

Constraints

Kernel is a small 2D array (typically 3×3 or 5×5)
Use zero-padding
Return result with same dimensions as input

Learn this in

Image ProcessingCV Study Plan

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

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

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.

Step-by-Step Strategy
Get dimensions

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

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.

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.

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.

Return / output

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

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.

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

solution.py

Python 3.13

Test results