Thürck, Daniel (2014):
Optimizing Large-scale Irregular Markov Random Fields on GPUs.
Darmstadt, Technische Universität, [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.
| 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. |
||||
| Place of Publication: | Darmstadt | ||||
| Collation: | 93 p. | ||||
| 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 | ||||
| PPN: | |||||
| Referees: | Goesele, Prof. Dr. Michael ; Pfetsch, Prof. Dr. Marc E. | ||||
| Alternative Abstract: |
|
||||
| Export: | |||||
| Suche nach Titel in: | TUfind oder in Google | ||||
 |
Send an inquiry |
Options (only for editors)
 |
Show editorial Details |
Drucken
Impressum