TU Darmstadt / ULB / TUbiblio

Optimizing Large-scale Irregular Markov Random Fields on GPUs

Thürck, Daniel (2014):
Optimizing Large-scale Irregular Markov Random Fields on GPUs.
Darmstadt, TU, Master Thesis, 2014, [Master Thesis]

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. available. 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.

Item Type: Master Thesis
Erschienen: 2014
Creators: Thürck, Daniel
Title: Optimizing Large-scale Irregular Markov Random Fields on GPUs
Language: English
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. available. 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.

Uncontrolled Keywords: 3D Computer vision, Discrete optimization, Markov random fields (MRF), General Purpose Computation on Graphics Processing Unit (GPGPU), Algorithms
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Graphics, Capture and Massively Parallel Computing
20 Department of Computer Science > Interactive Graphics Systems
Exzellenzinitiative
Exzellenzinitiative > Graduate Schools
Exzellenzinitiative > Graduate Schools > Graduate School of Computational Engineering (CE)
Date Deposited: 12 Nov 2018 11:16
Additional Information:

93 p.

Referees: Goesele, Prof. Dr. Michael ; Pfetsch, Prof. Dr. Marc E.
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details