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

E. Levinkov, Jonas Uhrig, S. Tang, M. Omran, E. Insafutdinov, A. Kirillov, C. Rother, Thomas Brox, B. Schiele, B. Andres
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017
Abstract: We state a combinatorial optimization problem whose feasible solutions define both a decomposition and a node labeling of a given graph. This problem offers a common mathematical abstraction of seemingly unrelated computer vision tasks, including instance-separating semantic segmentation, articulated human body pose estimation and multiple object tracking. Conceptually, the problem we state generalizes the unconstrained integer quadratic program and the minimum cost lifted multicut problem, both of which are NP-hard. In order to find feasible solutions efficiently, we define two local search algorithms that converge monotonously to a local optimum, offering a feasible solution at any time. To demonstrate their effectiveness in tackling computer vision tasks, we apply these algorithms to instances of the problem that we construct from published data, using published algorithms. We report state-of-the-art application-specific accuracy for the three above-mentioned applications.

Other associated files : graph_decomposition.pdf [2.1MB]  

Images and movies


BibTex reference

  author       = "E. Levinkov and J. Uhrig and S. Tang and M. Omran and E. Insafutdinov and A. Kirillov and C. Rother and T. Brox and B. Schiele and B. Andres",
  title        = "Joint Graph Decomposition \& Node Labeling: Problem, Algorithms, Applications",
  booktitle    = "IEEE Conference on Computer Vision and Pattern Recognition (CVPR)",
  month        = " ",
  year         = "2017",
  url          = "http://lmb.informatik.uni-freiburg.de/Publications/2017/BU17"

Other publications in the database