Computer vision: Warp an image by backward mapping

Rotating or zooming an image by moving pixels forward leaves holes. Map every output pixel backwards instead.

What to build

A program that warps an image with an affine matrix, using backward mapping and nearest-neighbour sampling.

Requirements

  • The matrix maps input positions to output positions: x' = a x + b y + tx, y' = c x + d y + ty, with x the column and y the row. Its determinant is not 0.
  • The output has the same size as the input. For each output pixel (x, y), apply the inverse matrix to get the source position, round each coordinate to the nearest whole number (halves up), and copy that pixel; if it lies outside the image, write 0.
  • Print H rows of W values.

Input

Line 1: H and W. Then H rows of W values. Then two lines: a b tx and c d ty.

Output

H rows.

Constraints

1 ≤ H, W ≤ 40.

Example

Input:

2 3
1 2 3
4 5 6
1 0 1
0 1 0

Output:

0 1 2
0 4 5

Why it works

Because every output pixel asks the inverse transform where it comes from, each one receives exactly one value, and pixels whose source is outside the image are filled with 0.

Examples

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

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

Hints

Hint 1

Invert the matrix: with det = a d − b c, the inverse's 2 × 2 part is [[d, −b], [−c, a]] / det and its shift is −(that part) × (tx, ty).

Hint 2

Round a source position with `math.floor(v + 0.5)`; positions outside the image give 0.

Solution

Show one correct solution (try it yourself first)
import math

h, w = map(int, input().split())
img = [input().split() for _ in range(h)]
a, b, tx = map(float, input().split())
c, d, ty = map(float, input().split())
det = a * d - b * c
ia, ib, ic, id_ = d / det, -b / det, -c / det, a / det
itx, ity = -(ia * tx + ib * ty), -(ic * tx + id_ * ty)
for y in range(h):
    row = []
    for x in range(w):
        sx = math.floor(ia * x + ib * y + itx + 0.5)
        sy = math.floor(ic * x + id_ * y + ity + 0.5)
        row.append(img[sy][sx] if 0 <= sx < w and 0 <= sy < h else "0")
    print(" ".join(row))

Lesson: Affine transforms: shift, scale, rotate and warp →