A Study Of High-order Graph Matching Algorithm Based On ACS

Image matching is a fundamental problem in pattern recognition and computer vision field and it is a precondition and key part of varies of image processing tasks. The process of image matching is establishing correspondences between two feature sets. It is a challenging problem because of the interference with outliers, noises, deformations in scale and location of feature due to viewpoint change and so on.This paper first analyzes the current main theories and methods of image matching in three aspects of feature space, similarity measure rules and search strategies. It summarizes and classifies image matching algorithm in two categories according to the feature space: method based on statistical feature and method based on content and structure features. And then the exited similarity measure rules are classified into the categories of first-order rule, second-order rule and high-order rule, At the same time, it makes a summary of the commonly used search strategies and analyzes their advantages and disadvantages.Secondly, this paper focus on the methods of image matching based on graph structure model. It researches the methods of the graph model establishment in second-order or high-order constraint, implements the typical graph matching algorithms in second-order constraints and high-order constraints with specific instances and analyzes their advantages and disadvantages.Then, it have a further study about the building of affinity tensor, the redundancy elimination of tensor, the definition of the match score function and the optimization methods such as power iteration and random walks. The paper implements these algorithm and text their matching performance.In order to overcome the defects of traditional optimal algorithms which are easy to fall into local optimal solution, this paper adopts the ant colony system algorithm called ACS algorithm to optimize the match score function, proposes an high-order graph matching algorithm based on ACS. The reason of leading to the traditional algorithms falling into local optimal solution is that those algorithms usually calculate the stationary point through repeated iteration. The algorithm proposed in this paper firstlyapply tensor matching algorithm initialize the pheromone matrix to provide good start point, adopts affinity tensor to provide priori knowledge for computing the heuristic factor, and then calculates the transition probability using pheromone and heuristic factor, finally updates the pheromone in two ways by the solutions which have been searched. The two updating rules of pheromone are local and global. Compared with the exited graph matching algorithm, this algorithm has the following advantages: 1) The ACS algorithm is a random optimization method on probability and exploits a positive feedback mechanism. Therefore, it is hardly to fall into local optimal solution and can approximate optimal solution preferably; 2) it uses the affinity between feature triples as the heuristic information, which can provide prior knowledge for searching solution.Thus, the speed of convergence will be more quickly; 3) it initializes pheromone matrix by using tensor matching method to obtain a coarse solution. It will provide a good starting point for global searching and make the algorithm converge more quickly compared with the general method which initializes pheromone matrix as the same constant. The experimental results show that this algorithm is capable of getting a higher matching accuracy and has a stronger robust against with deformation noises and outliers compared with others.At last, this paper makes a summary of the work which has been done, and discusses the further research and the aspects might need to improve.