Zero-Assignment Constraint for Graph Matching With Outliers

Graph matching (GM), as a longstanding problem in computer vision and pattern recognition, still suffers from numerous cluttered outliers in practical applications. To address this issue, we present the zero-assignment constraint (ZAC) for approaching the graph matching problem in the presence of outliers. The underlying idea is to suppress the matchings of outliers by assigning zero-valued vectors to the potential outliers in the obtained optimal correspondence matrix. We provide elaborate theoretical analysis to the problem, i.e., GM with ZAC, and figure out that the GM problem with and without outliers are intrinsically different, which enables us to put forward a sufficient condition to construct valid and reasonable objective function. Consequently, we design an efficient outlier-robust algorithm to significantly reduce the incorrect or redundant matchings caused by numerous outliers. Extensive experiments demonstrate that our method can achieve the state-of-the-art performance in terms of accuracy and efficiency, especially in the presence of numerous outliers.

1. Introduction

In many real applications of computer vision and pattern recognition, the feature sets of interest represented as graphs are usually cluttered with numerous outliers [3], [42], [38], [30], which often reduce the accuracy of GM. Although recent works on GM [7], [11], [21], [22], [34], [44] can achieve satisfactory results for simple graphs that consist of only inliers or a few outliers, they still lack of ability to tolerate numerous outliers arising in complicated graphs. Empirically, the inliers in one graph are nodes that have highly-similar corresponding nodes in the other graph, while the outliers do not. Based on the empirical criterion, the aforementioned methods hope to match inliers to inliers correctly and force outliers to only match outliers. However, due to the complicated mutual relationships between inliers and outliers, they usually result in incorrect matchings between inliers or redundant matchings between outliers (e.g., Fig. 1(a)). Figure 1:

ZAC for graph matching in the presence of outliers. To suppress the undesired matchings of outliers in (a), We aim to assign the potential outliers with zero-valued vectors in our optimal correspondence matrix in (b), Based on which we can both establish a theoretical foundation for graph matching with outliers and put forward an outlier identification approach that can significantly reduce incorrect or redundant matches caused by outliers in practice.