Lagrangian relaxation graph matching

•We present a graph matching method based on Lagrangian relaxation model.•Our model incorporates affine mapping and discrete constraints simultaneously.•Experimental results show the effectiveness of our matching method.

Graph matching is a fundamental problem in computer vision area. Graph matching problem that incorporates pair-wise constraints can be formulated as an integer quadratic programming (IQP) problem with affine mapping constraint. Since it is known to be NP-hard, approximate relaxation methods are usually required to find approximate solutions. In this paper, we present a new effective graph matching relaxation method, called Lagrangian relaxation graph matching (LRGM), which aims to generate a relaxation model by incorporating the affine mapping constraint into the matching objective optimization. There are three main benefits of the proposed LRGM method: (1) The nonnegative affine mapping constraint encoding one-to-one mapping is naturally incorporated in LRGM relaxation via Lagrangian regularization. (2) By further adding a ℓ1-norm constraint, LRGM can generate a sparse solution empirically and thus returns a desired discrete solution for original IQP matching problem. (3) An effective update algorithm is derived to solve the proposed LRGM model. Theoretically, the converged solution can be proven to be Karush–Kuhn–Tucker (KKT) optimal. Experimental results on both synthetic data and real-world image datasets show the effectiveness and benefits of the proposed LRGM method.