Image Correspondence with CUR Decomposition-Based Graph Completion and Matching

Establishing correspondence between pictorial descriptions of two images is an important task and can be treated as graph matching problem. However, the process of extracting a favourable graph structure from raw images for matching is influenced by cluttered backgrounds and deformations, which may result in the abundance of noisy graph structures. This paper addresses the problem of point set correspondence and presents a robust graph matching method which recovers the correspondence matches among the graph nodes in a CUR based factorization framework. The graph representation in terms of CUR, inherently preserves the actual nodes connection in sparse manner, this particularly renders the complex space-time realization of affinities among graph nodes. The reformulation of graph matching in terms of small CUR factorization matrices, allows to compute and relax the partially observed graphs, without observing the whole large-scale graph matrix. In particular, we propose two variants of this approach, first, approximating the matching matrix from small CUR observed graph structure, and second, completing the graph structure with higher order CUR form to find correspondence. The CUR based matching algorithms are realized by computing set of compatibility coefficients from pairwise matching graphs and further conducting the probability relaxation procedure to find the matching confidences among nodes. Experiments and analysis on synthetic and natural images dataset prove the effectiveness of proposed methods against state-of-the-art methods. We also explore CUR matching for non-rigid moving object in a video sequence to demonstrate the potential application of graph matching to video analysis.