Fast similarity metric for real-time template-matching applications

In this study, a visual similarity metric based on precision-recall graphs is presented as an alternative to the widely used Hausdorff distance (HD). Such metric, called maximum cardinality similarity metric, is computed between a reference shape and a test template, each one represented by a set of edge points. We address this problem using a bipartite graph representation of the relationship between the sets. The matching problem is solved using the Hopcroft-Karp algorithm, taking advantage of its low computational complexity. We present a comparison between our results and those obtained from applying the partial Hausdorff distance (PHD) to the same test sets. Similar results were found using both approaches for standard template-matching applications. Nevertheless, the proposed methodology is more accurate at determining the completeness of partial shapes under noise conditions. Furthermore, the processing time required by our methodology is lower than that required to compute the PHD, for a large set of points.