Study On Spectral Methods Of Graph Matching And Their Applications

Many important applications in computer vision, such as2D and3D object matching, objectcategory and action recognition, object tracking, and texture discovery and analysis, require theability to match features efficiently in the presence of background clutter and occlusion. In order toimprove matching robustness and accuracy it is important to take in consideration not only thelocal appearance of features but also the higher-order geometry and appearance of groups offeatures.Graph matching is a fundamental problem in computer vision, which is applied widely inabove fields. In this thesis, we use the spectral method to analyze and solve the graph matchingproblem. We also study the spectral matching algorithm in image feature point matching and facetracking applications.First, this thesis introduces the spectral graph theory. Starting from the basic concept of graph,we discuss some methods of spectral analysis and common spectral features. Also introduced thePerron-Frobenius theorem, it is one of the important theoretical bases to the spectral matchingalgorithm.Subsequently, this thesis gives a detailed problem formulation of the graph matching. Andthen we introduce some applications and recent advances of graph matching in the field ofcomputer vision. Based on the problem formulation of the graph matching, we propose spectralmatching algorithm, which is an efficient method for matching features using local, first-orderinformation, as well as pair-wise interactions between the features. Then we analyze the feasibilityof the algorithm and the affinity matrix. By stability analysis, we explain the theoretical propertiesof spectral matching in detail. We also show its advantage in solving computer vision problems.In order to further improve the accuracy of spectral matching algorithm, we redesign thespectral matching algorithm from the perspective of probability theory. The experimental results oflocal invariant feature matching image show the improvement.Finally, we use Haar algorithm, Cam-Shift algorithm combined with spectral matchingalgorithm to achieve quick and anti-rotation face feature tracking.