NCC Template Matching

Problem

Slide a template over an image and find the valid position with the highest normalized cross-correlation.

For each valid top-left position, subtract the patch and template means and compute the correlation coefficient. Return [row, col, score] with the score rounded to 4 decimals; constant patches score 0.0 and ties keep the first position in row-major order.

Hint

A constant patch has zero variance, so its correlation is defined as 0.0.

Test cases

case 1

in: [[[0,0,0],[0,1,2],[0,3,4]],[[1,2],[3,4]]]

expected: [1,1,1]

case 2

in: [[[0,0,0],[0,1,2],[0,3,4]],[[0,0],[0,1]]]

expected: [0,0,1]

case 3

in: [[[1,2,3],[4,5,6],[7,8,9]],[[5,5],[5,5]]]

expected: [0,0,0]

case 4

in: [[[0,1,0],[1,0,1],[0,1,0]],[[1,0],[0,1]]]

expected: [0,1,1]

Starter codePython

def ncc_template_match(image, template):
    # Your code here
    pass

4 test cases · run your code against them in the editor