Towards Discrete Solution: A Sparse Preserving Method for Correspondence Problem
This addresses the challenge of incorporating discrete constraints in matching problems for computer vision applications, but it appears incremental as it builds on existing relaxation models.
The paper tackles the NP-hard feature correspondence problem in computer vision by proposing a new relaxation model called Sparse Constraint Preserving Matching (SPM), which encodes discrete permutation constraints via sparsity, and experimental results show it is effective and efficient.
Many problems of interest in computer vision can be formulated as a problem of finding consistent correspondences between two feature sets. Feature correspondence (matching) problem with one-to-one mapping constraint is usually formulated as an Integral Quadratic Programming (IQP) problem with permutation (or orthogonal) constraint. Since it is NP-hard, relaxation models are required. One main challenge for optimizing IQP matching problem is how to incorporate the discrete one-to-one mapping (permutation) constraint in its quadratic objective optimization. In this paper, we present a new relaxation model, called Sparse Constraint Preserving Matching (SPM), for IQP matching problem. SPM is motivated by our observation that the discrete permutation constraint can be well encoded via a sparse constraint. Comparing with traditional relaxation models, SPM can incorporate the discrete one-to-one mapping constraint straightly via a sparse constraint and thus provides a tighter relaxation for original IQP matching problem. A simple yet effective update algorithm has been derived to solve the proposed SPM model. Experimental results on several feature matching tasks demonstrate the effectiveness and efficiency of SPM method.