Persistency algorithms for efficient inference in Markov Random Fields

Abstract

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.