@PhDThesis{Shekhovtsov-TR-2013-24,
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 = {defence month to be announced},
day = {defence day to be announced},
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},
status = {Submitted in February 2013}
}