Functional Representation For Graph Matching

Graph matching is a fundamental problem in computer vision,computer graphics,pattern recognition,etc,where graph is often used to represent non-raster data with structural information,such as key points in image,3D point cloud,social media data and so on.And then,graph matching is developed to establish the correct(or optimal)correspondence between graphs by finding and matching the same(or similar)elements between graph-structured datas.In addition,using the results of graph matching,the similarity of corresponding elements between graphs can be calculated,so as to describe the overall similarity measurement between graph-structured datas.Therefore,graph matching plays an important role in many tasks,such as image or shape matching,object retrieval and classification,3D reconstruction,action recognition,motion tracking,to name a few.In this dissertation,a functional representation framework of general graph matching is established based on functional analysis.And then,this paper further develops both compatible theoretical analysis and efficient methods for geometric constrained graph matching and outlier-disturbed graph matching.The main achievements of this paper are as follows:1)A functional representation framework of general graph matching is established,which provides a unified basic theory for modeling representation,theoretical analysis and algorithm construction of graph matching.Firstly,the linear function space on graph is defined mathematically,whose basis functions are used to represent the vertex,edge and other information of the graph model.And the inner product,metric and other structures can be defined as measurements or constraints of graph matching.Then,the matching between graphs is equally represented as a linear transformation between the function spaces via the push-forward operation.Finally,the linear transformation under structural constraints is obtained by optimizing the objective function to preserve the structure of graphs,which results in the state-of-the-art graphs matching performance.The proposed functional representation framework not only provides theoretical basis and analysis guidelines for general graph matching problem,but also enlightens how to analyze and solve the geometric constrained graph matching and outlier-disturbed graph matching problems.2)A linear parametric representation of geometric constrained graph matching in Euclidean space is proposed to keep compatible with the original geometric(rigid or non-rigid)deformation parameters between graphs.According to the natural linear property of Euclidean space,based on the linear functional representation of graph matching,the matching matrix in the geometric constrained graph matching problem can be reduced to a linear geometric transformation between graphs,which defines a new linear parameterization with geometric meaning.Due to the associative law of matrix multiplication,it can be proved that this new parameterization and the origianl geometric deformation parameters can be expressed as two alternating linear operators,which provides a reasonable alternative estimation method for geometric deformation parameters and graph matching matrix.Moreover,in order to reduce the computational complexity in the process of alternating estimation,an entropy regularization-based fast approximation of Frank-Wolfe method is proposed with some properties(e.g.,the sub-linear convergence rate)proved,which improves the computational efficiency and robustness of the proposed method.3)A zero-assignment constraint and an outlier identification and removal approach for graph matching are developed to deal with numerous cluttered outliers arising in practical applications.Inspired by the null space of linear transformation in function space,outliers are regarded as vertices that can be mapped into null space,while inliers keep structural information unchanged during matching.Based on the property that the vertices mapped to the null space by the graph matching matrix have zero coefficient vector(i.e.,the zero-assignment constraint of outlier),the outliers and inliers are clustered into two classes,and then the outliers are identified and revomed.Due to the less similarity between outliers and other vertices,a discriminative objective function is designed to force the outliers to be given(nearly)zero coefficient vectors in the optimization process.After removing the identified outliers,the optimal correspondence between inliers of graphs are obtained.The experimental results show that the proposed method can greatly improve the accuracy of graph matching results by keeping inliers well and reducing the influence of outliers.In summary,this dissertation establishes a functional representation framework of graph matching,based on which the theoretical analysis and algorithm design are carried out for the three important problems of general graph matching,geometric constrained graph matching and outlier-disturbed graph matching.A large number of analytical and comparison experiments show that the proposed methods have strong robustness and efficiency,and have achieved the state-of-the-art performance on many commonly used dataset.The proposed functional representation framework gives a new theoretical basis and direction for graph matching,which is potential for studying new research topics such as graph matching with deep learning.