Eingang zum Volltext in OPUS

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:kobv:83-opus-24768
URL: http://opus.kobv.de/tuberlin/volltexte/2009/2476/

Nowozin, Sebastian

Learning with Structured Data: Applications to Computer Vision

Lernen mit Strukturierten Daten: Anwendungen in der Computer Vision

pdf-Format:
Dokument 1.pdf (13.674 KB)
Print-on-Demand:

Kurzfassung auf Englisch

In this thesis we address structured machine learning problems. Here “structured” refers to situations in which the input or output domain of a prediction function is non-vectorial. Instead, the input instance or the predicted value can be decomposed into parts that follow certain dependencies, relations and constraints. Throughout the thesis we will use hard computer vision tasks as a rich source of structured machine learning problems.
In the first part of the thesis we consider structure in the input domain.
We develop a general framework based on the notion of substructures. The
framework is broadly applicable and we show how to cast two computer
vision problems — class-level object recognition and human action recognition
— in terms of classifying structured input data. For the class-level object
recognition problem we model images as labeled graphs that encode local
appearance statistics at vertices and pairwise geometric relations at edges.
Recognizing an object can then be posed within our substructure framework
as finding discriminative matching subgraphs. For the recognition of human
actions we apply a similar principle in that we model a video as a sequence of
local motion information. Recognizing an action then becomes recognizing a
matching subsequence within the larger video sequence. For both applications,
our framework enables us to finding the discriminative substructures from
training data. This first part contains as a main contribution a set of abstract
algorithms for our framework to enable the construction of powerful classifiers
for a large family of structured input domains.
The second part of the thesis addresses structure in the output domain of a
prediction function. Specifically we consider image segmentation problems in
which the produced segmentation must satisfy global properties such as connectivity.
We develop a principled method to incorporate global interactions
into computer vision random field models by means of linear programming
relaxations. To further understand solutions produced by general linear programming relaxations we develop a tractable and novel concept of solution
stability, where stability is quantified with respect to perturbations of the
input data.
This second part of the thesis makes progress in modeling, solving and
understanding solution properties of hard structured prediction problems
arising in computer vision. In particular, we show how previously intractable
models integrating global constraints with local evidence can be well approximated. We further show how these solutions can be understood in light of
their stability properties.

Kurzfassung auf Deutsch

Die vorliegende Arbeit beschäftigt sich mit strukturierten Lernproblemen im
Bereich des maschinellen Lernens. Hierbei bezieht sich “strukturiert” auf
Prädiktionsfunktionen, deren Definitions- oder Zielmenge nicht wie sonst
üblich in Vektorform dargestellt werden kann. Stattdessen kann die Eingabeinstanz oder der prädizierte Wert in Teile zerlegt werden, die gewissen Abhängigkeiten, Relationen und Nebenbedingungen genügen. Im Forschungsfeld
der Computer Vision gibt es eine Vielzahl von strukturierten Lernproblemen,
von denen wir einige im Rahmen dieser Dissertation diskutieren werden.
Im ersten Teil der Arbeit behandeln wir strukturierte Definitionsmengen.
Basierend auf dem Konzept der Unterstrukturen entwickeln wir ein flexibel
anwendbares Schema zur Konstruktion von Klassifikationsfunktionen
und zeigen, wie zwei wichtige Probleme im Bereich der Computer Vision,
das Objekterkennen auf Klassenebene und das Erkennen von Aktivitäten
in Videodaten, darauf abgebildet werden können. Beim Objekterkennen
modellieren wir Bilder als Graphen, deren Knoten lokale Bildmerkmale
repräsentieren. Kanten in diesem Graphen kodieren Informationen über
die paarweise Geometrie der adjazenten Bildmerkmale. Die Aufgabe der Objekterkennung lässt sich in diesem Schema auf das Auffinden diskriminativer
Untergraphen reduzieren. Diesem Prinzip folgend können auch Videos als
Sequenz zeitlich und räumlich lokaler Bewegungsinformationen modelliert
werden. Das Erkennen von Aktivitäten in Videos kann somit analog zu den
Graphen auf das Auffinden von passenden Untersequenzen reduziert werden.
In beiden Anwendungen ermöglicht unser Schema die Identifikation
einer geeigneten Menge von diskriminativen Unterstrukturen anhand eines
gegebenen Trainingsdatensatzes.
In diesem ersten Teil besteht der Forschungsbeitrag aus unserem Schema
und passenden abstrakten Algorithmen, die es ermöglichen, leistungsfähige
Klassifikatoren für strukturierte Eingabemengen zu konstruieren.
Im zweiten Teil der Arbeit diskutieren wir Lernprobleme mit strukturierten
Zielmengen. Im Speziellen behandeln wir Bildsegmentierungsprobleme,
bei denen die prädizierte Segmentierung globalen Nebenbedingungen, zum
Beispiel Verbundenheit klassengleicher Pixel, genügen muss. Wir entwickeln
eine allgemeine Methode, diese Klasse von globalen Interaktionen in Markov
Random Field (MRF) Modelle der Computer Vision mit Hilfe von linearer
Programmierung und Relaxationen zu integrieren. Um diese Relaxationen
besser zu verstehen sowie Aussagen über die prädizierten Lösungen machen
zu können, entwickeln wir ein neuartiges Konzept der Lösungsstabilität unter
Störungen der Eingabedaten.
Der Hauptbeitrag zum Forschungsfeld dieses zweiten Teils liegt in der
Modellierung, den Lösungsalgorithmen und der Analyse der Lösungen
komplexer strukturierter Lernprobleme im Feld der Computer Vision. Im
Speziellen zeigen wir die Approximierbarkeit von Modellen, die sowohl globale
Nebenbedingungen als auch lokale Evidenz berücksichtigen. Zudem
zeigen wir erstmals, wie die Lösungen dieser Modelle mit Hilfe ihrer Stabilitätseigenschaften verstanden werden können.

Freie Schlagwörter (Deutsch): Maschinelles Lernen , Computer Vision , Objekterkennung
Freie Schlagwörter (Englisch): machine learning , computer vision , object recognition
Institut: Fakultät IV - Elektrotechnik und Informatik -ohne Zuordnung zu einem Institut-
Fakultät: Fakultät IV - Elektrotechnik und Informatik
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Hauptberichter: Hellwich, Olaf (Prof. Dr.-Ing.)
Sprache: Englisch
Tag der mündlichen Prüfung: 23.10.2009
Erstellungsjahr: 2009
Publikationsdatum: 10.12.2009
Lizenz: Open Access maximal: Typ CC by - Namensnennung erforderlich | Kommerziell ja | Weiterbearbeitung erlaubt | PoD ja