Nonparametric hierarchical Hausdorff distance matching algorithm

A Hausdorff distance (HD), which is defined between two point sets in two-dimensional (2-D) binary images and does not require us to establish correspondences, is one of common measures used for object matching. The proposed hierarchical HD (HHD) matching algorithm, based on coarse-to-fine matching, reduces the computational complexity greatly by using the pyramidal structures that consist of a distance transform (DT) map pyramid and an edge pyramid. In the proposed HHD matching, an automatic thresholding method is presented to select candidate positions at each level, in which the threshold Value is determined based on the property between adjacent levels of a DT map pyramid. Computer simulation with real images and noisy images shows that the proposed HHD algorithm yields matching results similar to those achieved by the conventional HD algorithm with greatly reduced computational complexity. (C) 2000 Society of Photo-Optical Instrumentation Engineers. [S0091-3286(00)02107-3].