2D Image Convolution

easyFREEConvolution and FilteringComputer Vision 2

Implement a 2D image convolution operation in valid mode, which involves sliding a kernel over an image to generate a feature map. This process is fundamental in Computer Vision as it enables the extraction of relevant features from images by applying a set of learnable filters.

The concept of convolution is based on the idea of scanning an image with a smaller matrix, known as a kernel, to compute feature values at each position. The kernel is slid over the entire image, and at each position, the element-wise product between the kernel and the overlapping image region is computed, followed by summation of these products. The resulting feature map has a size of $(H - kH + 1) \times (W - kW + 1)$ , where $H$ and $W$ are the dimensions of the image, and $kH$ and $kW$ are the dimensions of the kernel.

Here are the steps to perform the convolution:

Initialize an empty output matrix with dimensions $(H - kH + 1) \times (W - kW + 1)$ .
Slide the kernel over the image, scanning each valid position.
At each position, compute the element-wise product between the kernel and the overlapping image region.
Sum up the products to obtain the feature value at that position.

\text{Output}(i, j) = \sum_{x=0}^{kH-1} \sum_{y=0}^{kW-1} \text{Image}(i+x, j+y) \times \text{Kernel}(x, y)

This technique is widely used in image processing and analysis applications.

Example

Input

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

Output

[[45.0]]

Reasoning

image is a $3 \times 3$ grid of pixel values, and kernel is a $3 \times 3$ grid of weights, all $1$ .
Output size is $(3 - 3 + 1) \times (3 - 3 + 1) = 1 \times 1$ : a kernel as large as the image fits in exactly one place, so only $(i, j) = (0, 0)$ is valid.
There each pixel is multiplied by the weight on it and the products are summed: $(1+2+3) + (4+5+6) + (7+8+9) = 6 + 15 + 24 = 45$ .
Rounded to 4 decimal places, the sum appears as 45.0, in one row of one value: [[45.0]].
Notice that an all-ones kernel just totals the pixels under it. The kernel is not flipped: $\text{Kernel}(x, y)$ weights $\text{Image}(i+x, j+y)$ directly. A $2 \times 2$ kernel with $1$ in the top-left, $-1$ in the bottom-left and $0$ elsewhere gives $1 \cdot 1 + 4 \cdot (-1) = -3$ at $(0, 0)$ , and $-3$ at all four positions.

Constraints

image and kernel are 2D lists of numbers
kernel fits within the image
Return 2D list of convolution results rounded to 4 decimal places

Learn this in

Deep LearningCV Study Plan CNNs & Sequence ModelsML Study Plan

More from Computer Vision 2

1D Bilateral Filterhard Image Sharpening with Unsharp Maskmedium Gaussian Blurmedium Gaussian Kernel Generationeasy Homography Point Transformationhard

Concept primer

Background Knowledge

Convolution is a fundamental concept in computer vision and image processing. It involves sliding a small matrix, known as a kernel or filter, over a larger matrix, such as an image, to perform element-wise multiplication and summing. This process helps in extracting features from the image, such as edges, lines, or textures. In the context of 2D image convolution, the kernel is a small 2D array that slides over the image, performing the convolution operation at each position.

The valid mode of convolution, as specified in the problem, means that the kernel will only slide over positions where it fully overlaps with the image, without any padding. This results in an output image that is smaller than the original image. The size of the output image can be calculated using the formula $(H - kH + 1) \times (W - kW + 1)$ , where $H$ and $W$ are the height and width of the original image, and $kH$ and $kW$ are the height and width of the kernel.

Mathematically, the convolution operation can be represented as:

\begin{aligned} (I * K)(x, y) &= \sum_{i=0}^{kH-1} \sum_{j=0}^{kW-1} I(x+i, y+j) \cdot K(i, j) \end{aligned}

where $I$ is the input image, $K$ is the kernel, and $(x, y)$ is the current position of the kernel.

Algorithm/Approach

The general approach to solving this problem involves iterating over each valid position in the image, extracting the corresponding sub-matrix (or region of interest), performing element-wise multiplication with the kernel, and summing the results. This process is repeated for all valid positions, resulting in the output image.

Step-by-Step Strategy

To implement the solution:

Extract the dimensions of the input image and the kernel.
Calculate the output image size using the formula $(H - kH + 1) \times (W - kW + 1)$ .
Initialize an output image with the calculated size.
Iterate over each valid position in the image, using nested loops to cover all $x$ and $y$ coordinates.
For each position, extract the overlapping sub-matrix from the input image.
Perform element-wise multiplication between the sub-matrix and the kernel.
Sum the results of the multiplication and store the value in the corresponding position in the output image.
Round each output value to 4 decimal places.

Common Pitfalls

When implementing the solution, watch out for:

Incorrect calculation of the output image size.
Failure to handle boundary cases, where the kernel only partially overlaps with the image.
Incorrect implementation of the element-wise multiplication and summing.
Forgetting to round the output values to 4 decimal places.

Time & Space Complexity

The time complexity of the solution is $O(H \cdot W \cdot kH \cdot kW)$ , where $H$ and $W$ are the dimensions of the input image, and $kH$ and $kW$ are the dimensions of the kernel. This is because we are iterating over each valid position in the image and performing a convolution operation at each position.

The space complexity is $O((H - kH + 1) \cdot (W - kW + 1))$ , which is the size of the output image. We also need to consider the space required to store the input image and the kernel, but this is typically given as part of the problem and does not depend on the size of the input.

solution.py

Python 3.13

Test results