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},