Joint Graph Decomposition and Node Labeling: Problem, Algorithms,
(Max Planck Institute for Informatics Saarbrucken, Germany)
Combinatorial optimization problems whose feasible solutions define both a
decomposition and a node labeling of a given graph offer a common mathematical
abstraction of seemingly unrelated computer vision tasks. Examples include
instance-separating semantic segmentation, articulated human body pose
estimation and multiple object tracking. This talk is about one such
optimization problem, a generalization of the unconstrained integer quadratic
program and the minimum cost lifted multicut problem, both of which are NP-hard.
Selected properties of this problem are discussed that lead to exact and
heuristic algorithms for its solution and to state-of-the-art results for the
three above-mentioned applications.