Graph Mathcing using Discrete Tabu Search on the Penalized Association Graph

Abstract

Graph matching is a fundamental problem in computer vision. In this paper, we propose a novel graph matching algorithm based on tabu search. The proposed method solves graph matching problem by casting it into an equivalent weighted maximum clique problem of the corresponding penalized association graph, and then uses tabu search technique for the optimization. The distinct feature of tabu search optimization is that it utilizes the history of search to make more strategic decisions while looking for the optimal solution, thus effectively escaping local optima and in practice achieving superior results. The proposed method, unlike the existing algorithms, enables direct optimization in the original discrete space while encouraging rather than artificially enforcing hard one-to-one constraint, thus resulting in better solution. The experiments demonstrate the robustness of the algorithm in a variety of settings, presenting the state-of-the-art results.