When lighting changes, SSD fails. Normalised cross-correlation still finds the pattern.
What to build
A program that computes the zero-mean normalised cross-correlation map and the best match.
Requirements
- For each position, compute the NCC between the window and the template as in the hints; if the window or the template has no variation, the score is 0.
- Print the map with three decimal places (round, then add 0.0 so -0.000 never appears).
- Then print
best at row R, column C, score Sfor the largest score, the 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 ≤ 30; 1 ≤ w ≤ W ≤ 30.
Example
Input:
2 4
10 10 50 90
10 10 50 90
1 3
0 4 8
Output:
0.866 1.000
0.866 1.000
best at row 0, column 1, score 1.000
Why it works
Subtracting the means removes brightness differences and dividing by the spreads removes contrast differences, so only the shape of the pattern decides the score.
Examples
2 4 10 10 50 90 10 10 50 90 1 3 0 4 8
0.866 1.000 0.866 1.000 best at row 0, column 1, score 1.000
1 5 5 5 9 5 1 1 2 1 0
0.000 -1.000 1.000 1.000 best at row 0, column 2, score 1.000
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Subtract the template's mean from its values once; for each window, subtract the window's mean from its values.
Hint 2
The score is Σ(window deviation × template deviation) / √(Σ window deviation² × Σ template deviation²), or 0 if either sum of squares is 0.
Solution
Show one correct solution (try it yourself first)
import math
h, w = map(int, input().split())
img = [list(map(int, input().split())) for _ in range(h)]
th, tw = map(int, input().split())
t = [v for _ in range(th) for v in map(int, input().split())]
tm = sum(t) / len(t)
td = [v - tm for v in t]
tvar = sum(v * v for v in td)
best = None
for r in range(h - th + 1):
row = []
for c in range(w - tw + 1):
win = [img[r + i][c + j] for i in range(th) for j in range(tw)]
m = sum(win) / len(win)
wd = [v - m for v in win]
wvar = sum(v * v for v in wd)
s = 0.0 if wvar == 0 or tvar == 0 else sum(a * b for a, b in zip(wd, td)) / math.sqrt(wvar * tvar)
row.append(s)
if best is None or s > best[0]:
best = (s, r, c)
print(" ".join(f"{round(v, 3) + 0.0:.3f}" for v in row))
print(f"best at row {best[1]}, column {best[2]}, score {round(best[0], 3) + 0.0:.3f}")