eprintid: 11872
rev_number: 6
eprint_status: archive
userid: 1
dir: disk0/00/01/18/72
datestamp: 2011-05-03 11:54:18
lastmod: 2014-04-03 22:33:26
status_changed: 2012-08-15 08:58:45
type: doctoralThesis
metadata_visibility: show
creators_name: Kappes, Jörg Hendrik
title: Inference on Highly-Connected Discrete Graphical Models with Applications to Visual Object Recognition
title_de: Inferenz auf dicht vernetzten Graphischen Modellen und ihre Anwendung in der visuellen Objekterkennung
ispublished: pub
subjects: 004
divisions: 110300
adv_faculty: af-11
keywords: Objekt ErkennungObject Detection
cterms_swd: Markov-Feld
cterms_swd: Statistische Schlussweise
cterms_swd: Maschinelles Sehen
cterms_swd: Kombinatorische Optimierung
cterms_swd: Graphisches Modell
abstract: Das Erkennen und Finden von Objekten in Bildern ist eines der wichtigsten Teilprobleme in modernen Bildverarbeitungssystemen. Während die Detektion von starren Objekten aus beliebigen Blickwinkeln vor einigen Jahren noch als schwierig galt, verfolgt die momentane Forschung das Ziel, verformbare, artikulierte Objekte zu erkennen und zu detektieren. Bedingt durch die hohe Varianz innerhalb der Objektklasse, Verdeckungen und Hintergrund mit ähnlichem Aussehen, ist dies jedoch sehr schwer. Des Weiteren wird die Klassifikation der Objekte dadurch erschwert, dass die Beschreibung von ganzheitlichen Modellen häufig in dem dazugehörigen Merkmalsraum keine Cluster bildet. Daher hat sich in den letzten Jahren die Beschreibung von Objekten weg von einem ganzheitlichen hin zu  auf Teilen basierenden Modellen verschoben. Dabei wird ein Objekt aus einer Menge von individuellen Teilen zusammen mit Informationen über deren Abhängigkeiten  beschrieben. In diesem Zusammenhang stellen wir ein vielseitig anwendbares und erweiterbares Modell zur auf Teilen basierenden Objekterkennung vor. Die Theorie über probabilistische graphische Modelle ermöglicht es, aus manuell notierten Trainingsdaten alle Modellparameter in einer mathematisch fundierten Weise zu lernen.  Ein besonderer Augenmerk liegt des Weiteren auf der Berechnung der optimalen Pose eines Objektes in einem Bild. Im probabilistischem Sinne ist dies die Objektbeschreibung mit der maximalen a posteriori Wahrscheinlichkeit (MAP). Das Finden dieser wird auch als das MAP-Problem bezeichnet.  Sowohl das Lernen der Modellparameter als auch das Finden der optimalen Objektpose bedingen das Lösen von kombinatorischen Optimierungsproblemen, die in der Regel NP-schwer sind. Beschränkt man sich auf effizient berechenbare Modelle, können viele wichtige Abhängigkeiten zwischen den einzelnen Teilen nicht mehr beschrieben werden. Daher geht die Tendenz in der Modellierung zu generellen Modellen, welche weitaus komplexere Optimierungsprobleme mit sich bringen. In dieser Arbeit schlagen wir zwei neue Methoden zur Lösung des MAP-Problems für generelle diskrete Modelle vor. Unser erster Ansatz transformiert das MAP-Problem in ein Kürzeste-Wege-Problem, welches mittels einer A*-Suche unter Verwendung einer zulässigen Heuristik gelöst wird. Die zulässige Heuristik basiert auf einer azyklisch strukturierter Abschätzung des urspr"unglichen Problems. Da diese Methode für Modelle mit sehr vielen Modellteilen nicht mehr anwendbar ist, betrachten wir alternative Möglichkeiten. Hierzu transformieren wir das kombinatorische Problem unter Zuhilfenahme von exponentiellen Familien in ein lineares Programm. Dies ist jedoch, bedingt durch die große Anzahl von affinen Nebenbedingungen, in dieser Form praktisch nicht lösbar. Daher schlagen wir eine neuartige Zerlegung des MAP Problems in Teilprobleme mit einer k-fan Struktur vor. Alle diese Teilprobleme sind trotz ihrer zyklischen Struktur mit unserer A*-Methode effizient lösbar. Mittels der Lagrange-Methode und dieser Zerlegung erhalten wir bessere Relaxationen als mit der Standardrelaxation über dem lokalen Polytope.   In Experimenten auf künstlichen und realen Daten wurden diese Verfahren mit Standardverfahren aus dem Bereich der Bildverarbeitung und kommerzieller Software zum Lösen von  lineare und ganzzahlige Optimierungsproblemen verglichen. Abgesehen von Modellen mit sehr vielen Teilen zeigte der A*-Ansatz die besten Ergebnisse im Bezug auf Optimalität und Laufzeit. Auch die auf k-fan Zerlegungen basierenden Methode zeigte viel versprechende Ergebnisse bezüglich der Optimalität, konvergierte jedoch im Allgemeinen sehr langsam. 
abstract_translated_text: Object detection is one of the key components of modern computer vision systems.  While the detection of a specific rigid object under changing viewpoints was considered hard just a few years ago, current research strives to detect and recognize classes of non-rigid, articulated objects.  Hampered by the omnipresent problems due to clutter and occlusion, the focus has shifted from holistic approaches for object detection to representations of individual object parts linked by structural information, along with richer contextual descriptions of object configurations. Along this line of research, we present a practicable and expandable probabilistic framework for parts-based object class representation, using probabilistic graphical models, enabling the detection of rigid and articulated object classes in arbitrary views. We investigate computational learning of this representation from labelled training images and infer globally optimal solutions to the contextual maximum a posteriori (MAP) detection problem for object recognition. Both, learning the model parameters and inferring the optimal solution of such models, define combinatorial optimization problems that in general are NP-hard. Restrictions to feasible subclasses of models yield problems that can be solved efficiently. However, due to this limitation of modeling, not all relevant dependencies can be represented accurately. Thus, research has turned towards more general models that are associated with more complex optimization problems. In this thesis, we propose novel methods for solving the MAP problem for models encountered in our object detection applications. Our first ansatz transforms the MAP problem into a shortest path problem, which is solved by an A*-search with an admissible tree-based heuristic. As the A*-method does not scale well to large problems, we investigate convex relaxations of the inference problems using the theory of exponential families. Since solving the corresponding convex problem is still computationally infeasible due to an enormous number of affine constraints, we present a novel dual decomposition approach to MAP problems for highly connected discrete graphical models. We show that decompositions into cyclic, k-fan structured subproblems significantly tighten the Lagrangian relaxation compared to the standard local polytope relaxation. Furthermore, efficient integer programming for solving the subproblems with our A*-approach remains computationally feasible. We evaluate the proposed algorithms on synthetic and real world data and compare their performance to standard methods from the field of computer vision as well as to commercial standard solvers for linear and mixed integer programs. With the exception of larger problem instances our A*-approach outperforms all other methods in terms of run time and accuracy. Moreover, the dual decomposition methods show potential in terms of accuracy, but suffers from slower convergence.
abstract_translated_lang: eng
class_scheme: ccs
class_labels: Statistica, Computer v, Combinator, Graph and, Object rec
date: 2011
date_type: published
id_scheme: DOI
id_number: 10.11588/heidok.00011872
ppn_swb: 661889807
own_urn: urn:nbn:de:bsz:16-opus-118727
date_accepted: 2011-04-18
advisor: HASH(0x556120d4e2b0)
language: eng
bibsort: KAPPESJORGINFERENCEO2011
full_text_status: public
citation:   Kappes, Jörg Hendrik  (2011) Inference on Highly-Connected Discrete Graphical Models with Applications to Visual Object Recognition.  [Dissertation]     
document_url: https://archiv.ub.uni-heidelberg.de/volltextserver/11872/1/thesis.pdf