Graph and Hypergraph Matching in Computer Vision: Algorithms and Analysis

Abstract

Establishing image feature correspondences is fundamental problem in computer vision and machine learning research fields. Myriad of graph matching algorithms have been proposed to tackle this problem by regarding correspondence problem as a graph matching problem. However, the graph matching problem is challenging since there are various types of noises in real world scenario

e.g., non-rigid motion, view-point change, and background clutter. The objective of this dissertation is to propose robust graph matching algorithms for feature correspondence task in computer vision and to investigate an effective graph matching strategy. For the purpose, at first, two robust simulation based graph matching algorithms are introduced: the one is based on Random Walks simulation and the other is based on Markov Chain Monte Carlo sampling simulation. Secondly, two different graph matching formulations and their transformal relation are studied since equivalence between two formulations are not well studied in graph matching fields. It is demonstrated that conventional graph matching algorithms can solve both types of formulations by proposing conversion principle between two formulations. Finally, these whole statements are extended into hypergraph matching problem by introducing two robust hypergraph matching algorithms which are based on Random Walks and Markov Chain Monte Carlo, by relating two different hypergraph matching formulations, and by reinterpreting previous hypergraph matching algorithms into their counterpart formulations. Throughout chapters in this dissertation, comparative and extensive experiments verify characteristics of formulations, transformal relations, and algorithms. Synthetic graph matching problems as well as real image feature correspondence problems are performed in various and severe noise conditions.