Computer vision: Match with normalised cross-correlation

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 S for 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

Example 1 · Input
2 4
10 10 50 90
10 10 50 90
1 3
0 4 8
Expected output
0.866 1.000
0.866 1.000
best at row 0, column 1, score 1.000
Example 2 · Input
1 5
5 5 9 5 1
1 2
1 0
Expected output
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}")

Lesson: Template matching and corner features →