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