2D Convolution

A dense layer ignores where pixels are; a convolution uses it. It slides one small grid of weights, a kernel, across the image and computes one weighted sum per position. After this lesson your program applies a kernel to an image with any stride and padding, and predicts the output size.

Pattern matching by sliding a window

At each position, lay the kernel over the patch of the image beneath it, multiply the overlapping numbers pairwise, and add them up. The sum is large when the patch looks like the kernel and small otherwise. A kernel with negative weights on the left and positive on the right responds to a vertical edge; a learned network discovers such kernels for itself.

Deep-learning libraries do not flip the kernel before sliding it, which is what signal-processing textbooks call convolution. What they compute is technically cross-correlation. The difference is irrelevant for a learned kernel, so "convolution" here means: no flipping.

The computation

For output position (r, c), kernel height kh and width kw, stride s:

out[r][c] = sum over u in 0..kh-1, v in 0..kw-1 of  image[r*s + u][c*s + v] * kernel[u][v]

A worked trace

Image (3 rows by 4 columns) and a 2 by 2 kernel:

image:   1 2 0 1        kernel:  1 -1
         3 1 2 0                 2  0
         0 4 1 2

Stride 1, no padding. The window at (0, 0) is [1 2; 3 1]:

1*1 + 2*(-1) + 3*2 + 1*0 = 1 - 2 + 6 + 0 = 5

Sliding right and down gives the full 2 by 3 output:

5 4 3
2 7 4

With stride 2 the window jumps two cells at a time and the output shrinks to 1 by 2: 5 3.

Padding

Without padding the kernel can never sit centred on a border pixel, edge pixels are used less often than interior ones, and every layer shrinks the image. Zero padding adds a border of pad zeros on all four sides first. With a 3 by 3 kernel and pad = 1 the output keeps the input's size. Indexing is easy: position (y, x) in the padded image is (y - pad, x - pad) in the original, and anything outside the original reads as 0.

Output size

Along each axis, with input size n, kernel size k, stride s and padding p:

out = floor( (n + 2*p - k) / s ) + 1

The floor matters. A width of 7 with kernel 3, stride 2 and padding 1 gives floor(6 / 2) + 1 = 4. A width of 8 with kernel 3, stride 2 and no padding gives floor(5 / 2) + 1 = 3: the last column is never fully covered and is simply dropped.

Why this beats a dense layer on images

A kernel has only kh * kw weights, reused at every position (weight sharing). A 3 by 3 kernel has 9 weights where a dense layer over a 28 by 28 image needs 784 per output neuron. The same detector works anywhere in the picture, so a digit shifted by a pixel is still recognised. Stacking layers builds from edges to shapes to objects.

Common mistakes

• Forgetting to multiply the output index by the stride when finding the window's corner, which silently uses stride 1.
• Rounding the output size up, or using true division and getting a fraction.
• Flipping the kernel.
• Padding one side only, or reading outside the image instead of treating it as zero.
• Integer accumulation in a language where sums of floats were meant (the kernel may hold decimals).

Your exercise

The starter reads IMG, KERNEL, STRIDE, PAD and prints the result for CONV and SHAPE. Implement out_size and conv2d.