|
Convex Mathematical Programs for Relational Matching of Object Views
Schellewald, Christian
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)  Vorschau |
|
PDF
diss_cschellewald.pdf
- Veröffentlichte Version
Download (1MB)
|
|
URL:
|
http://ub-madoc.bib.uni-mannheim.de/1092
|
|
URN:
|
urn:nbn:de:bsz:180-madoc-10929
|
|
Dokumenttyp:
|
Dissertation
|
|
Erscheinungsjahr:
|
2004
|
|
Titel einer Zeitschrift oder einer Reihe:
|
None
|
|
Verlag:
|
Universität Mannheim
|
|
Gutachter:
|
Schnörr, Christoph
|
|
Datum der mündl. Prüfung:
|
14 Juli 2005
|
|
Sprache der Veröffentlichung:
|
Englisch
|
|
Einrichtung:
|
Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Bildverarbeitung, Mustererkennung u. Computergrafik (Schnörr 1999-2008)
|
|
Fachgebiet:
|
004 Informatik
|
|
Normierte Schlagwörter (SWD):
|
Bildverarbeitung , Relationales Matching , Kombinatorische Optimierung , Relaxationsmethode , Konvexe Optimierung , Semidefinite Optimierung
|
|
Freie Schlagwörter (Deutsch):
|
Computer Vision , Convex Relaxation , Quadratic Programming , Semidefinite Programming
|
|
Freie Schlagwörter (Englisch):
|
Graph Matching , Subgraph Matching
|
|
Abstract:
|
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 , which is combined with a linear program for post-processing. Conditions under which the quadratic assignment representation is adequate from the computer vision point of view are investigated, along with attempts to relax these conditions by modifying the approach accordingly. The second part of this work focuses directly on the matching of subgraphs -- representing a model -- to a considerably larger scene graph. A bipartite matching is extended with a quadratic regularization term to take into account relations within each set of vertices. Based on this convex relaxation, post-processing and the application to computer vision are investigated and discussed. Numerical experiments reveal both the power and the limitations of the approach. For problems of sizes which occur in applications the approach is quite reasonable and often the combinatorial optimal solution is found. For larger instances the intrinsic combinatorial nature of the problem comes out and leads to sub-optimal solutions which, however, are still good.
|
|
Übersetzter Titel:
|
Konvexe Optimierungsmethoden für die relationale Zuordnung von Objektansichten
(Deutsch)
|
|
Übersetzung des Abstracts:
|
Die automatische Erkennung von Objekten in Bildern ist eine der größten Herausforderungen in der Bildverarbeitung. Werden die Objekte und Szenarien durch Graphen repräsentiert, ist ein Teilproblem der Objekterkennung die gewünschte Zuordnung der Knoten zweier Graphen zu finden. Dabei soll möglichst die Graphstruktur und evtl. zusätzlich vorhandene Information berücksichtigt werden. Die Bestimmung der besten Korrespondenzen der Graphknoten, auch Graph Matching genannt, ist für allgemeine Graphen ein NP-Hartes kombinatorisches Problem und gehört damit zu den schwierigsten aller Probleme in der Bildverarbeitung. In dem ersten Teil dieser Arbeit untersuchen wir einen Ansatz, der das Problem des gewichteten Graph Matchings auf die Klasse von Quadratischen Assignment Problemen zurückführt. Die Relaxierung führt in diesem Fall zu einem konvexen quadratschen Optimierungsproblem. Um eine nahliegende kombinatorische Lösung zu erhalten, wird ein geeignetes lineares Optimierungsproblem nachgeschaltet. Wir untersuchen, in wie fern das Verfahren für Probleme der Bilderkennung geeignet ist und diskutieren mögliche Verbesserungen. Im zweiten Teil dieser Arbeit konzentrieren wir uns auf das Problem des Subgraph Matchings wobei die Knoten eines kleineren Objektgraphens den Knoten eines größeren Szenen-Graphens zugeordnet werden sollen. Dazu erweitern wir ein sogenanntes Bipartites Matching um einen quadratischen Term, so dass neben der Ähnlichkeit der Knoten untereinander auch die zugrundeliegende Struktur der Graphen berücksichtigt wird. Anschließend untersuchen wir eine konvexe Relaxierung dieser Problemformulierung mit einem entsprechenden Nachverarbeitungsschritt und diskutieren verschiedene Einflüsse auf diesen Subgraph Matching Ansatz. Unsere numerischen Experimente zeigen, dass unsere Verfahren meist sehr gute und oft optimale Lösungen finden. Bei größeren Problemen macht sich jedoch zunehmend die kombinatorische Natur der Probleme bemerkbar, trotzdem werden in der Regel suboptimale Lösungen sehr guter Qualität gefunden.
(Deutsch)
|
|
Zusätzliche Informationen:
|
|
 | Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
|
