eprintid: 17173 rev_number: 13 eprint_status: archive userid: 1293 dir: disk0/00/01/71/73 datestamp: 2014-07-29 07:34:05 lastmod: 2014-08-07 07:06:31 status_changed: 2014-07-29 07:34:05 type: doctoralThesis metadata_visibility: show creators_name: Speth, Markus title: Exact Solutions for Discrete Graphical Models: Multicuts and Reduction Techniques subjects: ddc-004 divisions: i-110300 adv_faculty: af-11 cterms_swd: Kombinatorische Optimierung cterms_swd: Ganzzahlige Optimierung cterms_swd: Bildsegmentierung abstract: In the past years, discrete graphical models have become a major conceptual tool to model the structure of problems in image processing - example applications are image segmentation, image labeling, stereo vision, and tracking problems. It is therefore crucial to have techniques which are able to handle the occurring optimization problems and to deliver good solutions. Because of the hardness of these inference problems, so far mainly fast heuristic methods were used which yield approximate solutions. In this thesis we present exact methods for obtaining optimal solutions for the energy minimization problem of discrete graphical models; image segmentation serves as the main application. Since these problems are NP-hard in general, it is clear that in order to be able to handle problem sizes occurring in real-world applications one has to either (a) reduce the size of the problems or (b) restrict oneself to special problem classes. Concerning (a), we develop a combination of existing and new preprocessing steps which transform models into equivalent yet less complex ones. Concerning (b), we introduce the so-called multicut approach to image analysis: This is a generalization of the min s-t cut method which allows for solving models of a certain structure significantly faster than previously possible or even solving them to global optimality for the first time at all. On the whole, we present methods which solve NP-hard problems to proven optimality and which in some cases are as fast or even faster than approximative methods. abstract_translated_text: In den letzten Jahren entwickelten sich diskrete graphische Modelle zu einem grundlegenden Hilfsmittel, um die Struktur in der Bildverarbeitung auftretender Probleme zu modellieren - Beispielanwendungen sind etwa Bildsegmentierung, Bildlabeling, Stereosehen und Tracking-Probleme. Es ist daher essentiell, über Techniken zu verfügen, die mit den auftretenden Optimierungsproblemen umgehen und gute Lösungen liefern können. Aufgrund der Schwere dieser Probleme wurden bisher hauptsächlich heuristische Verfahren eingesetzt, die Näherungslösungen liefern. In der vorliegenden Arbeit präsentieren wir exakte Methoden, um optimale Lösungen des Energieminimierungsproblems diskreter graphischer Modelle zu erhalten; unsere Hauptanwendung ist dabei die Bildsegmentierung. Da die Probleme im Allgemeinen NP-schwer sind, ist es klar, dass man, um in der Praxis auftretende Problemgrößen behandeln zu können, entweder (a) die Größe der Probleme reduzieren oder (b) sich auf spezielle Problemklassen beschränken muss. Hinsichtlich (a) entwickeln wir eine Kombination von existierenden und neuen Vorverarbeitungsschritten, die ein Modell in ein äquivalentes, aber weniger komplexes umwandeln. Bezüglich (b) führen wir den sogenannten Multicut-Ansatz in die Bildverarbeitung ein: Dabei handelt es sich um eine Verallgemeinerung des Min-s-t-Cut-Verfahrens, die es ermöglicht, Probleme einer gewissen Struktur signifikant schneller als bisherige Methoden oder sogar erstmals überhaupt global optimal zu lösen. Insgesamt präsentieren wir Methoden, die NP-schwere Probleme beweisbar optimal lösen und die in manchen Fällen genauso schnell oder sogar schneller sind als Näherungsverfahren. abstract_translated_lang: ger date: 2014 id_scheme: DOI id_number: 10.11588/heidok.00017173 ppn_swb: 1658772636 own_urn: urn:nbn:de:bsz:16-heidok-171731 date_accepted: 2014-07-23 advisor: HASH(0x55e0f7eb2e08) language: eng bibsort: SPETHMARKUEXACTSOLUT2014 full_text_status: public citation: Speth, Markus (2014) Exact Solutions for Discrete Graphical Models: Multicuts and Reduction Techniques. [Dissertation] document_url: https://archiv.ub.uni-heidelberg.de/volltextserver/17173/1/Dissertation_Speth.pdf