Deep learning: A 2D convolution with padding and stride

Compute a 2D convolution the way a CNN layer does.

What to build

A program that convolves an image with a kernel, using padding and stride.

Requirements

  • Output size in each direction is ⌊(n + 2p − k) / s⌋ + 1. Each output is the sum of the kernel times the padded-image patch under it.
  • Print the output rows, values written with Python's g format and separated by spaces.

Input

Line 1: image height and width. Then the image rows. Then kernel height and width, then its rows. Last line: padding and stride.

Output

One line per output row.

Constraints

Images up to 20 × 20; kernels up to 5 × 5.

Example

Input:

3 3
1 2 3
4 5 6
7 8 9
2 2
1 0
0 1
0 1

Output:

6 8
12 14

Why it works

Padding lets the kernel reach the edge pixels and stride skips positions, so together they set how large the feature map is.

Examples

Example 1 · Input
3 3
1 2 3
4 5 6
7 8 9
2 2
1 0
0 1
0 1
Expected output
6 8
12 14
Example 2 · Input
3 3
1 2 3
4 5 6
7 8 9
1 1
2
1 2
Expected output
0 0 0
0 10 0
0 0 0

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Pad the image with p rows and columns of zeros on every side first.

Hint 2

Output (r, c) uses the patch whose top-left corner is (r × stride, c × stride) of the padded image.

Solution

Show one correct solution (try it yourself first)
h, w = map(int, input().split())
img = [list(map(float, input().split())) for _ in range(h)]
kh, kw = map(int, input().split())
kernel = [list(map(float, input().split())) for _ in range(kh)]
pad, stride = map(int, input().split())
width = w + 2 * pad
padded = [[0.0] * width for _ in range(pad)]
padded += [[0.0] * pad + row + [0.0] * pad for row in img]
padded += [[0.0] * width for _ in range(pad)]
rows = (h + 2 * pad - kh) // stride + 1
cols = (w + 2 * pad - kw) // stride + 1
for r in range(rows):
    out = []
    for c in range(cols):
        total = sum(padded[r * stride + a][c * stride + b] * kernel[a][b] for a in range(kh) for b in range(kw))
        out.append(f"{total + 0.0:g}")
    print(" ".join(out))

Lesson: Convolutions →