2D Convolution - CNNs & Computer Vision

2D Convolution

What you'll build

The forward pass of a single-channel 2D convolution with no padding and stride 1: slide a small kernel over an image and take a weighted sum at every position.

Background

This is the core operation of every CNN. A conv layer applies the same small kernel at every position, so it detects a pattern (an edge, a corner) wherever it appears. Deep learning frameworks actually compute cross-correlation: the kernel is not flipped. That is what nn.Conv2d / F.conv2d do, and what is asked here.

Formula

For every output position (i, j):

out[i, j] = sum over a in [0, kH), b in [0, kW) of  image[i + a, j + b] * kernel[a, b]
          = sum(image[i:i+kH, j:j+kW] * kernel)

H_out = H - kH + 1
W_out = W - kW + 1

Inputs

• image: 2D array of shape (H, W) (one channel, no batch axis; a nested list is also fine, convert with np.asarray). Values can be ints or floats.
• kernel: 2D array of shape (kH, kW) with kH <= H and kW <= W. Kernels can be non-square.

Expected return format

A NumPy float array of shape (H - kH + 1, W - kW + 1). Keep the exact values: don't round or cast to int.

Edge cases and conventions

• No padding: the output is smaller than the input ("valid" convolution).
• Don't flip the kernel. For an asymmetric kernel, flipping changes the answer.
• A kernel the same size as the image gives a 1 x 1 output.

Constraints

NumPy only; don't call scipy.signal.correlate2d or similar. Two nested loops over output positions are fine; looping over the kH * kW kernel taps instead is faster.

Follow-up

• How would you add padding and stride? (See Advanced 2D Convolution.)
• How does im2col turn this into a single matrix multiply, and what does it cost in memory?

Input: image = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], kernel = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Output: [[5.]]

Input: image = [[0.5, 1.5, -1.0], [2.0, 0.25, 1.0], [-0.5, 3.0, 2.0]], kernel = [[1.0, -0.5], [0.5, 2.0]]
Output: [[1.25, 4.125], [7.625, 5.25]]

import numpy as np

def conv2d(image, kernel):
    """
    Apply a 2D convolution (cross-correlation, no padding, stride 1).

    Args:
        image: Input image, shape (H, W)
        kernel: Convolution kernel, shape (kH, kW)

    Returns:
        output: Float array of shape (H - kH + 1, W - kW + 1)
    """
    # Your code here
    pass