Computer vision: Same-size true convolution

Real filters return an image of the same size, handle the borders and keep values in range. Build one.

What to build

A program that convolves an image with a kernel, keeping its size, and produces valid pixel values.

Requirements

  • Use true convolution: flip the kernel top to bottom and left to right, then centre it on every pixel.
  • Outside the image, use replicate padding (copy the nearest edge pixel).
  • Divide each sum by d with floor division (//), then clamp the result into 0 to 255.
  • Print H rows of W values.

Input

Line 1: H and W. Then H rows of W values. Then k (odd) and d. Then k rows of k whole-number weights.

Output

H rows.

Constraints

1 ≤ H, W ≤ 40; k is 1, 3 or 5; d ≥ 1.

Example

Input:

3 3
10 10 10
10 90 10
10 10 10
3 9
1 1 1
1 1 1
1 1 1

Output:

18 18 18
18 18 18
18 18 18

Why it works

Centring the flipped kernel on every pixel with replicated borders gives one output per input pixel, and dividing then clamping turns the weighted sum back into a valid brightness.

Examples

Example 1 · Input
3 3
10 10 10
10 90 10
10 10 10
3 9
1 1 1
1 1 1
1 1 1
Expected output
18 18 18
18 18 18
18 18 18
Example 2 · Input
1 4
0 0 9 0
3 1
0 0 0
1 0 0
0 0 0
Expected output
0 9 0 0

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

Hints

Hint 1

Flip the kernel first: `[row[::-1] for row in kernel[::-1]]`. Then centre it on each pixel with offsets from −k // 2 to k // 2.

Hint 2

For replicate borders, clamp the row into 0 to H − 1 and the column into 0 to W − 1 before reading a pixel.

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, d = map(int, input().split())
ker = [list(map(int, input().split())) for _ in range(k)]
flipped = [row[::-1] for row in ker[::-1]]
m = k // 2


def px(r, c):
    return img[min(max(r, 0), h - 1)][min(max(c, 0), w - 1)]


for r in range(h):
    out = []
    for c in range(w):
        s = sum(flipped[i][j] * px(r + i - m, c + j - m) for i in range(k) for j in range(k))
        out.append(min(255, max(0, s // d)))
    print(" ".join(map(str, out)))

Lesson: Convolution and kernels →