Computer vision: Convolution, ReLU and max pooling

One stage of a CNN is a convolution, a ReLU and a pooling step. Compute one by hand.

What to build

A program that applies a 3 × 3 convolution with a bias, ReLU and 2 × 2 max pooling.

Requirements

  • Feature map: valid cross-correlation of the image with the 3 × 3 kernel (not flipped), plus the bias, then ReLU (negative values become 0).
  • Pooling: 2 × 2 blocks with stride 2; a leftover last row or column is dropped.
  • Print feature map and its rows, then pooled and its rows.

Input

Line 1: H and W. Then H rows. Then 3 kernel rows. Then the bias.

Output

The two labelled blocks.

Constraints

4 ≤ H, W ≤ 40.

Example

Input:

4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
0 0 0
0 1 0
0 0 0
-6

Output:

feature map
0 1
4 5
pooled
5

Why it works

The convolution measures how strongly the kernel's pattern appears at each position, ReLU keeps only positive evidence, and pooling keeps the strongest evidence in each block.

Examples

Example 1 · Input
4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
0 0 0
0 1 0
0 0 0
-6
Expected output
feature map
0 1
4 5
pooled
5
Example 2 · Input
4 5
0 0 9 9 0
0 0 9 9 0
0 0 9 9 0
0 0 9 9 0
-1 0 1
-1 0 1
-1 0 1
0
Expected output
feature map
27 27 0
27 27 0
pooled
27

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

Hints

Hint 1

The feature map has H − 2 rows and W − 2 columns; add the bias to each sum and apply max(0, value).

Hint 2

Pooling uses blocks (2r, 2c), (2r, 2c + 1), (2r + 1, 2c), (2r + 1, 2c + 1) for r < rows // 2 and c < columns // 2.

Solution

Show one correct solution (try it yourself first)
h, w = map(int, input().split())
img = [list(map(int, input().split())) for _ in range(h)]
k = [list(map(int, input().split())) for _ in range(3)]
b = int(input())
fmap = [[max(0, b + sum(k[i][j] * img[r + i][c + j] for i in range(3) for j in range(3))) for c in range(w - 2)] for r in range(h - 2)]
print("feature map")
for row in fmap:
    print(" ".join(map(str, row)))
print("pooled")
for r in range(len(fmap) // 2):
    print(" ".join(str(max(fmap[2 * r][2 * c], fmap[2 * r][2 * c + 1], fmap[2 * r + 1][2 * c], fmap[2 * r + 1][2 * c + 1])) for c in range(len(fmap[0]) // 2)))

Lesson: Convolutional neural networks for images →