Variational methods have become an established way to approach a multitude of image analysis problems such as image denoising, segmentation, stereo reconstruction, optical flow and 3D reconstruction. However, most practical energies are not convex and thus hard to optimize, and local methods may lead to suboptimal solutions and will depend on appropriate initialization. In this work, we present novel convexification techniques for several classes of energies frequently encountered in imaging problems. This allows to obtain initialization independent solutions which are within computable bounds of the global optimum, thus coming closer to the goal of reliable and automatic computer vision algorithms. We extend and generalize existing convexification techniques, and in each case strive to find convex relaxations as tight as possible but which still allow efficient optimization. The contributions of this thesis are concentrated on two broad areas of energies: Multilabel segmentation, and vectorial functionals. The first part of the thesis deals with multilabel problems. Such energies lie at the heart of fundamental problems like image segmentation and optical flow, but they are difficult to optimize since NP-hard problems typically arise after discretization. After an overview of the state-of-the-art approaches, subsequently we present efficient novel convex relaxations for three different types of priors based on higher-level knowledge about label configurations. As the first prior, we revisit the length regularized multi-object segmentation. We propose an approach which allows general label transition functions instead of only metric ones, which improves the segmentations. Second, we describe how constraints on the relative geometric location of label regions can be cast in a convex way. Our approach unifies three different special case solutions and generalizes to new cases such as the convex shape prior. Third, we consider image sequence segmentation. We introduce proportion priors to ensure the constancy of the relative sizes of objects parts, and propose their convexifications. This leads to increased robustness with respect to strong deformations in shape and size. The second part of the thesis is about energies defined on vectorial functions with a continuous range. Their optimization remains a challenge since the general functional lifting method is only applicable in the scalar case. We focus on three special cases and propose especially tailored convex relaxations. In the first case, we consider separable regularizers. We propose a relaxation based on a new reduction technique, which reduces the run time and memory requirements by orders of magnitude. This enables to consider previously infeasible large-scale problems. Second, we consider special coupling regularizers and propose a convex relaxation which is as tight as possible among the tractable ones. Third, we provide a first tractable convexification for the vectorial Mumford-Shah functional. This yields efficiently computable high-quality solutions for contrast-preserving and edge-enhancing regularization. The developed methods highlight the general advantages of convexification methods such as optimality guarantees, independence of initialization, and the major parallelization capabilities of the resulting algorithms. This shows that these methods are a viable way to tackle important optimization problems in computer vision.      «

Variational methods have become an established way to approach a multitude of image analysis problems such as image denoising, segmentation, stereo reconstruction, optical flow and 3D reconstruction. However, most practical energies are not convex and thus hard to optimize, and local methods may lead to suboptimal solutions and will depend on appropriate initialization. In this work, we present novel convexification techniques for several classes of energies frequently encountered in imaging...     »

