Computer vision: Find a template by SSD

The simplest way to find a known pattern is to try every position and measure the difference.

What to build

A program that computes the sum-of-squared-differences map and the best match.

Requirements

  • The score at (r, c) is the sum over the template of (img[r + i][c + j] − t[i][j])².
  • Print the score map, one line per row of positions, then best at row R, column C for the smallest score (first in reading order on ties).

Input

Line 1: H and W. Then H rows. Then h and w. Then h template rows.

Output

The score rows and the best line.

Constraints

1 ≤ h ≤ H ≤ 40; 1 ≤ w ≤ W ≤ 40.

Example

Input:

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

Output:

64 36
4 0
best at row 1, column 1

Why it works

Squared differences are 0 only where window and template agree exactly, so the smallest score marks the position that differs least from the template.

Examples

Example 1 · Input
3 3
1 2 3
4 5 6
7 8 9
2 2
5 6
8 9
Expected output
64 36
4 0
best at row 1, column 1
Example 2 · Input
2 4
0 9 0 9
9 0 9 0
1 2
9 0
Expected output
162 0 162
0 162 0
best at row 0, column 1

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

Hints

Hint 1

The template fits at (H − h + 1) × (W − w + 1) top-left positions.

Hint 2

Keep the first position with the smallest score when scanning row by row.

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)]
th, tw = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(th)]
best = None
for r in range(h - th + 1):
    row = []
    for c in range(w - tw + 1):
        s = sum((img[r + i][c + j] - t[i][j]) ** 2 for i in range(th) for j in range(tw))
        row.append(s)
        if best is None or s < best[0]:
            best = (s, r, c)
    print(" ".join(map(str, row)))
print(f"best at row {best[1]}, column {best[2]}")

Lesson: Template matching and corner features →