A spectral technique for correspondence problems using pairwise constraints

TLDR

Correct correspondences tend to form strongly connected clusters, whereas incorrect ones rarely do. The paper proposes an efficient spectral method to find consistent correspondences between two feature sets. The method constructs an adjacency matrix of potential correspondences weighted by pairwise agreements, then extracts the principal eigenvector to identify the main cluster and imposes mapping constraints to recover the correct assignments. Experiments demonstrate that the method is robust to outliers, achieves high matching accuracy, and runs significantly faster than existing approaches.

Abstract

We present an efficient spectral method for finding consistent correspondences between two sets of features. We build the adjacency matrix M of a graph whose nodes represent the potential correspondences and the weights on the links represent pairwise agreements between potential correspondences. Correct assignments are likely to establish links among each other and thus form a strongly connected cluster. Incorrect correspondences establish links with the other correspondences only accidentally, so they are unlikely to belong to strongly connected clusters. We recover the correct assignments based on how strongly they belong to the main cluster of M, by using the principal eigenvector of M and imposing the mapping constraints required by the overall correspondence mapping (one-to-one or one-to-many). The experimental evaluation shows that our method is robust to outliers, accurate in terms of matching rate, while being much faster than existing methods