Convex Mathematical Programs for Relational Matching of Object Views
Christian Schellewald · MADOC (University of Mannheim) · 2004
Automatic recognition of objects in images is a difficult and challenging task in computer vision which has been tackled in many different ways. Based on the powerful and widely used concept to represent objects and scenes as relational structures, the problem of graph matching, i.e. to find correspondences between two graphs is a part of the object recognition problem. Belonging to the field of combinatorial optimization graph matching is considered to be one of the most complex problems in computer vision: It is known to be NP-complete in the general case. In this thesis, two novel approaches to the graph matching problem are proposed and investigated. They are based on recent progress in the mathematical literature on convex programming. Starting out from describing the desired matchings by suitable objective functions in terms of binary variables, relaxations of combinatorial constraints and an adequate adaption of the objective function lead to continuous convex optimization problems which can be solved without parameter tuning and in polynomial time. A subsequent post-processing step results in feasible, sub-optimal combinatorial solutions to the original decision problem. In the first part of this thesis, the connection between specific graph-matching problems and the quadratic assignment problem is explored. In this case, the convex relaxation leads to a convex quadratic program