Abstract
We present a novel approach to template matching that
is efficient, can handle partial occlusions, and comes with
provable performance guarantees. A key component of
the method is a reduction that transforms the problem of
searching a nearest neighbor among N high-dimensional
vectors, to searching neighbors among two sets of order
?N vectors, which can be found efficiently using range
search techniques. This allows for a quadratic improvement in search complexity, and makes the method scalable
in handling large search spaces. The second contribution
is a hashing scheme based on consensus set maximization, which allows us to handle occlusions. The resulting
scheme can be seen as a randomized hypothesize-and-test
algorithm, which is equipped with guarantees regarding the
number of iterations required for obtaining an optimal solution with high probability. The predicted matching rates
are validated empirically and the algorithm shows a significant improvement over the state-of-the-art in both speed
and robustness to occlusions