Algorithmic Studies And Design On Graph Matching

This thesis deals with one of the fundamental problems for multimedia and computer vision– graph matching. Graph matching is aimed to automatically establish the node correspondence between two or across multiple graphs. This topic is widely studied and applied in different areas including image processing, multimedia, computer vision, pattern recognition, graphics and bioinformatics. This paper focuses on the two important aspects of graph matching: two-graph matching and multi-graph matching/registration. The contribution are as follows.First, for the proposed baseline i.e. linearized iterative gradient assignment method for twograph matching, the author analyzes its convergence behavior from two perspectives: solution domain and affinity order. Given an arbitrary second-order affinity matrix, this thesis proves the baseline method will trap into a double circulating sequence. This conclusion is generalized to the continuous domain. The theory gives rise to an adaptive relaxation mechanism, and an effective convergent algorithm. We further show that the N-th order variant of the baseline that deals with the second-order problem, will fall into an N-circulating sequence. Then a new convergent algorithm is devised. Theoretical analysis and experimental results suggest the discrete methods are efficient and the continuous method can achieve higher matching accuracy.Second, the thesis proposes an alternating matching variable updating framework for multigraph matching. Under this framework, the sub-problem over iterations is transformed to a twograph matching problem. Meanwhile, this formulation can exhaustively incorporate two cases for the affinity matrix being non-factorized or factorized. Therefore, any two-graph matching solvers can be reused in an out-of-box fashion. Furthermore, a matching consistency metric is proposed to determine the reference graph for building the sub-problem, as well as the matching variable updating order. The empirical study shows that this mechanism notably improves the quality of the initial solution and speeds up the convergence rate. Moreover, the author tailors the alternating updating framework to the problem of multiple point set registration under parametric transformations, whereby a novel iterative method is proposed which achieves trade-off between efficiency and accuracy.Third, the thesis proposes a graduated consistency regularized affinity score boosting model.This method is based on two observations: i) via correspondence relation diffusion across the pairwise matching chain, both the overall matching accuracy and the matching affinity score can be improved in a self-boosting fashion; ii) due to the presence of noises and inherent difficulty in modeling the semantic accuracy by the parametric affinity function, the affinity score is less indicative to the semantic accuracy while the matching consistency becomes more relevant. For the first observation, the empirical finding further shows the first-order diffusion strategy is more cost-effective compared with the higher-order diffusion along the pairwise matching chain. Based on the second observation, the model is further improved by adding the matching consistency as a regularization term in a graduated manner. The author also provides the theoretical proof for the convergence of one of the proposed algorithms. Finally, an inlier node eliciting mechanism is devised to handle the presence of a majority of outlier nodes. Theoretical analysis and experimental results show the method is robust, especially as the number of graphs increases, it outperforms by accuracy.Last, the author devises a matrix recovery based graph matching method under the explicit representation of attributed graphs. On one hand, this method explores the underlying connection between graph matching and matrix recovery, and formulates the multi-graph matching to a matrix low-rank sparsity decomposition problem. This reformulation opens the door for the state-of-theart convex optimization algorithms. On the other hand, this model assumes the raw edge and node information of the attributed graphs are explicitly given, which is more restricted than knowing the similarity between nodes and edges as assumed in the other proposed methods. Meanwhile,a profile-personalized mutually-exciting point process model is proposed to uncover the attributes of graphs from the event data in real problems, in order to ensure the applicability of the proposed matching algorithm. Theoretical analysis and experimental results show our matrix recovery based matching method has a linear complexity w.r.t. the number of graphs, and performs competitively w.r.t. matching accuracy especially given a moderate number of graphs.In conclusion, this thesis is devoted to the problem of graph matching. For two-graph matching under arbitrary order, an adaptive relaxation mechanism is proposed together with a convergent algorithm. For multi-graph matching, three methods are proposed, exploring the different aspects of the problem respectively. Theoretical analysis and extensive experimental results show our methods well capture the nature of the problem, and improve the performance notably.