Progressively Decomposing Graph Matching

Abstract

Existing approaches to graph matching mainly include two types, i.e., the Koopmans-Beckmann's QAP formulation (KB-QAP) and Lawler's QAP formulation (L-QAP). The former is advantageous in scalability but disadvantageous in generality, while the latter is exactly the opposite. In this paper, we present a novel graph matching method, called progressively decomposing graph matching (PDGM), which can simultaneously possess the merits of the scalability of KB-QAP and the generality of L-QAP. Our method is motivated by a key observation that, the matching accuracy of KB-QAP can be dramatically boosted by properly introducing a guidance term into the formulation. Based on this observation, the proposed PDGM method progressively incorporates edge affinity information into the optimization procedure of KB-QAP through a guidance term, which mainly involves two iterative steps, i.e., solving the guided KB-QAP and updating the guidance matrix. The extensive experiments on both synthetic data and real image datasets demonstrate that our method can outperform the state-of-the-art in terms of the robustness to noise/deformation and outliers, and the good balance between effectiveness and computational efficiency.

Keywords

• Graph matching
• quadratic assignment problem
• progressively decomposing graph matching
• Frank-Wolfe algorithm