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

Evgeny Levinkov, Jonas Uhrig, Siyu Tang, Mohamed Omran, Eldar Insafutdinov, Alexander Kirillov, Carsten Rother, Thomas Brox, Bernt Schiele, Bjoern Andres; The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017, pp. 6012-6020

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, it 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 the effectiveness of these algorithms in tackling computer vision tasks, we apply them to instances of the problem that we construct from published data, using published algorithms. We report state-of-the-art application-specific accuracy in the three above-mentioned applications.

Related Material


[pdf] [Supp] [arXiv]
[bibtex]
@InProceedings{Levinkov_2017_CVPR,
author = {Levinkov, Evgeny and Uhrig, Jonas and Tang, Siyu and Omran, Mohamed and Insafutdinov, Eldar and Kirillov, Alexander and Rother, Carsten and Brox, Thomas and Schiele, Bernt and Andres, Bjoern},
title = {Joint Graph Decomposition & Node Labeling: Problem, Algorithms, Applications},
booktitle = {The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
month = {July},
year = {2017}
}