Optimizing Large-scale Irregular Markov Random Fields on GPUs

Thürck, Daniel (2014)
Optimizing Large-scale Irregular Markov Random Fields on GPUs.
Technische Universität Darmstadt
Masterarbeit, Bibliographie

Kurzbeschreibung (Abstract)

Energy optimization by graph cuts in alpha-Expansion have become ubiquitous in computer vision during the last decade. Especially for grid topologies, fast multicore and even massively-parallel solvers have been developed. However, those are based on cache-optimal storage of the topology and hardcoded neighborhoods. For irregular topologies, few implementations of different methods are available. Additionally, none of them uses multicore systems or even massively-parallel systems such as graphics processing units (GPUs). In this thesis, we first review the state-of-the-art techniques and analyze their potential for parallelization. After pointing out that most methods are inherently serial, we present two novel methods for energy minimization in pairwise markov random fields: (Heuristic) iterative monotonic fixing (HIMF) and monte carlo partial cuts (MCCO). While HIMF adapts the method of dynamic programming with different heuristics, MCCO relies on a theoretical foundation to find a minimum s-t-cut in a graph without computing the maximum flow. Theorems that state sufficient conditions for partially solving those cuts are given and for the first time proven. Both methods are evaluated against different (single core) author implementations that are available.

Typ des Eintrags:

Masterarbeit

Erschienen:

2014

Autor(en):

Thürck, Daniel

Art des Eintrags:

Bibliographie

Titel:

Optimizing Large-scale Irregular Markov Random Fields on GPUs

Sprache:

Englisch

Referenten:

Goesele, Prof. Dr. Michael ; Pfetsch, Prof. Dr. Marc E.

Publikationsjahr:

2014

Ort:

Darmstadt

Kollation:

93 p.

Kurzbeschreibung (Abstract):

Alternatives oder übersetztes Abstract:

Alternatives Abstract

Sprache

In der letzten Dekade entwickelten sich Graph Cuts in Kombination mit der alpha-Expansion Technik zu einer weit verbreiteten Technik der Energieminimierung in Applikationen der Computer Vision. Insbesondere für Markov Random Fields mit gitterartiger Topologie wurden spezialisierte Löser veröffentlicht, die durch Kodierung der Nachbarschaftsstruktur und cacheoptimalem Speicherlayout sehr schnell arbeiten. Für irreguläre Topologien stehen allerdings weiterhin keine Mehrkern- oder massive-parallele Implementierungen bereit. In dieser Arbeit analysieren wir die verfügbaren Algorithmen daher auf ihre Parallelisierbarkeit. Nachdem wir festgestellt haben, dass die meisten Verfahren inhärent seriell sind, beschreiben wir mit Heuristic Iterative Monotonic Fixing (HIMF) und Monte Carlo Partial Cuts (MCCO) zwei neue Verfahren. HIMF setzt dabei auf dynamische Programmierung und verschiedene Heuristiken, während MCCO auf theoretischer Grundlage versucht, einen minimalen Schnitt im alpha-Expansion Graphen ohne einen maximalen Fluss zu berechnen. Dazu führen wir verschiedene Theoreme auf und beweisen diese zum ersten Mal, womit wir in der Lage sind, solche Schnitte zumindest partiell zu lösen. Abschließend evaluieren wir beide Verfahren und die beschriebenen Implementierungen auf Grafikkarten gegen Methoden anderer Autoren.

Deutsch

Freie Schlagworte:

3D Computer vision, Discrete optimization, Markov random fields (MRF), General Purpose Computation on Graphics Processing Unit (GPGPU), Algorithms

Fachbereich(e)/-gebiet(e):

20 Fachbereich Informatik
20 Fachbereich Informatik > Graphics, Capture and Massively Parallel Computing
20 Fachbereich Informatik > Graphisch-Interaktive Systeme
Exzellenzinitiative
Exzellenzinitiative > Graduiertenschulen
Exzellenzinitiative > Graduiertenschulen > Graduate School of Computational Engineering (CE)

Hinterlegungsdatum:

12 Nov 2018 11:16

Letzte Änderung:

10 Dez 2021 07:23

PPN:

Referenten:

Goesele, Prof. Dr. Michael ; Pfetsch, Prof. Dr. Marc E.