Preview

PDF, English - main document Download (3MB) | Terms of use

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.

Translation of abstract (German)

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.