Preview

PDF, English Download (12MB) | Terms of use

Abstract

In this thesis we focus on the image labeling problem, which is used as a subroutine in many image processing applications. Our work is based on the assignment flow which was recently introduced as a novel geometric approach to the image labeling problem. This flow evolves over time on the manifold of row-stochastic matrices, whose elements represent label assignments as assignment probabilities. The strict separation of assignment manifold and feature space enables the data to lie in any metric space, while a smoothing operation on the assignment manifold results in an unbiased and spatially regularized labeling.

The first part of this work focuses on theoretical statements about the asymptotic behavior of the assignment flow. We show under weak assumptions on the parameters that the assignment flow for data in general position converges towards integral probabilities and thus ensures unique assignment decisions. Furthermore, we investigate the stability of possible limit points depending on the input data and parameters. For stable limits, we derive conditions that allow early evidence of convergence towards these limits and thus provide convergence guarantees.

In the second part, we extend the assignment flow approach in order to impose global convex constraints on the labeling results based on linear filter statistics of the assignments. The corresponding filters are learned from examples using an eigendecomposition. The effectiveness of the approach is numerically demonstrated in several academic labeling scenarios.

In the last part of this thesis we consider the situation in which no labels are given and therefore these prototypical elements have to be determined from the data as well. To this end we introduce an additional flow on the feature manifold, which is coupled to the assignment flow. The resulting flow adapts the prototypes in time to the assignment probabilities. The simultaneous adaptation and assignment of prototypes not only provides suitable prototypes, but also improves the resulting image segmentation, which is demonstrated by experiments. For this approach it is assumed that the data lie on a Riemannian manifold. We elaborate the approach for a range of manifolds that occur in applications and evaluate the resulting approaches in numerical experiments.

Translation of abstract (German)

In dieser Dissertation beschäftigen wir uns mit dem Image Labeling Problem, welches als Unterroutine in zahlreichen Anwendungen in der Bildverarbeitung gebraucht wird. Unsere Arbeit baut auf dem Assignment Flow auf, welcher kürzlich als neuer geometrischer Ansatz zum Image Labeling Problem eingeführt wurde. Dieser Fluss entwickelt sich zeitlich auf der Mannigfaltigkeit der zeilenstochastischen Matrizen, dessen Elemente die Wahrscheinlichkeiten der Zuweisungen von Klassenlabels repräsentieren. Die strikte Trennung von Zuweisungen und Daten ermöglicht es, dass die Daten aus jedem beliebigen metrischen Raum stammen dürfen. Zudem führt eine Glättungsoperation im Raum der Zuweisungen zu einem räumlich regularisierten Labeling, das ohne systematischen Fehler auf dem zugrundeliegenden Graphen realisiert wird.

Der erste Teil der Arbeit ist theoretischen Aussagen zum asymptotischen Verhalten des Assignment Flows gewidmet. Wir zeigen unter schwachen Voraussetzungen an die Parameter, dass der Assignment Flow für Daten in allgemeiner Lage gegen ganzzahlige Wahrscheinlichkeiten und somit eindeutige Zuweisungsentscheidungen konvergiert. Zudem untersuchen wir die Stabilität der möglichen Grenzwerte in Abhängigkeit der Eingabedaten und Parameter. Für stabile Grenzwerte leiten wir Bedingungen her, welche das frühzeitige Erkennen der Konvergenz zu diesen Werten ermöglichen und somit eine Konvergenzgarantie liefern.

Im zweiten Teil der Arbeit diskutieren wir, wie der ursprüngliche Ansatz des Assignment Flows erweitert werden kann, um einfache Label-Statistiken als Vorwissen für eine zusätzliche Regularisierung einzuführen. Diese Label-Statistiken ergeben sich durch globale konvexe Einschränkungen auf lineare Filterstatistiken des resultierenden Labelings. Die zugehörigen Filter können anhand von Beispielen mittels einer Eigenwertzerlegung gelernt werden. Die Wirksamkeit des neuen Ansatzes wird anhand akademischer Beispiele demonstriert.

Im letzten Teil der Arbeit betrachten wir die Situation, in der keine Labels gegeben sind und somit diese prototypischen Elemente aus den Daten mitbestimmt werden müssen. Hierfür führen wir einen zusätzlichen Fluss im Raum der Daten ein, der an den Assignment Flow gekoppelt wird. Der resultierende Fluss adaptiert die Prototypen zeitlich an die Zuweisungswahrscheinlichkeiten. Die simultane Adaption und Zuweisung der Prototypen liefert nicht nur passende Prototypen, sondern verbessert auch die resultierende Bildsegmentierung, was durch Experimente belegt wird. Für diesen Ansatz wird angenommen, dass die Daten auf einer Riemannschen Mannigfaltigkeit liegen. Wir konkretisieren den Ansatz für eine Reihe von Mannigfaltigkeiten aus der Anwendung und evaluieren die resultierenden Verfahren anhand experimenteller Beispiele.