Demo Template Matching using Normalized Cross Correlation

In this lesson we show the template matching method to localize a given pattern in a image. We use the NCC - Normalized Cross-Correlation.

1. Image input and template extraction

This code reads a gray scale image and extracts a piece as template.

 1 import numpy as np
 2 import ia636 as ia
 3 
 4 f = iaread('cameraman.pgm')
 5 f = np.asarray(f).astype(float)
 6 adshow(f, title='f: Original Image')
 7 (r0,c0) = 25,106
 8 N = 17
 9 t = f[r0:r0+N,c0:c0+N]
10 adshow(t, title='t: Template')

f: Original Image

t: Template

2. Direct Image Cross Correlation

Direct image correlation is not a efficient procedure as gray levels and illuminations issues contain strong variations.

1 c = ia.iapconv2(f, t[::-1,::-1])
2 adshow(ia.ianormalize(c,[0,255]), title='Cross Correlation')
3 (row,col) = np.unravel_index(np.argmax(c),c.shape) - np.array([N-1,N-1])
4 print 'found best match at (%3.0f,%3.0f)\n' %(row,col)
found best match at (152,210)

Cross Correlation

3. NCC - Normalized Cross Correlation

It is necessary to subtract the image from it´s mean in order to make all regions(light or dark) receive the same importance value. The normalization factor can be used to improve the model detection.

If our concert in only to find the maximum response of , the above equation can be simplified in:

where is the template subtracted from its mean.

The denominator can be further simplified:

Using periodic convolution, the above equation can result in:

 1 n = t.size
 2 t1 = t[::-1,::-1] - t.mean()
 3 num = ia.iapconv2(f,t1)
 4 adshow(ia.ianormalize(num), title='numerator')
 5 i = np.ones(t.shape)
 6 fm2 = ia.iapconv2(f*f, i)
 7 fm  = ia.iapconv2(f,i)
 8 den = np.sqrt(fm2 - fm*fm/n)
 9 adshow(ia.ianormalize(den), title='denominator')
10 gamma1 = num/den
11 adshow(ia.ianormalize(gamma1), title='gamma1')
12 (row,col) = np.unravel_index(np.argmax(gamma1),gamma1.shape) - np.array([N-1,N-1])
13 print 'found best match at (%3.0f,%3.0f)\n' %(row,col)
found best match at ( 25,106)

numerator

denominator

gamma1