Discrete Tabu Search for Graph Matching

Kamil Adamczewski, Yumin Suh, Kyoung Mu Lee; Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2015, pp. 109-117

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 association graph, which we further penalize through introducing negative weights. Subsequent tabu search optimization allows for overcoming the convention of using positive weights. The method's distinct feature 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. The code is available at http://cv.snu.ac.kr/research/ DTSGM/