Consistency Driven Optimization for Multigraph Matching

The problem of graph matching (GM) in general is nondeterministic polynomial-complete and many approximate pairwise matching techniques have been proposed. For a general setting in real applications, it typically requires to find the consistent matching across a batch of graphs. Sequentially performing pairwise matching is prone to error propagation along the pairwise matching sequence, and the sequences generated in different pairwise matching orders can lead to contradictory solutions. Motivated by devising a robust and consistent multiple-GM model, we propose a unified alternating optimization framework for multi-GM. In addition, we define and use two metrics related to graphwise and pairwise consistencies.

The former is used to find an appropriate reference graph, which induces a set of basis variables and launches the iteration procedure. The latter defines the order in which the considered graphs in the iterations are manipulated. We show two embodiments under the proposed framework that can cope with the nonfactorized and factorized affinity matrix, respectively. Our multi-GM model has two major characters: 1) the affinity information across multiple graphs are explored in each iteration by fixing part of the matching variables via a consistency-driven mechanism and 2) the framework is flexible to incorporate various existing pairwise GM solvers in an out-of-box fashion, and also can proceed with the output of other multi-GM methods. The experimental results on both synthetic data and real images empirically show that the proposed framework performs competitively with the state-of-the-art.