Variationelle Methoden sind zu einem etablierten Modellierungsmittel in der Bildverarbeitung geworden. Beliebte Einsatzgebiete sind Bildentrauschung, Segmentierung, Tiefenrekonstruktion, Berechnung des optischen Flusses und 3D-Rekonstruktion. Die meisten Energien sind jedoch nicht konvex, was ihre Optimierung deutlich erschwert. Lokale Methoden liefern dann mit großer Wahrscheinlichkeit suboptimale Lösungen, die zudem von der Initialisierung abhängen. In dieser Arbeit präsentieren wir neue Konvexifizierungsmethoden für mehrere allgemeine Problemklassen in der Bildverarbeitung. Diese ermöglichen es, Lösungen zu erhalten, die unabhängig von der Initialisierung sind und in einer verifizierbaren Nähe des Optimums liegen. Dadurch nähert man sich dem Ziel, für praktische Bildverarbeitungsprobleme zuverlässige und automatische Algorithmen zu entwickeln. Wir erweitern und verallgemeinern bestehende Techniken zur Konvexifizierung von Energien. Für jeden betrachteten Fall schlagen wir spezielle Relaxierungen vor, die nah an den optimalen und dennoch effizient berechenbar sind. Der Fokus der Beiträge dieser Arbeit liegt auf zwei allgemeinen Energieklassen: Multilabel-Segmentierung und vektorielle Funktionale. Der erste Teil der Arbeit beschäftigt sich mit Multilabelproblemen. Diese Energien stehen im Zentrum von fundamentalen Problemen der Bildverarbeitung wie Segmentierung und Berechnung des optischen Flusses. Sie sind jedoch sehr schwierig zu optimieren, da sich nach der Diskretisierung meist NP-schwere Probleme ergeben. Wir geben einen Überblick über die modernen Lösungsansätze und präsentieren anschließend neue effiziente konvexe Relaxierungen für drei spezielle Anwendungen. In jedem Fall gehen wir auf die verschiedenen Weisen ein, wie High-Level-Wissen über die wahrscheinlichen Labelkonfigurationen effizient integriert werden kann. Zuerst betrachten wir die Multilabelsegmentierung mit Längenregularisierung. Wir schlagen einen Ansatz vor, der allgemeine Labeltransferfunktionen erlaubt, anstatt nur Metriken wie bei den klassischen Methoden. Dies ermöglicht allgemeinere Energien und verbessert die Segmentierungen. Als zweites beschreiben wir, wie man Bedingungen an die relative geometrische Lage der Labelregionen auf eine konvexe Weise formulieren kann. Unser Ansatz vereinheitlicht drei bisherige Spezialfalllösungen und lässt Verallgemeinerungen wie die Konvexform zu. Als drittes betrachten wir die Bildsequenzsegmentierung. Dazu schlagen wir Proportionalitätsregularisierer, die die relative Größe von Objektteilen im Wesentlichen konstant halten, und entsprechende Konvexifizierungen vor. Dies führt zur Robustheit bezüglich starker Form- und Größenänderungen des Objekts. Im zweiten Teil der Arbeit betrachten wir Energieminimierungsprobleme für vektorwertige Lösungsfunktionen mit kontinuierlichem Wertebereich. Ihre Optimierung stellt immer noch eine Herausforderung dar, da das leistungsfähige "Functional-Lifting" Verfahren sich nur im skalaren Fall anwenden lässt. Wir betrachten drei Spezialfälle und schlagen jeweils individuell entwickelte konvexe Relaxierungen vor. Im ersten Spezialfall betrachten wir separable Regularisierer. Wir schlagen eine auf einer neuen Reduzierungstechnik beruhende Relaxierung vor, die den Speicherverbrauch und die Berechnungszeit im Vergleich zu den bestehenden Methoden um Größenordnungen reduziert. Dadurch können neue und größere Probleme als bisher angegangen werden. Als zweites betrachten wir Regularisierer mit einer speziellen Kanalkopplung, und stellen eine neue Relaxierung vor, die unter den effizient berechenbaren optimal ist. Als drittes schlagen wir die erste effizient umsetzbare konvexe Relaxierung für das vektorielle Mumford-Shah-Funktional vor. Dies liefert hochqualitative Lösungen für kontrasterhaltende und kantenverstärkende Regularisierung. Die Doktorarbeit demonstriert die allgemeinen Vorteile von Konvexifizierungsmethoden wie Optimalitätsgarantien, Initialisierungsunabhängigkeit, und Parallelisierung von resultierenden Algorithmen. Diese Methoden stellen so ein effektives Werkzeug zur Lösung von einer Vielzahl von Optimierungsaufgaben in der Bildverarbeitung dar.     «

Variationelle Methoden sind zu einem etablierten Modellierungsmittel in der Bildverarbeitung geworden. Beliebte Einsatzgebiete sind Bildentrauschung, Segmentierung, Tiefenrekonstruktion, Berechnung des optischen Flusses und 3D-Rekonstruktion. Die meisten Energien sind jedoch nicht konvex, was ihre Optimierung deutlich erschwert. Lokale Methoden liefern dann mit großer Wahrscheinlichkeit suboptimale Lösungen, die zudem von der Initialisierung abhängen. In dieser Arbeit präsentieren wir neue Ko...     »