Cornell University
Persistency algorithms for efficient inference in Markov Random Fields
Abstract
dc:description.abstractMarkov Random Fields (MRFs) have achieved great success in a variety of computer vision problems, including image segmentation, stereo estimation, optical flow and image denoising, during the past 20 years. Despite the inference problem being NP-hard, a large number of approximation algorithms, e.g., graphcuts, have been studied, although all of these methods are computationally expensive. We observed that most problems in practice contains a large easy part and a small hard part. Therefore, in this thesis, we investigated a few persistency-based approaches which could compute optimal labeling for a large set of variables efficiently and reduce the scale of the problem that the expensive inference algorithms need to solve. In particular, we will explore two different lines of research. The first direction focuses on generalizing the sufficient local condition to check persistency on a set of variables as opposed to a single variable in previous works, and provides a hierarchical relaxation to trade-off between efficiency and effectiveness. The second direction gives a discriminative view of persistency, which allow us to label more variables optimally with a small cost to label a few wrongly. This thesis will present a literature study of persistency used for MRF inference, the mathematical formalization of the algorithms and the experimental results for both the first-order and higher-order MRF inference problems.
Degree
thesis:*- Name thesis:degree_name
- Ph. D., Computer Science
- Level thesis:degree_level
- Doctor of Philosophy
- Discipline thesis:degree_discipline
- Computer Science
- Grantor
- Cornell University
- Year dc:date.issued
- 2018
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Wang, Chen
- Chair dc:contributor.chair
-
- Zabih, Ramin
- Committee members dc:contributor.committeemember
-
- Shmoys, David B.
- Kleinberg, Robert David
Subjects
dc:subject × 5Rights
dc:rights- Statement dc:rights
-
- Attribution-ShareAlike 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Dc Identifier Bibid
- 10489608
- Dc Identifier Other
-
ProQuest Submission ID: 11054
ProQuest Publication ID: 10928229