1 Pattern Matching Using the Hausdorff Distance

Abstract Point matching can be a computationally intensive task, especially when large point sets are involved and when the transformation space has many degree of freedom. Here, we employ two efficient algorithms to solve the problem, in an attempt to reduce its computational complexity, while providing acceptable result. The first method is an approximation algorithm based on branch-and-bound approach, it is possible to achieve a tradeoff between the quality of result and the running time. The second method operates within the framework of the first method but accelerate it by using point alignments. We demonstrate the algorithms ’ performances on synthetically generate data. Moreover, we apply them on finding facial feature points in images and show some preliminary results