German Title: Lernen von probabilistischen grafischen Modellen für Bildsegmentierung

Preview

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

Abstract

Probabilistic graphical models provide a powerful framework for representing image structures. Based on this concept, many inference and learning algorithms have been developed. However, both algorithm classes are NP-hard combinatorial problems in the general case. As a consequence, relaxation methods were developed to approximate the original problems but with the benefit of being computationally efficient. In this work we consider the learning problem on binary graphical models and their relaxations. Two novel methods for determining the model parameters in discrete energy functions from training data are proposed. Learning the model parameters overcomes the problem of heuristically determining them. Motivated by common learning methods which aim at minimizing the training error measured by a loss function we develop a new learning method similar in fashion to structured SVM. However, computationally more efficient. We term this method as linearized approach (LA) as it is restricted to linearly dependent potentials. The linearity of LA is crucial to come up with a tight convex relaxation, which allows to use off-the-shelf inference solvers to approach subproblems which emerge from solving the overall problem. However, this type of learning methods almost never yield optimal solutions or perfect performance on the training data set. So what happens if the learned graphical model on the training data would lead to exact ground segmentation? Will this give a benefit when predicting? Motivated by the idea of inverse optimization, we take advantage of inverse linear programming to develop a learning approach, referred to as inverse linear programming approach (invLPA). It further refines the graphical models trained, using the previously introduced methods and is capable to perfectly predict ground truth on training data. The empirical results from implementing invLPA give answers to our questions posed before. LA is able to learn both unary and pairwise potentials jointly while with invLPA this is not possible due to the representation we use. On the other hand, invLPA does not rely on a certain form for the potentials and thus is flexible in the choice of the fitting method. Although the corrected potentials with invLPA always result in ground truth segmentation of the training data, invLPA is able to find corrections on the foreground segments only. Due to the relaxed problem formulation this does not affect the final segmentation result. Moreover, as long as we initialize invLPA with model parameters of a learning method performing sufficiently well, this drawback of invLPA does not significantly affect the final prediction result. The performance of the proposed learning methods is evaluated on both synthetic and real world datasets. We demonstrate that LA is competitive in comparison to other parameter learning methods using loss functions based on Maximum a Posteriori Marginal (MPM) and Maximum Likelihood Estimation (MLE). Moreover, we illustrate the benefits of learning with inverse linear programming. In a further experiment we demonstrate the versatility of our learning methods by applying LA to learning motion segmentation in video sequences and comparing it to state-of-the-art segmentation algorithms.

Translation of abstract (German)

Probabilistische grafische Modelle bieten ein mächtiges Framework für die Darstellung von Strukturen in Bildern. Auf diesem Konzept basierend wurden viele Inferenz- und Lernalgorithmen entwickelt. Jedoch, sowohl Lernen als auch Inferenz sind im allgemeinen Fall kombinatorische NP-harte Probleme. Infolgedessen wurden Relaxierungsmethoden entwickelt um die Originalprobleme zu approximieren aber mit dem Vorteil, dass sie vom Rechenaufwandt effizient sind. In dieser Arbeit betrachten wir das Lernproblem von binären graphischen Modellen und deren Relaxierungen. Zwei neuartige Methoden zum Bestimmen der Modellparameter von diskreten Energiefunk- tionen aus Trainingsdaten werden vorgeschlagen. Das Lernen der Modellparameter löst elegant das Problem, diese heuristisch zu bestimmen. Motiviert durch gängige Lernmethoden, die auf die Minimierung des Trainings- fehlers oder einer Verlustfunktion aufbauen, entwickeln wir eine neue Lernmethode ähnlich zu structural SVM. Jedoch von dem Gesichtspunkt der Optimierung ist diese einfacher. Wir benennen diese Methode als linearisierten Ansatz (LA), da er auf linear abhängige Potentiale beschränkt ist. Die Linearität von LA ist entscheidend um eine feste konvexe Relaxierung zu erhalten, die den Einsatz von Standard-Inferenz-Lösern zum behandeln der Teilprobleme ermöglicht die beim Lösen des Gesamtproblems auftreten. Allerdings wird diese Art von Lernmethoden fast nie die optimale Lösung liefern oder perfekte Performance auf der ganzen Trainingsmenge. Was würde also passieren, wenn das gelernte grafische Modell auf den ganzen Trainingsdaten die exakte Ground- Truth-Segmentierung wiedergeben würde? Würde das einen Vorteil für die Vorhersage versprechen? Inspiriert von inverser Optimierung nutzen wir die inversen linearen Program- mierung um eine weitere Lernmethode zu entwickeln, bezeichnet als inversen linearen Programmierungsansatz (invLPA). Dieser Ansatz verbessert die trainierten graphis- chen Modelle weiter unter Verwendung der zuvor eingeführten Methoden und ist fähig die exakten Ground-Truth-Daten auf der Trainingsmenge vorherzusagen. Die empirischen Ergebnisse aus der Umsetzung von invLPA geben Antworten auf unsere zuvor gestellte Frage. LA ist in der Lage gleichzeitig die unären und paarweisen Potentiale zu lernen während dies mit invLPA wegen der gewählten Repräsentierung nicht möglich ist. Auf der anderen Seite jedoch ist invLPA bezüglich der verwendeten Fittingmethode sehr flexibel, da die Potentiale nicht auf eine feste Gestalt beschränkt sind. Auch wenn die korrigierten Potentiale mit invLPA immer zu Ground-Truth-Segmentierung der Trainingsdaten führen, kann invLPA nur Korrekturen der Vordergrundsegmente vornehmen. Wegen der relaxierten Problemformulierung beeinflußt dies jedoch nicht das endgültige Ergebnis der Segmentierung. Vielmehr, solange wir mit vorberechneten Modellparametern einer hinreichend guten Lernmethode initialisieren, wird diese Schwäche von invLPA das endgültige Vorhersageergebnis nicht signifikant beeinflussen. Die Performance von unseren vorgeschlagenen Lernmethoden wird sowohl auf synthetischen als auch auf realen Datensätzen evaluiert. Wir zeigen das LA konkurrenzfähig ist im Vergleich zu anderen Lernmethoden, die Verlustfunktionen verwenden basierend auf Maximum a Posteriori Marginal (MPM) und Maximum Likelihood Estimation (MLE). Darüber hinaus veranschaulichen wir die Vorteile des Lernens mit Hilfe von inverser linearer Programmierung. In einem weiteren Experiment demonstrieren wir die Vielseitigkeit von unseren Lernansätzen indem wir LA anwenden zum Lernen von Bewegungssegmentierung in Videosequenzen und vergleichen dies gegenüber state-of-the-art Segmentierungsalgorithmen.