@PhDThesis{Shekhovtsov-TR-2013-24, IS = { zkontrolovano 25 Jan 2014 }, UPDATE = { 2013-10-07 }, author = {Shekhovtsov, Alexander}, supervisor = {Hlav{\'a}{\v c}, V{\'a}clav}, title = {Exact and Partial Energy Minimization in Computer Vision}, school = {Center for Machine Perception, K13133 FEE Czech Technical University in Prague}, address = {Prague, Czech Republic}, year = {2013}, month = {December}, day = {16}, type = {{PhD Thesis CTU--CMP--2013--24}}, issn = {1213-2365}, pages = {122}, figures = {29}, authorship = {100}, psurl = {[Shekhovtsov-TR-2013-24.pdf]}, project = {ICT-215078 DIPLECS, GACR 102/07/1317, 1M0567 CAK, FP7-ICT-247870 NIFTi}, annote = {One of the major advances in computer vision in the past few years is the development of efficient deterministic algorithms for minimization of a partially separable function of discrete variables, commonly known as energy minimization, max-sum labeling problem, or weighted constraint satisfaction. The optimization model of this general form has proved useful in nearly all areas. In computer vision, it arises in particular as the maximum a posteriori inference in Markov random fields and conditional random fields, which are used to model a variety of vision problems ranging from the dense stereo and image segmentation to the use of pictorial structures for object recognition. This work brings two contributions. The first contribution is a unified study of methods for partial optimality. Such methods, given an instance of the problem, output an assignment for a subset of variables that is guaranteed to be a part of any (or at least some) global optimum. We show that several widely applied but previously unrelated partial optimality methods can be obtained from the same unifying sufficient conditions. It implies that they share several common properties, in particular the property to preserve solutions of the standard LP relaxation. We prove a characterization of the new unifying sufficient condition and propose a systematic way to derive partial optimality guarantees. For several subclasses of problems we derive methods to find the maximum partial optimality w.r.t. the unifying sufficient condition. This includes one new non-trivial subclass, for which the maximum partial optimality is found via solving a series of minimum cut problems. }, keywords = {combinatorial optimization; energy minimization; maximum a posteriori inference in Markov random fields; partial optimality; persistency; distributed min-cut/maxflow}, note = {Supervisor-specialist: Tom\'a\v s Werner}, }