Demo Template Matching

In this lesson we show the template matching method to localize a given pattern in a image. We also demonstrate that implementing is invariant to translation and scale variations.

1. Image input and template extraction

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

1. from ia636 import *
2. 
3. f = iaread('cameraman.pgm')
4. f = asarray(f).astype(float)
5. adshow(f, title='Original Image')
6. w = f[25:25+17,106:106+17]
7. adshow(w, title='Template')

Original Image

Template

2. Image Correlation

Direct image correlation is not a efficient procedure as gray levels and iluminations issues contain strong variations. Thus, 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.

01. from ia636 import *
02. 
03. # periodic correlation
04. g = iapconv(f, w[::-1,::-1])
05. adshow(ianormalize(g,[0,255]), title='Correlation with inverted w')
06. 
07. i = ones(w.shape)
08. fm2 = iapconv(f*f, i)
09. g2 = g/sqrt(fm2)
10. adshow(ianormalize(g2,[0,255]), title='Correlation using normalized variance')
11. v, pos = max(ravel(g2)), argmax(ravel(g2))
12. 
13. (row, col) = iaind2sub(g2.shape, pos)
14. print 'found best match at (%3.0f,%3.0f)\n' %(row,col)
found best match at ( 33,114)

Correlation with inverted w

Correlation using normalized variance

3. Image correlation without using normalization

01. from ia636 import *
02. 
03. # periodic correlation
04. g = iapconv(f, w[::-1,::-1])
05. adshow(ianormalize(g,[0,255]), title='Correlation with inverted w')
06. 
07. i = ones(w.shape)
08. fm2 = iapconv(f*f, i)
09. g2 = g
10. #g2 = g/sqrt(fm2)
11. adshow(ianormalize(g2,[0,255]), title='Correlation using normalized variance')
12. v, pos = max(ravel(g2)), argmax(ravel(g2))
13. 
14. (row, col) = iaind2sub(g2.shape, pos)
15. print 'found best match at (%3.0f,%3.0f)\n' %(row,col)
found best match at (160,218)

Correlation with inverted w

Correlation using normalized variance

4. Correlation indice

A method improvement can be achieved by subtracting the image by it´s mean

01. from numpy import *
02. n = prod(w.shape)
03. wm = mean(ravel(w))
04. fm = 1.*iapconv(f,i)/n
05. num = g - (fm*wm*n)
06. adshow(ianormalize(num), title='numerador')
07. den = sqrt(fm2 - (n*fm*fm))
08. adshow(ianormalize(den), title='denominador')
09. cn = 1.*num/den
10. adshow(ianormalize(cn), title='cn')
11. v, pos = max(ravel(cn)), argmax(ravel(cn))
12. (row, col) = iaind2sub(g2.shape, pos)
13. print 'found best match at (%3.0f,%3.0f)\n' %(row,col)
found best match at ( 33,114)

numerador

denominador

cn

4.1. Correlation indice - scale invariance

01. from numpy import *
02. f = f*1.2
03. fm2 = iapconv(f*f, i)
04. adshow(ianormalize(f), title='Original Image')
05. n = prod(w.shape)
06. wm = mean(ravel(w))
07. i = ones(w.shape)
08. fm = 1.*iapconv(f,i)/n
09. g = iapconv(f, w[::-1,::-1])
10. num = g - (fm*wm*n)
11. adshow(ianormalize(num), title='numerador')
12. den = sqrt(fm2 - (n*fm*fm))
13. adshow(ianormalize(den), title='denominador')
14. cn = 1.*num/den
15. adshow(ianormalize(cn), title='cn')
16. v, pos = max(ravel(cn)), argmax(ravel(cn))
17. (row, col) = iaind2sub(g2.shape, pos)
18. print 'found best match at (%3.0f,%3.0f)\n' %(row,col)
found best match at ( 33,114)

Original Image

numerador

denominador

cn

4.2. Correlation indice - translation invariance

01. from numpy import *
02. f = iaread('cameraman.pgm')
03. f = asarray(f).astype(float)
04. f = iageorigid(f, [1,1], 0, [20,20])
05. fm2 = iapconv(f*f, i)
06. adshow(ianormalize(f), title='Original Image')
07. n = prod(w.shape)
08. wm = mean(ravel(w))
09. i = ones(w.shape)
10. fm = 1.*iapconv(f,i)/n
11. g = iapconv(f, w[::-1,::-1])
12. num = g - (fm*wm*n)
13. adshow(ianormalize(num), title='numerador')
14. den = sqrt(fm2 - (n*fm*fm))
15. adshow(ianormalize(den), title='denominador')
16. #adshow(den==0, title='denominador == 0')
17. den = where(den == 0, 1, den)
18. cn = 1.*num/den
19. adshow(ianormalize(cn), title='cn')
20. v, pos = max(ravel(cn)), argmax(ravel(cn))
21. (row, col) = iaind2sub(g2.shape, pos)
22. print 'found best match at (%3.0f,%3.0f)\n' %(row,col)
23. adshow(f[row-8:row+8,col-8:col+8])
found best match at ( 53,134)

Original Image

numerador

denominador

cn

Contributions

  • Mariana Pinheiro Bento, 1st semester 2011.
  • Fernando Paolieri Neto, 1st semester 2010.