2D Convolution

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.

\sum_i \sum_j I(x-i, y-j) \cdot K(i,j)

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:

[[-4, -4], [-4, -4]]

Reasoning:

2D Convolution formula:

$(I * K)[i,j] = \sum_{m}\sum_{n} I[i+m, j+n] \cdot K[m,n]$

Valid convolution: Output size = $(3-2+1) \times (3-2+1) = 2 \times 2$

Position $(0,0)$ : Top-left $2 \times 2$ region
- Image patch: $\begin{pmatrix} 1 & 2 \\ 4 & 5 \end{pmatrix}$
- Kernel: $\begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$ $\text{Sum} = (1 \times 1) + (2 \times 0) + (4 \times 0) + (5 \times -1) = 1 - 5 = -4$
Position $(0,1)$ : Top-right $2 \times 2$ region $\text{Sum} = (2 \times 1) + (3 \times 0) + (5 \times 0) + (6 \times -1) = 2 - 6 = -4$
Position $(1,0)$ : Bottom-left $2 \times 2$ region $\text{Sum} = (4 \times 1) + (5 \times 0) + (7 \times 0) + (8 \times -1) = 4 - 8 = -4$
Position $(1,1)$ : Bottom-right $2 \times 2$ region $\text{Sum} = (5 \times 1) + (6 \times 0) + (8 \times 0) + (9 \times -1) = 5 - 9 = -4$

Result: $[[-4, -4], [-4, -4]]$

This kernel computes the diagonal difference, detecting diagonal edges.

Constraints:

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

Example:

Constraints:

Test Results