Globally consistent correspondence of multiple feature sets using proximal Gauss-Seidel relaxation

Feature correspondence between two or more images is a fundamental problem towards many computer vision applications. The case of correspondence between two images has been intensively studied, however, few works so far have been concerned with multi-image correspondence. In this paper, we address the problem of establishing a globally consistent correspondence among multiple (more than two) feature sets given the pairwise feature affinity information. Our main contribution is to propose a novel optimization framework for solving this problem based on the so-called Proximal Gauss-Seidel Relaxation (PGSR). The proposed method is distinguished from previous works mainly in three aspects: (1) it is more robust to noise and outliers; (2) its solution is based on convex relaxation and the principled PGSR method, which in general has convergence guarantee; (3) the scale of the problem in our method is linear with respect to the number of feature sets, making it computationally practical to be used in real-world applications. Experimental results both synthetic and real image datasets have demonstrated the effectiveness and superiority of the proposed method.