Computer vision: Bilinear resize with aligned pixel centres

This is how OpenCV's default resize works: pixel centres are lined up, then four neighbours are blended.

What to build

A program that resizes an image with bilinear interpolation and pixel-centre alignment.

Requirements

  • For output column d, the source position is (d + 0.5) × W / newW − 0.5, clamped into 0 to W − 1. Rows use H and newH the same way. Compute it in exactly this order.
  • Blend the four surrounding source pixels bilinearly and round to the nearest whole number, with halves rounded up (add 0.5, then round down).
  • Print newH rows of newW values.

Input

Line 1: H, W, newH and newW. Then H rows of W values.

Output

newH rows.

Constraints

1 ≤ H, W, newH, newW ≤ 40.

Example

Input:

1 2 1 4
0 100

Output:

0 25 75 100

Why it works

Aligning pixel centres keeps the picture from shifting, clamping handles output pixels whose centres fall outside the source, and the bilinear blend gives each output a smooth mix of its four nearest source pixels.

Examples

Example 1 · Input
1 2 1 4
0 100
Expected output
0 25 75 100
Example 2 · Input
2 2 4 4
0 100
100 200
Expected output
0 25 75 100
25 50 100 125
75 100 150 175
100 125 175 200

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

Hints

Hint 1

Compute, for each output column, the source position `(d + 0.5) * W / newW - 0.5`, clamped into 0 to W − 1; do the same for rows.

Hint 2

From each position take the left index, the right index (at most W − 1) and the fraction between them; then blend as in bilinear sampling.

Solution

Show one correct solution (try it yourself first)
h, w, nh, nw = map(int, input().split())
img = [list(map(int, input().split())) for _ in range(h)]


def positions(n_out, n_in):
    out = []
    for d in range(n_out):
        s = min(max((d + 0.5) * n_in / n_out - 0.5, 0.0), n_in - 1.0)
        i = int(s)
        out.append((i, min(i + 1, n_in - 1), s - i))
    return out


xs = positions(nw, w)
for y0, y1, fy in positions(nh, h):
    top, bottom = img[y0], img[y1]
    row = []
    for a, b, f in xs:
        v = (top[a] * (1 - f) + top[b] * f) * (1 - fy) + (bottom[a] * (1 - f) + bottom[b] * f) * fy
        row.append(int(v + 0.5))
    print(" ".join(map(str, row)))

Lesson: Resizing and interpolation →