Fast exact feature based data correspondence search with an efficient bit-parallel MCP solver

摘要

The problem of finding the optimal correspondence between two sets of geometric entities or features is known to be NP-hard in the worst case. This problem appears in many real scenarios such as fingerprint comparisons, image matching and global localization of mobile robots. The inherent complexity of the problem can be avoided by suboptimal solutions, but these could fail with high noise or corrupted data. The correspondence problem has an interesting equivalent formulation in finding a maximum clique in an association graph. We have developed a novel algorithm to solve the correspondence problem between two sets of features based on an efficient solution to the Maximum Clique Problem using bit parallelism. It outperforms an equivalent non bit parallel algorithm in a number of experiments with simulated and real data from two different correspondence problems. This article validates for the first time, to the best of our knowledge, that bit parallel optimization techniques can greatly reduce computational cost, thus making feasible the use of an exact solution in real correspondence search problems despite their inherent NP computational complexity.