title: Inference on Highly-Connected Discrete Graphical Models with Applications to Visual Object Recognition
creator: Kappes, Jörg Hendrik
subject: 004
subject: 004 Data processing Computer science
description: 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. 
date: 2011
type: Dissertation
type: info:eu-repo/semantics/doctoralThesis
type: NonPeerReviewed
format: application/pdf
identifier: https://archiv.ub.uni-heidelberg.de/volltextserverhttps://archiv.ub.uni-heidelberg.de/volltextserver/11872/1/thesis.pdf
identifier: DOI:10.11588/heidok.00011872
identifier: urn:nbn:de:bsz:16-opus-118727
identifier:   Kappes, Jörg Hendrik  (2011) Inference on Highly-Connected Discrete Graphical Models with Applications to Visual Object Recognition.  [Dissertation]     
relation: https://archiv.ub.uni-heidelberg.de/volltextserver/11872/
rights: info:eu-repo/semantics/openAccess
rights: http://archiv.ub.uni-heidelberg.de/volltextserver/help/license_urhg.html
language: eng