Joint Graph Decomposition and Node Labeling: Problem, Algorithms, Applications

Bjoern Andres (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.