OATM: Occlusion Aware Template Matching by Consensus Set Maximization
This addresses the challenge of efficient and robust template matching in computer vision, particularly for applications like object detection under occlusion, with incremental advancements in handling occlusions and scalability.
The paper tackles the problem of template matching with partial occlusions by proposing OATM, which achieves a quadratic improvement in search complexity and demonstrates significant improvements in speed and robustness to occlusions over state-of-the-art methods.
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 $\sqrt{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.