Show simple item record

dc.contributor.authorWang, Chen
dc.identifier.otherbibid: 10489608
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.
dc.rightsAttribution-ShareAlike 4.0 International*
dc.subjectMarkov Random Fields
dc.subjectMRF inference
dc.subjectComputer science
dc.titlePersistency algorithms for efficient inference in Markov Random Fields
dc.typedissertation or thesis Science University of Philosophy D., Computer Science
dc.contributor.chairZabih, Ramin
dc.contributor.committeeMemberShmoys, David B.
dc.contributor.committeeMemberKleinberg, Robert David

Files in this item


This item appears in the following Collection(s)

Show simple item record

Except where otherwise noted, this item's license is described as Attribution-ShareAlike 4.0 International