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

11.1 Hausdorff matching

Binary image templates can be considered as a set of points and their similarity assessed by means of an appropriate point set distance, the Hausdorff distance or its variation, the directed Hausdorff distance. The latter can be computed efficiently using the Euclidean distance transform, a transform that associates to each background image pixel its distance from the closest foreground image pixel. Once the distance transform has been computed, computation of the directed Hausdorff distance can be accomplished by looking at the distance transform value at the pixels representative of the point set.

The resulting set of distance values can be used to compute several variations of the basic definition by taking the maximum, the average, or any specified quantile, improving the robustness of the matching score.

We illustrate it using one of the available sample images and adding noise to it:

1 sampleimages <- file.path(system.file(package="TeMa"), 
2 ...                               "sampleimages") 
3 face         <- ia.get(ia.scale(as.animage(getChannels(read.pnm( 
4 ...                   file.path(sampleimages, "sampleFace_01.pgm")))), 
5 ...                   255), animask(10,60,90,90)) 
6 face@outside <- 255 
7 nface        <- tm.addNoise(face, scale = 1.0, clipRange = c(0,255)) 
8 eface        <- tm.edgeDetection(nface,2, alpha=0.01, onlyFirstThr = FALSE)

As template, we get the eye of the image without noise:

1 eye          <- ia.get(face, animask(32,92,50,30)) 
2 eeye         <- tm.edgeDetection(eye,2, alpha=0.01, onlyFirstThr = FALSE)

and compute several variations of the partial Hausdorff distance

1 h1 <- tm.hausdorffMatching(eface, eeye, distance="max") 
2 h2 <- tm.hausdorffMatching(eface, eeye, distance="average") 
3 h3 <- tm.hausdorffMatching(eface, eeye, distance="rank", q=0.7) 
4 h4 <- tm.hausdorffMatching(eface, eeye, distance="rank", q=0.95)

reporting the results in Figure 11.1.

1   tm.dev("figures/hausdorffMatching", width=6, height=6) 
2   par(mfrow = c(2,2)) 
3   ia.show(h1, main = "Max") 
4   ia.show(h2, main = "Average") 
5   ia.show(h3, main = "Rank (0.7)") 
6   ia.show(h4, main = "Rank (0.9)") 
7   dev.off()


PIC

Figure 11.1: The Hausdorff partial distance is a flexible technique to compare templates represented by sets of points. The template would be located at the darkest point, the one with the lowest distance. The figures shows that using the max version may not be always the best choice.