Fondazione Bruno Kessler - Technologies of Vision

contains material from
Template Matching Techniques in Computer Vision: Theory and Practice
Roberto Brunelli 2009 John Wiley & Sons, Ltd

3.2 The normalized correlation coefficient

The basic template matching algorithm described in Chapter 1 is (very) sensitive to some commonly encountered template variations. When taking a digital image of a scene with a digital camera, even if we constrain ourselves to a fixed focal length, position and orientation, we have some remaining degrees of freedom, such as exposure time and focusing distance. We briefly consider the former: if we increase the exposure time (and the scene is relatively static) the result will be a lighter image. More photons are captured by the sensor and the reported intensity value will be proportionally higher. Additionally, sometimes, in order to make better use of the dynamic range available for image representation, the actual intensity values are streteched to fill a larger interval. The resulting transformation is of the following type

x →  x′ = αx + β

These transformations can be easily simulated:

1 sampleimages <- file.path(system.file(package = "AnImAl"), "sampleimages/") 
2 face1        <- as.animage(getChannels(read.pnm( 
3 ...                 file.path(sampleimages, "sampleFace_01.pgm")))) 
4 # generate a low contrast version of the face 
5 lcFace       <- ia.add(ia.div(face1,4),0.25) 
6 lcEye        <- ia.get(lcFace, animask(26,87,58,36))

We can modify the basic template matching of the previous chapter computing instead the following similarity measure

              (                   )
           1    1 ∑                 1∕p
rLp = 1 ------  --    |A (iii) - B(iii)|p
         dmax   N  iii

where A, and B are two congruent patterns and dmax is the maximum possible distance between them. This is exactly what ia.correlation does when invoked with type = "Lp" and normalize = FALSE:

1 cpa <- ia.correlation(lcFace, lcEye, 
2 ...                  type = "Lp", p=2L, range = 1, normalize = FALSE)[[1]]@data 
3 # get the position of the most similar image region 
4 which(cpa == max(cpa), arr.ind = TRUE)

The low contrast eye template is correctly locate in the low contrast face (let us note that which acts on array whose indices start from 1 while image indices, in this case, start from 0). However, if we try to locate the eye in the normal contrast image we see that the returned positio is not correct:

1 cpb <- ia.correlation(face1, lcEye, type = "Lp", p = 2L, 
2 ...                  range = 1, normalize = FALSE)[[1]]@data 
3 which(cpb == max(cpb), arr.ind = TRUE)

The problem can be solved by normalizing each image window to zero average and unit standard deviation before comparing it to the similarly normalized template:

1 cpc <- ia.correlation(face1, lcEye, type = "Lp", p = 2L, 
2 ...                  range = 1, normalize = TRUE)[[1]]@data 
3 which(cpc == max(cpc), arr.ind = TRUE)

The normalization procedure let us spot the template correctly. The difference between the similarity measure obtained with the normalized/unnormalized Lp similarity measure can be appreciated by inspecting the contour plot of the corresponding maps:

1"figures/simContours", width=6, height=6) 
2   par(mfrow = c(2,2)) 
3   persp(cpb, main = "Not normalized") 
4   persp(cpc, main = "Normalized") 
5   contour(cpb) 
6   contour(cpc) 


Figure 3.2: When data are normally distributed the maximum achievable performance is determined by the separation of the classes relative to the standard deviation of the distribution σ0: the higher σ0, the closer to the upper left corner the curve.