10.1 Hierarchical matching

One of the simplest way to speed up the process of template matching is that of working at different image resolutions, starting from the lowest resolution at which the template can be discriminated, and progressively focusing the computation when increasing image resolution to the most promising candidates.

The basic structure needed to implement a hierarchical matching strategy is that of the resolution pyramid. We can build it starting from the highest available resolution, progressively smoothing and undersampling the current level to avoid aliasing artifacts.

The same procedure must be applied to the template.

In order to spot our template, we start from the lowest resolution level, generating a filter mask containing the most promising locations.

We then iterate the process of zooming the mask, slightly enlarging it, and computing the correlation value only at the corresponding image positions.

As the process relies on a thresholding operation in order to compute the mask constraining the computation, the distribution of the correlation values at the different levels of the pyramid should be considered. The figure reports the distribution of the correlation values (obtained without any filtering mask) at three levels. The plots clearly show that they differ, the distributions from the low resolution levels being suggestive of decreased discrimination capability of the correlation values. The threshold used in the computation of the mask should then be more strict at the first levels. However, as we want to be sure that we are not loosing any valid location and the number of computations is small, it is usually better not to use a (too) high threhsold.

Codelet 6 Hierachical template matching (../TeMa/R/tm.hierarchicalMatching.R)
____________________________________________________________________________________________________________

This function illustrates how we can achieve a significant speed up in correlation matching by using a multiresolution strategy: we

1tm.hierarchicalMatching <- function(I, T, levels = 3, thr = 90) {

We keep track of the original position of the image region of interest:

2  ofocus  <- I@focus

and consider it (temporarily) as our new coordinate origin

3  I@focus <- c(0L, 0L) 
4  T@focus <- c(0L, 0L)

The first step is to build the multiresolution representations of the image and of the template by carefully smoothing them at each resolution step before subsampling them:

5  pyrI    <- tm.gaussianPyramid(I, levels) 
6  pyrT    <- tm.gaussianPyramid(T, levels)

The first element of the resolution list (the pyramid) is the one at the lowest resolution and we create the corresponding computation filter encompassing all pixels:

7  mask    <- as.animage(array(1, dim(pyrI[[1]]@data)))

When we map the mask to the next higher resolution level we want to slightly enlarge it to avoid missing the right template position. Mathematical morphology provides an easy way to implement the growing operation by means of a simple structuring element and using the ia.mmBitDilation function:

8  eltA <- animage(array(1L, c(3,3)), focus=c(-1L,-1L))

We start from the lowest resolution level,

9  for(l in 1:levels) {

performing correlation only an selected pixels

10    cor  <- ia.correlation(pyrI[[l]], pyrT[[l]], filter=mask)[[1]]

and compute the mask for the next (higher) resolution level:

11    mask <- ia.integerAnimage(ia.greater(cor, thr)) 
12    mask <- ia.realAnimage(ia.pzoom(ia.mmBitDilation(mask, eltA), 2L, 2L)) 
13  }

finally returning the correlation map, at the correct position in the original coordinate system:

14  cor@focus <- ofocus 
15}

______________________________________________________________________________________

The following code shows a sample application